Wenn Sie ein Spieleentwickler sind, wollten Sie vielleicht schon immer A* als Charakter (oder Feind) Pathfinding implementieren. Ich weiß, dass ich das vor ein paar Jahren schon einmal vorhatte, aber mit meinen damaligen Programmierkenntnissen hatte ich Probleme mit den aktuellen Artikeln, die es gibt. Ich wollte dies als eine einfache Einführung mit einem klaren Quellcode-Beispiel für die A*-Pfadfindung schreiben, so dass jeder sie leicht aufgreifen und in seinem Spiel verwenden kann.
Ein wichtiger Aspekt von A* ist f = g + h. Die Variablen f, g und h befinden sich in unserer Node-Klasse und werden jedes Mal berechnet, wenn wir einen neuen Knoten erstellen. Ich werde kurz erläutern, was diese Variablen bedeuten.
- F ist die Gesamtkosten des Knotens.
- G ist die Entfernung zwischen dem aktuellen Knoten und dem Startknoten.
- H ist die heuristische – geschätzte Entfernung vom aktuellen Knoten zum Endknoten.
Lassen Sie uns einen Blick auf eine schnelle Grafik werfen, um dies zu veranschaulichen.
Aufregend! Nehmen wir an, node(0) ist unsere Startposition und node(19) ist unsere Endposition. Sagen wir auch, dass sich unser aktueller Knoten an dem roten Quadrat node(4) befindet.
G
G ist der Abstand zwischen dem aktuellen Knoten und dem Startknoten.
Wenn wir zurückzählen, sehen wir, dass node(4) 4 Felder von unserem Startknoten entfernt ist.
Wir können auch sagen, dass G um 1 größer ist als unser Elternknoten (node(3)). In diesem Fall ist node(4) also currentNode.g = 4.
H
H ist die heuristische – geschätzte Entfernung vom aktuellen Knoten zum Endknoten.
So lasst uns die Entfernung berechnen. Wenn wir einen Blick darauf werfen, sehen wir, dass wir unseren Endknoten (node(19)) erreicht haben, wenn wir über 7 Felder und 3 Felder nach oben gehen.
Lassen Sie uns den Satz des Pythagoras anwenden! a² + b² = c². Nachdem wir ihn angewandt haben, werden wir sehen, dass currentNode.h = 7² + 3². Oder currentNode.h = 58.
Aber müssen wir nicht die Quadratwurzel aus 58 ziehen? Nein! Wir können diese Berechnung bei jedem Knoten überspringen und erhalten trotzdem das gleiche Ergebnis. Clever!
Bei einer Heuristik müssen wir sicherstellen, dass wir sie tatsächlich berechnen können. Es ist auch sehr wichtig, dass die Heuristik immer eine Unterschätzung des Gesamtpfades ist, da eine Überschätzung dazu führt, dass A* nach Durchgangsknoten sucht, die vielleicht nicht die „besten“ in Bezug auf den f Wert sind.
F
F ist die Gesamtkosten des Knotens.
Summieren wir also h und g, um die Gesamtkosten unseres Knotens zu erhalten. currentNode.f = currentNode.g + currentNode.h. Oder currentNode.f = 4+ 58. Oder currentNode.f = 62.
Zeit für f = g + h
Also, das war eine Menge Arbeit. Wofür verwende ich nun diesen f-Wert?
Mit diesem neuen f-Wert können wir alle unsere Knoten betrachten und sagen: „Hey, ist das der beste Knoten, mit dem ich jetzt weitermachen kann?“. Anstatt alle Knoten durchzugehen, können wir die auswählen, die die besten Chancen haben, uns zum Ziel zu bringen.
Hier ist eine Grafik zur Veranschaulichung. Oben haben wir Dijkstras Algorithmus, der ohne diesen f-Wert sucht, und unten haben wir A*, der diesen f-Wert verwendet.
Dijkstra’s Algorithm
Wenn wir uns also Dijkstras Algorithmus ansehen, sehen wir, dass er einfach weiter sucht. Er hat keine Ahnung, welcher Knoten der „beste“ ist, also berechnet er Pfade für alle.
A* Algorithmus
Bei A* sehen wir, dass der Algorithmus, sobald wir das Hindernis überwunden haben, den Knoten mit der niedrigsten f und der „besten“ Chance, das Ziel zu erreichen, bevorzugt.