Wegfindung mit A*
Aus Spieleprogrammierer-Wiki
(Unterschied zwischen Versionen)
[gesichtete Version] | [gesichtete Version] |
K (→Die Werte F, G und optionale Werte) |
(Schlechte Empfehlungen für Datenstrukturen verbessert) |
||
Zeile 71: | Zeile 71: | ||
=== 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* == |
Version vom 20. November 2011, 15:25 Uhr
Klicke hier, um diese Version anzusehen.