spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Also es funktioniert folgendermaßen:
Der Algorithmus breitet seine beiden Listen langsam über
das Spielfeld aus.
Zuerst einmal sucht er sich den Knoten, zu dem der Weg am
besten ist.
Den findet er indem er die g-Werte vergleicht, die aus der
Summe der kompletten Wegkosten Knoten liegen berechnet werden.
Daraufhin untersucht er alle Nachfolgeknoten, d.h. er geht alle Wege
ab die zu Knoten führen die nicht in der Closed list liegen und speichert
sie mit ihrem g-Wert. Sollte einer davon in der Open list liegen, so speichert
er ihn nur, falls dieser Weg besser ist (der g-Wert kleiner ist).

Da der Algorithmus stets den Knoten untersucht, zu dem der Weg am
kleinsten ist, ist der Weg der dorthin gefunden wurde perfekt (alle anderen
Wege sind schließlich länger und führen noch nichtmal mehr undbedingt zu
diesem Knoten).
Wenn du also mit der untersuchung dieses Knotens fertig bist, kannst du
dir sicher sein, dass du den Idealenweg gefunden hast.

Ich hatte ein Problem, weil ich lange Zeit nicht kapiert habe, das der g-Wert
aus der Summe aller Wegkosten besteht. Dem ist aber NICHT so.

Der Beweis dafuer ist induktiv. Induktionsanfang, ist das du vom Startpunkt mit einem Weg der Laenge 0 zum Startpunkt gelangst. Von da aus breitet sich dann die "Sicherheit", dass man den kuerzesten Weg schon hat, ueber alle Knoten aus. Die Argumentation ist da im Prinzip: "wenn ich hier den Weg mit Laenge x habe, und alle anderen Wege gehen durch closed Nodes (koennen also nicht mehr kuerzer werden), und haben schon mindestens Laenge x, so kann ich unmoeglich einen Weg kuerzer x finden, also ist dieser optimal". Das ist auch der Grund, warum keine Kante negativ bewertet sein darf, dann liesse sich naemlich evtl. ein solcher Weg finden.

Zitat von »Flonk«

Ich hatte ein Problem, weil ich lange Zeit nicht kapiert habe, das der g-Wert
aus der Summe aller Wegkosten besteht. Dem ist aber NICHT so.

hmmm, du sagst also: du hattest ein Problem, weil du nicht verstanden hast, wie es NICHT ist?

UPS naja, ich war grad aus der schule zurück und um 15:30 hat man dann echt die schnauze voll,
zumal man den ganzen Tag von Lehrern in einer anderen Sprache belabert wird.

Zitat von »TGGC«

Das ist auch der Grund, warum keine Kante negativ bewertet sein darf, dann liesse sich naemlich evtl. ein solcher Weg finden.

Bellman-Ford ftw!

Zum Thema:
Ich weiss nicht, ob es hilft, aber hier hat es 2 recht gute Seiten, die verschiedene Wegsuch Algorithmen vorstellen/vergleichen:

http://www.stefan-baur.de/priv.studies.hauptseminar.html
http://theory.stanford.edu/~amitp/GameProgramming/

Zitat von »dispy«

@TGGC: Könntest du den induktiven Beweis "einfach" kurz führen?
im Beispiel ist es mir klar, dass der kürzeste Weg von Saarbrücken nach Kaiserslautern bekannt ist - nur beim Schritt nach Ludwigshafen fliege ich dann raus


MfG
dispy

Die h's stellen einen noch zu erwartenden Weg dar. Das "Gewicht" eines Knoten setzt sich dann aus den Kanten dort hin + der noch wahrscheinlich dazukommende zusammen. Um das ganze ein wenig besser zu verstehen kannst du dir zuerst ja einfach mal Dijkstra ansehen, welcher das gleiche macht, einfach ohne die Heuristik mit dem noch erwartendem Weg.

Aber zurück zum Beispiel. Du bist ja jetzt in Kaiserslauten. Jetzt weisst du, dass der Weg nach Frankfurt 70+103 kostet. Der Weg nach Ludwigshafen 70+53. Dijkstra würde hier jetzt einfach das kürzere nehmen also in dem Falle Ludwigshafen. A* macht hier aber noch eine zusätzliche Betrachtung, indem er schaut was man no so für einen weiteren Weg minimal erwartet (Luftlinie). Also kommen jeweils noch die h's dazu. In dem Falle wählt auch A* hier Ludwigshafen. Wenn man jetzt aus irgendwelchen Gründen beim Ludwigshafen aber einen viel weiteren Weg erwartet, als über Frankfurt, dann würde A* hier Frankfurt wählen, während Dijkstra stupide Ludwigshafen nimmt. In betracht gezogen für den nächsten Ort werden dann alle in der offenen Liste (grau bei dem Beispiel). Und das machst du jetzt solange bis du das Ziel erreicht hast.

Es ist eigentlich intuitiv begreifbar dass das so sein muss. Gäbe es einen kürzeren Weg zu x so hätte A* diesen zuerst probiert und wäre damit über den kürzeren Weg bei x angekommen.

Der optimale Weg muss aus optimalen Teilwegen zusammengesetzt sein. Denn angenommen der kürzeste Weg von A nach C führt über B, dann muss natürlich der Teilweg von A nach B auch der global kürzeste Weg von A nach B sein denn gäbe es einen noch kürzeren Weg von A nach B so könnte man sofort auch einen kürzeren Weg von A über B nach C angeben und unser optimaler Weg wäre nicht optimal => Widerspruch.