Browsergame Karte Dijkstra

Brill16

Brill16

Grünschnabel
Hallo Experten :)

Ich bin zur Zeit an nem Browsergame dran, welches auch eine Karte beinhalten soll.

So weit so gut, nur hab ich jetz bemerkt, dass man ja auch eine exakte Berechnung der Routen zwischen Städten braucht.

In anderen Foren hab ich was von Dijkstra gelesen. Ich selber habe gute PHP und HTML Kenntnisse. Javascript geht auch so, aber ich glaub dieser Algorithmus basiert auf JAVA...das is nich so mein Ding.

Wenn jemand nen Ansatz für mich hat, wie ich daran gehen kann wäre das gut.
Ich habe bis jetz die Karte und jede Stadt hat nen Link. Wenn ich jetz auf eine Stadt klicke sollen die Detailles der Stadt aufgerufen werden. Dann soll man Rohstoffe eingeben und diese werden dann abgeholt. Da kommt der Algorithmus ins Spiel, denn die Fahrt soll eine Zeit bekommen und eine Länge. Z.B. muss man von Berlin nach München über sonstige Städte fahren, also nicht linear durch (Das ist einfach), sondern über Knotenpunkte.

So.....ich verzweifel noch daran:mad:....danke schonma im Vorraus !
 
Zuletzt bearbeitet:
Ein Algorithmus beschreibt nur einen Lösungsweg und ist nie an eine bestimmte Sprache gebunden. Letzteres wäre nur die Implementierung eines Algorithmus.

Wobei genau brauchst du denn Hilfe?


Algorithmus hat übrigens nichts mit Rhythmus zu tun.
 
Ehm...das mit den Knotenpunkten versteh ich nicht ganz q.q

Bisher alle Browsergames die ich kenne, die eine Karte beinhalten, war das so, das diese Karte wie ein Schachbrett aufgeteilt war.

D.h. es wurde einfach gesagt (beispiel) um von einem Feld zum anderen zu gehen braucht man 5 minuten.
EIn weiteres Script hat die anzahl der Felder berechnet, welches zwischen den zwei dörfern ist.

Das müsste (prinzipiell) so funktionieren:
Das Dorf hat X und Y Koordinaten.
Das Script überprüft die X und Y koordinaten beider Dörfer und vergleicht sie.

Ist zum Beispiel die X Coord von Dorf1 größer als von Dorf2 liegt Dorf2 also westlich von dorf 1.
Nun wird (mit eine for schleife beispielsweise) so lange die gespeicherte X-Coord um 1 verringert, bis sie gleich der von Dorf 2 ist! (dabei wird die anzahl der insgesamt abgezogenen Werte in einer Variable gespeichert, unsigned!)
Nun wird der selbe schritt mit Y gemacht
die beiden Variablen, welche die abgezogenen Werte beinhalten, werden addiert und voila, man hat die anzahl der Felder, die zwischen zwei dörfern sind :D

Hoffe du kannst damit was anfangen.
MfG
 
Brill möchte vermutlich noch weitere Faktoren mit einbeziehen. So beispielsweise, dass zwei unterschiedliche, gleich lange Wege unterschiedlich beschaffen sind (etwa hügeliger Feldweg und gepflasterte Straße) und so unterschiedliche Kosten aufwerfen. Oder dass es mehrere Wege gibt und der kürzeste gesucht ist.
 
@Sephcom Deine Berechnung hat einen kleinen Fehler so kann man nie den kürzesten Weg wählen. Man kann keine Diagonalle gehen. Der Spieler würde immer ein Eck gehen zuerst die x Kordinaten entlang dann eine Kurve machen und den restlichen Weg den y Kordinaten entlang

Um weitere Faktoren abzurufen muss jedes Feld ein Status bekommen zB von 1 bis 5

Wobei
1 am wenigsten Zeit und mit wenig Kosten verbunden ist und
5 am längsten Zeit benötigt und mit den meisten Kosten verbunden ist

Der User könnte dann bestimmte Knotenpunkte in der Landkarte wählen da der kürzeste Weg nicht immer der schnellste und der günstigste wäre
 
