Jump to content

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

Diesen Beitrag teilen


Link zum Beitrag
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.

Diesen Beitrag teilen


Link zum Beitrag
Auf anderen Seiten teilen

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 von sharpy35

Diesen Beitrag teilen


Link zum Beitrag
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*

Diesen Beitrag teilen


Link zum Beitrag
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.

Diesen Beitrag teilen


Link zum Beitrag
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

Diesen Beitrag teilen


Link zum Beitrag
Auf anderen Seiten teilen

Nimm an der Diskussion teil

Du kannst jetzt hier posten und Dich später registrieren. Wenn Du bereits über eine Konto verfügst, melde Dich jetzt an, um mit Deinem Konto zu posten.

Gast
Auf dieses Thema antworten...

×   Du hast formatierten Text eingefügt.   Formatierung jetzt entfernen

  Only 75 emoji are allowed.

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

×   Dein vorheriger Inhalt wurde wiederhergestellt.   Clear editor

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


Fachinformatiker.de, 2019 SE Internet Services

fidelogo_small.png

if_icon-6-mail-envelope-closed_314900.pnSchicken Sie uns eine Nachricht!

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

Fachinformatiker.de App


Get it on Google Play

Kontakt

Hier werben?
Oder senden Sie eine E-Mail an

Social media u. feeds

Jobboard für Fachinformatiker und IT-Fachkräfte

×
×
  • Neu erstellen...

Wichtige Information

Fachinformatiker.de verwendet Cookies. Mehr dazu in unserer Datenschutzerklärung