A* Pathfinding

A* Pathfinding ist einer der bekanntesten Suchalgorithmen in der Informatik, da er relativ einfach zu verstehen und zu implementieren ist. Das Ziel des Algorithmusses ist es, den kürzesten Weg zwischen zwei Punkten zu finden, dabei soll Hindernissen ausgewichen werden. Im Folgenden möchte ich erläutern, wie der Algorithmus genau funktioniert und wie gut er für praktische Anwendungen geeignet ist.

Die Theorie von A*

Kosten und Kostenfunktionen
Bei dem A* Algorithmus werden mögliche Wege in ein Raster aufgeteilt, so kann man jedem möglichen Endpunkt eine Zelle im Raster zuweisen. Zu einer Zelle gibt es drei verschiedene Arten von Kosten, die angeben, wie gut es wäre diese Zelle als nächstes zu betreten. Niedrige Werte sind dabei besser als hohe Werte, da die Kosten hier als Distanz zu verstehen sind. G-Cost: steht hier für den bereits zurückgelegten Weg.
H-Cost: auch Heuristische Kosten genannt, macht eine Schätzung darüber wie weit das Ziel von der aktuellen Zelle entfernt ist. Die Wahl der heuristischen Kostenfunktion ist hier entscheidend, weil diese bestimmt, wie gut der Algorithmus funktioniert. Wenn die Distanz z.B einfach über den Pythagoras ausgerechnet wird kann es in manchen Fällen zu unerwünschten Ergebnissen kommen.
F-Cost: Summe der Kosten (F = G + H) Wenn eine neue Zelle betreten wird erhöhen sich die G-Costs, dabei ist zu beachten, dass diagonale Bewegungen länger sind als gerade Bewegungen. Angenommen eine Zelle ist 10 Einheiten groß, dann wären die Kosten für gerade Bewegungen 10 und für Diagonale Bewegungen 14 (\( c = \sqrt{10^2 + 10^2} = 14 \)) Wahl der Kostenfunktion
Option 1: keine Kostenfunktion   -   \( h(x, y) = 0\)
Option 2: euklidische Kostenfunktion   -   \( h(x, y) = \sqrt{x^2 + y^2}\)
Option 3: oktil Kostenfunktion   -   \( h(x, y) = max(|x1-x2|, |y1-y2| + (\sqrt{2}-1) * min(|x1-x2|, |y1-y2|))\)
Option 4: Manhattan Kostenfunktion   -   \( h(x, y) = min(|x1-x2|, |y1-y2|) * \sqrt{2} + ||x1-x2|-|y1-y2||\)

Unterschiedliche Kostenfunktionen liefern unterschiedliche Ergebnisse. Welche nun am Besten ist, werde ich später in einer Übersicht näher erläutern.

Umsetzung

Pseudocode
Der Algorithmus funktioniert eigentlich ganz einfach: Die Nachbarn der aktuellen Zelle werden untersucht und es werden die Kosten deren bestimmt. Falls eine benachbarte Zelle schon einmal betrachtet wurde, werden dessen Werte neu gesetzt, wenn die Kosten geringer ausfallen. Diese Zellen landen in einer offenen Liste. Zellen über die schon gelaufen wurde, werden aus der offenen Liste entfernt und zu einer geschlossenen Liste hinzugefügt. Dieser ganze Prozess weiderholt sich, bis das Ziel gleich der aktuellen Position ist.
So könnte eine Implementierung in Pseudocode-Form aussehen:

OPEN    // the set of nodes to be evaluated
CLOSED  // the set of nodes already evaluated
add the start node to OPEN

loop
    current = node in OPEN with the lowest f_cost
    remove current from OPEN
    add current to CLOSED
    if current is the target node // path has been found
        return

    foreach neighbour of the current node
        if neighbour is not traversabte or neighbour is in CLOSED
            skip to the next neighbour
        
        if new path to neighbour is shorter OR neighbour is not in OPEN
            set f_cost of neighbour
            set parent of neighbour to current
            if neighbour is not in OPEN
                add neighbour to OPEN        

Die komplette Implementierung gibt es auf meinem GitHub Implementierung der Kostenfunktionen

// Euklidische Kostenfunktion (2)
function getDist(x1=0, y1=0, x2=0, y2=0) {
    return Math.floor(Math.sqrt((x1-x2)**2 + (y1-y2)**2) * 10);
}        

// Oktil Kostenfunktion (3)
function getDist(x1=0, y1=0, x2=0, y2=0) {
    return Math.floor(Math.max(Math.abs(x1-x2), Math.abs(y1-y2) + (Math.sqrt(2)-1) *
                                                Math.min(Math.abs(x1-x2), Math.abs(y1-y2))) * 10);
}        

// Manhattan Kostenfunktion (4)
function getDist(x1=0, y1=0, x2=0, y2=0) {
    return Math.min(Math.abs(x1-x2), Math.abs(y1-y2)) * 14 + Math.abs(Math.abs(x1-x2) - Math.abs(y1-y2)) * 10;
}        

Performance

Die beste Kostenfunktion?
Um herauszufinden, welches eine gute Kostenfunktion ist habe ich eine Tabelle als Gegenüberstellung aller Funktionen angefertigt: In der Tabelle oben, kann man erkennen, dass das Benutzen gar keiner Kostenfunktion am genausten ist. Warum ist das aber trotzdem nicht sinnvoll? Antwort: Die Berechnung dauert viel zu lange. Wenn man die Rechenschritte relativ zum Raster sieht, dann wird fast das ganze Raster durchgerechnet, also jede Zelle probiert, um den optimalen Pfad zu finden. In der Praxis möchte man jedoch schnelle Berechnungen eines Weges haben, da z.B. bei den meisten Computerspielen sich Gegner bewegen oder Hindernisse sich ändern und das 60 Mal pro Sekunde oder mehr! Also ist eine Schätzung des optimalen Weges doch die bessere Herangehensweise, mit dem Kompromiss, dass vielleicht nicht immer der ganz optimale Pfad gefunden wird. In diesem Fall ist die Manhatten Berechnung am Besten.
Man kann den A* Algorithmus dann noch weiter verbessern, indem man anstatt von Listen eine Binärbaumstruktur für die Speicherung der bereits belaufenden Zellen benutzt. Genaueres dazu hier. Falls du selber mit dem A* Algorithmus rumprobieren möchtest, schaue gerne bei meiner A* Pathfinding Testumgebung vorbei. Referenzen
Patel, Amit (02.12.1998). Amit's A* Pages
http://theory.stanford.edu/~amitp/GameProgramming
Patel, Amit (26.05.2014). Introduction to the A* Algorithm
https://www.redblobgames.com/pathfinding/a-star/introduction.html
Swift, Nicholas (28.02.2017). Easy A* (star) Pathfinding
https://medium.com/@nicholas.w.swift/easy-a-star-pathfinding-7e6689c7f7b2
Cui, Xiao; Shi, Hao (01.11.2010). A*-based Pathfinding in Modern Computer Games
https://www.researchgate.net/publication/267809499_A-based_Pathfinding_in_Modern_Computer_Games
Sidhu, Harinder Kau (01.01.2020). Performance Evaluation of Pathfinding Algorithms
https://scholar.uwindsor.ca/cgi/viewcontent.cgi?article=9230&context=etd