Du bist nicht angemeldet.

Werbeanzeige

1

16.12.2014, 18:52

Kantengraph definieren für Dijkstra Wegfindung

Hallo,

für mein Tile-basiertes Spiel benötige ich eine Wegfindung, damit meine Autos den besten weg durchs Straßennetz finden.
Meinen Recherchen nach ist der Dijkstra-Algorithmus dafür die beste Lösung und ich habe auch schon eine Implementierung gefunden, die recht übersichtlich ausschaut.
Allerdings ist keine Dokumentation vorhanden und muss nun rausfinden, wie die Arrays aufgebaut sein müssen, die als Argumente übergeben werden müssen.

Es geht vor allem um das Array $g, im welchem vermutlich das Straßennetz als Kantengewichtiger Graph gespeichert ist. Kann jemand aus dem Script ablesen wie die Punkte und gewichteten Verbindungen darin gespeichert werden müssen?

Quellcode

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
function dijkstra( array $g, $start, $end = null ){
    $d = array();
    $p = array();
    $q = array( 0 => $start );
    
    foreach( $q as $v )
    {
        $d[$v] = $q[$v];
        if( $v == $end )
            break;
        
        foreach( $g[$v] as $w )
        {
            $vw = $d[$v] + $g[$v][$w];
            
            if( in_array( $w, $d ))
            {
                if( $vw < $d[$w])
                    throw new Exception('Dijkstra: found better path to already-final vertex');
            }
            elseif( $vw < $q[$w] )
            {
                $q[$w] = $vw;
                $p[$w] = $v;
            }
        }
        
        return array( $d, $p );
    }
}

function shortestPath( array $g, $start, $end )
{
    list( $d, $p ) = dijkstra( $g, $start, $end );
    $path = array();
    while( true )
    {
        $path[] = $end;
        if( $end == $start ) break;
        $end = $p[$end];
    }
    
    array_reverse( $path );
    
    return $path; }



vielen Dank schonmal im Voraus.. :-)

2

16.12.2014, 19:47

Hallo

bin mir jetzt nicht 100% sicher aber ich meine der Dijkstra-Algorithmus ist quasi A* ohne Schäztfunktion.

Dann sollte $g wahrscheinlich der Wert für den zurück gelegten Weg beinhalten.

Das Bild auf der Wiki Seite erklärt es vielleicht besser Klick mich

Ansonsten findest du hier im Wiki noch den A* Algorithmuss der beinhaltet dann noch eine Schätzfunktion um den Weg zum ziel noch ein stück schneller zu finden.

Gruß Koschi
Wer aufhört besser werden zu wollen hört auf gut zu sein!

aktuelles Projekt:Rickety Racquet

3

16.12.2014, 20:03

Für wie vielen Autos willst du den kürzesten Pfad finden? Ist die Karte statisch? Hier wäre eventuell Bellman-Ford effektiver.
"Theory is when you know something, but it doesn’t work. Practice is when something works, but you don’t know why. Programmers combine theory and practice: Nothing works and they don’t know why." - Anon

4

16.12.2014, 20:41

Bevor du daran gehst, deine Datenstuktur umzubauen, sodass diese kompatibel mit dem gefundenen Algorithmus ist, würde ich hergehen und der Algorithmus selber so implementieren, dass dieser mit der vorhandenen Datenstruktur arbeiten kann.

5

16.12.2014, 20:49

Also, die Wiki-Artikel zu Dijkstra, sowie zum Kantengraphen habe ich mir schon zu Gemüte geführt und auch prinzipiell verstanden. Wir war nur nicht klar, wie die Knoten und Graphen definiert und ins Array übertragen werden sollen.

Das hat sich inzwischen jedoch erledigt, da ich eine Java-Version gefunden habe, die gleich mit Beispiel war und sich sehr gut nachvollziehen lässt.

Die Map ist übrigens soweit statisch, wobei ich dynamische Änderungen in der Zukunft nicht ausschließen will. Generell werden diese aber eher selten sein.
Die Anzahl der Fahrzeuge wird abhängig sein von der Zahl der Spieler, aber dazu werde ich demnächst mehr in meiner Projektvorstellung erläutern.

Aber kurz, es handelt sich um eine MMO-Wirtschaftssimulation die mit einem Java-Client läuft und sämtliche Daten online in einer mySQL-DB speichert.

Für mich wird der nächste Schritt jetzt sein, ein Programm zu schreiben, das aus dem Straßensystem einer Existierenden Maps die entsprechenden Knoten samt Entfernungen generiert. Das wird mühsam aber interessant. Für Vorschläge möglicher Herangehensweisen wäre ich sehr dankbar!

