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!
Werbeanzeige
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; } |
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!
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.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.
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.
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!
Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Koschi« (16.12.2014, 22:16)
Werbeanzeige