Wie berechne ich Wege

Oft kam im Forum wie man Wegzeit zwischen 2 Punkten ausrechnet
dieses soll erstmal nur erklären wie es aussieht wenn man keine Hinderniss im weg hat:
zumal klären wir ab, das eine koordinate 1m² ist heisst
entfernung von 87:87 zu 87:86 entspricht 1km
nun die berechnung von 50:50 zu 77:99

$xkord = ;//x-koordinate start
$ykord = ;//y-koordinate start
$xkord2 = ;//x-koordinate ziel
$ykord2 = ;//y-koordinate ziel
//hier muss mit pythagoras gearbietet werden! a²+b²=c²
$unterschiedx = ($xkord - $xkord2);
$unterschiedy = ($ykord - $ykord2);
$weg = sqrt(($unterschiedx * $unterschiedx) + ($unterschiedy * $unterschiedy));
}
am ende kommt 28.7576076891 raus
also ist die entfernung 28.75 km
ich hoffe das stimmt^^
ich werde las nächstes erklären wie man das macht wenn die welt rund ist
achja um die zeit zu berechen

$zeit = $weg * $zeitprokilometer;

Geht einfacher:

$wert=hypot ( $zu_y-$von_y, $zu_x-$von_x );

Gruß
Moo

llöööööööööööööl
sei doch nicht so gemein^^

es geht ja nur ums prinzip^^

Deine ganzen if abfragen sind absolut überflüssig.
Der Weg ist einfach s =sqrt( (x1-x2)² + (y1-y2)²) egal ob die nun auf einer linie liegen oder nicht. (pythagoras wie du selbst ja geschrieben hast in deinem kommentar)
Du brauchst dir nur zusätzliche gedanken machen wenn du solch späße bauen willst wie ein Donut das linker mit rechtem kartenrand verbunden ist und oberer mit unterem.

ich weiss schon wie das geht^^
aber muss für pythagoras nicht ein rechter winkel vorhanden sein?
wenn das nicht der fall ist dürfte das eigentlich nicht gehen

pardon hab mein fehler 0²=0^^
muss ja doch nicht sein^^

So und nu misch ich mich doch nochmal ein.
Es gibt eine Bearbeiten-Funktion!! Und damit kannst du - oh Wunder - dein vorherigen Beitrag editieren!
Du brauchst nicht für jeden Satz ein neuen Post erstellen.. Und da ich auch nicht der erste bin der dir das erklären musste hoffe ich, dass du es nun verstanden hast.
Danke!

ist ok

Ja es muss immer ein rechter winkel da sein, der aber auch immer da ist da du ja x-teil und y-teil nimmst.

y
‘
2 |\
| \
| \
1 | \
| \
|_____\ ’ x
0/0 1
Die Streke geht von (1|0) zu (0|2). Also von rechts unten nach links oben, die Diagonale mit Backslashes. Der rechte Winkel wird von der X- und Y-Achse gebildet, er liegt bei (0|0). Somit ist die Strecke von (0|0) zu (1|0) - der X-Achsenabschnitt - a, von (0|0) zu (0|2) - der Y-Achsenabschnitt - b, und die Diagonale c. Man packe das in eine Formel, den Satz des Pythagoras: a² + b² = c² ; 1² + 2² = c² ; 1+4 = 5 ; c = wurzel(5) = 2,24;
et voila, gelöst, ich denke, das hätte hier jeder geschafft, wenn ihm grad langweilig wäre, wie mir
EDIT: Scheiße, meine schöne ASCII-Art
Hoffentlich ist sie erkennbar, wenn ihr sie zitiert

Original von Fornax

y
‘
2 |\
| \
| \
1 | \
| \
|_____\ ’ x
0/0 1

$weg = sqrt(($unterschiedx * $unterschiedx) + ($unterschiedy + $unterschiedy));

müsste richtig

$weg = sqrt(($unterschiedx * $unterschiedx) + ($unterschiedy * $unterschiedy));

Also nur ein Tippfehler

könntest du mal hervorheben was falsch sein soll?

ich hab plus statt mal
also *2
stat hoch 2

Also Pythagoras, 7. Klasse?
BTW: Das kann man mit pow() noch vereinfachen.

