Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Kantengraph definieren für Dijkstra Wegfindung

  • 1
  • 2

Werbeanzeige

Buschmann82

Frischling

  • »Buschmann82« ist der Autor dieses Themas

Beiträge: 13

  • Private Nachricht senden

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.. :-)

Koschi

Alter Hase

Beiträge: 657

  • Private Nachricht senden

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

Steef

Alter Hase

Beiträge: 492

  • Private Nachricht senden

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

ChrisvA

Frischling

Beiträge: 83

  • Private Nachricht senden

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.

Buschmann82

Frischling

  • »Buschmann82« ist der Autor dieses Themas

Beiträge: 13

  • Private Nachricht senden

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!

ChrisvA

Frischling

Beiträge: 83

  • Private Nachricht senden

6

16.12.2014, 21:20

Zitat von »Buschmann82«

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.

Buschmann82

Frischling

  • »Buschmann82« ist der Autor dieses Themas

Beiträge: 13

  • Private Nachricht senden

7

16.12.2014, 21:37

Zitat von »ChrisvA«

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.

ChrisvA

Frischling

Beiträge: 83

  • Private Nachricht senden

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: 756

Wohnort: Schorndorf

Beruf: Junior Software Engineer

  • Private Nachricht senden

9

16.12.2014, 21:51

Zitat von »Koschi«

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.

Koschi

Alter Hase

Beiträge: 657

  • Private Nachricht senden

10

16.12.2014, 22:08

Zitat von »birdfreeyahoo«

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.


Zitat von »Buschmann82«

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

  • 1
  • 2

Ähnliche Themen