Wegfindung mit A*
Aus Spieleprogrammierer-Wiki
(Unterschied zwischen Versionen)
| [gesichtete Version] | [gesichtete Version] |
(→Die Werte F, G und optionale Werte) |
(→Die Schätzfunktion H) |
||
| Zeile 43: | Zeile 43: | ||
Ein unbekannter Knoten muss dem A*-Algorithmus erst im Laufe der Zeit bekannt gemacht werden. Bekannte Knoten können untersucht werden. Durch diese Untersuchung können unbekannte Knoten entdeckt werden. Diese unbekannten Knoten werden analysiert und werden zu bekannten Knoten. Wenn der bekannte Knoten einmal untersucht wurde, bleibt es dabei, und er wird nicht noch einmal untersucht. Allerdings können bekannte Knoten wiederholt analysiert werden. | Ein unbekannter Knoten muss dem A*-Algorithmus erst im Laufe der Zeit bekannt gemacht werden. Bekannte Knoten können untersucht werden. Durch diese Untersuchung können unbekannte Knoten entdeckt werden. Diese unbekannten Knoten werden analysiert und werden zu bekannten Knoten. Wenn der bekannte Knoten einmal untersucht wurde, bleibt es dabei, und er wird nicht noch einmal untersucht. Allerdings können bekannte Knoten wiederholt analysiert werden. | ||
| − | === Die Schätzfunktion | + | === Die Schätzfunktion === |
[[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. Das muss nicht unbedingt die rein geometrische Entfernung sein, sondern es können beispielsweise auch Eigenschaften des Spielfelds mit einbezogen werden (Bodenbeschaffenheit, Steigung). Ein kurzer Weg durch ein Sumpfgebiet könnte "teurer" sein als ein doppelt so langer Weg über normalen Boden. Die Schätzfunktion wird im Allgemeinen als <math> | + | 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. Das muss nicht unbedingt die rein geometrische Entfernung sein, sondern es können beispielsweise auch Eigenschaften des Spielfelds mit einbezogen werden (Bodenbeschaffenheit, Steigung). Ein kurzer Weg durch ein Sumpfgebiet könnte "teurer" sein als ein doppelt so langer Weg über normalen Boden. Die Schätzfunktion wird im Allgemeinen als <math>h</math> bezeichnet (für ''Heuristik''). |
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''. | 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''. | ||
| Zeile 52: | Zeile 52: | ||
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. | ||
| − | Eine weitere Möglichkeit ist die Manhattan-Distanz. Bei dieser Methode werden vom entstehenden Dreieck einfach die Längen der beiden Katheten addiert. Diese darf aber nur dann angewendet werden, wenn keine diagonalen Bewegungen erlaubt sind, ansonsten würde sie die Kosten überschätzen. | + | Eine weitere Möglichkeit ist die Manhattan-Distanz. Bei dieser Methode werden vom entstehenden Dreieck einfach die Längen der beiden Katheten addiert. Diese darf aber nur dann angewendet werden, wenn keine diagonalen Bewegungen erlaubt sind, ansonsten würde sie die Kosten überschätzen. Ihren Namen hat diese Distanzfunktion aus dem New Yorker Stadtteil Manhattan, da man sich dort normalerweise nur vertikal und horizontal durch die Straßen um die Gebäudeblöcke bewegen kann. |
'''Nach Pythagoras:''' | '''Nach Pythagoras:''' | ||
Version vom 20. November 2011, 15:08 Uhr
Klicke hier, um diese Version anzusehen.