Und nun bitte so, dass das Ziel noch nicht feststeht, sondern ein sich bewegendes Objekt mit konstanter Geschwindigkeit und bekannter Route ist.
Wenn schon, denn schon (jaja Undeadable und Drezil haben das schonmal in dem Projektforum gepostet, aber es gibt ja zig Moeglichkeiten der Implementation und in einige Wochen muss ich mir da selbst mal Gedanken zu machen).

wie bekommt man denn jetzt z.b. eine Runde welt hin wenn man 5x5 ozeane hat.. und vom 5 ozuean auch schnellstens in den 1 Ocean kommen will oder vom 5 in den 25 ozean... oder auch 20 ozean, sprich in alle anliegenden ozeanen, wenn es eine runde welt währe...

du berechnest einfach die koordinaten:
zb. ein feld 5x5 alle felder zeilenweise durchnummeriert von links nach rechts:

$id = 0; // feldnummer

$x = $id % 5; // x-koordinate
$y = ceil( $id / 5 ); // y-koordinate
dann einfach mit pyth. weiter verfahren.
mfg
dmx

wo muss ich das nun einbauen, dei Variable hat für mich ein anderer aus unseren Team geschreiben:

function getPos($ozean, $gruppe, $position){

$ozean--; $gruppe--; $position--;
$oz_x = floor($ozean / 5);
$oz_y = $ozean - 5 * $oz_x;

$gr_x = floor($gruppe / 5);
$gr_y = $gruppe - 5 * $gr_x;

$is_x = floor($position / 5);
$is_y = $position - 5 * $is_x;

$pos_y = $oz_y * 5 * 5 + $gr_y * 5 + $is_y;
$pos_x = $oz_x * 5 * 5 + $gr_x * 5 + $is_x;

return array("X" => $pos_x, "Y" => $pos_y);
}
function getDistance($at_x, $at_y, $get_x, $get_y){
if ($at_x > $get_x)
$difx = $at_x - $get_x;
else
$difx = $get_x - $at_x;

if ($at_y > $dsty)
$dify = $at_y - $get_y;
else
$dify = $get_y - $at_y;
$res = sqrt($dify * $dify + $difx * $difx);

return $res;
}
$pos_an = getPos(1, 1, 1);
$pos_von = getPos(5, 5, 5);
$seemeilen = getDistance($pos_an['X'], $pos_an['Y'], $pos_von['X'], $pos_von['Y']);

Wenn du sagst, du möchtest eine "runde Welt" haben, nehme ich einfach mal an, deine 5x5 Ozeane stellen die Oberfläche eines Zylinders dar. D.h. wenn man aus dem linken Rand herausfährt, erscheint man am rechten Rand und umgekehrt.
Betrachet man diesen Zylinder direkt von oben (d.h. man lässt die y-Achse zunächst ausser Acht und beachtet nur die x-Achse) sieht man einen Kreis mit dem Umfang U = 5 x Breite_eines_Ozeans. Auf einem Kreis ist die maximale Entfernung zwischen beliebigen 2 Punkten E_max = U / 2 (unter der Vorraussetzung, dass man sich nur auf dem Kreis bewegen kann, der direkte Weg ist natürlich kürzer). Das kann man sich folgendermaßen vorstellen: Wäre ein Weg W länger als E_max, geht man einfach in die andere Richtung und schon beträgt die Entfernung nur noch E = U - W.
Auf deinen Code bezogen heisst das:

if($difx > 5 * 5 * 5 / 2)

$difx = 5 * 5 * 5 - $difx;
Edit: E = E_max - W war natürlich verkehrt, das muss E = U - W heissen.

Vielen Dank!
Ich währe sonst echt aufgeschmissen gewesen ich danke dir!
Problem dabei ist jetzt wenn ich von 5:5:5 zu 1:1:1 fahren würde, was ja theoretisch neben an leigt, fährt er trozdem durch die wallachhei, sprich für y muss das gleich wie für x gemacht werden richitg?

Original von Dexus
Vielen Dank!
Ich währe sonst echt aufgeschmissen gewesen ich danke dir!
Problem dabei ist jetzt wenn ich von 5:5:5 zu 1:1:1 fahren würde, was ja theoretisch neben an leigt, fährt er trozdem durch die wallachhei, sprich für y muss das gleich wie für x gemacht werden richitg?

