Kürzeste Strecke zwischen 2 Feldern berechnen

[sharpy35]

Hi Leute, 

ich arbeite grade an einem Spiel, welches aus einer Karte besteht.  Diese Karte besteht aus einem Koordinatensystem, wobei jedes Feld z.B. eine Koordinate hat. 

Als Beispiel 1:1 oder 1:5. Also x:y Werte. 

Jetzt möchte ich den kürzesten Weg von Feld 1 nach Feld 2 berechnen und dabei alle Felder auflisten, die dazwischen liegen. Ist das machbar? Wenn ja hat da jemand einen Ansatzpunkt für mich? 

Ich würde z.B. gerne den Weg von 1:1 nach 2:6. 

Meine Idee war, die Differenz von x berechnen und dann die Differenz von y. 

also sprich 1->2 wäre 1 nach unten. 1->6 wären 5 nach rechts. Dazwischen liegen dann 2:1, 2:2, 2:3, 2:4, 2:5 und dann 2:6.
Ist das der richtige Ansatz? oder gibt es da einen besseren?

Gruß sharpy!

Achja, das Ganze ist auf PHP Basis

Bearbeitet 9. April 2019 von sharpy35

[Whiz-zarD]

Soll also quasi eine Linie zwischen den beiden Punkten gezogen werden?
Können die Felder auch diagonal erreicht werden oder nur horizontal und vertikal?

Wenn sie auch diagonal erreicht werden können, dann schaue dir den Bresenham-Algorithmus an. Dieser wurde eigentlich entwickelt, um eine Linie auf dem Bildschirm zu zeichnen aber den könnte man auch hierfür verwenden.

[sharpy35]

Hey  nein, diese kann nur Horizontal und Vertikal erreicht werden, nicht diagonal. 

Und ja, es wird eine Art Routenplaner, wo ich auf der Karte die Route zwischen den Feldern zeichne

 

Bearbeitet 9. April 2019 von sharpy35

[_n4p_]

Sind die Felder gleichmäßig verteilt, also hat jede Zeile/Spalte die gleiche Anzahl Felder? Gibt es Hindernisse? Irgendwelche Regeln die die Bewegung einschränken?

Falls nein, sollte dein Ansatz problemlos funktionieren. In diesem Fall gibt es keine günstige/schnelle Strecke.

Falls doch hilft dir vermutlich A*

[sharpy35]

@_n4p_
Die Felder sind gleichmäßig verteilt  Es gibt pro Karte insgesamt 10.000 Felder, welche auf 100 x 100 verteilt sind  

Ok Danke euch, für eure Hilfe  

[el_pollo_diablo]

Unter https://qiao.github.io/PathFinding.js/visual/ kann man sich einige der populären Pathfinding-Algorithmen, sowie deren jeweilige Eigenarten und Verhalten direkt anschauen. Danach kann man direkt den Quellcode der Library im Repository (https://github.com/qiao/PathFinding.js) begutachten und/oder sich tiefer in die Thematik einlesen...

Hier liefert zum Beispiel folgender Eintrag weiterführende Informationen: https://gamedev.stackexchange.com/questions/28041/path-finding-algorithms .

Persönlich würde ich als Einstieg zum Buch "Programming Game AI by Example" (Mat Buckland, ISBN-13: 978-1556220784) raten. Es deckt neben Pathfinding-Algorithmen auch sehr viele weitere Aspekte (wie z.B. mathematische Grundlagen, Finite State Machines (FSMs), Steering and goal driven Behaviors und Fuzzy Logic) verständlich und anschaulich erklärt ab.

Wenn man dann wirklich Blut geleckt hat, kann man sich noch sein zweites Buch "AI Techniques for Game Programming" (Mat Buckland, ISBN-13: 978-1931841085) geben. Hier werden dann Themen wie Genetic Algorithms und Neural Networks ebenfalls verständlich erklärt. Nachdem beide Themen relativ harter Tobak sind, dürfte der ein oder andere mit leerem Blick und apathisch wippend zurückbleiben...

Noch eine kleine Anmerkung: Obwohl beide Bücher schon älter sind, enthalten sie dennoch sehr hilfreiche Informationen, so dass sie regelmäßig auf entsprechenden Fachseiten als Lektüre empfohlen werden.

Sollte es dann irgendwann in Richtung 3D gehen, so landet man zwangsläufig bei Mikko Mononen, einem der Hauptentwickler der RecastDetour-Library, welche sehr viele 3D-Engines, Spiele und andere Grafikapplilkationen einsetzen. Auf seinem Blog http://digestingduck.blogspot.com/ gibt es einige anschauliche Videos und Informationen zur Funktionsweise von Recast (Navmesh Generator) und Detour (Pathfinding). In seinem Repository https://github.com/recastnavigation/recastnavigation ist die C++-Variante der Library zu finden. Durch deren Populariät wurde sie inzwischen auch in viele andere Sprachen portiert.

[sharpy35]

Vielen Dank dir @el_pollo_diablo, ich werde mir diese auf jeden Fall mal anschauen! 
Ich finde solchen Themen mega interessant, vor allem, weil man damit in der normalen Webentwicklung nicht auf sowas stößt, was aber komplett andere Ansätze offenlegt wie z.B. auch den Binary Heap. 

Aber genau deswegen finde ich Spieleentwicklung auch ein sehr faszinierendes Thema. 

EDIT: 

PathFinding.js kann sogar genau das, was ich auch können möchte. Vielen Dank dir für diesen geilen Tipp  

Bearbeitet 10. April 2019 von sharpy35