A* Suchalgorithmus: Wegfindung in Spielen und KI

1. Was ist der A* Algorithmus?

Der A* (ausgesprochen "A-Stern" oder "A-Star") Algorithmus ist ein Graphdurchsuchungs- und Pfadsuchalgorithmus, der aufgrund seiner Vollständigkeit, Optimalität und optimalen Effizienz in der Informatik weit verbreitet ist. Er wurde 1968 von Peter Hart, Nils Nilsson und Bertram Raphael vom Stanford Research Institute erfunden und ursprünglich entwickelt, um dem Shakey-Roboter bei der Navigation durch Räume zu helfen.

Heute ist A* der absolute Industriestandard für Routing und Pathfinding. Ob eine Figur in einem Strategiespiel über ein Raster läuft oder ein GPS die schnellste Fahrt durch ein Land berechnet, A* (oder eine Variante davon) übernimmt höchstwahrscheinlich die schwere Arbeit.

2. Das Problem mit dem Dijkstra-Algorithmus

Um zu verstehen, warum A* brillant ist, müssen wir zuerst verstehen, was er verbessert. Vor A* war der Goldstandard für das Finden des kürzesten Pfades der Dijkstra-Algorithmus.

Der Dijkstra-Algorithmus findet garantiert den kürzesten Pfad. Er ist jedoch grundlegend "blind". Wenn Sie Dijkstra bitten, einen Weg von New York nach Los Angeles zu finden, wird er Straßen, die nach Boston, Miami und Chicago führen, genauso eifrig erkunden wie Straßen, die nach Westen führen. Er sucht nach außen in einem perfekten Kreis (oder einer Kugel) in alle Richtungen gleichmäßig, bis er zufällig auf das Ziel stößt.

Auf einer großen Karte ist die Erkundung jeder möglichen Richtung unglaublich langsam und verschwendet massive Mengen an Rechenleistung. Wir brauchen einen Algorithmus, der "clever" genug ist, um zu wissen, in welcher Richtung sich das Ziel befindet, damit er priorisieren kann, Wege zu erkunden, die in Richtung des Ziels führen.

3. Das Geheimrezept: Heuristiken (f = g + h)

A* löst das "Blindheits"-Problem durch die Einführung einer Heuristik. Eine Heuristik ist eine fundierte Schätzung. Beim Pathfinding ist es eine Funktion, die schätzt, wie weit ein Knoten vom endgültigen Ziel entfernt ist.

A* weist jedem entdeckten Knoten eine Punktzahl zu. Der Knoten mit der niedrigsten Punktzahl ist derjenige, den er als Nächstes erkundet. Die Kerngleichung von A* lautet:

• n ist der aktuell ausgewertete Knoten im Graphen.
• g(n) sind die Exakten Kosten. Es ist die bekannte Entfernung vom Startknoten zum Knoten n. (Dies ist genau das, was Dijkstra verwendet).
• h(n) ist die Heuristische Schätzung. Es ist die geschätzte Entfernung vom Knoten n zum endgültigen Ziel.
• f(n) sind die Gesamtkosten. Dies ist die Summe von g und h. A* priorisiert immer den Knoten mit dem niedrigsten f-Wert.

Durch Hinzufügen der h(n)-Komponente wird A* wie von einem Magneten zum Ziel gezogen. Er ignoriert Pfade, die in die entgegengesetzte Richtung des Ziels führen, was den Suchraum im Vergleich zum Dijkstra-Algorithmus drastisch reduziert.

4. Die richtige Heuristik wählen

Die Magie von A* hängt vollständig von der Genauigkeit der Heuristikfunktion h(n) ab. Wenn Ihre Heuristik die Entfernung zum Ziel überschätzt, garantiert A* nicht mehr, dass er den kürzesten Pfad findet. Wenn sie unterschätzt, wird er langsamer. Daher ist die Auswahl der richtigen Heuristik für Ihr spezifisches Spiel oder Ihre Karte von entscheidender Bedeutung.

Manhattan-Distanz (Für Rasterwelten ohne Diagonalen)

Wenn Ihr Spiel ein Raster verwendet (wie Pac-Man oder ein traditionelles Roguelike) und sich Charaktere nur nach oben, unten, links oder rechts bewegen können, sollten Sie die Manhattan-Distanz verwenden. Sie berechnet die Gesamtzahl der Blöcke horizontal und vertikal zwischen dem aktuellen Knoten und dem Ziel.

function heuristic(node, goal) {
    return abs(node.x - goal.x) + abs(node.y - goal.y)
}

Euklidische Distanz (Für offene Welten oder Bewegung in jedem Winkel)

Wenn sich Charaktere in jede Richtung bewegen können (oder wenn Sie auf einer kontinuierlichen Karte routen), sollten Sie die Euklidische Distanz verwenden. Dies ist die geradlinige "Luftlinien"-Entfernung zwischen zwei Punkten, berechnet mit dem Satz des Pythagoras.

function heuristic(node, goal) {
    return sqrt((node.x - goal.x)^2 + (node.y - goal.y)^2)
}

Tschebyschow-Distanz (Für Rasterwelten mit Diagonalen)

Wenn Ihr Spiel ein Raster verwendet, aber diagonale Bewegungen zulässt (wobei diagonales Bewegen genauso viel kostet wie gerades Bewegen), verwenden Sie die Tschebyschow-Distanz. Sie nimmt das Maximum der horizontalen oder vertikalen Differenzen.

function heuristic(node, goal) {
    return max(abs(node.x - goal.x), abs(node.y - goal.y))
}

5. Schritt-für-Schritt Ausführung von A*

Hier ist genau, wie der Algorithmus seinen Status aufrechterhält und Knoten während der Ausführung verarbeitet:

1. Initialisierung: Erstellen Sie zwei Mengen: eine OPEN-Menge (zu evaluierende Knoten) und eine CLOSED-Menge (bereits evaluierte Knoten). Fügen Sie den Startknoten der OPEN-Menge hinzu.
2. Schleifenstart: Finden Sie den Knoten in der OPEN-Menge mit den niedrigsten f-Kosten. Nennen wir diesen den Current (aktuellen) Knoten.
3. Zielprüfung: Wenn der Current Knoten das Ziel ist, sind Sie fertig! Folgen Sie den Eltern-Zeigern rückwärts, um den Pfad zu rekonstruieren.
4. Nach Closed verschieben: Entfernen Sie den Current Knoten aus der OPEN-Menge und fügen Sie ihn der CLOSED-Menge hinzu.
5. Nachbarn erweitern: Betrachten Sie alle benachbarten Knoten des Current Knotens. Für jeden Nachbarn:
   • Wenn der Nachbar ein Hindernis (Wand) ist oder sich in der CLOSED-Menge befindet, ignorieren Sie ihn.
   • Berechnen Sie die g-Kosten des Nachbarn (Aktuelles g + Entfernung zum Nachbarn).
   • Wenn sich der Nachbar nicht in der OPEN-Menge befindet, berechnen Sie seine h- und f-Kosten, setzen Sie seinen Elternteil auf Current und fügen Sie ihn der OPEN-Menge hinzu.
   • Wenn sich der Nachbar bereits in der OPEN-Menge befindet, prüfen Sie, ob dieser neue Pfad zum Nachbarn besser ist (niedrigere g-Kosten hat). Wenn ja, aktualisieren Sie sein Elternteil und die g-Kosten.
6. Wiederholen: Gehen Sie zurück zu Schritt 2. Wenn die OPEN-Menge leer wird und das Ziel nicht erreicht wurde, gibt es keinen gültigen Pfad.

6. Reale Anwendungen in Spieleentwicklung & KI

A* ist das Rückgrat der Bewegung in digitalen Räumen.

• Echtzeit-Strategiespiele (RTS): Wenn Sie 50 Einheiten in StarCraft oder Age of Empires per Drag-Select auswählen und auf einen Punkt auf der Karte klicken, berechnet A* 50 individuelle Pfade und leitet sie um Gebäude, Flüsse und einander herum. (Häufig unter Verwendung spezieller Varianten wie Flow Fields oder Hierarchischem A*).
• RPG und Stealth-Spiele: NPCs verwenden A* auf einem "NavMesh" (Navigationsnetz - ein vereinfachter Graph begehbarer Flächen), um den Spieler zu jagen, Korridore zu patrouillieren oder Deckung zu finden.
• Robotik: Automatisierte Lagerroboter (wie die von Amazon) verwenden A*, um auf Fabrikböden zu navigieren, ohne mit Regalen oder anderen Robotern zu kollidieren.
• GPS Navigation: Während Standard-A* für kontinentale Karten zu langsam ist, werden modifizierte Versionen (wie ALT - A* mit Landmarks und Dreiecksungleichung) verwendet, um optimale Fahrtrouten schnell zu berechnen.