Wegfindung mit A*

Aus Spieleprogrammierer-Wiki
(Unterschied zwischen Versionen)
Wechseln zu: Navigation, Suche
[unmarkierte Version][gesichtete Version]
(→Quellen)
 
(8 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
−
{{Verbesserungsbedarf}}
 
 
[[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, dabei ist es egal ob es sich um eine 2D Spielwelt oder 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.  
+
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 zu zuweisen. Dieser Wert macht darüber eine Aussage, 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 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, und es hängt auch immer davon ab, was im Spiel genau erreicht werden soll. Wichtig ist jedoch, dass die geschätzten Kosten nie größer sein dürfen als die tatsächlichen Kosten. Die Schätzfunktion darf die Kosten also ''nicht überschätzen''. Die Schätzfunktion muss ebenfalls monoton sein.
+
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 84: Zeile 85:
 
* <tt>G</tt> enthält die bisher zurückgelegten Wegkosten.
 
* <tt>G</tt> enthält die bisher zurückgelegten Wegkosten.
 
* <tt>F</tt> enthält die Summe aus <tt>G</tt> und <tt>H</tt>.
 
* <tt>F</tt> enthält die Summe aus <tt>G</tt> und <tt>H</tt>.
−
* <tt>CoordX</tt> ist die x-Koordinate des Knotens.
+
* <tt>CoordX</tt>, <tt>CoordY</tt> (und ggf. <tt>CoordZ</tt>) sind die Koordinaten des Knotens.
−
* <tt>CoordY</tt> ist die y-Koordinate 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>ComeFromX</tt> ist die x-Koordinate des Knotens, von dem auf den aktuellen Knoten zugegriffen wurde.
+
−
* <tt>ComeFromY</tt> ist die y-Koordinate des Knotens, von dem 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).
 
* <tt>IsClosed</tt> ist ein optionales Flag, das angibt, ob der Knoten bereits abschließend untersucht wurde (er also in der Closedlist ist).
  
Zeile 1.035: Zeile 1.034:
 
== Quellen ==
 
== Quellen ==
 
* http://de.wikipedia.org/wiki/A_Stern
 
* http://de.wikipedia.org/wiki/A_Stern
−
* http://www.policyalmanac.org/games/aStarTutorial_de.html
 

Aktuelle Version vom 20. Oktober 2020, 20:29 Uhr

Klicke hier, um diese Version anzusehen.

Von „https://www.spieleprogrammierer.de/wiki/Wegfindung_mit_A*“
Meine Werkzeuge
Namensräume
Varianten
Aktionen
Navigation
Werkzeuge