6

16.12.2014, 21:20

Für mich wird der nächste Schritt jetzt sein, ein Programm zu schreiben, das aus dem Straßensystem einer Existierenden Maps die entsprechenden Knoten samt Entfernungen generiert. Das wird mühsam aber interessant. Für Vorschläge möglicher Herangehensweisen wäre ich sehr dankbar!


Kennst du OpenStreet Maps?

Damit hättest du schon mal eine reale Karte, mit der du arbeiten kannst.

7

16.12.2014, 21:37

Bevor du daran gehst, deine Datenstuktur umzubauen, sodass diese kompatibel mit dem gefundenen Algorithmus ist, würde ich hergehen und der Algorithmus selber so implementieren, dass dieser mit der vorhandenen Datenstruktur arbeiten kann.
Bisher habe ich das Fahrzeug -und Fahrplan-System noch gar nicht implementiert. Die einzige bestehende Datenstruktur die nicht kompatibel ist, ist die Tile-Map, die auf einem kartesischen Koordinatensystem aufbaut, weswegen ich daraus nun Knoten (Städte, Spielergrundstücke, Abbiegungen und Kreuzungen) und gewichtete Kanten (Die Geraden dazwischen) generieren muss.

OpenStreet Maps kenne ich, wohl. Aber meine Weltkarte ist rein fiktiv und basiert auf Kacheln, von daher ist das für mein Projekt nur bedingt relevant.

8

16.12.2014, 21:41

Ach so, hatte mit "Existierenden Maps" gedacht du möchtest das ganze auf echten Karten machen ;)

birdfreeyahoo

Alter Hase

Beiträge: 766

Wohnort: Schorndorf

Beruf: Junior Software Engineer

  • Private Nachricht senden

9

16.12.2014, 21:51

bin mir jetzt nicht 100% sicher aber ich meine der Dijkstra-Algorithmus ist quasi A* ohne Schäztfunktion.


Ist A* nicht bei einem TileGrid und Dijkstras bei einem Graph? Dijkstras berechnet von einem Startpunkt aus einmal und mann kann danach alle Endpunkte holen, bei A* macht man direkt von Start nach Ende.

10

16.12.2014, 22:08

Ist A* nicht bei einem TileGrid und Dijkstras bei einem Graph? Dijkstras berechnet von einem Startpunkt aus einmal und mann kann danach alle Endpunkte holen, bei A* macht man direkt von Start nach Ende.


A* sucht dir den optimalsten Weg, du hast am Ende den Weg von Start zum Ziel der die wenigsten "Kosten" Verursacht. Du bist dabei aber nicht auf ein TileGrid angewiesen.

Habe es noch mal nachgelsen A* ist aus dem Dijkstras Algorithmus hervor gegangen.

Zitat

In 1968 Nils Nilsson suggested a heuristic approach for Shakey the Robot to navigate through a room containing obstacles. This path-finding algorithm, called A1, was a faster version of the then best known formal approach, Dijkstra's algorithm, for finding shortest paths in graphs. Bertram Raphael suggested some significant improvements upon this algorithm, calling the revised version A2. Then Peter E. Hart introduced an argument that established A2, with only minor changes, to be the best possible algorithm for finding shortest paths. Hart, Nilsson and Raphael then jointly developed a proof that the revised A2 algorithm was optimal for finding shortest paths under certain well-defined conditions.


Für mich wird der nächste Schritt jetzt sein, ein Programm zu schreiben, das aus dem Straßensystem einer Existierenden Maps die entsprechenden Knoten samt Entfernungen generiert. Das wird mühsam aber interessant. Für Vorschläge möglicher Herangehensweisen wäre ich sehr dankbar!


Am einfachsten wäre wohl für jede Straßenverbinfung von einem Straßentile zum nachbar Straßentile die Wertigkeit 1 zu vergeben.
Sollten mehrer Straßentypen existieren sollte die optimalere eine kleine Gewichtung haben wie die suboptimaleren.

Bsp.: Autobahn 1/130 Landstraße 1/100 Feldweg 1/50 jweils mit der Länge multipliziert (die bei einer TileMap ja immer gleich sein sollt) könnte eine Gewichtung sein um den schnellsten Weg zu ermitteln.

Möchtest du wirklich nur den kürzesten haben sollten die Kanten einfach nur den Wert 1 haben um so den kürzesten Weg zu bekommen.

Gruß koschi
Wer aufhört besser werden zu wollen hört auf gut zu sein!

aktuelles Projekt:Rickety Racquet

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Koschi« (16.12.2014, 22:16)


Werbeanzeige