Also: der A*-Algorithmus ist Breitensuche in Verbindung mit einer Prioritätswarteschlange und einer heuristischen Kostenschätzfunktion.
Breitensuche:
Der Begriff kommt aus der Graphentheorie und meint ein Durchsuchen des Graphen Ebene für Ebene. Übertragen auf eine 2D-Karte bedeutet das: Untersuche erst alle Punkte, die einen Schritt vom Start entfernt sind, dann alle mit zwei Schritten Abstand...
Der Sinn: sobald man den Zielpunkt erreicht hat, ist das auch der kürzeste Weg. Denn es werden danach nur noch Punkte überprüft, die entweder gleich viele Schritte oder sogar mehr haben.
Für die Umsetzung braucht man eine Warteschlange für die zu besuchenden Knoten und eine Array für das Speichern ob ein Knoten schon besucht wurde (diese müssen ja nicht noch einmal untersucht werden).
Man nimmt sich nun den ersten Knoten aus der Warteschlange und schaut (für alle Richtungen), ob der Knoten schon besucht wurde, falls nein, ob der frei ist, falls ja, als besucht setzen und an die Warteschlange hängen.
Entweder untersucht man mal einen Knoten, der dem Ziel entspricht oder die Warteschlange ist leer.
Zur Rekonstruktion des Weges speichert man beim Einfügen in die Warteschlange immer den Vaterknoten mit ab, damit kann man nun den Pfad rückwärts konstruieren.
Prioritätswarteschlange:
Eine weitere Verbesserung ist das Einfügen einer Bewertung der Wege (man gibt also die Zeit an, die für das Überqueren eines bestimmten Untergrunds gebraucht wird). Nun wählt man den nächsten Knoten nicht mehr nach der Anzahl der Schritte aus, sonder nach den Kosten. Das hat zur Folge, dass man entweder die Warteschlange sortieren muß, indem man beim Einfügen das Element schon an die richtige Stelle setzt. Oder man durchsucht sie nach dem Element mit den niedrigsten Kosten.
Das Ergebnis ist eine Simulation des Untergrunds.
heuristischen Kostenschätzfunktion:
Die zentrale Frage war: welcher Knoten soll als nächstes untersucht werden. Bis jetzt wurde immer der mit den geringsten Kosten gewählt. Ein anderer Weg wäre immer den Knoten zu nehmen, der dem Ziel am nähsten ist (dieser Weg ist aber nicht optimal).
A* greift diese Idee aber auf: f(x)=g(x)+h(x)
Das bedeutet die Kosten(f) nach denen aus der Warteschlange ausgewählt wird, setzen sich aus den Kosten für den zurückgelegten Weg(g) und einer Kostenabschätzung(h) für den noch zu gehenden Weg. Am einfachsten ist, wenn man für die Schätzung den Abstand zum Ziel mit einer Konstante (hängt von den Kosten für den Untergrund ab) multipliziert.
Das Resultat ist eine Ausbreitung der Suchknoten, die stark in Richtung Ziel verschoben ist. (Bei einer Heuristik von 0 (entspricht Breitensuche) hätte man einen Kreis, der sich konstant ausbreitet, bis das Ziel erreicht wird).
hier gibts noch eine Implementation von mir.
Dann hoffe ich mal, dass man es verstehen kann.
M4EiB
