A* für die Wegfindung

In diesem Artikel möchte ich den A*-Algorithmus vorstellen, mit dessen Hilfe man den “besten” Weg zwischen zwei Punkten finden kann.

Allgemeines

Im Folgenden betrachte ich die Wegfindung bezogen auf Spieleentwicklung. Einige Ausführungen mögen daher nicht mathematisch korrekt sein, dafür aber hoffentlich verständlicher. Mit Karte bezeichne ich das Spielfeld auf dem gespielt wird und auf dem ein Weg gefunden werden soll.

Um sich dem Konzept der Wegfindung etwas zu nähern, sollten wir vorher noch einige Begriffe klären:

Definitionen

Kennt ein Algorithmus jederzeit die gesamte Karte mit allen Daten und Werten, so wird er informiert genannt. Berücksichtigt ein Algorithmus während der Berechnung auftretende Veränderungen der Karte korrekt, so wird er dynamisch genannt, andernfalls statisch. Ich werde mich hier weitgehend auf statische informierte Algorithmen beschränken, da sie für die meisten Zwecke ausreichen und verhältnismäßig einfach zu implementieren sind.

Arten von Wegfindung

Startpunkt zu Zielpunkt

Dies ist der für Spiele häufigste Fall: Finde zwischen einem gegebenen Start und Zielpunkt den idealen Weg. Ein typischer Algorithmus für dieses Problem ist A* (statisch) oder auch D* (dynamisch).

Startpunkt zu allen anderen Punkten

Etwas andere Aufgabenstellung, die nicht ganz so häufig in Spielen anzutreffen ist. Dieses Problem ist unter anderem mit dem Dijkstra-Algorithmus lösbar und tritt zum Beispiel bei der Berechnung von Routingtabellen in einem Netzwerk auf.

Von allen Punkten zu allen Punkten

Für Spiele kaum relevanter Fall, den ich hier nicht weiter vertiefen möchte. Kommt als Problemstellung aus der Graphentheorie und der theoretischen Informatik und ist lösbar mit dem Algorithmus von Floyd und Warshall.

Was brauchen wir?

Natürlich brauchen wir eine Datenstruktur, die unser Spielfeld abbildet. Zusätzlich brauchen wir noch eine Datenstruktur, in der wir einzelne Spielfelder ablegen können und überprüfen können, ob ein gegebenes Feld bereits enthalten ist. Dazu reicht eine lineare Liste. Außerdem müssen wir für jedes Feld speichern können, über welches andere Feld wir es betreten haben. (ein Zeiger oder eine Referenz reichen aus)

Damit wir überhaupt sagen können, dass wir den “günstigsten” oder den “besten” Weg gefunden haben, brauchen wir erstmal ein entsprechendes Kriterium. Es reicht jedem Feld eine Zahl als Kosten zuzuweisen und zu definieren, dass eine kleinere Zahl “günstiger” bzw. “besser” ist.

A* benötigt außerdem eine Heuristik, d.h. eine Schätzung, wie weit es von einem gegebenen Feld noch bis zum Ziel ist. Diese Heuristik muss man an die jeweilige Topologie der Karte anpassen. Bei Quadratrastern kann man die Manhattan-Methode nehmen. Man zählt die Zeilen und Spalten bis zum Ziel und addiert diese Werte:

Distanz := Abs(Zielfeld.X - AktuellesFeld.X) + Abs(Zielfeld.Y - AktuellesFeld.Y)

Abs() ist hier die Betragsfunktion.

Bei Hexfeldern benötigt man eine Funktion, die die Anzahl der Felder bis zum Zielfeld zurückliefert. Eine solche Funktion habe ich in Entfernungsberechnung für Hexraster beschrieben.

