Der Algorithmus im Überblick
Wenn ein Benutzer zwei Knoten ausgewählt hat, so soll der kürzeste Weg zwischen beiden bestimmt werden. Dies erreichen wir durch Nutzung des A*-Algorithmus. Das Prinzip des Algorithmus ist wie folgt: man startet bei meinem Startknoten und wähle ihn als aktiven Knoten. Dazu bestimmt man nun jene Knoten, die direkt über eine einzelne Kante vom aktiven Knoten aus erreicht werden können. Zu jedem dieser Knoten, welche nicht maskiert sind, wird der euklidische Abstand berechnet. Die 'Kosten', um zu diesem Knoten zu gelangen sind die Kosten, welche nötig waren, um zu dem aktiven Knoten zu gelangen (diese sind 0, wenn der aktive Knoten der Startknoten ist) zuzüglich des euklidischen Abstands vom aktiven Knoten zu dem nichtmaskierten Nachbarn. Die gefunden Knoten werden dann nach Kosten sortiert in eine Liste oder Queue (OpenList genannt) eingefügt, wobei der Knoten mit den geringsten Kosten am Anfang steht. Sind alle Knoten ausgelesen worden, so wird der erste Knoten von der OpenList genommen, also der mit den geringsten Wegkosten. Dieser Knoten wird nun der aktive Knoten und das Verfahren wird so lange wiederholt, bis der Zielknoten gefunden wurde und damit der Algorithmus terminiert, dann sind wir fertig, oder aber, bis die OpenList leer ist. Ist dies der Fall, so wird die Wegsuche abgebrochen, da dies bedeutet, dass der Graph nicht zusammenhängend ist und kein Weg gefunden werden kann. Wurden alle Nachbarn eines Knotens ausgewertet, so wird dieser maskiert, um nicht erneut bearbeitet zu werden und eventuell eine Schleife zu erzeugen. Die folgende Abbildung zeigt den Algorithmus im Überblick:
