A*Algorithmus (Wegfindung)

[Streak]

HeyHo,
ich programmiere derzeit ein Browsergame, was auf der Grundideee von Travianer basiert. Nun wollte ich, wie dort, ein Männchen machen, dass zum letzten Mausklick läuft. Klappt auch alles wunderbar, nur macht mir eben die "Wegfindung" Kopfzerbrechen.
Als erstes hatte ich es so gemacht, dass die "kurven" als Knotenpunkte gespeichert werden und dann einfach abgefragt wird, welche Knotenpunkte zwischen $start und $ziel liegen. Dann habe ich jedoch gemerkt dass es doch nicht so einfach ist ().
Nachdem ich schon einiges gelesen hatte bin dann auf A*-Algorithmus gestoßen.
Nur werde ich daraus nicht wirklich schlau und hab auch nicht wirklich Ahnung wie ich dass umsetzten kann. Die Javascript Umsetzung ist für mich kein Problem.

Hat jemand eventuelle Lösungsansätze oder Tutorials bzw. links?


Mit besten Grüßen
Streak

Ps.: Ich will es jedenfalls versuchen dies hinzubekommen, bevor ich vor diesem Vorhaben kapituliere

[luke.-]

also ich kenne den A*Algo nicht und bin in PHP auch noch Anfänger, aber ich könnt dir folgenden Artikel empfehlen, vielleicht hilft er dir ja:
GIS | Dijkstra's algorithm - GISWiki

es geht um den Algorithmus von Dijkstra und bei wiki ist auch ein beispielcode in php angegeben, vielleicht trägt der zum verständnis bei...

[Chriz]

Das Beispiel beim Wikiartikel ist doch ganz anschaulich. Die verwendeten Werte (Kantenwiderstand, "Luftlinie") musst du eben vorliegen haben. Wobei ich in dem Artikel nicht ganz verstehe, warum der potentiell schnellste Weg als erstes berechnet werden soll, wenn doch sowieso alle Wege berechnet werden müssen.

[lstegelitz]

Wobei ich in dem Artikel nicht ganz verstehe, warum der potentiell schnellste Weg als erstes berechnet werden soll, wenn doch sowieso alle Wege berechnet werden müssen.

Weil manche Sprachen Multithreading unterstützen

[Chriz]

Ich muss doch trotzdem warten, bis alle Streckenergebnisse vorliegen?!

[Asipak]

Dies ist auch noch ein ganz hübsches Tut, finde ich: A* Pathfinding for Beginners

Gruß

[nikosch]

Wobei ich in dem Artikel nicht ganz verstehe, warum der potentiell schnellste Weg als erstes berechnet werden soll, wenn doch sowieso alle Wege berechnet werden müssen.

Deshalb?

// wenn der Nachfolgeknoten bereits auf der Open List ist,
// aber der neue Weg länger ist als der alte - tue nichts
if openlist.contains(successor) and f > openlist.find(successor).f then
continue

Wenn während der Wegberechnung die bisher kürzeste Länge überschritten wird, kann man ja dort abbrechen.

[KarlEgon]

Sind 'Dijkstra' und 'A*' sich nicht ähnlich?
Wenn ich richtig informiert bin, dann sucht 'Dijkstra' in alle Richtungen, beim 'A*' hat man durch eine Heuristik schon die grobe Richtung und braucht die anderen Richtungen deswegen gar nicht zu beachten.

[Asipak]

Verwandte Algorithmen

Der A*-Algorithmus ist verwandt mit dem Dijkstra-Algorithmus [...]. Der Algorithmus von Dijkstra verwendet keine Heuristik (h = 0, also f = g) und wählt Knoten nur anhand der bisherigen Kosten aus.

[lstegelitz]

Ich muss doch trotzdem warten, bis alle Streckenergebnisse vorliegen?!

In PHP schon... da es sich um Portierungen eines Algorithmus handelt, ist das warscheinlich aus einer anderen Sprache übernommen worden.

In einer MT Umgebung kann ein Ergebnis bereits verwendet werden (i.e. sobald es fertig berechnet ist), während andere Ergenisse noch kalkuliert werden.

[Chriz]

Deshalb?
Wenn während der Wegberechnung die bisher kürzeste Länge überschritten wird, kann man ja dort abbrechen.

OK, macht Sinn.

[Streak]

ok, der Link von Asipak (A* Pathfinding for Beginners) hat mich schon ein ganzes stück weiter gebracht, ich verstehe das jetzt so einigermaßen.
Nur eine Frage stellt sich mir noch, wie stell ich das mit so einer Karte dann an? Mache ich nur "quadrate" für die Wege?


Beste Grüße
Streak

[KarlEgon]

Musst nicht unbedingt quadrate nehmen, kannst jede beliebige Form nehmen, allerdings wird es dann komplizierter mit der Berechnung