A* (A-star) Pathfinding Methode
Afair einer der besten Pathfinding Algorithmen, den ich hier mal vorstellen möchte. Es handelt sich um reine Theorie und ist nicht programmspezifisch. Hier geht es wirklich um die Grundlagen und Anfänge. Dazu versuche ich mich an einer Übersetzung der wichtigsten Punkte eines Artikels aus dem Netz. Deswegen könnte das dem ein oder anderen ziemlich bekannt vorkommen. Der Original englische Text stammt btw von Patrick Lester. (URL findet sich im Anhang)
Los geht's^^
Wir wollen von Punkt A (grün) zu Punkt B (rot), dazwischen liegt ein Hindernis (blau).
http://www.policyalmanac.org/games/aStarT1.jpg
Beginn der Suche
Wir fangen bei Punkt A an und untersuchen die anliegenden Felder und dann von da aus weiter, bis wir zum Ziel gelangen.
1. Wir fügen Feld A zu unserer Liste "Offen" hinzu. (In dieser Liste befindet sich jetzt nur dieses eine Feld, später kommen aber weitere Felder hinzu, die wir untersuchen wollen.)
2. Wir suchen alle Felder die an Feld A angrenzen (mit "einem Schritt" erreichbar sind -> 8 Felder da Diagonal-Movement angenommen wird) und ignorieren alle Felder die man nicht betreten kann (Wasser, Wände, usw.). Die Felder die betretbar sind, werden unserer Liste "Offen" hinzugefügt (in unserem Fall sind das alle 8). Dann speichern wir noch für all diese 8 Felder, das Feld A als unser "Herkunftsfeld".
3. Dann streichen wir Feld A aus unserer Liste "Offen" heraus und tragen es in eine zweite Liste "Zu" ein. In diese Liste kommen Felder, die erstmal nicht mehr überprüft werden müssen.
Grafisch veranschaulicht kann das dann so aussehen:
Das dunkelgrüne Feld in der Mitte ist unser Startfeld A, jetzt hellblau umrandet, um anzuzeigen, dass es in der Liste "Zu" steht. Alle umliegenden Felder sind hellgrün umrandet um anzuzeigen, dass sie in der "Offen" Liste stehen und noch geprüft werden. Der graue Zeiger in jedem anliegenden Feld, verweist auf das "Ursprungsfeld" (in diesem Fall Feld A).
http://www.policyalmanac.org/games/aStarT2.jpg
Als nächstes suchen wir uns ein Feld aus der Lite "Offen" und wiederholen mehr oder weniger den obigen Prozess.
Aber welches Feld nehmen wir? -> Das mit dem niedrigsten F-Wert.
"Path Scoring" (die Bewertung der möglichen Wege)
Das Problem herauszufinden welches Feld man als nächstes nimmt, berechnet sich durch folgende Formel:
F=G+H
wobei
G = die Bewegungskosten um sich von Starfeld A zu einem beliebigen Feld zu bewegen, dem Pfad folgend, der generiert wurde um das Feld zu erreichen.
H = die geschätzten Bewegungskosten von diesem gegebenen Feld zum Ziel (Feld B). H wird also nur geschätzt. Es gibt viele Wege H zu berechnen und einer wird hier erläutert werden.
Jetzt kommen wir zur Berechnung an einem Beispiel. Wir ordnen jedem Schritt in horizontaler oder vertikaler Richtung den Wert 10 zu und jedem Schritt in diagonaler Richtung den Wert 14. Um also den Wert von G zu erhalten, müssen wir den G-Wert des Ursprungsfeldes nehmen und entweder 10 oder 14 hinzufügen.
H berechnen wir nach der "Manhatten Methode" die folgendermaßen funktioniert: wir errechnen die Gesamtanzahl Felder die wir uns in horizontaler und vertikaler Richtung bewegen und ignorieren dabei diagonale Bewegungen und Hindernisse. Dann multiplizieren wir diese Gesamtzahl mit 10.
F berechnen wir dann wie gesagt indem wir G und H addieren.
Hier wieder eine grafische Darstellung, bei der die Werte in die jeweiligen Felder eingetragen wurden. In den Feldern steht F linksoben, G linksunten, und H rechtsunten.
http://www.policyalmanac.org/games/aStarT3.jpg
Weiterführung der Suche
Um die Suche fortzusetzen, nehmen wir uns jetzt das Feld mit dem niedrigsten F-Wert.
4. Wir nehmen das Feld aus unserer Liste "Offen" heraus und fügen es in die Liste "Zu" ein.
5. Wir untersuchen alle anliegenden Felder und ignorieren die, die nicht betreten werden können und Felder die sich in der Liste "Zu" befinden. Alle anderen untersuchten Felder werden zur Liste "Offen" hinzugefügt, wenn sie sich nicht schon in dieser Liste befinden. Dann speichern wir noch für diese Felder, das in Punkt 1 ausgewählte Feld als unser "Herkunftsfeld".
6. Wenn ein anliegendes Feld sich schon in der Liste "Offen" befindet, dann untersuchen wir, ob dieser Weg zu diesem Feld ein besserer ist. In anderen Worten, ob der G-Wert dieses Feldes niedriger ist, als wenn wir das aktuelle Feld nutzen um dorthin zu gelangen. Wenn nicht, machen wir nichts.
Andererseits, wenn der G-Wert des neuen Pfades niedriger ist, ändern wir das Herkunftsfeld des anliegenden Feldes zum ausgewähltem Feld (im obigen Diagramm, ändern wir die Richtung des Zeigers, sodass dieser zum ausgewählten Feld zeigt. Zum Schluss berechnen wir die F und G-Werte für dieses Feld neu).
Da das vielleicht etwas konfus war, hier nochmal am Bsp. erklärt wie diese Schritte funktionieren.
Von unseren 9 Anfangsfeldern haben wir noch 8 übrig, die in der Liste "Offen" stehen, nachdem unser Startfeld zur Liste "Zu" hinzugefügt wurde. Von diesen 8, ist das mit dem niedrigsten F-Wert das Feld direkt rechts neben unserem Startfeld (F=40). Also wählen wir das als unser nächstes Feld aus. Es ist deshalb im nächsten Diagramm hellblau umrandet.
http://www.policyalmanac.org/games/aStarT4.jpg
Zuerst nehmen wir es nun aus unserer Liste "Offen" und fügen es in die Liste "Zu" ein (deshalb ist es jetzt hellblau unterlegt). Dann prüfen wir die anliegenden Felder. Die drei Felder rechts sind "Wandfelder" und werden ignoriert, ebenso das Feld genau links (unser Startfeld A) welches sich ja auf der Liste "Zu" befindet.
Die anderen vier Felder sind bereits auf der Liste "Offen", also müssen wir prüfen ob die Wege zu diesen Feldern besser sind, wenn wir dieses Feld nutzen um zu ihnen hin zu gelangen, wobei wir den G-Wert als Maßstab nehmen. Prüfen wir zuerst das Feld direkt über unserem ausgewählten Feld. Dessen aktueller G-Wert ist 14. Wenn wir stattdessen über das aktuelle Feld gehen würden um dorthin zu gelangen, wäre der G-Wert 20 (10, was dem G-Wert des aktuellen Feldes entspricht, plus 10 für einen weiteren Schritt vertikal nach oben). Ein G-Wert von 20 ist höher als 14, also ist dies kein besserer Weg. Das sieht man auch, wenn man auf's Diagramm sieht. Es geht schneller zu diesem Feld zu gelangen, wenn man direkt einen Schritt diagonal nach rechtsoben geht, anstatt erst ein Feld nach rechts und dann noch ein Feld nach oben.
Wenn wir diesen Vorgang für alle 4 Felder, die bereits auf unserer Liste "Offen" stehen, wiederholen, stellen wir fest, dass sich kein Weg verbessert, wenn wir über das aktuelle Feld gehen, also ändern wir nichts. Da wir nun fertig sind mit allen anliegenden Feldern, können wir nun zum nächsten Feld wechseln.
Also gehen wir wieder durch unsere Liste "Offen" in der sich jetzt noch 7 Felder befinden und suchen wieder das mit dem niedrigsten F-Wert. Interessanterweise sind es diesmal 2 Felder (mit einem F-Wert von jeweils 54). Welches nehmen wir? Eigentlich egal, aber wenn man auf Geschwindigkeit achten will, kann es von Vorteil sein, dass Feld zu nehmen, was man als letztes zur Liste "Offen" hinzugefügt hat.
Wir nehmen das Feld gleich darunter und eins rechts vom Startfeld wie in der nächsten Darstellung.
http://www.policyalmanac.org/games/aStarT5.jpg
Wenn wir nun die anliegenden Felder untersuchen, stellen wir fest, dass genau rechts ein "Wandfeld" ist, welches wir ignorieren. Genauso das Feld unter dem Wandfeld. Warum? Da wir, um dieses zu erreichen, durch die Ecke der Wand "hindurchgehen" müssten. Deswegen sollte man da drumherum gehen müssen. (Diese Regel ist optional und kann natürlich nach belieben abgeändert werden).
Somit bleiben noch fünf andere Felder. Die zwei Felder unten sind noch nicht in der Liste "Offen" also fügen wir sie hinzu und das aktuelle (ausgewählte) Feld wird als ihr Herkunftsfeld gespeichert. Von den restlichen drei Feldern sind zwei bereits in der Liste "Zu", nähmlich das Startfeld A und das Feld genau über dem aktuellen Feld (beide hellblau umrandet), also ignorieren wir die Beiden. Bleibt noch das Feld genau links neben dem aktuellen Feld, bei dem wir prüfen, ob der G-Wert niedriger ist, wenn wir über das aktuelle Feld gehen um dorthin zu gelangen. Da das nicht der Fall ist, sind wir fertig und sind nun bereit, das nächste Feld aus unserer Liste "Offen" zu wählen.
Wir wiederholen diesen Vorgang bis wir das Zielfeld zu unserer Liste "Offen" hinzufügen. An diesem Punkt dürfte das ungefähr wie in folgendem Diagramm aussehen.
http://www.policyalmanac.org/games/aStarT6.jpg
Zu sehen ist, dass das "Herkunftsfeld" des Feldes zwei Kästchen unter dem Starfeld sich gegenüber der vorigen grafischen Darstellung geändert hat. Vorher hatte es einen G-Wert von 28 und zeigte auf das Herkunftsfeld nach Rechtsoben. Jetzt jedoch hat es einen Wert von 20 und zeigt auf das Herkunftsfeld genau nach Oben. Dies passierte irgendwann auf dem Weg zum Ziel, als der G-Wert geprüft wurde und herauskam dass er niedriger ist, wenn ein neuer Weg genommen wird - sodass das Herkunftsfeld gewechselt wurde und die G und F-Werte neu berechnet wurden. Auch wenn das bei diesem Beispiel keinen Unterschied zu machen scheint, gibt es viele Situationen wo dieses "Geprüfe" den Unterschied macht, ob man den schnellsten Weg zum Ziel findet oder nicht.
So.. wie legen wir jetzt den Pfad fest? Einfach beim roten Feld (Ziel B) anfangen und rückwärts von einem Feld zum nächsten Herkunftsfeld bewegen und den Zeigern folgen. Das bringt einen zurück zum Startfeld und das ist der fertige Weg. Es sollte wie in folgender Darstellung aussehen.
http://www.policyalmanac.org/games/aStarT7.jpg
Zusammenfassung der A* Methode
1) Füge das "Startfeld" zur Liste "Offen" hinzu.
2) Wiederhole Folgendes:
a) Suche das Feld mit dem niedrigsten F-Wert aus der Liste "Offen". Wir bezeichnen dies als aktuelles Feld.
b) Wechsle es in die Liste "Zu"
c) Für jedes der 8 Felder die an diesem aktuellen Feld anliegen …
* Wenn es nicht begehbar ist oder auf der Liste "Zu", ignoriere es. Andernfalls mache Folgendes.
* Wenn es nicht auf der Liste "Offen" ist, füge es zur Liste "Offen" hinzu. Speichere das aktuelle Feld als "Herkunftsfeld" dieses Feldes. Speichere die F, G und H-Werte des Feldes.
* Wenn es schon auf der Liste "Offen" ist, überprüfe, um zu sehen, ob dieser Weg zu diesem Feld besser ist, mit dem G-Wert als Maßstab. Ein niedriger G-Wert bedeuted, dass dies ein besserer Weg ist. Wenn dies der Fall ist, tausche das Herkunftsfeld des Feldes mit dem aktuellen Feld, und berechne die G und F-Werte des Feldes neu. Wenn du deine Liste "Offen" nach F-Werten sortierst hälst, musst du sie wegen der Änderung eventuell neu sortieren..
d) Halte an, wenn du:
* Das Zielfeld zur Liste "Offen" hinzufügst, in welchem Fall der Weg gefunden wurde, oder
* es nicht geschafft hast, das Zielfeld zu finden, und die Liste "Offen" leer ist. In diesem Fall gibt es keinen Weg.
3) Speichere den Weg. Arbeite dich rückwärts vom Zielfeld, indem du von Feld zu Feld zu den jeweiligen Herkunftsfeldern zurückgehst, vor, bis du das Startfeld erreichst. Dies ist dann dein Weg.
Anhang
Für weiterführende Infos und den englischen Originaltext schaut hier vorbei:
http://www.policyalmanac.org/games/aStarTutorial.htm
Hoffe ich konnte es einigermaßen verständlich verfassen, ist aber wie gesagt nicht programmspezifisch, und somit auf eigentlich jede Programmiersprache übertragbar. Deshalb sollte man es mit dem RPGMaker umsetzen können.
