dijkstra-Algorithmus
0 0 0 
niklaskamenisch
dijkstra-Algorithmus
Tach,
sagt mal, wie ist denn das mit diesem Algorithmus hier: http://de.wikipedia.org/wiki/Dijkstra-Algorithmus
In meinem Spiel gibt es keine Knoten, sondern der Spieler bewegt sich frei über das Feld. Das Raster ist also sehr fein. Nach welcher Methode schafft man nun ein Raster/Knotenfeld, welches für den Algo geeignet wäre? Legt man eine Art gröberes Dijkstra-Raster über das feinmaschige Feld?
Danke!
Pit16
-
Tach,
sagt mal, wie ist denn das mit diesem Algorithmus hier: http://de.wikipedia.org/wiki/Dijkstra-Algorithmus
In meinem Spiel gibt es keine Knoten, sondern der Spieler bewegt sich frei über das Feld. Das Raster ist also sehr fein. Nach welcher Methode schafft man nun ein Raster/Knotenfeld, welches für den Algo geeignet wäre? Legt man eine Art gröberes Dijkstra-Raster über das feinmaschige Feld?
Ich nehme an, du möchtest automatische Wegfindung in irgendeiner Form realisieren? Pathfinding ist dein Stichwort. Das ist aber absolut kein einfaches Thema.
-
Hi
Ich nehme an, du möchtest automatische Wegfindung in irgendeiner Form realisieren? Pathfinding ist dein Stichwort. Das ist aber absolut kein einfaches Thema.
genau! Dazu ist ja der Dijkstra-Algorithmus da! Ich habe das schonmal mit gegebenen Knoten durchprobiert, das klappt. Der NPC (Bot) guckt sich alle paar Sekunden die Knoten an und reagiert darauf entsprechend. Das war aber ein altes Game von mir, da konnte man nur von Feld zu Feld laufen (wobei dann ein Feld = ein Knoten sozusagen).
Nun ist das Problem, dass ich keine Felder (grid) habe, sondern eine freie Fläche. Ich müsste also vermutlich ein Grid über die freie FLäche legen. Nur so wirds ja gehen, ich kann ja nicht alle Pixel durchgehen.-
Zum besseren Verständnis:
Entwickelst du ein 2D oder 3D Game?
Benutzt du irgendwelche fertigen Engines oder rollst du deine eigenen?-
hi,
Entwickelst du ein 2D oder 3D Game?
Benutzt du irgendwelche fertigen Engines oder rollst du deine eigenen?2D (raycasting, also pseudo-3D). Ansonsten entwickel ich noch mit jmonkey 3D, da habe ich aber noch keinen Dijstra implementiert :(
-
hi,
Entwickelst du ein 2D oder 3D Game?
Benutzt du irgendwelche fertigen Engines oder rollst du deine eigenen?2D (raycasting, also pseudo-3D).
Yeah, wie Wolfenstein 3d? Klassiker.
Ansonsten entwickel ich noch mit jmonkey 3D, da habe ich aber noch keinen Dijstra implementiert :(
Gerade kurze Nachforschungen angestellt und gesehen jmonkey benutzt jBullet als Phyikengine. Pathfinding ist eine Sache der Physik und nicht des Renderings.
Aber wie gesagt, die Topic ist so komplex, dass du hier keine fertiggebackene Lösung erwarten kannst. Aber die Stichworte Bullet und Pathfinding sollten dir bei deinen Recherchen zumindest eine Hilfestellung sein.Wie sieht denn dein Kartenmaterial aus? Also, wie speicherst du dein Level ab? Das könnte ein anderer, möglicherweise sogar besserer Ansatz für dein Problem sein.
-
Hi,
2D (raycasting, also pseudo-3D).
Yeah, wie Wolfenstein 3d? Klassiker.genau! Mir gefällt irgendwie die Optik und für dein Einstieg ist es auch noch einigermaßen leicht. Gleich von scretch in 3D ist bisschen heftig, finde ich. 2D JumpnRuns habe ich schon paar gemacht. Und halt Spielchen wie worms, tetris und sowas he he.
Ansonsten entwickel ich noch mit jmonkey 3D, da habe ich aber noch keinen Dijstra implementiert :(
Gerade kurze Nachforschungen angestellt und gesehen jmonkey benutzt jBullet als Phyikengine. Pathfinding ist eine Sache der Physik und nicht des Renderings.
Echt der Physik? Krass... ok, na, ja, wie gesagt, dass eine Spiel entwickel ich von Scretch auf in Java. Ohne Framework oder so. Da gibts halt keine Engine (ausser meine eigene).
Aber wie gesagt, die Topic ist so komplex, dass du hier keine fertiggebackene Lösung erwarten kannst. Aber die Stichworte Bullet und Pathfinding sollten dir bei deinen Recherchen zumindest eine Hilfestellung sein.
Danke! Das hilft mir für mein 3D-Game dann. Aber da bin ich noch weit davon entfernt, Feinde zu haben (also im Spiel meine ich).
Wie sieht denn dein Kartenmaterial aus? Also, wie speicherst du dein Level ab? Das könnte ein anderer, möglicherweise sogar besserer Ansatz für dein Problem sein.
die Karten sind einfach mehrdimensionale Arrays. Aber du hast recht, das ist ja schon mein Raster für den Djikstra. Die Rasterpunkte werden später als Wände und sowas gerendert. Genau, so mach ichs. Mal sehn obs klappt. Danke!
-
Wie sieht denn dein Kartenmaterial aus? Also, wie speicherst du dein Level ab? Das könnte ein anderer, möglicherweise sogar besserer Ansatz für dein Problem sein.
die Karten sind einfach mehrdimensionale Arrays. Aber du hast recht, das ist ja schon mein Raster für den Djikstra. Die Rasterpunkte werden später als Wände und sowas gerendert. Genau, so mach ichs. Mal sehn obs klappt. Danke!Hab ich mirs fast gedacht ;) Dann wird es sogar ziemlich einfach und du kannst jeden Tile-basierten Algorithmus verwenden.
-
Hi,
Hab ich mirs fast gedacht ;) Dann wird es sogar ziemlich einfach und du kannst jeden Tile-basierten Algorithmus verwenden.
was gibts denn da noch? Meinst du den A*-Algorithmus?
-
Hi,
Hab ich mirs fast gedacht ;) Dann wird es sogar ziemlich einfach und du kannst jeden Tile-basierten Algorithmus verwenden.
Im Prinzip Vereinfachungen von Dijkstra, die auf orthogonale Tilemaps angewandt werden.
-
-
-
Echt der Physik? Krass...
Physik stimmt eigentlich nicht wirklich. Spielmechanik wäre exakt gewesen.
-
-
-
-
-
-
-
gudn tach!
In meinem Spiel gibt es keine Knoten, sondern der Spieler bewegt sich frei über das Feld.
wie frei? 2d oder 3d oder sonstwas? wie liegen die hindernisse vor?
prost
seth-
Hi!
In meinem Spiel gibt es keine Knoten, sondern der Spieler bewegt sich frei über das Feld.
wie frei? 2d oder 3d oder sonstwas? wie liegen die hindernisse vor?
ich bastel gerade bisschen was mit raycasting zusammen. also 2D prinzipiell. Der Spieler kann sich frei auf einer MAP bewegen. Die Bots ebenfalls. Nur um Dijkstra zu implementieren, brauche ich eben ein übergeordnetes Knotensystem (Netz, Grid, was auch immer). Das sehe ich doch richtig...?
-
Nur um Dijkstra zu implementieren, brauche ich eben ein übergeordnetes Knotensystem (Netz, Grid, was auch immer). Das sehe ich doch richtig...?
Übergeordnet, oder eben in deiner feinen Auflösung.
Was hast du denn genau für eine Situation? Wenn man sich frei bewegen kann wie du schreibst, wo sind dann die Hindernisse?
-
-
-
hi,
ich stand auch schon vor so versuchen.
Dabei bin ich hingegangen und habe mir das 2D-Feld (sollte auch mit 3D gehen, ist dann nur eine koordinate mehr) erst mal vergröbert. Also wenn du das ganze eigentlich in mm rechnest dann z.b. in km gesehen. Dadrüber konnte ich dann schnell die groben wege berechnen. Dafür waren aber Infos notwendig ob die sektoren überhaupt durchgängig waren. Ich hatte dabei nur ja oder nein. Theoretisch kann man das noch auf die richtungen beziehen usw.Erst bei der Bewegung der Figuren innerhalb der Sektoren, wurde berechnet, wie sie am besten da durch kommen. dafür wurde dann das ganze z.b. auf m runtergebrochen und vereinfacht. Damit gings dann runter bis auf die Stufe wie ich die bewegung eben wollte.
Das ganze kann dann aber etwas "unvorteilhaft" werden, da die Logik nicht die nächsten Sektoren beachtet hatte.
Ich stimme daher den anderen zu, bewegungen sind komplex zu berechnen.
Man muss alle ersatzwege beachten und bei 3D-spielen auch noch die höhenunterschiede (die eventuell als "zeit" oder "wegekosten" zu berücksichtigen sind). Das kennt man ja aus der Routerwelt, bei der auch "wegekosten" anfallen und somit bei dijkstra beachtet werden.Der direkteste ist nicht immer der billigste oder kürzeste (siehe Auto-Navis)
Gruß Niklas
--
Man muss nicht alles wissen, man sollte aber wissen, wo das nicht gewusste zu finden ist.-
Hi,
Ich stimme daher den anderen zu, bewegungen sind komplex zu berechnen.
Man muss alle ersatzwege beachten und bei 3D-spielen auch noch die höhenunterschiede (die eventuell als "zeit" oder "wegekosten" zu berücksichtigen sind). Das kennt man ja aus der Routerwelt, bei der auch "wegekosten" anfallen und somit bei dijkstra beachtet werden.Hm, haste Recht. Die Höhenunterschiede gibts ja auch noch... na, ja, erstmal in 2D so hinbekommen, wie ich mir das vorstelle. Auch wenn's nicht 100% perfekt wird. Muss es erstmal nicht. Aber Danke dir! Interessant! mit der Routewelt wusste ich so noch gar nicht!
-
hi,
über diese "Wegekosten" kann man etwas die Nutzung verteilen und etwas die last dirigieren. So kann man z.b. eine Leitung mit 1000 Mbit für 1 anbieten und die Leitung mit 100Mbit für 10. Eventuell ist der Weg über die 100Mbit zwar kürzer (also ein hop weniger) aber über den 1000Mbit günstiger und schneller. Je nach Maschennetz, kommt es natürlich vor, dass die 100Mbits doch der bessere Weg sind. Ich glaube im Wiki-Beitrag ist dafür sogar eine Skizze. (Hin und Rückwege werden nicht gleich behandelt)
Ist ein ganz interessantes Thema. Man sieht dadrüber aber auch, dass man den weg nicht immer auf den ersten blick finden kann (als Mensch) und ein PC dadurch umso länger braucht. Ich denke das "navi"-Prinzip ist hier nicht schlecht. Erst mal grob machen und dann wenn der grobe weg gefunden wurde, das ganze verfeinern um den besten weg zu finden.
3D ist im übrigen dann nicht mehr viel komplexer, da es "nur" ein drittes mal gemacht werden müsste. Was ich auch zu bedenken geben möchte: Du brauchst nicht immer 3D nur weil du z.b. Maps mit höhenunterschieden hast. Solange du nicht noch tunnel hast, ist alles ok. Immerhin laufen die Einheiten immer auf dem Boden.
Was lustiges dazu: Ich bin vor 2-3 Jahren auf der Autobahn gefahren (ca. mit 180) und da sagt mir das Navi plötzlich: Kreisel in 150m! Mein Erstaunen (nachts) kann man sich natürlich vorstellen. Mein Navi hat nicht so ganz verstanden, das der Kreisel unter der Autobahn ist und ich eben auf der autobahn fahre. Wenn du solche fälle also ausschließen kannst, dann reicht dir 2D ja auch vollkommen aus für koordinaten. Die höhe kannst du dir anhand der Map dann errechnen. (So als idee, bevor du dir da unnötig den kopf zerbrichts ...)
Gruß Niklas
--
Man muss nicht alles wissen, man sollte aber wissen, wo das nicht gewusste zu finden ist.
-
-