Wegfindung mit A*
Aus Spieleprogrammierer-Wiki
(Unterschied zwischen Versionen)
| [gesichtete Version] | [gesichtete Version] |
K (hat „A-Stern“ nach „Wegfindung mit A*“ verschoben) |
|||
| Zeile 2: | Zeile 2: | ||
[[Kategorie:Tutorial]] | [[Kategorie:Tutorial]] | ||
[[Kategorie:Für Fortgeschrittene]] | [[Kategorie:Für Fortgeschrittene]] | ||
| − | == Was ist A | + | == Was ist A*? == |
[[Datei:A-Stern_Anim1.gif|thumb|right|Optimaler Weg zum Ziel]] | [[Datei:A-Stern_Anim1.gif|thumb|right|Optimaler Weg zum Ziel]] | ||
| − | A | + | 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 die Effizienz verbessern soll. Gibt es einen Weg zwischen den zwei Punkten, so ist garantiert, dass A* ihn auch findet. |
| − | == Wo findet A | + | == Wo findet A* Verwendung? == |
| − | Im Prinzip kann A | + | Im Prinzip kann A* überall da verwendet werden, wo Spielobjekte (z.B. die Spielfigur oder Gegner) von A nach B müssen und dabei eigenständig ihren Weg finden sollen. |
{| class="wikitable" | {| class="wikitable" | ||
| Zeile 30: | Zeile 30: | ||
|} | |} | ||
| − | == Wichtige Bestandteile von A | + | == Wichtige Bestandteile von A* == |
Hier wird auf die wichtigsten Komponenten des Algorithmus eingegangen, weil diese Begriffe später immer wieder auftauchen. | Hier wird auf die wichtigsten Komponenten des Algorithmus eingegangen, weil diese Begriffe später immer wieder auftauchen. | ||
=== Die Knoten === | === Die Knoten === | ||
| Zeile 40: | Zeile 40: | ||
* untersuchte Knoten | * untersuchte Knoten | ||
| − | Ein unbekannter Knoten muss dem A- | + | 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 unbekannt Knoten entdeckt werden. Diese unbekannten Knoten werden analysiert und werden zu bekannten Knoten. Wenn der bekannte Knoten einmal untersucht wurden, bleibt es dabei und er wird nicht noch einmal untersucht. Allerdings können bekannte Knoten öfters Analysiert werden. |
=== Die Schätzfunktion H=== | === Die Schätzfunktion H=== | ||
| Zeile 72: | Zeile 72: | ||
In die ClosedList kommen alle Knoten die bereits untersucht wurden. Bei diese Liste handelt es sich ebenfals um eine [http://de.wikipedia.org/wiki/Liste_%28Datenstruktur%29 Verkettete Liste] oder einem [http://de.wikipedia.org/wiki/Feld_%28Datentyp%29 Array]. Die Reihenfolge in der Closedlist spielt keine Rolle. | In die ClosedList kommen alle Knoten die bereits untersucht wurden. Bei diese Liste handelt es sich ebenfals um eine [http://de.wikipedia.org/wiki/Liste_%28Datenstruktur%29 Verkettete Liste] oder einem [http://de.wikipedia.org/wiki/Feld_%28Datentyp%29 Array]. Die Reihenfolge in der Closedlist spielt keine Rolle. | ||
| − | == Arbeitsweise von A | + | == Arbeitsweise von A* == |
Hier wird jetzt beschrieben wie alle Komponenten des Algorithmus zusammen arbeiten. <br/> | Hier wird jetzt beschrieben wie alle Komponenten des Algorithmus zusammen arbeiten. <br/> | ||
=== Datenstruktur eines Knoten === | === Datenstruktur eines Knoten === | ||
Version vom 12. November 2011, 13:43 Uhr
Klicke hier, um diese Version anzusehen.