probier es doch einfach aus!
nen kleiner tipp, wenn du dir das als die weltkarte vorstellst: man will von alaska nach australien kommen... man muss die ganze karte vertikal durchfahren und eine einheit nach links/rechts.
gruß
dmx

Original von Dexus
Problem dabei ist jetzt wenn ich von 5:5:5 zu 1:1:1 fahren würde, was ja theoretisch neben an leigt, fährt er trozdem durch die wallachhei, sprich für y muss das gleich wie für x gemacht werden richitg?

Nein, dass 5/5 und 1/1 nicht direkt nebeneinander liegen, ist bei meinem Zylinder-Modell durchaus korrekt.
Wenn es dich nicht stört, dass man deine 2-dimensionelle Karte dann nicht mehr ohne weiteres im 3-dimensionalen Raum darstellen kann, dann kannst du das gleiche Prinzip auch auf die y-Achse anwenden. Es ist zwar durchaus möglich, die Karte dann z.B. auf einer Kugel abzubilden - d.h. alle 4 Eckpunkte deiner Karte wären im Prinzip ein einziger Punkt auf der Kugel - allerdings könnte man dann genaugenommen die Entfernung zwischen 2 Punkten nicht mehr so einfach berechnen.
Langer Rede kurzer Sinn: Du kannst es so machen, dann wäre deine Karte aber nicht mehr physikalisch korrekt.

Es sei denn, du nimmst an, dass deine Welt auf der Oberfläche eines Donut liegt.

hmm,
ich mein so schwer ist es nicht eine globuskarte zu erstellen. man muss doch dann einfach nur - wie oben beschrieben - die kanten beachten und dann ein paar sonderfälle für die pole einbauen.
mit ein paar if-abzweigungen ist die sache in nicht mehr als 20 zeilen gemacht. wie viel mühe sollte man sich schon geben und nicht nur kompromise eingehen.
mfg
dmx

Hallo zusammen,
hat jemand von euch sich schon mal Gedanken gemacht über eine Karte mit Hindernissen und verschiedenen Wegekosten, also z.B. auf Straße kommt man 1km / t, auf Wasser dann nur 0,5km / t usw. und davond ann abzuwägen, was am kürzesten ist?
Mfg,
Sammy

Genau das macht der A*, in dem Du jedem Feld eine Wertigkeit gibst, also Straße 1, Wasser 2, Sumpf 4 usw.
Der findet immer den kürzesten Weg.

Ganz so einfach ist es nicht. Du brauchst immer noch eine Funktion, die von dem betrachteten Ort die Kosten bis zum Ziel schätzt und dabei darf diese Funktion die Kosten niemals überschätzen, sonst findet der A* nicht den günstigsten Weg.

Hallo,
die Datenstruktur dafür abzubilden ist nicht das Problem, problematisch ist eher daraus dann den optimalen Weg zu berechnen.
Man könnte natürlich immer Luftlinie der Koordinaten nehmen und dann dazu berechnen wieviel das genau kostet, aber ich möchte ja erreichen, wenn z.B. ein Fluß dazwischen ist, der "Umweg" über die Brücke genommen wird, da dies schneller geht.
Irgendwelche Ansätze muss es zu solchen Szenarien ja geben. Wie machen die Routenplaner sowas, das ist ja auch ähnlich (Autobahn, Landstraße...)
Sammy

A* wurde doch schon genannt, der berechnet den Weg auch um Hindernisse.
de.wikipedia.org/wiki/A%2A-Algorithmus
www.policyalmanac.org/games/aStarTutorial_de.html
Implementierung in PHP: snippets.galaxy-news.de/php:astar
Implementierung in Java: www.peachpit.com/articles/article.asp?p=101142&rl=1
Das Wichtigste bei A* ist, die Schätzung der Wegstrecke. A* tut ständig den verbleibenden Weg schätzen um herauszufinden, welche Richtung die schnellste ist. Wenn deine Schätzfunktion schlecht ist, findet A* keinen guten Weg. Deine Schätzung muss also Felder miteinbeziehen die langsamer oder gar nicht durchlaufbar sind.

