Der A-Stern-Algorithmus gehört zu den klassischen Verfahren für Wegfindung in Spielen. Ein am 13. November 2018 veröffentlichtes C++-Beispiel mit der ClanLib-Engine visualisiert, wie Spielfiguren und Gegner einen Weg durch eine Karte berechnen.
A* bewertet jeden Knoten eines Graphen mit den bisher angefallenen Kosten und einer Heuristik für die verbleibende Strecke. Im Beispiel kommt die Manhattan-Metrik zum Einsatz. Hindernisse werden als nicht passierbare Felder behandelt, während Wege, Wälder und Berge unterschiedliche Kosten erhalten können.
Kostenwerte steuern das Verhalten von Spielfiguren
Sobald ein Knoten das Ziel erreicht, wird der Pfad rückwärts vom Ziel zum Start rekonstruiert. Der Algorithmus wählt dabei jeweils den Knoten mit dem niedrigsten Kostenwert. Dadurch kann die Figur nicht nur irgendeinen Weg nehmen, sondern eine Route mit geringeren Gesamtkosten bevorzugen.
Das Beispiel berechnet den Pfad laufend neu. Patrouillierende Gegner verändern dazu eine zusätzliche Potentialkarte, die Felder in ihrer Nähe mit höheren Kosten versieht. Die Spielfigur weicht diesen Bereichen aus, solange ein anderer Weg erreichbar bleibt.
Die Implementierung teilt sich in die Methoden init, searchPath und getPath. Der vollständige Quellcode zu A* liegt auf GitHub. Das Beispiel knüpft an den zuvor veröffentlichten ClanLib-Beitrag zu einer Minimax-Spiele-KI an.
Für die Darstellung verwendet das Projekt Sechsecke, weil jedes der sechs Nachbarfelder gleich weit entfernt ist. Bei quadratischen Feldern muss zwischen vier Nachbarn oder acht Nachbarn mit unterschiedlich bewerteten Diagonalen unterschieden werden. Diese Entscheidung beeinflusst damit direkt die Qualität und das Verhalten der berechneten Route.