[XP] Pathfinding

[Doktor von Stein]

Hallo,
ich versuche mich grade in einem meiner Projekte ein wenig mit Pathfinding zu beschäftigen. Hierbei greife ich auf ein einfaches Rastersystem zurück, in dem sich gerade bewegt wird, ausserdem gibt es wie gehabt verschiedene, unterschiedlich leicht zu überquerende Felder. Ich versuche grade einen Weg zu finden, dass das System den schnellsten Weg von Feld A nach B findet. Ich hatte auch schon fast einen Weg im Kopf, der mir aber nicht sehr schlau erschien. Wenn nötig, kann ich den auch mal beschreiben. Ich habe schon viel über das A+-Pathfinding gehört. Es würde mich freuen, wenn mir jemand ein Paar Tipps in die Richtung geben könnte, es muss nicht unbedingt Code sein, mir reicht schon eine Erklärung des logischen Ablaufes. Andere Ideen zu dem Thema sind auch gern gesehen. :3

MfG SalamiE

[Cornix]

Ich hatte einmal ein nettes Beispielprojekt zum A*-Pathfinding-Algorithmus geschrieben, du kannst gerne einen Blick auf das Projekt werfen.

Ich weis nicht inwiefern du dich mit dem Scripten selbst beschäftigst aber du kannst auch gerne durch die Scripte schauen welche ich dafür geschrieben habe.
Ich muss allerdings zugeben, es ist schon eine Weile her, daher ist die Qualität nicht ganz so Vorzeigefähig wie mir lieb wäre.

[Doktor von Stein]

Hm, hier ist die diagonale Bewegung mit drin. Ich weiß jetzt ungefährt, wie's hier geht, jedoch verstehe ich das mit den Zahlen noch nicht wirklich...

[Cornix]

http://www.policyalmanac.org/games/aStarTutorial.htm

Ich hoffe ich irre mich jetzt nicht, es ist schon ein klein wenig her seitdem ich mich zuletzt hiermit beschäftigt habe, aber was ich glaube mich zu errinern ist, dass du 2 Listen führst:
Eine offene Liste von Knoten welche du möglicherweise untersuchen willst, diesen Knoten ordnest du einen approximierten Wert zu welcher anzeigt wie "gut" dieser Knoten wahrscheinlich sein wird.
Und dann eine "geschlossene" Liste mit Knoten von denen du tatsächlich weist wie kostenspielig ein Weg zu diesen exakt sein würde.
Du nimmst dir immer den nächsten Knoten aus der offenen Liste welcher den besten Wert zu haben scheint und nimmst diesen in die geschlossene Liste auf indem du seinen tatsächlichen Wert berechnest.
Du fährst solange fort bis du dein Ziel erreicht hast oder keine Knoten mehr in der offenen Liste sind. (in welchem Fall kein Weg zum Ziel existiert.)

Das schwierige ist nur die richtigen Berechnungen für die erwarteten Werte für Knoten der offenen Liste zu implementieren damit der Algorithmus möglichst effektiv ist.

Der Anfang ist natürlich dein Start Knoten welcher die tatsächlichen Wegkosten von 0 besitzen sollte und der erste Knoten der geschlossenen Liste ist.
In die offene Liste nimmst du genau diejenigen Knoten auf welche direkt angrenzend an Knoten aus deiner geschlossenen Liste sind.

Mit diesen Überlegungen im Hinterkopf wirst du das Programm vielleicht ein wenig besser verstehen können.

Edit:
Kleine Verbesserung, die Werte der Knoten in der geschlossenen Liste sind die tatsächlichen Kosten welche entstehen wenn du zu diesem Knoten willst.
Die Werte der Knoten in der offenen Liste sind die geschätzen Kosten welche entstehen werden wenn du über eben diesen Knoten zum Ziel gehen willst.