3D Pathfinding

[RalleYTN]

Hey Loits!

Ich habe schon seit Stunden versucht etwas brauchbares zu finden aber kläglich versagt.
Ich habe bloß ganz viel zu A* gefunden.
Ich möchte universelles Pathfinding im 3dimensionalen Raum durchführen. mit universell meine ich für möglichst viele Spiel-Genres einsetzbar. Außerdem soll es möglichst performant sein.

Hat da bereits jemand Erfahrung? Wenn ja so möchte er doch bitte den Algorithmus erklären.

 

[Baldur]

Ich will jetzt nicht auf konkrete Algorithmen eingehn, aber ansich ist A* schon sehr universell einsetzbar.

Im Prinzip basiert der A* ja auf Knoten/Nodes und deren Nachfolger. Auf einer 2D-Karte hat ein Knoten eben 4 Nachfolger (oder 8 mit Diagonalen), im 3D-Raum entsprechend mehr. Der A* ist nichtmal auf ein 2D bzw. 3D-Raster beschränkt. Wenn du z.B. an einen Straßenatlas denkst, dann ist jede Kreuzung und jede Abbiegung ein Knoten. Die jeweiligen Nachfolger sind dann die nächsten Abzweigungen und die Kosten für den Nachfolger ist dann z.B. die Wegstrecke bis dorthin (mit unterschiedlichen Modifikatoren für Feldweg, Autobahn, etc)

Performance ist halt so eine Sache. A* findet immer den besten Weg, sofern fehlerfrei implementiert. Dafür ist er halt - vor allem bei großen Graphen - sehr, sehr langsam. Es gibt verschiedene Tricks, mit denen man einen A* beschleunigen kann, aber das hängt auch sehr stark davon ab, was du damit machen willst.
Wenn du komplexe Labyrinthe hast, kommst du um A* nicht drum herum. Bei einem offenen, freien Gelände kannst du schnellere Algorithmen verwenden, allerdings besteht dann die Gefahr, daß du dabei in einer Sackgasse landest. Du kannst auch beides kombinieren und z.B. erst einen groben Pfad berechnen und in die Richtung schicken, gleichzeitig im Hintergrund eine detaillierte Pfadsuche berechnen und dann deine Spielfigur in diese Richtung schicken.

Eine Möglichkeit den A* zu optimieren ist z.B. schon bekannte Wege abzuspeichern und bei erneuter Suche dann in deinem Zwischenspeicher zu kucken, ob schon ein Weg bekannt ist. Dann kannst du z.B. deine Karte in unterschiedliche Sektoren mit Portalen aufteilen.
Angenommen du hast ein Haus mit verschiedenen Zimmern. Dann kannst du pro Zimmer(=Sektor) alle möglichen Pfade zwischen allen Türen(=Portal) zwischenspeichern und musst am Ende nur Pfade von Tür X zu Tür Y suchen und kannst dabei die zwischengespeicherten Teilstrecken nutzen.

Aber wenn du es schnell haben willst, kommst du nicht drum rum deinen Algorithmus auf die entsprechende Problemstellung anzupassen. 100%ig unversell und dabei beste Performance wirst du leider nicht finden

 

[RalleYTN]

ok. dann muss ich jetzt nur noch wissen, wie ich indoor und outdoor level in einen graphen umwandle. Zum Glück habe ich schon etwas vorarbeitet geleistet. Ich möchte das alles nämlich schonmal im Hinterkopf habe wenn ich an das AI Modul rangehe.

Das Wissen von Phaden kann ich mir schonmal abschmieren, da es auch Zufalssgenerierte Level und Terrains gibt.

Das Pathfinding muss erstmal nicht so intelligent sein. erstmal bloß performant. Gibt es noch andere Algorithm nach denen ich mal googlen könnte?

und kennt jemand eine gute Methode zum erstellen eines Graphen von Levels und Welten?

 

[Baldur]

Hier gibts ein Video bei dem ein paar Suchalgorithmen vorgestellt werden. Die Ergebnisse können je nachdem wie dein Level aufgebaut ist, vollkommen unterschiedlich sein. Der eine ist gut, wenn du einen offenen Level mit ein paar Hindernissen hast, versagt aber dann bei komplexen Labyrinthen. A* ist gut bei Labyrinthen, sucht aber bei offenen Leveln unnötig viel in der Gegend rum..
Ich persönlich bin wegen der Flexibilität letztendlich doch immer beim A* hängen geblieben (plus diverser Tricks und Optimierungen)
Interessant ist evtl noch der Jump Point Search. Geht ein bisschen in Richtung der Geschichte mit den Portalen was ich erwähnt hatte. Wenn dein Level recht statisch ist, kann man da evtl auch die Zwischenergebnisse cachen.

 

[RalleYTN]

Ok ich habe gesehen, dass der Best-First-Search Algorithmus der schnellste ist. allerdings sucht er nicht unbedingt den besten weg und er fängt an sich in Sackgassen zu loopen. Ich glaube ich werde mich mal an dessen Bruder die Breadth-First-Search hängen und zum Erstellen des Graphen habe ich einen netten Algorithmus gefunden der sich 2^n-Trees nennt. sieht vielversprechend aus. mal sehen wie weit ich komme.
Danke @Baldur

 

[mrBrown]

Ok ich habe gesehen, dass der Best-First-Search Algorithmus der schnellste ist. allerdings sucht er nicht unbedingt den besten weg und er fängt an sich in Sackgassen zu loopen. Ich glaube ich werde mich mal an dessen Bruder die Breadth-First-Search hängen und zum Erstellen des Graphen habe ich einen netten Algorithmus gefunden der sich 2^n-Trees nennt. sieht vielversprechend aus. mal sehen wie weit ich komme.
Danke @Baldur

Best-First-Search findet durchaus den optimalen Weg, und kommt auch mit Sackgassen klar, A* zB ist Best-First-Search.
Normale Breitensuche klappt im Gegensatz zu Best-First-Search nur, wenn jede Kante gleiche Kosten hat, ist bei Spielen in den meisten Fällen nicht gegeben. Wenn doch, dürfte sich das erstellen des Graphen in dein meisten Fällen erübrigen, weil man direkt auf der Map arbeiten kann, wenn ich mich grad nicht vertu...

 

[Baldur]

Ja, das kommt auch noch dazu. Unterschiedliche Wegkosten (über Straßen bewegen ist effizienter als durch den Wald) machen so ziemlich jede Optimierung zunichte. Aber drum muss man ja kucken was für konkrete Anforderungen man hat und seinen Algorithmus darauf optimieren

 

[RalleYTN]

Best-First-Search findet durchaus den optimalen Weg, und kommt auch mit Sackgassen klar, A* zB ist Best-First-Search.
Normale Breitensuche klappt im Gegensatz zu Best-First-Search nur, wenn jede Kante gleiche Kosten hat, ist bei Spielen in den meisten Fällen nicht gegeben. Wenn doch, dürfte sich das erstellen des Graphen in dein meisten Fällen erübrigen, weil man direkt auf der Map arbeiten kann, wenn ich mich grad nicht vertu...

erstmal muss es ohne wegkosten funktionieren.
es geht erstmal darum eine funktionierende KI in meine Engine einzubauen.
Optimierungen kann ich später auch noch machen.

 

[mrBrown]

Dann dürfte Dijkstra oder A* erstmal die beste Wahl sein.