Nur soals Hinweis Snippets A* hat aber keine Gewichtung der Kanten / Wege - wenn ich mich nicht täusche.

Wenn die Schätzfunktion zulässig ist (zulässig := keine Überschätzung des Weges) findet A* immer die optimale Lösung. Bei Wegberechnungen ist eine zulässige Schätzfunktion die Luftlinie, da sie die Kosten nie überschätzen kann. Einbeziehung von langsameren Wegen ist nicht nötig. Das Problem ist nur, eine vernünftige Datenstruktur zu basteln, aber das ist ja nicht so schwierig.

Original von Todi42
Ganz so einfach ist es nicht. Du brauchst immer noch eine Funktion, die von dem betrachteten Ort die Kosten bis zum Ziel schätzt und dabei darf diese Funktion die Kosten niemals überschätzen, sonst findet der A* nicht den günstigsten Weg.

Wo ist das Problem? Die Schätzfunktion schätzt immer Luftlinie mit Faktor = 1, damit ist ein Überschätzen unmöglich.

Luftlinie ist aber Phytagoras und damit sind Quadratfunktionen und Wurzeln drin. Das ist bei solch häufiger Anwendung der Heuristik (bei jedem Knoten) möglicherweise nicht optimal. Da gibt es je nach Anwendungsgebiet einen besseren Mittelweg aus Performance und Monotonie der Heuristik:

$schaetzung = abs($startX-$zielX + $startY-$zielY);
Das ist zwar nicht der kürzeste Weg, aber da nur simple Addition drin ist und vor allem keine Wurzelfunktion, diese Heuristik ist damit etwas schneller, wenn auch möglicherweise etwas ungenauer.
Es gibt bestimmt auch noch bessere Möglichkeiten einer schnellen und genauen Heuristik...

wenn ich ganz neben der Kappe bin erzeugt dein code aber Murks, wenn es z.b. von oben nach unten und rechts nach links geht, wenn der Nullpunkt oben links ist.
wenn dann
$schaetzung = abs($startX-$zielX) + abs($startY-$zielY);
Naja, sind die Wurzeln nicht ein paar einfache Lookups in entsprechenden Tabellen? Und auch das Quadrieren sollte jede CPU in einem Takt beherschen.
Ich denke dass da selbst die Interpretation des entsprechenden Bytecodes mehr Laufzeit braucht als das eigentliche Rechnen, vom A*-Algo ganz zu schweigen.

Original von mifritscher
$schaetzung = abs($startX-$zielX) + abs($startY-$zielY);

Für Pfadfindung in normalen 2-dimensionalen Spielkarten ist diese Heuristik schon ausreichend. Ich benutze die bei mir für zwei Pfadfinder (einmal A*, einmal Luftlinie) und es funktioniert. Man kann auch den Pythagoras benutzen, der dann etwas genauer ist. Am besten man tüfftelt das selbst aus, indem man die beiden Schätzungen miteinander vergleicht, vorallem was Geschwindigkeit angeht.
Selbst wenn die Pythagorasversion nur geringfügig langsamer ist, muss man bedenken, dass die Schätzung während der Pfadberechnung unter Umständen ein paar hundert Mal aufgerufen wird (für längeren Pfade). Aus einer Tausendstelsekunde werden dann schnell mehrere Zehntelsekunden.

Alternativ zu A* kann man auch den Dijkstra-Algorithmus verwenden. Der Aufwand, also die Iterationsschritte, zwischen beiden ist gleich und hängt jeweils von den verwendeten Datenstrukturen ab. Alternativ fallen mir zur Lösung solcher Probleme noch Backtracking und genetische Algorithmen ein. Genetische Algorithmen liefern aber nicht umbedingt den besten Weg, sondern eine Lösung die möglichst nah am besten Weg dran ist. Je nachdem wie das Spiel konzipiert ist, könnte das interessante Aspekte für die Spieler liefern.

Original von Itchy

Original von Todi42
Ganz so einfach ist es nicht. Du brauchst immer noch eine Funktion, die von dem betrachteten Ort die Kosten bis zum Ziel schätzt und dabei darf diese Funktion die Kosten niemals überschätzen, sonst findet der A* nicht den günstigsten Weg.

