[XP] Pathfinding

[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.