spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Guck dir mal A* an.

A* baut ja auf Dijkstra auf und erweitert diesen. Das schöne an Dijkstra ist aber, dass die Position vom Ziel nicht unbedingt bekannt sein muss. Stell dir vor du hast an jedem Knoten bestimmte Eigenschaften gespeichert. sagen wir einfach mal jeder Knoten ist ein Haus und hat die Eigenschaften der Farbe. Jetzt könntest du von einem bestimmten Haus aus das nächste gelbe Haus suchen. Das Haus selbst muss vorher nicht bekannt sein. Das kann schon schick sein. A* hat dann natürlich auch seien Vorteile. Allgemein solltest du mal nach Graphenalgorithmen suchen. Es gibt zum Beispiel auch den Algorithmus von Floyd und Warshall. Damit werden alle kürzesten Pfade zwischen allen Knotenpaaren in einem Graphen berechnet. So könnte man zum Beispiel alle Wege vorberechnen und speichern. Wenn man nun wirklich einen Weg benötigt muss man diesen nur noch nachgucken. Da kommt es natürlich auch wieder auf die Umstände an.

Wenn es Dir 'nur' darum geht einen möglichen Weg von A nach B zu 'finden',
hilft Dir vielleicht die erste Seite dieses Threads?!

Ansatz zur Wegfindung

Auch da kommt mein Link vor.

Was du suchst ist der bereits genannte A* Algorithmus: http://en.wikipedia.org/wiki/A-star_algorithm

Zitat von »dot«

Was du suchst ist der bereits genannte A* Algorithmus: http://en.wikipedia.org/wiki/A-star_algorithm

Zweifach genannt.

Nein. Wenn du eine bestimmte Feuerwache suchst dann macht das mehr Sinn mit A* dran zu gehen. Wenn du aber 5 Feuerwachen in der Stadt hättest und du wolltest den Weg zur nächsten Feuerwache berechnen, dann würde sich Dijkstra anbieten. Du brichst in dem Fall ab, sobald irgendeine Feuerwache gefunden wurde. Diese ist dann die nächste Feuerwache. Und wenn deine Knoten auf dem Grafen nicht stark verteilt sind, dann musst du nicht erst zu dem Knoten fahren. Du nimmst den Weg von dir zum nächstgelegenen Knoten einfach mit in deine Pfadliste auf. Am Ende kannst du den Pfad smoothen. Du guckst quasi ob du Knoten im Pfad überspringen kannst und direkt zum nächstlegegenen Knoten Luftlinie fahren kannst. Das machst du solange wie du den Pfad verkürzen kannst. Dadurch entfallen teilweise hässliche Bewegungen im Pfad, wie zum Beispiel gerade beim ersten Knoten und dem dann weiteren Verlauf.