Algorithmus zur Wegberechnung?

Kennt sich jemand vielleicht mit folgendem Problem aus?

Ich habe eine Landkarte mit Städten. Spieler können von Stadt zu Stadt oder auch zu beliebigen Koordinaten reisen. Dabei wird einfach über den Satz des Pythagoras und ein paar weitere Berechnungen die Strecke ermittelt und auch im Browser per JavaScript die momentane Position angezeigt. Jetzt kommt es aber vor, dass Helden bei ihren Reisen durchs Meer reisen ( z. B. durch eine Bucht), weil das Progamm immer den geraden, kürzesten Weg wählt. Gibt es einen effektiven und einfach zu implementierenden Algorithmus, der die Strecke auf enthaltene Wasserfelder überprüft und den Weg dann so aufteilt oder neu festlegt, dass der Held den Umweg übers Land nehmen muss?

Hat sich jemand schonmal damit auseinandergesetzt und/oder kann dabei helfen? Das wäre sehr hilfreich

Schau dir mal den A* (A-Star) Algorithmus an.

Eine modifizierte Version von diesem habe ich genutzt.

Im Netz findest du einige Java-Applets, die diesen Algorithmus recht anschaulich zeigen.

Vielen Dank, das hat mir schonmal viel weitergeholfen!
Allerdings ist der Algorithmus (so wie er ist) nicht so optimal für mich - meine Reise wird modelliert als Liste von Punkten im 2D-Raum, z. B. ist (10,10),(20,10),(30,20) eine Reise von (10,10) nach (30,20) über (20,10). Und da brauche ich nach Möglichkeit einen Weg, der möglichst selten die Richtung wechselt und trotzdem relativ optimal ist... Also eine Reise mit möglichst wenig Punkten in der Liste.
Und A* in der Originalform ist in PHP erstens ziemlich speicheraufwendig und generiert mir für Reisen an "ausgefransten" Buchten entlang sehr sehr lange Listen...
Aber ich denke, auf dem A*-Algorithmus kann ich erstmal aufbauen und den für meine Zwecke anpassen.

Du solltest Deine Karte als Graph modellieren.
D.h. eine Menge von Knoten [Orte an denem man sein kann] und Kanten [Verbindungen zwischen den Knoten].

Dadurch kannst Du dann ganz einfach Wasserfelder ausschliessen bzw. nur erlauben wenn der Spieler ein Schiff besitzt.

A* ist meiner Meinung nach der Algorithmus der Wahl, ansonsten kannst Du aber auch noch andere ausprobieren ["Künstliche Intelligenz" ISBN: 3827370892].

Falls Deine Karte statisch ist, kannst Du auch den Kleene-Warshall Algorithmus verwenden. Der berechnet von allen Punkten auf der Karte zu allen anderen die kuerzesten Wege, ist aber recht langsam.
Wenn Deine Karte allerdings statisch ist kannst Du alle kuerzesten Wege offline berechnen und dann online nur noch den vorberechneten Weg auslesen.

hey leute,

ich hab auchn problem mit A*-Algorithmus und zwar dass ich das nich kapiere. ich hab mir schon seiten durchgelesen und versucht es zu verstehen.

ich häng nun schon den ganzen tag dran und hab noch kein stückchen code schreiben können.

vllt beschreib ich noch kurz meine anforderungen an dieses system:
ich brauchn system, das mir auf einer karte den kürzesten weg berechnet (damit mein ich nicht die weglänge, sondern die wegdauer) und das um hinternisse herrumläuft. wegdauer wird pro feld das zu laufen ist nicht direkt festgelegt (also zb 1 feld 8 minuten), sondern es wird entschieden um welches feld es sich handelt (zb flaches land 8 minuten, berge 16 minuten, fluss 9 minuten, ...). das system hab ich schon entwickelt und getestet, es funktioniert. aber aus den minuten bzw sekunden, soll er den kürzesten weg berechnen. für den fall, dass es zu kompliziert ist oder zu aufwendig von den rechnungen her, dann lass ich das auch weg, bräuchte dann halt nur noch, dass er um hinternisse rumläuft (zb an nem strand vorbei in die bucht reinlaufen, statt gegen das meer).

das is also mein problem, will mich aber nich vorträngeln, deshalb behandelt erstmal Tweetys Problem. dachte nur, bevor ich ein gleiches thema öffne schreib ichs hier rein

grüße
DarkSnake

Danke, mein Problem hat sich durch die gegebenen Antworten (thanks) schon sehr weit eingegrenzt. A* kann ich zwar nicht so übernehmen, wie er ist, aber ich versuche ihn mal an meine Bedürfnisse anzupassen.

@DarkSnake: Das ganze System funktioniert mit Graphen - vielleicht lies dir einfach mal zum Verständnis bei der deutschen Wikipedia den Artikel Graphentheorie, Graph etc. durch.
Es kommt natürlich auf die Struktur deiner Karte an, wie die intern aufgebaut ist.

Wenn du einfach eine Menge von Punkten hast, die durch Wege verbunden sind, hast du schon einen Graphen, A* ist hier optimal.

Wenn du (wie z. B. ich) eine Karte hast, die gerastert ist (also mit einer regelmäßigen geometrischen Struktur, z. B. wie eine Pixelgrafik oder in Sechsecken) gibts laut diverser Anmerkungen in meinen Google-Ergebnissen noch geeignetere Algorithmen - aber welche das sind, weiß ich nicht.

