Browsergame Karte Dijkstra

ich versuche einfach nur viele Städte auf einer Deutschlandkarte einzutragen. Dann soll Dijkstra die Kürzeste Route von z.B. Hamburg nach München berechnen und anzeigen...
Das soll über andere Städte laufen, wie in der Realität. Will ein Straßensystem aufbauen und immer wenn ich 2 Orte vorgebe, soll er die Route berechnen.
 
....könnt sich ja ma jemand mit beschäftigen :) vllt auch um mir zu helfen.

Du könntest dich ja auch damit beschäftigen um anderen zu helfen ;)

Ich will dir ja nicht den Mut nehmen, aber sicher das du sowas einbauen willst, wenn du nicht mal per Google ein paar Treffer findest oder aus anderen Sprachen adaptieren kannst?

Zudem sollte so ein Alorithmus nicht einfach Copy&Paste genutzt werden. Wenn du dir mal 1-2 Tutorialseiten angesehen hast oder auch nur im Wiki Eintrag unter "Nachteile" geschaut hast, wirst du lesen, das der Algo zu hohem Speicherverbrauch neigt. Gerade bei einem Browsergame mit vermutlich mehr als 10 Spielern gleichzeitig könntes knapp werden. Natürlich kann man das eindämmen, wenn man weiss wie der Algo funktioniert.

Ich habe gestern, wo ich geantwortet habe nach einem passendem Tutorial gesucht, aber mir sind dermaßen viele entgegen gesprungen, sodass ich nur den Wiki Eintrag als Einstieg gepostet habe. Irgendein Franzose hat als Studiumsprojekt den Algo in PHP mit direktem Google Maps Mashup gebaut, glaub der Link war in der englischen Wikipedia zu AStar. Ansonsten habe ich auch Javascript, Flash, C#, C++, Java, VB...... Umsetzungen gefunden. Einfach nur 1-2 Stunden googlen und du hast soviel Einstiegsmaterial, das du nicht weisst womit du anfangen sollst.

Wenn dir die dynamische Routenberechnung zu komplex wird, dann musst du auf statisches Routing zurückgreifen, sprich von jedem Punkt zu jedem die Route festlegen.

Schönen Abend und nicht den Mut verlieren!
 
Wie mein Vorposter schon geschrieben hat...
Wirste wohl die Routen für jede mögliche Strecke festlegen...

Es sei denn irgendjemand hat ne Idee, wie man Städte in der direkten Nähe der liniearen Route ermitteln kann, um den Weg dann über diese zu leiten...

Ich denke was man deutlich hervorheben muss ist, ob du eine EIGENE Karte mit SELBST festgelegten Koordinaten verwendest oder halt ne GeoDB o.ä...
 
ja... :confused:

Mut nicht verlieren klingt gut...ich danke euch für die Anteilnahme...

Dann werd ich jetz mal "1-2 Stunden googeln" und sehen was dabei rumkommt. Obwohl ich das schon seid 3 Wochen mache...aber die Idee mit der GeoDB is sicher nützlich....danke
 
Ich weiß noch nciht ob ich dich richtig verstanden habe, aber wenn du es so machen willst wie ich glaube dann solltest du so vorgehen.

Du schreibst in eine Tabelle alle möglichen Orte auf und schreibts in eine Spalte die schnellsten verbindungen auf. D.h. eine Spalte
"Stadtverbindung" mit einer Id als Inhalt.
Die Id ist die Id der am nähesten liegenden Stadt.
Wenn du alles vernetzt hast kannst Du über eine Rekursive-Funktion den Weg zu deinem Bestimmungsort finden. Zwischenpunkte kannst Du dann natürlich auch angeben.
Zusätzlich kannst Du dann noch eine Spalte Wegaufwand berechnen um dann am Ende zu schauen welcher der Wege am besten ist.
 
Gerade diese Vorgehensweise ergibt eben nicht immer den günstigsten Weg. Ein Beispiel:
Code:
    3       2     2
  +---- B ---- C ---- D
 /                   / 1
A --------- E ----- F
      4         2
Von A nach F gibt es zwei Wege. Der Weg [A, B, C, D, F] hat die Kosten 8, der Weg [A, E, F] die Kosten 6. Doch dein Algorithmus würde den ersten, kostenintensiveren Weg wählen, da die Kosten von [A, B] geringer sind als die von [A, E].
 
Oha das stimmt wohl, das hatte ich nicht bedacht.
Allerdings, nur nicht schön, kann ich natürich erst mit erschöpfendem Suchen alle Wege durchgehen und dann den kostengünstigsten Weg benutzen... Jetzt weiß ich nur nicht ob das schon gesagt worden ist.
 
Ja entweder so wie Gumbo bereits schrieb oder du liest dir artikel über Algorythmen und Datenstrukturen durch. Hier gibt es mehrere Probleme zu lösen. Du hast die Möglichkeit die Diskussion aufzunehmen und zu verarbeiten oder dir einen anderen einfachen Weg wie zum Beipiel den mit den Quadranten zu suchen.
 
Zurück