Boldar - Fr 05.02.10 14:46
Titel: Pathfinding OHNE A*

---

Hallo Leute,
ich hab euch ja lange nicht mehr mit Fragen genervt :wink:
Aaalso:
Ich versuche Pathfinding in 2d zu implementieren.
Allerdings möchte ich nicht nur 4 (oder 8) Bewegungsrichtungen haben, sondern der weg kann jeden beliebigen Winkel haben.
Dafür wollte ich dieses Tutorial verwenden:
http://wiki.delphigl.com/index.php/Tutorial_pathfinding2
Aber:
Ich blicke da überhaupt nicht durch.
Angenommen, ich habe ein

als Feld und 2 TPoints als Start/Ziel.
Wie ermittele ich dann die Kanten/Ecken?? In welchen Strukturen soll ich das speichern?
Ich verstehe da zwar das Prinzip, habe aber keine Ahnung, wie ich das Implementieren soll.
mfg Boldar

Flamefire - Fr 05.02.10 15:13

---

ich hab das ganze auch mal gemacht und sehr effektiv (aber sehr speziell) hinbekommen.

möglichkeit a) du kennste alle ecken der objekte, speicherst diese mit einem offset (also statt ein 3-eck (0,0)-(1,0)-(1,1) speicherst du (-0.5;-0.5)-...) damit man nicht aneckt.
das sind dann deine knoten
möglichkeit b) du speicherst einfach ein raster mit einer bestimmten auflösung (also z.b. (1,1),(1,2),(1,3)...)
dann sind das deine knoten (ggfls in der nähe von obj. das raster enger machen)

dann brauchst du eine fkt die für 2 knoten sagt, ob die eine kante haben. also i.A. einfach ob die direkte verbindung zwischen denen eine objektkante schneidet oder zu nahe kommt. das ist nicht so einfach!
am besten dann einfach sagen für abstand der 2 punkte >maxAbstand gibt es keine kante, das spart etwas aufwand.

jetzt hast du 2 möglichkeiten
1) graph-algo wie a* auf den graphen dann mittels der funktion gucken, ob einzelne wegpunkte wegfallen können
2) den beschriebenen algo implementieren und die fkt oben verwenden oder schon als graph gespeichert haben