Wo ist das Problem? Die Schätzfunktion schätzt immer Luftlinie mit Faktor = 1, damit ist ein Überschätzen unmöglich.
Da ist kein Problem, es ist nur eine, so finde ich, wichtige Randbedingung, damit der Algorithmus wirklich den kürzesten Weg findet.

Agmemon

Alternativ zu A* kann man auch den Dijkstra-Algorithmus verwenden. Der Aufwand, also die Iterationsschritte, zwischen beiden ist gleich und hängt jeweils von den verwendeten Datenstrukturen ab.
Wenn man den A* implementiert hat, braucht man die Schätzfunktion (oder Heuristik) nur dahingehend zu ändern, dass sie immer 0 zurück liefert (vorrausgesetzt, Kosten sind immer nicht negativ), dann hat man den Dijkstra (oder auch einfach Breitensuche genannt). Wenn die Heuristik beim A* Sinnvoll unterschätzt, braucht sie niemals mehr Schritte als der Dijkstra, wird aber meistens deutlich weniger Schritte brauchen. Beim Dijktra brauch man sich lediglich die geschätzten Kosten nicht merken. Es gibt allerdings auch Fälle, in denen das Schätzen nicht einfach geht, dann ist der Dijkstra natürlich besser geeignet.

Original von Todi42Wenn die Heuristik beim A* Sinnvoll unterschätzt, braucht sie niemals mehr Schritte als der Dijkstra, wird aber meistens deutlich weniger Schritte brauchen.

Das wirst Du besser bewerten können, denn dafür stecke ich zu wenig in der Thematik drin. Als alter Informatiker bin ich jetzt einfach von der O-Notation ausgegangen.

Hat sich jemand schonmal Gedanken gemacht um die Rechnerressourcen die benötigt werden für die Wegfindung? Bei kleinen Karten geht es ja noch, aber um so größer die Karten werden und um so mehr Benutzer eine Berechnung auslösen desto enger wird es mit dem RAM und mit der CPU.
Habt Ihr vielleicht andere Erfahrungen gemacht?

Eine Eigenschaft des A* ist die Tatsache, dass er auch auf sehr sehr große "Gebiete" losgelassen werden kann. Die Karte wirst du sowieso auf die eine oder andere Weise im RAM haben. Vom Startpunkt aus wird er aber nur die Wegpunkte aktiv bearbeiten (und somit in den RAM speichern), die er auch tatsächlich braucht. Bei einer normalen Wegfindung wird also nur ein Bruchteil der Pixel, Wege oder was auch immer angefasst. Sollte also eigentlich kein Problem sein, was die Performance angeht. Wende das selber auf sehr großen Karten an und es gibt keine Probleme.

Original von Dexus
Vielen Dank!
Ich währe sonst echt aufgeschmissen gewesen ich danke dir!
Problem dabei ist jetzt wenn ich von 5:5:5 zu 1:1:1 fahren würde, was ja theoretisch neben an leigt, fährt er trozdem durch die wallachhei, sprich für y muss das gleich wie für x gemacht werden richitg?

Ohne jetzt zu kompliziert werden zu wollen, kann man doch über Galoisfeldern rechnen, im speziellen Falle ein GF[5] ^^
Inwiefern das "einfach" umsetzbar ist, ist erstmal 2tens

Ich weiss nicht, ob das hier schon angesprochen wurde:
Es haengt auch davon ab, ob die Karten dynamisch oder statisch sind.
Bei statischen Karten kann mit Hilfe des Kleene-Warshall bzw. Floyd-Warshall-Algorithmus die kuerzesten Wege vorberechnen und dann aus einer Matrix auslesen.
Man spart damit Rechenzeit zur Laufzeit (verbraucht aber natuerlich Speicher fuer die Matrix).

Original von thecruel
Hat sich jemand schonmal Gedanken gemacht um die Rechnerressourcen die benötigt werden für die Wegfindung? Bei kleinen Karten geht es ja noch, aber um so größer die Karten werden und um so mehr Benutzer eine Berechnung auslösen desto enger wird es mit dem RAM und mit der CPU.
Habt Ihr vielleicht andere Erfahrungen gemacht?

