A*-Algorithmus: Wie virtuelle Armeen lernten, sich nicht mehr zu verlaufen
Eine verlorene Schlacht, weil der Nachschub an einem Fluss hängengeblieben ist: Bei alten Spielen war das ein übliches Ärgernis. Denn einen Weg von A nach B zu finden ist gar nicht so einfach, wenn es Hindernisse oder gar Gelände mit unterschiedlichen Fortbewegungskosten gibt – und die Wegfindung gleichzeitig noch möglichst effizient sein soll. Der A*-Algorithmus(öffnet im neuen Fenster) löst das Problem optimal und auch noch mit minimalem Rechenaufwand. Trotz seiner Vorteile, und obwohl A* seit 1968 bekannt ist, blieb er bei Spielen dennoch lange außen vor – wir erklären, weshalb.
Wie bei Wegfindungsalgorithmen üblich, arbeitet A* auf einem Graphen, einer Menge von durch Kanten verbundenen Punkten (die korrekte Terminologie ist Knoten). Jede Kante verursacht Kosten – bei einem Computerspiel die Bewegungskosten eines Feldes. Kann ein Feld nicht betreten werden, existiert die entsprechende Kante nicht. Die Bewegungskosten sind dabei nur ein Beispiel für eine Kostenfunktion, beliebige andere sind denkbar.