Du kannst aber A* auf deine Rastergrafik anwenden. Dabei sind alle deine Felder einfach Punkte innerhalb des Graphen. Die Kanten (Übergänge zu anderen Feldern) gehen dann von einem quadratischen Feld in die Himmelsrichtungen zu den Nachbarfeldern ab. Auf Wasserfelder führt dann allerdings keine Kante. Als "Wert" oder Länge der Kanten kannst du dann die geographische Entfernung, die Dauer oder in deinem Fall auch die Geländeart der beiden Felder nehmen. Mit diesem Graphen kannst du dann A* implementieren.
Ich hoffe, das hilft erstmal weiter.

Ich finde diese Seite beschreibt A* sehr gut:
http://www.geosimulation.de/umsetzungen/Beschreibungen/Routenoptinierung_A_Stern_Algorithmus.htm

Das mag jetzt zwar Geschmack sein, und das Java-Applet ist auf jeden Fall nützlich zum Veranschaulichen, aber als Vorlage für die Implementierung des Algorithmus hat mir eher der Wikipedia-Artikel weitergeholfen.

ich verstehe nun die funktionsweise teilweise :/

aber leider keine ahnung wie ich das in php umsetzen soll. hat einer vllt nen beispielcode zum draus lernen? ganz einfach und billig würde mir eigentlich schon langen, ich brauch nurn ansatz denk ich. auf einer gerasteten karte wärs ganz praktisch, weil das meinen vorstellungen näher kommen könnte.

es will wohl auch nicht ganz in mein kopf rein, wie er schon im vorfeld entscheiden kann, ob da der weg endet oder nicht. also gute hilfe wär nich schlecht

http://theory.stanford.edu/~amitp/GameProgramming/

also ich hab mein eigenen a-star entwickelt... am anfang wusst ich auch nicht wirklich wie ich da ran gehen sollte, hab denn aber einige Seiten gelesen und denn wusst ich schon so ca. wie das abläuft...
und im endeffekt hat dieser Pseudo-Code mir geholfen das umzusetzen:

Der A-Star Algorithmus als Pseudocode. Dies ist kein richtiger Code, enthält aber alles wichtige für diese Methodik:

Create a node containing the goal state node_goal
Create a node containing the start state node_start
Put node_start on the open list
while the OPEN list is not empty
{
Get the node off the open list with the lowest f and call it node_current
if node_current is the same state as node_goal we have found the solution;
break from the while loop
Generate each state node_successor that can come after node_current
for each node_successor of node_current
{
Set the cost of node_successor to be the cost of node_current plus the
cost to get to node_successor from node_current
find node_successor on the OPEN list
if node_successor is on the OPEN list but the existing one is as good or
better then discard this successor and continue
if node_successor is on the CLOSED list but the existing one is as good
or better then discard this successor and continue
Remove occurences of node_successor from OPEN and CLOSED
Set the parent of node_successor to node_current
Set h to be the estimated distance to node_goal (Using the heuristic function)
Add node_successor to the OPEN list
}
Add node_current to the CLOSED list
}


greetz
OranGe

ich hab mich mal wieder seit langem hingesetzt und versucht genau diesen pseudo code in php umzusetzen. ich hoffe auf hilfe von anderen weil ich das wohl wirklich nich gebacken bekomm

$zielx = 44;
$ziely = 50;
$startx = 40;
$starty = 40;

$liste = array();
$liste[start][x] = $startx;
$liste[start][y] = $starty;

while(is_array($liste) && count($liste) > 0)
{
$node_current =
if(


ich hoffe ich habs bis dahin richtig, wobei ich mir auch nichmal sicher bin. kann mir einer (oder mehrere) helfen den code zu vervollständigen?

Hi!
Aus Zeitgründen kann ich dir leider nicht helfen deinen code zu vervollständingen. Aber es fehlen noch einige Bausteine! Meine A* Klasse umfasst 149 Zeilen sprich 1 Hauptmethode und 5 helfer Methoden.

Meine empfehlung ist:
Nicht den Server den wegberechnen lassen! Den Fehler hatte ich auch gemacht! 10 User gleichzeitig und es gibt lag... (Bei einem Highend Server) Lass es den Client tun und mit dem Server nur den Weg hinterher prüfen. Spart _irrsinnige_ cpu leistung!

greets

Bei uns berechnet es auch der Server, aber nur in einem beschränkten Bereich. Man kann also nur "kurze" routen suchen lassen. Jedoch hatten wir deswegen noch keinen Lag.

also ich würds auch gern aufm server berechnen lassen, leider fehlt mir das nötige wissen um den code fertig zu schreiben. oder es ist einfach höhere mathematik , keine ahnung. jedenfalls würde es mein spiel ein ganzes stück weiter bringen, wenn ihr mir helft....

ne seite vorher is ja der code von Orange gepostet worden, den ich nachstellen will. vielleicht kann jemand mehr draus lesen als ich. bei zeile 6 bin ich stecken geblieben.

Anbei ein paar Links, die auf verschiedene Implementationen von A* in C# zeigen. Die Portierung PHP dürfte im Allgemeinen nicht so schwer sein:

http://www.codeproject.com/csharp/graphs_astar.asp
http://www.programmersheaven.com/zone30/cat848/29244.htm <- sehr einfache Umsetzung

Wenn Bedarf besteht, könnte ich meine Umsetzung in C# posten, dazu müsste ich sie zuvor aus einem Projekt lösen.

Ich habe heute mal ein paar Stunden damit verbracht einen A* in PHP zu implementiern und soweit mir möglich zu optimieren. Das Ergebnis reicht zumindest mir und ist jetzt in der Snippet-Ecke zu finden :

http://snippets.galaxy-news.de/php:astar

echt super!

danke RedMax

endlich hab ich was zum anschaun und zum verstehen