Für den A* wächst der Resourcenbedarf nicht stark mit der Kartengröße. Mit der Anzahl der Benutzer sollte er linear wachsen. Wenn deine Applikation z.B. JavaScript clientseitig verwendet, könntest Du das auch den Client machen lassen, dann muß der Server nur noch prüfen, ob es ein gültiger Weg ist.

Zensiert Reflink by Auris

Hallo zusammen,
ich bin auch grad mit der Wegeberechnung für mein BG beschäftigt, nur hat bei mir jede basis 3 Koordinaten (Kontinent:Quadrant:Basis) desshalb muss ich ja, bevor ich mit dem Pythagoras meinen Weg berechnen kann, nur noch 2 Koordinaten haben und hab mir dafür folgende Funktion ausgedacht:

function getcoords(){

$coords = array();

$sqrbasis = sqrt($max_basis);
$sqrquadrant = sqrt($max_quadrant);
$sqrkontinent = sqrt($max_kontinent);



$basisway = $sqrbasis - ($basis%$sqrbasis);
$quadrantway = $sqrquadrant - ($quadrant%$sqrquadrant);
$kontinentway = $sqrkontinent - ($kontinent%$sqrkontinent);
$coords(0) = ($kontinentway-1)*$max_quadrant*$max_basis+($quadrantway-1)*$max_basis+$basisway;
$basisway2 = ($basis + $basis%$sqrbasis)/$sqrbasis;
$quadrantway2 = ($quadrant + $quadrant%$sqrquadrant)/$sqrquadrant;
$kontinentway2 = ($kontinent + $kontinent%$sqrkontinent)/$sqrkontinent;

$coords(1) = ($kontinentway2-1)*$max_quadrant*$max_basis+($quadrantway2-1)*$max_basis+$basisway2;

return $coords;
}
$max_kontinente gibt an wie viele Kontinente es gibt
$max_quadrant ist die anzahl der Quadranten pro Kontinent
und $max_basis die anzahl der Basen pro Quadrant.
Und jetzt ist meine Frage an euch ob die Funktion so gut ist oder ob ihr ne bessere Lösung habt.
mfg
foxxy
edit:
hab ich ganz vergessen:
$basis ist die Basisnummer im Quadranten
$quadrant ist der quadrant im Kontinent
$kontinent ist der Kontinent in dem sich die Basis befindet

Original von Foxxy
Und jetzt ist meine Frage an euch ob die Funktion so gut ist oder ob ihr ne bessere Lösung habt.

wenn wir wüssten, wie die karte ausschaut ..
ist das eher nen schachbrett in nem schachbrett? oder ne perlenkette in ner perlenkette? oder gemischt? oder etwa eine schlange?
ich wäre folgenden weg gegangen:
1. betimme absolouten x-abstand zwischen a und b
2. bestimme absolouten y-abstand zwischen a und b
3. weg = sqrt(x^2+y^2);
ist imho viel einfacher..

die karte ist ehr wie ein Schachbrett in nem Schachbrett also es gibt eine Bestimmte anzahl von Kontinent, meinetwegen 16, diese 16 Kontinente sind Quadratisch zusammen gefasst, also 4 nebeneinander und 4 untereinander, in jedem Kontinent gibt es 16 Quadranten, die genauso wie die Kontinente angeordnet sind und in jedem Quadrant sind 25 Basen.
Also die Karte sieht dann ungefähr so aus:
Die gesamte Karte
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Jeder Kontinent besteht aus Quadranten
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Und in jdem Quadranten sind die Basen
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
Eine Beispiel Koordinate wäre dann:
Ozean:5
Quadrant:8
Basis 18

Sei Kx die Kantenlänge der Karte in Kontinenten und Qx die Kantenlänge eines Kontinents in Quadraten und Bx die Kantelänge eines Quadrats in Basen, dann sind die Koordinaten der Basis aus Kontienten k, Quadrat q, und Basis b (alle Divisionen sind Integerdivisionen; und bei mir begint die Zählung bei 0, nicht bei 1):
x = (k / Kx) * Qx*Bx + (q / Qx) * Bx + (b / Bx);
y = (k % Kx) * Qx*Bx + (q % Qx) * Bx + (b % Bx);
Einfach mal alle Basen auf ein Stück Karopapier malen, dann kommst Du auch von alleine drauf und findest evtl. auch noch die Fehler in meinem Ansatz ;-)