Zum Inhalt springen

Kürzeste Strecke zwischen 2 Feldern berechnen


Empfohlene Beiträge

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 von sharpy35
Link zu diesem Kommentar
Auf anderen Seiten teilen

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.

Link zu diesem Kommentar
Auf anderen Seiten teilen

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*

Link zu diesem Kommentar
Auf anderen Seiten teilen

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.

Link zu diesem Kommentar
Auf anderen Seiten teilen

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 von sharpy35
Link zu diesem Kommentar
Auf anderen Seiten teilen

Dein Kommentar

Du kannst jetzt schreiben und Dich später registrieren. Wenn Du ein Konto hast, melde Dich jetzt an, um unter Deinem Benutzernamen zu schreiben.

Gast
Auf dieses Thema antworten...

×   Du hast formatierten Text eingefügt.   Formatierung wiederherstellen

  Nur 75 Emojis sind erlaubt.

×   Dein Link wurde automatisch eingebettet.   Einbetten rückgängig machen und als Link darstellen

×   Dein vorheriger Inhalt wurde wiederhergestellt.   Editor leeren

×   Du kannst Bilder nicht direkt einfügen. Lade Bilder hoch oder lade sie von einer URL.

Fachinformatiker.de, 2024 by SE Internet Services

fidelogo_small.png

Schicke uns eine Nachricht!

Fachinformatiker.de ist die größte IT-Community
rund um Ausbildung, Job, Weiterbildung für IT-Fachkräfte.

Fachinformatiker.de App

Download on the App Store
Get it on Google Play

Kontakt

Hier werben?
Oder sende eine E-Mail an

Social media u. feeds

Jobboard für Fachinformatiker und IT-Fachkräfte

×
×
  • Neu erstellen...