A* Pathfinding

[Airblader]

Mhm...die Methode hab ich nu leider nich verstanden ;)
A* versteh ich ja, mir geht es nur um den groben Aufbau, dass es auch performant ist :)

Problem ist ja nicht nur der Weg (sollte natürlich der möglichst kürzeste sein), sondern auch, dass er Hinternissen halbwegs intelligent ausweicht :)

air

[alzaimar]

Du hast ein Spielfeld, ähnlich wie z.B. ein Schachfeld?
Dann sind die Felder die Knoten, und die Übergänge von einem Feld zum Nachbarn die Kanten. Ein Feld hat ja maximal 8 Nachbarn, also hat jeder Knoten maximal 8 Kanten.

Code:

+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| 4 | 5*| 6*|
+---+---+---+
| 7 | 8 | 9 |
+---+---+---+

Feld 5 und 6 sind Hindernisse. Die Kanten sind also
(1,2) (2,3) (1,4) (4,7) (7,8) (8,9)
Wenn man schräg laufen darf, kommen noch (2,4) und (4,8) hinzu.
Wenn man in beide Richtungen laufen darf, dann natürlich auch die Inversen der Kanten.
Nun erstellst Du deine Matrix, wo z.B. E[1,2] = E[2,1] = 1 und E[2,5] = MaxInt ist.
Dann den A* oder jeden anderen "single source minimum Path" Algorithmus auf z.B. auf (3->9) loslassen und schon bist du fertig.

Übrigens kann man damit auch 'Berge' darstellen. Wenn der Weg von 1->4 bergauf geht, dann ist E[1,4] > E[4,1]. Der A* Algorithmus findet dann den Weg, der am wenigsten anstrengend ist.

[Airblader]

Naja, meine Spielmatrix hab ich ja, grob gesagt etwa sowas:

Map1 => Fields[X,Y] => Image/Typ/...

Image is z.B. welches Image es im Tileset hat und Typ eben 0/1/2 für begehbar etc.
Der Algo selbst hat mir auch noch keine Sorgen gemacht bzw. meine Matrix - eher eben das grundlegende mit welcher Idee ich rangehen sollte ;)
Werds nu wie gesagt mal mit dem TObjectList (nochmal) versuchen :)

air