tz_08 hat gesagt.:
@Sephcom Deine Berechnung hat einen kleinen Fehler so kann man nie den kürzesten Weg wählen. Man kann keine Diagonalle gehen. Der Spieler würde immer ein Eck gehen zuerst die x Kordinaten entlang dann eine Kurve machen und den restlichen Weg den y Kordinaten entlang

Um weitere Faktoren abzurufen muss jedes Feld ein Status bekommen zB von 1 bis 5

Wobei
1 am wenigsten Zeit und mit wenig Kosten verbunden ist und
5 am längsten Zeit benötigt und mit den meisten Kosten verbunden ist

Der User könnte dann bestimmte Knotenpunkte in der Landkarte wählen da der kürzeste Weg nicht immer der schnellste und der günstigste wäre
Zum Vergrößern anklicken....

Hmm tut mir leid, ich hatte seine Frage so verstanden, dass der User eben NICHT diagonal gehen soll, und da bleibt eigentlich nurnoch die möglichkeit, dass er von Feld zu Feld läuft.

Und ob der User jetzt erst entlang der x achse und dann entlang der y achse geht, ist das gleiche, wie wenn er einen schritt an der x achse, einen an der y achse, einen an der x achse, einen an der y achse und so weiter, geht ^^
kommt aufs selbe raus :D (also rein von der anzahl an feldern, die er betritt)

Allerdings wenn man noch in betracht zieht das es unpassierbare felder gibt, ist die möglichkeit die berechnung wie ich sie gemacht habe, natürlich nicht sehr praktisch.
 
jo danke für die zahlreichen Antworten...
aber das hier:


program a-star
// Initialisierung der Open List, die Closed List ist noch leer
// (die Priorität bzw. der f Wert des Startknotens ist unerheblich)
openlist.enqueue(startknoten, 0)
// diese Schleife wird durchlaufen bis entweder
// - die optimale Lösung gefunden wurde oder
// - feststeht, dass keine Lösung existiert
repeat
// Knoten mit dem geringsten f Wert aus der Open List entfernen
currentNode := openlist.removeMin()
// wurde das Ziel gefunden?
if (currentNode == zielknoten) then
return PathFound
// Nachfolgeknoten auf die Open List setzen
expandNode(currentNode)
// der aktuelle Knoten ist nun abschließend untersucht
closedlist.add(currentNode)
until openlist.isEmpty()
// die Open List ist leer, es existiert kein Pfad zum Ziel
return NoPathFound
end

// überprüft alle Nachfolgeknoten und fügt sie der Open List hinzu, wenn entweder
// - der Nachfolgeknoten zum ersten Mal gefunden wird oder
// - ein besserer Weg zu diesem Knoten gefunden wird
function expandNode(currentNode)
foreach successor of currentNode
// wenn der Nachfolgeknoten bereits auf der Closed List ist - tue nichts
if closedlist.contains(successor) then
continue
// f Wert für den neuen Weg berechnen: g Wert des Vorgängers plus die Kosten der
// gerade benutzten Kante plus die geschätzten Kosten von Nachfolger bis Ziel
f := g(currentNode) + c(currentNode, successor) + h(successor)
// 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
// Vorgängerzeiger setzen
successor.predecessor := currentNode
// f Wert des Knotens in der Open List aktualisieren
// bzw. Knoten mit f Wert in die Open List einfügen
if openlist.contains(successor) then
openlist.decreaseKey(successor, f)
else
openlist.enqueue(successor, f)
end
end


...ist doch nicht php oder Javascript...womit nutze ich das denn ? wie binde ich meine Karte ein und wie gebe ich das dann aus ?
Da sind soooooo viele Fragen, die ich dazu hab ? Bei Wiki steht ja kein Anfängertutorial...ich glaub das wär ma was für tutorials.de....könnt sich ja ma jemand mit beschäftigen :) vllt auch um mir zu helfen.
 
Eine Enzyklopädie ist auch für so etwas nicht gedacht.

Aber zurück zum Thema: Was genau erhoffst du denn mit dem Algorithmus zu erreichen beziehungsweise was genau ist dein Problem?
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück