Pathfinding für bewegliche Ziele

Übersicht

BlitzBasic

Allgemein

	Hubsi Betreff: Pathfinding für bewegliche Ziele	So, Okt 09, 2011 9:25 Antworten mit Zitat
Schönen guten Morgen zusammen. Ich stecke derzeit in einem Projekt fest in welchem sich Bots (bis zu 20 davon) auf einer Tilemap untereinander finden müssen. Das Problem dabei ist jetzt das jeder Bot ständig in Bewegung ist oder von einer auf die andere Sekunde kaputt sein kann, was es dem A* unmöglich macht schnell genug zu sein. Meine Frage jetzt, gibt es eine Möglichkeit (bzw. einen Algo oder irgendwas) das zu handlen?
Den ganzen Doag im Bett umanandflagga und iaz daherkema und meine Hendl`n fressn...

Hubsi

Betreff: Pathfinding für bewegliche Ziele

So, Okt 09, 2011 9:25
Antworten mit Zitat

Schönen guten Morgen zusammen.

Ich stecke derzeit in einem Projekt fest in welchem sich Bots (bis zu 20 davon) auf einer Tilemap untereinander finden müssen. Das Problem dabei ist jetzt das jeder Bot ständig in Bewegung ist oder von einer auf die andere Sekunde kaputt sein kann, was es dem A* unmöglich macht schnell genug zu sein. Meine Frage jetzt, gibt es eine Möglichkeit (bzw. einen Algo oder irgendwas) das zu handlen?

Den ganzen Doag im Bett umanandflagga und iaz daherkema und meine Hendl`n fressn...

	PhillipK	So, Okt 09, 2011 10:33 Antworten mit Zitat
Ich beschäftige mich grade witziger auch ziemlich intensiv mit der Wegfindung. Für mich habe ich 2 möglichkeiten herauskristalisiert: Ein A* algorythmus und ein grundlegendes Knotensystem, das sich durch die map zieht. Nun gibts noch eine sache der Rahmenbedingungen: Wissen deine Bots immer, wo wer ist und suchen sich direkt ein Ziel und versuchen, dorthin zu gelangen? Oder durchstreifen sie die Map und suchen sich gegner "on Sight" ? Wenn du von einer Tilemap erzählst, wo sich bots finden sollen (und wohl auch ausschalten, da sie von einer Sekunde auf die andere zerstört werden können?) klingt es nach nem Shooter oder ähnlichen. Da ist es weniger wahrscheinlich, das du dynamische maps hast. Sollte ich mit dieser Vermutung richtig liegen, reicht doch ein Knotensystem was verschiedene ecken der map miteinander verbindet. Da reichts, wenn ein Knoten mit max. 4 anderen verbunden ist - oben,unten,links, rechts. Diese musst du nun als grundlegende Wegfindung nutzen, dh du lässt deine Bots einem Pfad dieser Knoten folgen und versuchst rückschritte zu vermeiden. Sollten sie in einer Sackgasse landen, drehen sie um und suchen weiter. Wenn sie nun einem anderen begegenen, kannst du A* anschalten, da eine Sichtverbindung herscht. In diesem fall muss der A* algo nur gefühlte 20 knoten überprüfen, das is nix. Ansonsten gibt es noch eine andere möglichkeit (an der ich Grade zu knappen hab) Wenn deine map etwas wie ein C aufgebaut ist und dein punkt von innen nach aussen irgendwas sucht, werden enorm Viele eckpunkte durchforstet. (Das kannst du HIER mal als Java Applet nachspielen!) Diverse möglichkeiten, die ich gelesen habe, sind zb Dead Ends, dh stellen ohne durchgang etc zu makieren. Hierfür brauchst du einen etwas mehr RAM. sollte deine CPU nun in so einem 'Dead end' sein, musst du erst einen weg herraus finden. Danach wirds wahrscheinlich einfacher, unter meidung des eben verlassenen Dead Ends, das Ziel zu finden. Auch solltest du von vornherein "Islands" ausfindig machen, so hat mein Tutorial Vorbild bereiche benannt, die ringsherum eine wand, wasser, etc haben. PS: Ich habe meinen A* Algo auf mehrere Frames aufgeteilt. Das braucht genausolange wie vorher, komplexe Wegfindungen mal gut 5 sekunden, aber im Spiel ist nur bei großen Zahlen von Test-bewegungs-Rects ein FPS dropt zu erkennen. Dh wenn wirklich dauerhaft ein a* algo läuft.

PhillipK

So, Okt 09, 2011 10:33
Antworten mit Zitat

Ich beschäftige mich grade witziger auch ziemlich intensiv mit der Wegfindung.
Für mich habe ich 2 möglichkeiten herauskristalisiert: Ein A* algorythmus und ein grundlegendes Knotensystem, das sich durch die map zieht.

Nun gibts noch eine sache der Rahmenbedingungen:
Wissen deine Bots immer, wo wer ist und suchen sich direkt ein Ziel und versuchen, dorthin zu gelangen?
Oder durchstreifen sie die Map und suchen sich gegner "on Sight" ?

Wenn du von einer Tilemap erzählst, wo sich bots finden sollen (und wohl auch ausschalten, da sie von einer Sekunde auf die andere zerstört werden können?) klingt es nach nem Shooter oder ähnlichen. Da ist es weniger wahrscheinlich, das du dynamische maps hast.

Sollte ich mit dieser Vermutung richtig liegen, reicht doch ein Knotensystem was verschiedene ecken der map miteinander verbindet. Da reichts, wenn ein Knoten mit max. 4 anderen verbunden ist - oben,unten,links, rechts.
Diese musst du nun als grundlegende Wegfindung nutzen, dh du lässt deine Bots einem Pfad dieser Knoten folgen und versuchst rückschritte zu vermeiden. Sollten sie in einer Sackgasse landen, drehen sie um und suchen weiter.
Wenn sie nun einem anderen begegenen, kannst du A* anschalten, da eine Sichtverbindung herscht. In diesem fall muss der A* algo nur gefühlte 20 knoten überprüfen, das is nix.

Ansonsten gibt es noch eine andere möglichkeit (an der ich Grade zu knappen hab)

Wenn deine map etwas wie ein C aufgebaut ist und dein punkt von innen nach aussen irgendwas sucht, werden enorm Viele eckpunkte durchforstet.
(Das kannst du HIER mal als Java Applet nachspielen!)
Diverse möglichkeiten, die ich gelesen habe, sind zb Dead Ends, dh stellen ohne durchgang etc zu makieren. Hierfür brauchst du einen etwas mehr RAM.
sollte deine CPU nun in so einem 'Dead end' sein, musst du erst einen weg herraus finden. Danach wirds wahrscheinlich einfacher, unter meidung des eben verlassenen Dead Ends, das Ziel zu finden.
Auch solltest du von vornherein "Islands" ausfindig machen, so hat mein Tutorial Vorbild bereiche benannt, die ringsherum eine wand, wasser, etc haben.

PS: Ich habe meinen A* Algo auf mehrere Frames aufgeteilt. Das braucht genausolange wie vorher, komplexe Wegfindungen mal gut 5 sekunden, aber im Spiel ist nur bei großen Zahlen von Test-bewegungs-Rects ein FPS dropt zu erkennen. Dh wenn wirklich dauerhaft ein a* algo läuft.

	M0rgenstern	So, Okt 09, 2011 10:34 Antworten mit Zitat
Ehrlich gesagt sehe ich dein Problem mit A* nicht, außer du hast wirklich riesige, verzweigte Labyrinthe als Map. Ansonsten ist der schnell genug. Du könntest alternativ auch folgendes einbauen: Der Zielknoten ist nicht die Position des anderen Bots sondern eine größere (begehbare) Fläche um den Bot herum. Wenn der Bot sich dann bewegt, so wird er trotzdem noch sehr wahrscheinlich innerhalb dieser Fläche sein. Der Bot der nach dem Weg sucht, ist also dann schon viel näher dran und die Suche ist dann schnell genug. Ansonsten schau dir mal Dijkstra an, vielleicht gefällt der dir besser. Da könntest du jede Abzweigung in der Tilemap als Knoten angeben und musst nicht jedes Tile benutzen. http://de.wikipedia.org/wiki/Dijkstra-Algorithmus Lg, M0rgenstern

M0rgenstern

So, Okt 09, 2011 10:34
Antworten mit Zitat

Ehrlich gesagt sehe ich dein Problem mit A* nicht, außer du hast wirklich riesige, verzweigte Labyrinthe als Map.
Ansonsten ist der schnell genug.
Du könntest alternativ auch folgendes einbauen:
Der Zielknoten ist nicht die Position des anderen Bots sondern eine größere (begehbare) Fläche um den Bot herum. Wenn der Bot sich dann bewegt, so wird er trotzdem noch sehr wahrscheinlich innerhalb dieser Fläche sein. Der Bot der nach dem Weg sucht, ist also dann schon viel näher dran und die Suche ist dann schnell genug.

Ansonsten schau dir mal Dijkstra an, vielleicht gefällt der dir besser.
Da könntest du jede Abzweigung in der Tilemap als Knoten angeben und musst nicht jedes Tile benutzen.
http://de.wikipedia.org/wiki/Dijkstra-Algorithmus

Lg, M0rgenstern

	PhillipK	So, Okt 09, 2011 10:50 Antworten mit Zitat
Er kann auch für A* die abzweigungen als Knoten angeben Hier muss dann nur statt der Schrittkosten (zb 10 und 14) die distanz angegeben werden. In dem Applet was ich gepostet habe, sieht Dijjkstra nicht wirklich gut aus. Es scheint kreisförmig die Tiles zu durchsuchen, das ist garnicht toll Ausser wenn wirklich klar ist, das man in einem solchen "Dead End" ist. Allerdings fungiert der A* aus dem Applet auch wesentlich langsamer wie meine version, das liegt wohl an der Heuristik. BlitzMax: [AUSKLAPPEN] [EINKLAPPEN] Local h:Int = 14 * Max(Abs(x - zielX), Abs(y - zielY)) Das verwende ich zur berechnung der Entfernung zum Ziel. Fazit: Extrem zielgerichtet, bis ein hinderniss auftritt. Dann wirds lahm, bis entsprechdene Kanten gefunden wurden, wo man "entlangschlüpfen" kann. PS: Grade, wenns ein labyrinth ist, ist A* ziemlich schnell. Anders sieht es bei großen Flächen aus, wo nur ein kleiner punkt (weit entfernt vom ziel, hinter dem Startpunkt!) zum ziel führt. Dann werden enorm viele Sinnlose felder durchforstet, da diese vermeidlich schneller scheinen. In einem Labyrinth schießt der A* algo da durch als gäbs kein Morgen mehr Ich wollte auchnoch eine 2te idee testen. Sobald der A* algo eine Wand erkennt (beim direkt zum-ziel-schießen), solll er der Wand folgen. Das wäre dann eine mischung aus Greedy und A* - so könnte man relativ schnell Eckpunkte erkennen. Ich bin gespannt, was Hubsi für Rahmenbedingungen für seinen algo hat, denn hier kann ich sicher auch noch ein - zwei sachen für mein Problem übernehmen g

PhillipK

So, Okt 09, 2011 10:50
Antworten mit Zitat

Er kann auch für A* die abzweigungen als Knoten angeben Wink

Hier muss dann nur statt der Schrittkosten (zb 10 und 14) die distanz angegeben werden.

In dem Applet was ich gepostet habe, sieht Dijjkstra nicht wirklich gut aus. Es scheint kreisförmig die Tiles zu durchsuchen, das ist garnicht toll Smile

Ausser wenn wirklich klar ist, das man in einem solchen "Dead End" ist.

Allerdings fungiert der A* aus dem Applet auch wesentlich langsamer wie meine version, das liegt wohl an der Heuristik.
BlitzMax: [AUSKLAPPEN]

Local h:Int = 14 * Max(Abs(x - zielX), Abs(y - zielY))

Das verwende ich zur berechnung der Entfernung zum Ziel. Fazit: Extrem zielgerichtet, bis ein hinderniss auftritt. Dann wirds lahm, bis entsprechdene Kanten gefunden wurden, wo man "entlangschlüpfen" kann.

PS: Grade, wenns ein labyrinth ist, ist A* ziemlich schnell. Anders sieht es bei großen Flächen aus, wo nur ein kleiner punkt (weit entfernt vom ziel, hinter dem Startpunkt!) zum ziel führt. Dann werden enorm viele Sinnlose felder durchforstet, da diese vermeidlich schneller scheinen. In einem Labyrinth schießt der A* algo da durch als gäbs kein Morgen mehr Smile

Ich wollte auchnoch eine 2te idee testen. Sobald der A* algo eine Wand erkennt (beim direkt zum-ziel-schießen), solll er der Wand folgen. Das wäre dann eine mischung aus Greedy und A* - so könnte man relativ schnell Eckpunkte erkennen.
Ich bin gespannt, was Hubsi für Rahmenbedingungen für seinen algo hat, denn hier kann ich sicher auch noch ein - zwei sachen für mein Problem übernehmen *g*

	Midimaster	So, Okt 09, 2011 11:02 Antworten mit Zitat
aber so isses doch auch im wirklichen Leben. Der Algo verrät dir den nächsten Schritt, den gehts du. Beim nächsten mal kann schon alles anders sein, aber der Algo verrät dir wieder den nächsten Schritt. Dadurch kommen sich die Bots langfristig schon näher. Man muss halt tatsächlich jede Runde neue nachsehen. Oder, wenn das zu zeitraubend ist, dann schaut man nur gelegentlich nach und läuft z.b. 10 Schritte in die festgestellte Richtung um dann nach 10 Schritten zu merken, das eine ganz andere Richtung bereits besser gewesen wäre. Aber gerade das wirkt für Bots sehr "menschlich". Es sieht so aus, als ob sie einen Plan haben und den ab und zu verwerfen. Auch hier werden sie sich letztendlich finden!
Gewinner des BCC #53 mit "Gitarrist vs Fussballer" http://www.midimaster.de/downl...ssball.exe

Midimaster

So, Okt 09, 2011 11:02
Antworten mit Zitat

aber so isses doch auch im wirklichen Leben. Der Algo verrät dir den nächsten Schritt, den gehts du. Beim nächsten mal kann schon alles anders sein, aber der Algo verrät dir wieder den nächsten Schritt. Dadurch kommen sich die Bots langfristig schon näher. Man muss halt tatsächlich jede Runde neue nachsehen. Oder, wenn das zu zeitraubend ist, dann schaut man nur gelegentlich nach und läuft z.b. 10 Schritte in die festgestellte Richtung um dann nach 10 Schritten zu merken, das eine ganz andere Richtung bereits besser gewesen wäre. Aber gerade das wirkt für Bots sehr "menschlich". Es sieht so aus, als ob sie einen Plan haben und den ab und zu verwerfen. Auch hier werden sie sich letztendlich finden!

Gewinner des BCC #53 mit "Gitarrist vs Fussballer" http://www.midimaster.de/downl...ssball.exe

	PhillipK	So, Okt 09, 2011 11:19 Antworten mit Zitat
Das geht bei Wegfindungen leider meist nicht so einfach. Würde man immerzu zb 10 knoten prüfen und den vermeidlich besten weg Nehmen, bleibt man über kurz oder lang vor einer wand kleben. Wenn man allerdings so nah dran ist, das man sich diese 10-schritte-taktik erlauben kann, wird A* auch innerhalb von 0,0004 sekunden den weg finden Also nichtmal eine MS. Dazu gibts immernoch einen gebissen puffer, da die Bots ja nicht direkt aufeinander Kleben müssne, um ihre aktionen auszuführen. Sinds vampire, müssen sie halt n feld davor anfangen zu saugen. Sinds soldaten, dann können sie schon ab 10 felder distanz mit dem Schießen anfangen. Bei Rittern sind es 1-2 felder, bis sie anfangen können, mit dem Schwert zu prügeln^^ In meinen augen ist das Wichtigste problem: Schnell einen weg in die Richtige richtung finden. Sobald man sich nahe genug ist, kann auch jede andere Wegfinde idee her, die großen distanzen sind das wichtigste. ausser hubsi hat ein paar andere Rahmenbedingungen =)

PhillipK

So, Okt 09, 2011 11:19
Antworten mit Zitat

Das geht bei Wegfindungen leider meist nicht so einfach.
Würde man immerzu zb 10 knoten prüfen und den vermeidlich besten weg Nehmen, bleibt man über kurz oder lang vor einer wand kleben.
Wenn man allerdings so nah dran ist, das man sich diese 10-schritte-taktik erlauben kann, wird A* auch innerhalb von 0,0004 sekunden den weg finden Smile

Also nichtmal eine MS.
Dazu gibts immernoch einen gebissen puffer, da die Bots ja nicht direkt aufeinander Kleben müssne, um ihre aktionen auszuführen. Sinds vampire, müssen sie halt n feld davor anfangen zu saugen. Sinds soldaten, dann können sie schon ab 10 felder distanz mit dem Schießen anfangen.
Bei Rittern sind es 1-2 felder, bis sie anfangen können, mit dem Schwert zu prügeln^^

In meinen augen ist das Wichtigste problem: Schnell einen weg in die Richtige richtung finden. Sobald man sich nahe genug ist, kann auch jede andere Wegfinde idee her, die großen distanzen sind das wichtigste.
ausser hubsi hat ein paar andere Rahmenbedingungen =)

	Midimaster	So, Okt 09, 2011 12:15 Antworten mit Zitat
@PhillipK ich meinte mit den 10 Schritten aber nicht nur 10 Knoten! Nein, der Weg soll komplett gefunden werden vom einen Bot zum anderen. Jetzt speicher man die ersten 10 richtigen Schritte genau dieses Weges und geht sie in den nächsten 10 Runden. Erst dann wird wieder ein Algo gestartet, der wiederum den Weg komplett richtig ermittelt, wovon man aber wieder nur die ersten 10 Schritte umsetzen wird. u.s.w. Probiers aus! Das sieht beängstigend realistisch beim Bot aus, auch wenn man sich bewegt.
Gewinner des BCC #53 mit "Gitarrist vs Fussballer" http://www.midimaster.de/downl...ssball.exe

Midimaster

So, Okt 09, 2011 12:15
Antworten mit Zitat

@PhillipK

ich meinte mit den 10 Schritten aber nicht nur 10 Knoten! Nein, der Weg soll komplett gefunden werden vom einen Bot zum anderen. Jetzt speicher man die ersten 10 richtigen Schritte genau dieses Weges und geht sie in den nächsten 10 Runden. Erst dann wird wieder ein Algo gestartet, der wiederum den Weg komplett richtig ermittelt, wovon man aber wieder nur die ersten 10 Schritte umsetzen wird. u.s.w.

Probiers aus! Das sieht beängstigend realistisch beim Bot aus, auch wenn man sich bewegt.

Gewinner des BCC #53 mit "Gitarrist vs Fussballer" http://www.midimaster.de/downl...ssball.exe

	PhillipK	So, Okt 09, 2011 12:48 Antworten mit Zitat
Okay, das klingt wirklich nach einem plan. Allerdings: Uff. Ich habe in meiner Testszene grade ein 75x75 raster, wo ich wände einzeichnen kann und platziere ~ 20 einheiten. Diese suchen sich jedesmal, wenn sie ihr ziel erreicht haben ,einen neuen weg. Gibt es keinen, suchen sie wieder einen. Wenn 5 gleichzeitig suchen, dauert es schon ewigkeiten. Genau hierfür muss etwas übergeordnetes her, was stark vereinfachte pfade enthält. Ich spiele grade mit dem gedanken, ein kleineres raster über meine map zu legen, alle 4 oder 5 felder - welche einen zeiger auf die punkte oben, unten, links und rechts halten. Dadurch ist es nurnoch ein bruchteil der Map zu überprüfen und das ganze ist eventuell halbwegs Echtzeit tauglich Ich könnte das ganze im Jetzigen Algo einmal umschreiben und 2 gruppen erstellen - eine rennt simpel ihre wege, die andere versucht, die Wege-renner zu verfolgen. Das dürfte aber dafür sorgen, das mindestens die hälfte etwa 20sekunden steht, bevor ihr weg "fertig" ist Da sehe ich leider, performancetechnisch, alle 10 schritte den algo neu zu starten, als utopisch an. Das ganze wird erst wieder echtzeittauglich, wenn man "näher dran" ist - sonst sollte auf keinenfall ein neuer A* gestartete werden! :O

PhillipK

So, Okt 09, 2011 12:48
Antworten mit Zitat

Okay, das klingt wirklich nach einem plan.
Allerdings: Uff.
Ich habe in meiner Testszene grade ein 75x75 raster, wo ich wände einzeichnen kann und platziere ~ 20 einheiten. Diese suchen sich jedesmal, wenn sie ihr ziel erreicht haben ,einen neuen weg. Gibt es keinen, suchen sie wieder einen.
Wenn 5 gleichzeitig suchen, dauert es schon ewigkeiten. Genau hierfür muss etwas übergeordnetes her, was stark vereinfachte pfade enthält. Ich spiele grade mit dem gedanken, ein kleineres raster über meine map zu legen, alle 4 oder 5 felder - welche einen zeiger auf die punkte oben, unten, links und rechts halten. Dadurch ist es nurnoch ein bruchteil der Map zu überprüfen und das ganze ist eventuell halbwegs Echtzeit tauglich Smile

Ich könnte das ganze im Jetzigen Algo einmal umschreiben und 2 gruppen erstellen - eine rennt simpel ihre wege, die andere versucht, die Wege-renner zu verfolgen. Das dürfte aber dafür sorgen, das mindestens die hälfte etwa 20sekunden steht, bevor ihr weg "fertig" ist Sad

Da sehe ich leider, performancetechnisch, alle 10 schritte den algo neu zu starten, als utopisch an. Das ganze wird erst wieder echtzeittauglich, wenn man "näher dran" ist - sonst sollte auf keinenfall ein neuer A* gestartete werden! :O

	Hubsi	So, Okt 09, 2011 22:12 Antworten mit Zitat
Puuh, soviele Antworten. Tausend Dank erstmal an alle Helfer Erstmal zu den offenen Fragen (man möge mir verzeihen sollte ich noch etwas übersehen). Die Bots wissen laufend um die Position ihres Zieles und (sollten) versuchen dorthin zu gelangen, bzw. würden die Bewegung stoppen wenn sie freie Schussbahn hätten. Die Map ist dabei statisch und bietet im finalen Zustand relativ großzügige Flächen zur Bewegung an (derzeit wird mit einer Entwicklungsmap gearbeitet um Probleme isoliert debuggen zu können). Noch als Erklärung, weil ich denke Midimaster hat das Botverhalten falsch aufgefasst: Die Bots verabreden sich nicht untereinander zum fröhlichen Köpfe einschlagen. Sprich Bot A ist auf Bot C scharf, der wiederrum Bot B an die Gurgel will, wobei B gerade dem Spieler Löcher in den Hut stanzt. Die können also mit völlig verschiedenen Zielkoords durch die Gegend eiern Versuchen werde ich jetzt als erstes die Geschichte mit den fixen Knotenpunkten. Das ist schnell intergriert und scheint mir performancetechnisch am unproblematischten. Interessant und allemal einen Testcode wert sehe ich aber auch die Geschichte mit dem A* und 10 Punkten laufen etc. Mal sehen was mich mehr begeistern kann Vielen Dank nochmal an alle die sich mal wieder die Mühe mit mir gemacht haben
Den ganzen Doag im Bett umanandflagga und iaz daherkema und meine Hendl`n fressn...

Hubsi

So, Okt 09, 2011 22:12
Antworten mit Zitat

Puuh, soviele Antworten. Tausend Dank erstmal an alle Helfer Very Happy

Erstmal zu den offenen Fragen (man möge mir verzeihen sollte ich noch etwas übersehen). Die Bots wissen laufend um die Position ihres Zieles und (sollten) versuchen dorthin zu gelangen, bzw. würden die Bewegung stoppen wenn sie freie Schussbahn hätten. Die Map ist dabei statisch und bietet im finalen Zustand relativ großzügige Flächen zur Bewegung an (derzeit wird mit einer Entwicklungsmap gearbeitet um Probleme isoliert debuggen zu können).
Noch als Erklärung, weil ich denke Midimaster hat das Botverhalten falsch aufgefasst: Die Bots verabreden sich nicht untereinander zum fröhlichen Köpfe einschlagen. Sprich Bot A ist auf Bot C scharf, der wiederrum Bot B an die Gurgel will, wobei B gerade dem Spieler Löcher in den Hut stanzt. Die können also mit völlig verschiedenen Zielkoords durch die Gegend eiern Very Happy

Versuchen werde ich jetzt als erstes die Geschichte mit den fixen Knotenpunkten. Das ist schnell intergriert und scheint mir performancetechnisch am unproblematischten. Interessant und allemal einen Testcode wert sehe ich aber auch die Geschichte mit dem A* und 10 Punkten laufen etc. Mal sehen was mich mehr begeistern kann Very Happy

Vielen Dank nochmal an alle die sich mal wieder die Mühe mit mir gemacht haben Very Happy

Den ganzen Doag im Bett umanandflagga und iaz daherkema und meine Hendl`n fressn...

	PhillipK	So, Okt 09, 2011 22:29 Antworten mit Zitat
Die fixen knotenpunkte sind meiner meinung nach auch das sinnvollste. Ich kanns leider nicht so statisch einbinden, deshalb sitze ich auch schon 2 Tage an der austüftelung. Bei einer (relativ) statischen map sieht das ganze aber Tausenmal einfacher aus - meine idee wäre, Globale knotenpunkten an allen relativen ecken etc eines raumes zu setzen, dh die tür aus Raum A raus kriegt einen, sowie die tür nach Raum B rein. Nun wird noch jeder punkt mit jedem "direkt erreichbaren" verknüpft - klare sichtlinie erforderlich. So kannst du ein simples A* über die knoten legen und erstmal "in die nähe" kommen, danach wird jede weitere suche ein kinderspiel. Sofern du die passende Heuristik verwendest, geht der A* algo zielstrebig vor und braucht keine 0.3 ms um eine Kurze, hinernislose, distanz zu überbrücken. Ich würde mich über eine kleine demo aus deinem Testszenario freuen, vielleich komme ich damita uch bei meinem problem weiter ^^

PhillipK

So, Okt 09, 2011 22:29
Antworten mit Zitat

Die fixen knotenpunkte sind meiner meinung nach auch das sinnvollste.
Ich kanns leider nicht so statisch einbinden, deshalb sitze ich auch schon 2 Tage an der austüftelung.
Bei einer (relativ) statischen map sieht das ganze aber Tausenmal einfacher aus - meine idee wäre, Globale knotenpunkten an allen relativen ecken etc eines raumes zu setzen, dh die tür aus Raum A raus kriegt einen, sowie die tür nach Raum B rein.
Nun wird noch jeder punkt mit jedem "direkt erreichbaren" verknüpft - klare sichtlinie erforderlich.
So kannst du ein simples A* über die knoten legen und erstmal "in die nähe" kommen, danach wird jede weitere suche ein kinderspiel.

Sofern du die passende Heuristik verwendest, geht der A* algo zielstrebig vor und braucht keine 0.3 ms um eine Kurze, hinernislose, distanz zu überbrücken.

Ich würde mich über eine kleine demo aus deinem Testszenario freuen, vielleich komme ich damita uch bei meinem problem weiter ^^

	Hubsi	So, Okt 16, 2011 11:37 Antworten mit Zitat
Für alle die mal vor der selben Frage stehen: Es hat mit A* funktioniert. Der beste Test war gerade eben ein Tippfehler als ich das Spiel mit 99 statt 9 Bots startete. Trotz der sinnlos vielen Bots lief das Progrämmelchen mit 60 Fps (die maximal möglichen Fps habe ich jetzt nicht zur Hand, konnte das nur am Rückgabewert von WaitTimer sehen, weil der eben auf 60 Frames eingestellt ist). Und vielen Dank nochmal an alle Helfer
Den ganzen Doag im Bett umanandflagga und iaz daherkema und meine Hendl`n fressn...

Hubsi

So, Okt 16, 2011 11:37
Antworten mit Zitat

Für alle die mal vor der selben Frage stehen: Es hat mit A* funktioniert. Der beste Test war gerade eben ein Tippfehler als ich das Spiel mit 99 statt 9 Bots startete. Trotz der sinnlos vielen Bots lief das Progrämmelchen mit 60 Fps (die maximal möglichen Fps habe ich jetzt nicht zur Hand, konnte das nur am Rückgabewert von WaitTimer sehen, weil der eben auf 60 Frames eingestellt ist). Und vielen Dank nochmal an alle Helfer Mr. Green

Den ganzen Doag im Bett umanandflagga und iaz daherkema und meine Hendl`n fressn...

	PhillipK	So, Okt 16, 2011 12:52 Antworten mit Zitat
Falls es dennoch mal komplexer wird, sieh dir Noobodys beitrag zu meinem problem mit A* an. Das ist einfach nur beeindruckend ^^ A* ist unter blitzmax - laut den testergebnissen und der erklärung von Noo - einfach viel langsamer als eine Breitenfeld suche. Ich habs mehrmals getestet - sein TBFS ist immer konstant schnell (+/- 2ms) - abhängig von der größe der Map. A* ist aber ein vielfaches langsamer, vorallem bei komplexeren maps. einzig eine direkte sichtverbindung in einem breiten feld (mit passender heuristik) lies A* 4x schneller sein.

PhillipK

So, Okt 16, 2011 12:52
Antworten mit Zitat

Falls es dennoch mal komplexer wird, sieh dir Noobodys beitrag zu meinem problem mit A* an.

Das ist einfach nur beeindruckend ^^ A* ist unter blitzmax - laut den testergebnissen und der erklärung von Noo - einfach viel langsamer als eine Breitenfeld suche.

Ich habs mehrmals getestet - sein TBFS ist immer konstant schnell (+/- 2ms) - abhängig von der größe der Map.
A* ist aber ein vielfaches langsamer, vorallem bei komplexeren maps.
einzig eine direkte sichtverbindung in einem breiten feld (mit passender heuristik) lies A* 4x schneller sein.

Übersicht

BlitzBasic

Allgemein

Nach Oben

BlitzBasic Portal

Pathfinding für bewegliche Ziele

Betreff: Pathfinding für bewegliche Ziele