Wegfindung mit A*
Aus Spieleprogrammierer-Wiki
(Unterschied zwischen Versionen)
| [gesichtete Version] | [gesichtete Version] |
K (→Verwendung) |
Tris (Diskussion | Beiträge) (→Quellen) |
||
| (19 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
| − | |||
[[Kategorie:Algorithmus]] | [[Kategorie:Algorithmus]] | ||
[[Kategorie:Tutorial]] | [[Kategorie:Tutorial]] | ||
[[Kategorie:Für Fortgeschrittene]] | [[Kategorie:Für Fortgeschrittene]] | ||
[[Datei:A-Stern_Anim1.gif|thumb|right|Optimaler Weg zum Ziel]] | [[Datei:A-Stern_Anim1.gif|thumb|right|Optimaler Weg zum Ziel]] | ||
| − | A* (''A Stern'') ist ein Algorithmus, um einen ''kürzesten oder kostengünstigsten Weg zwischen zwei Punkten'' zu finden. Dafür verwendet er eine ''Schätzfunktion'', die dazu beiträgt gerichtet zu suchen, was im Allgemeinen die Effizienz der Suche verbessert. Gibt es einen Weg zwischen den zwei Punkten, so ist garantiert, dass A* ihn auch findet. Weiterhin ist garantiert, dass immer ein kürzester Weg gefunden wird. | + | A* (''A Stern'') ist ein Algorithmus, um einen ''kürzesten oder kostengünstigsten Weg zwischen zwei Punkten'' zu finden. Dabei ist es egal, ob es sich um eine 2D- oder eine 3D-Spielwelt handelt. Dafür verwendet er eine ''Schätzfunktion'', die dazu beiträgt gerichtet zu suchen, was im Allgemeinen die Effizienz der Suche verbessert. Gibt es einen Weg zwischen den zwei Punkten, so ist garantiert, dass A* ihn auch findet. Weiterhin ist garantiert, dass immer ein kürzester Weg gefunden wird. |
== Verwendung == | == Verwendung == | ||
| Zeile 46: | Zeile 45: | ||
[[Datei:A-Stern_Distanz1.png|thumb|right|Entfernungen zum Schätzen bestimmen]] | [[Datei:A-Stern_Distanz1.png|thumb|right|Entfernungen zum Schätzen bestimmen]] | ||
| − | Die Schätzfunktion wird benötigt, um dem aktuell untersuchten Knoten einen Wert | + | Die Schätzfunktion wird benötigt, um dem aktuell untersuchten Knoten einen Wert zuzuweisen. Dieser Wert macht eine Aussage darüber, wie weit der Knoten schätzungsweise vom Ziel entfernt ist. Die Schätzfunktion wird im Allgemeinen als <math>h</math> bezeichnet (für ''Heuristik''), und die geschätzten Kosten nennen wir <math>H</math>. Die ''tatsächlichen Kosten'' bezeichnen wir mit <math>c</math>. <math>c(k)</math> gibt die Kosten an, um vom Knoten <math>k</math> zum Ziel zu gelangen, <math>c(k, k')</math> gibt die Kosten an, um vom Knoten <math>k</math> zum Knoten <math>k'</math> zu gelangen. |
| − | Es gibt verschiedene Ansätze für die Schätzfunktion, | + | Es gibt verschiedene Ansätze für die Schätzfunktion. Welche davon eine gute Wahl ist, hängt auch immer davon ab, was im Spiel genau erreicht werden soll. Damit der hier gezeigte A*-Algorithmus korrekt funktioniert, muss die Schätzfunktion eine Voraussetzung erfüllen, sie muss nämlich ''[http://de.wikipedia.org/wiki/Monotonie_(Mathematik) monoton]'' sein. Das bedeutet in diesem Zusammenhang: |
| + | # <math>h(k) \leq c(k)</math>: Die geschätzten Kosten dürfen nie größer sein dürfen als die tatsächlichen Kosten. Die Schätzfunktion darf die Kosten also ''nicht überschätzen''. | ||
| + | # <math>h(k) \leq c(k, k') + h(k')</math> für benachbarte Knoten <math>k</math> und <math>k'</math>: Die geschätzten Kosten von einem Knoten <math>k</math> zum Ziel dürfen nicht größer sein als die tatsächlichen Kosten zu einem beliebigen Nachbarknoten <math>k'</math> plus die geschätzten Kosten von <math>k'</math> bis zum Ziel. | ||
Eine einfache Schätzfunktion ist die direkte Distanz zwischen dem aktuellen Knoten und dem Ziel. Diese Distanz wird mittels des Satz des Pythagoras ermittelt. | Eine einfache Schätzfunktion ist die direkte Distanz zwischen dem aktuellen Knoten und dem Ziel. Diese Distanz wird mittels des Satz des Pythagoras ermittelt. | ||
| Zeile 66: | Zeile 67: | ||
Eng verbunden mit der Schätzfunktion sind zwei weitere Werte. Der Wert für den bereits zurückgelegten Weg vom Startknoten wird im Allgemeinen als <math>G</math> bezeichnet. Ein weiterer wichtiger Wert ist die Summe aus <math>H</math> und <math>G</math>. Dieser Wert wird <math>F</math> genannt. Er stellt später das Suchkriterium dar, nach dem aus der Openlist ein Knoten ausgewählt wird. | Eng verbunden mit der Schätzfunktion sind zwei weitere Werte. Der Wert für den bereits zurückgelegten Weg vom Startknoten wird im Allgemeinen als <math>G</math> bezeichnet. Ein weiterer wichtiger Wert ist die Summe aus <math>H</math> und <math>G</math>. Dieser Wert wird <math>F</math> genannt. Er stellt später das Suchkriterium dar, nach dem aus der Openlist ein Knoten ausgewählt wird. | ||
| − | Es gibt auch weitere Werte, die auf den Algorithmus einen Einfluss haben können. Zum Beispiel Extrakosten, die bei Strategiespielen durch unwegsames Gelände zustande kommen. Eine weitere Möglichkeit sind | + | Es gibt auch weitere Werte, die auf den Algorithmus einen Einfluss haben können. Zum Beispiel könnte es Extrakosten geben, die bei Strategiespielen durch unwegsames Gelände zustande kommen. Eine weitere Möglichkeit sind Drehbewegung einer Spielfigur, die ebenfalls Kosten verursachen können. Diese "optionalen Werte" sollten auch mit in die Berechnung von <math>F</math> einfließen. |
| − | + | ||
| − | Diese "optionalen Werte" sollten auch mit in die | + | |
Berechnungsformel: <math>F = H + G + Optional</math> | Berechnungsformel: <math>F = H + G + Optional</math> | ||
=== Die Openlist === | === Die Openlist === | ||
| − | In die Openlist kommen alle Knoten die bekannt sind. Bei der Openlist | + | In die Openlist kommen alle Knoten, die bekannt sind. Bei der Openlist wird die Verwendung einer [http://de.wikipedia.org/wiki/Vorrangwarteschlange Vorrangwarteschlange] empfohlen, in der die Knoten nach ihren <math>F</math>-Werten sortiert werden. Somit kann sehr schnell auf den erfolgversprechendsten Knoten zugegriffen werden. |
=== Die Closedlist === | === Die Closedlist === | ||
| − | In die Closedlist kommen alle Knoten die bereits untersucht wurden. | + | In die Closedlist kommen alle Knoten, die bereits untersucht wurden. Die Closedlist kann implizit dadurch dargestellt werden, dass man sich für jeden Knoten merkt, ob er in der Closedlist steht oder nicht. Alternativ bietet sich eine sortierte Liste oder eine [http://de.wikipedia.org/wiki/Hashtabelle Hashtabelle] an, da diese Datenstrukturen eine Abfrage der Art "''Ist Element x enthalten?''" sehr schnell beantworten können. |
== Arbeitsweise von A* == | == Arbeitsweise von A* == | ||
| − | + | Im Folgenden wird beschrieben, wie alle Komponenten des A*-Algorithmus zusammen arbeiten. | |
=== Datenstruktur eines Knoten === | === Datenstruktur eines Knoten === | ||
| − | Diese Werte sollte ein Knoten mindestens speichern können | + | Diese Werte sollte ein Knoten mindestens speichern können: |
| − | *H | + | * <tt>H</tt> beinhaltet den Schätzwert der Wegkosten von diesem Knoten bis zum Ziel. |
| − | *G | + | * <tt>G</tt> enthält die bisher zurückgelegten Wegkosten. |
| − | *F | + | * <tt>F</tt> enthält die Summe aus <tt>G</tt> und <tt>H</tt>. |
| − | * | + | * <tt>CoordX</tt>, <tt>CoordY</tt> (und ggf. <tt>CoordZ</tt>) sind die Koordinaten des Knotens. |
| − | * | + | * <tt>ComeFromX</tt>, <tt>ComeFromY</tt> (und ggf. <tt>ComeFromZ</tt>) sind die Koordinaten des Knotens, von denen auf den aktuellen Knoten zugegriffen wurde. |
| − | + | * <tt>IsClosed</tt> ist ein optionales Flag, das angibt, ob der Knoten bereits abschließend untersucht wurde (er also in der Closedlist ist). | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | * | + | |
| − | + | ||
| − | + | ||
=== Beschreibung === | === Beschreibung === | ||
| − | Zu | + | Zu Beginn sind dem Algorithmus nur zwei Knoten bekannt, der Startknoten und der Zielknoten. Der Startknoten wird der Openlist hinzugefügt. Den Zielknoten behalten wir erst einmal nur im Hinterkopf. |
| − | In der Openlist wird nun nach dem | + | In der Openlist wird nun nach dem geeignetsten Knoten gesucht. Da hier nur der Startknoten enthalten ist, fällt die Wahl nicht schwer. Jetzt wird der Startknoten untersucht, das bedeutet, dass nach allen benachbarten begehbaren Knoten gesucht wird. Für jeden gefundenen Knoten werden die Werte für <math>H</math>, <math>G</math> und <math>F</math> ermittelt. Die ermittelten Werte werden in den jeweiligen Knoten gespeichert. Weiterhin muss auch gespeichert werden, von welchem Knoten man auf den neuen Knoten gekommen ist. Die neu gefunden Knoten werden alle in die Openlist eingefügt. Der Startknoten wird von einem bekannten Knoten zu einem untersuchten Knoten und wird damit in die Closedlist eingefügt. |
| − | Jetzt wird in der Openlist nach dem Knoten gesucht der den geringsten F Wert hat. Von diesem Knoten werden nun wieder alle benachbarten Knoten gesucht und analysiert. Dabei kann es vorkommen | + | Jetzt wird in der Openlist nach dem Knoten gesucht der den geringsten <math>F</math>-Wert hat. Von diesem Knoten werden nun wieder alle benachbarten Knoten gesucht und analysiert. Dabei kann es vorkommen, dass im Laufe der Zeit Knoten die schon in der Openlist stehen, erneut analysiert werden. Wenn der <math>F</math>-Wert sich verbessert, sollten alle Daten des Knotens überschrieben werden. Sind die Daten gleich oder schlechter, können die alten Daten beibehalten werden. |
| − | So arbeitet der Algorithmus die Openlist ab, fügt unbekannte Knoten der Openlist zu und fügt untersuchte Knoten der Closedlist zu. Wenn jetzt der Zielknoten der Closedlist zugefügt wird | + | So arbeitet der Algorithmus die Openlist ab, fügt unbekannte Knoten der Openlist zu und fügt untersuchte Knoten der Closedlist zu. Wenn jetzt der Zielknoten der Closedlist zugefügt wird, endet der Algorithmus. Der günstigste Weg ist gefunden. |
| − | Nun kann ausgehend vom Zielknoten | + | Nun kann ausgehend vom Zielknoten nachvollzogen werden, von welchem Knoten man auf den Zielknoten kam. Von diesem ausgehend wird dann wieder geschaut, von welchem Knoten man auf diesen kam, und immer so weiter, bis man wieder am Startknoten angekommen ist. Auf diese Weise wird der komplette Weg rekonstruiert. |
| − | Wenn die Openlist leer ist bevor man den Zielknoten erreicht hat kann der Algorithmus abgebrochen werden, da dann kein Weg zwischen Start- und | + | Wenn die Openlist leer ist, bevor man den Zielknoten erreicht hat, kann der Algorithmus abgebrochen werden, da dann kein Weg zwischen Start- und Zielknoten existiert. |
=== Schritt für Schritt mit Bildern === | === Schritt für Schritt mit Bildern === | ||
| + | [[Datei:A-Stern_Step_by_Step.gif|thumb|right|Der komplette Ablauf des A*-Algorithmus für ein einfaches Beispiel.]] | ||
Da Bilder bekanntlich mehr sagen als 1000 Worte, noch einmal alles in Bildern erklärt. | Da Bilder bekanntlich mehr sagen als 1000 Worte, noch einmal alles in Bildern erklärt. | ||
Die Rahmenbedingungen für den Algorithmus: | Die Rahmenbedingungen für den Algorithmus: | ||
| − | * | + | * Es sind keine diagonalen Schritte erlaubt. |
| − | * Schätzfunktion | + | * Die Schätzfunktion ist die Manhattan-Distanz. |
| − | * 1 Schritt | + | * 1 Schritt kostet 1 Punkt. |
| − | * Richtungswechsel kostet 1 Punkt (in Tabelle Spalte Z) | + | * Ein Richtungswechsel kostet 1 Punkt (in der Tabelle die Spalte Z). |
| − | * | + | * Knoten werden durch ihre x- und y-Koordinaten benannt. |
Spielfeld-Legende: | Spielfeld-Legende: | ||
| − | * | + | * Grün: Startpunkt (7/10) |
| − | * | + | * Orange: Zielpunkt (2/2) |
| − | * | + | * Weiß: unbekannte Knoten |
| − | * | + | * Gelb: bekannte Knoten (Openlist) |
| − | * | + | * Blau: untersuchte Knoten (Closedlist) |
| − | * | + | * Schwarz: nicht begehbare Knoten (Hindernis) |
| − | + | ||
| − | + | ||
{| class="wikitable" | {| class="wikitable" | ||
| Zeile 133: | Zeile 125: | ||
| align="center" colspan="6" style="background-color:#FFF200;"| Openlist | | align="center" colspan="6" style="background-color:#FFF200;"| Openlist | ||
| colspan="1" style="background-color:#949494;" | | | colspan="1" style="background-color:#949494;" | | ||
| − | | align="center" colspan="2" style="background-color:# | + | | align="center" colspan="2" style="background-color:#00A2E8;"| Closedlist |
|- | |- | ||
! '''Schritt''' !!'''Knotenname''' !! '''H''' !! '''G''' !! '''Z''' !! '''F''' !! Bild !! '''Knotenname''' !! '''ComeFrom''' | ! '''Schritt''' !!'''Knotenname''' !! '''H''' !! '''G''' !! '''Z''' !! '''F''' !! Bild !! '''Knotenname''' !! '''ComeFrom''' | ||
| Zeile 1.034: | Zeile 1.026: | ||
|} | |} | ||
| − | In der | + | In der Closedlist steht jetzt schon der richtige Weg, zwar ist er nicht in der richtigen Reihenfolge, aber das stört nicht. Wenn man jetzt beim Zielknoten (2/2) in die Spalte ''ComeFrom'' schaut, steht dort ein Knoten (3/2). Jetzt sucht man sich in der Spalte ''Knotenname'' diesen Knoten heraus. In dieser Reihe steht unter ''ComeFrom'' wieder ein Knoten, und so "hangelt" man sich die Liste entlang bis man zum Startknoten kommt. |
Der Weg, den der Algorithmus abgeht, sieht dann so aus: | Der Weg, den der Algorithmus abgeht, sieht dann so aus: | ||
| − | (2/2) -> (3/2) -> (4/2) -> (5/2) -> (6/2) -> (7/2) -> (7/3) -> (7/4) -> (7/5) -> (7/6) -> (7/7) -> (7/8) -> (7/9) -> (7/10) | + | (2/2) -> (3/2) -> (4/2) -> (5/2) -> (6/2) -> (7/2) -> (7/3) -> (7/4) -> (7/5) -> (7/6) -> (7/7) -> (7/8) -> (7/9) -> (7/10) |
== Quellen == | == Quellen == | ||
* http://de.wikipedia.org/wiki/A_Stern | * http://de.wikipedia.org/wiki/A_Stern | ||
| − | |||
Aktuelle Version vom 20. Oktober 2020, 20:29 Uhr
Klicke hier, um diese Version anzusehen.