Die Wahl der Heuristik bestimmt zum einen die Performance der Wegfindung, aber auch den Erfolg. Man kann für A* durchaus mathematisch beweisen, dass er immer den besten Weg findet bzw. wenn mehrere Wege mit gleichen Kosten existieren findet A* implementierungsabhängig einen davon. Doch wenn man sich verschätzt, hat das Auswirkungen auf die Wegfindung: Je niedrigerer die Heuristik die Kosten unter den tatsächlichen Wert hinaus verschätzt, desto mehr letztlich unnötige Wege untersucht A*. Hat die Heuristik immer den Weg 0 wird A* zum Dijkstra-Algorithmus findet immer eine Lösung ist aber alles andere als performant. Eine gute Schätzung hilft also die Wegsuche zu verkürzen. Man muss aber aufpassen: Schätzt man die Kosten öfter über den tatsächlichen Wert, so kann es passieren, dass A* nicht mehr den besten Weg findet, sondern nur noch einen bestenfalls “guten” Weg – den aber relativ schnell. Schätzt man die Kosten immer exakt richtig, so wird A* sofort den idealen Weg auf kürzeste Weise finden. Mehr zum Thema Heuristiken findet man unter anderem bei Amit oder in einschlägiger Fachliteratur.

Der Algorithmus

Die beiden oben beschriebenen Listen (oder andere passende Datenstrukturen) nennen wir im folgenden OpenList und CloseList. Die OpenList ist eine Art Einkaufsliste mit Knoten, die für die Wegsuche noch interessant sein könnten. Die CloseList ist eine Liste aller Knoten, die wir bereits untersucht haben und nicht erneut anschauen werden. Der Ablauf ist dann wie folgt:

Lege den Startknoten in die OpenList (Herkunftsfeld = NULL)
Wiederhole
   Next := Feld aus der OpenList mit den geringsten Kosten
   Wenn Next = NULL
      Abbrechen -> Kein Weg möglich
 Entferne Next aus der OpenList
 Füge Next in die CloseList ein
   Wiederhole für alle Nachbarn n von Next, die nicht in der CloseList oder OpenList sind
      Setze die Herkunftsreferenz von n auf Next
      Berechne mit Wegkosten und Heuristik die Kosten von n
      Füge das Feld n in die OpenList ein

solange bis Next das Zielfeld ist

Next ist jetzt das Zielfeld und der Weg steckt in den Herkunftsreferenzen. Über eine einfache Schleife kann man jetzt vom Ziel zum Start den Weg rekonstruieren.

Verbesserungen

Man kann das Verfahren selbst zwar nicht optimieren, aber den Einsatz. Für sehr große Karten ist A* bei schlechter Heuristik sehr langsam, weil eine Vielzahl von Feldern untersucht werden muss, bis der Weg gefunden wurde. Wenn die Wegfindung nicht extrem schnell ist, sollte sie auf jeden Fall in einen eigenen Thread ausgelagert werden, damit das Spiel während der Berechnung keine Sichtbaren Verzögerungen hat.

Aber wie kann man denn auf großen Karten Wege berechnen? Man kann beispielsweise für große Entfernungen eine gröbere Karte mit weniger Knoten nehmen und sobald man sich dem Zielfeld nähert, eine neue feine Berechnung auf kürzere Distanz durchführen. Zum anderen kann man die Wahl der Knoten einschränken. Ein Schiff beispielsweise muss Landfelder in seiner Berechnung überhaupt nicht berücksichtigen. Man fügt also nur Nachbarn in die OpenList ein, die auch spielregeltechnisch in Betracht kommen. Diese Idee ist schon sehr alt und wurde zum Beispiel beim Echtzeitstrategiespiel Warcraft II von Blizzard eingesetzt: Hier ist der Wald einfach unpassierbar, was die Wegfindung deutlich erleichtert.

Screenshot von Warcraft II

Weitere Optimierungen sind insbesondere für Echtzeitstrategiespiele, die ohne feste Felder arbeiten, das Bewegen in Formationen und die Berechnung einer gleichmäßigeren, sanften Bewegung um Kurven.

Weitere Links

Formationsbewegung bei Gamasutra

Weitere Beschreibung von A* bei Polyalmanac

Sanftere Pfadberechnung bei Gamasutra