Pfadplanung für Volumes in Spielen

7

Wie würden Sie ein Volume für ein Spiel planen?

Zum Beispiel ein 1 km langer Würfel mit Tunneln und Höhlen. Auch das Gelände ist zerstörbar.

Sie haben Geh- und Flugmodi.

Ich würde es in Phasen unterteilen. Erstellen Sie ein Volumen des offenen Raums. Suchen Sie einen Pfad, der die dynamische Zerstörung berücksichtigt.

Leistung ist ein großes Problem und die Fähigkeit, Pfade zu finden, die in kurzer Zeit verwendet werden.

Konkretes Beispiel: Etwas tief im Boden effizient abbauen.

Der Boden ist zerstörbar. "Höhlen" sind leicht zu grabende Gebiete. Bergbau ist wie Fliegen. Muss mit Sensoren sehen. Der Datensatz ist riesig. Sie müssen einen Transportweg zum Ziel erstellen. Kann Multi-Agent sein.

Feuer
quelle
1
Gibt es einen Nebel des Krieges und sollte er die Wegfindung beeinflussen?
Wird
Es gibt eine Sichtlinie, obwohl Sie Sensoren verbinden können.
Feuer
Arbeiten Sie am Level-Design - entwerfen Sie ein Level und richten Sie die (anfänglichen, vorbeschädigten) Tunnel und Höhlen Wochen vor dem Spiel ein? Oder arbeiten Sie an der Wegfindung - programmieren Sie computergesteuerte Agenten so, dass sie sich während des Spiels "vernünftig" bewegen, anstatt dumme Dinge wie das Betreten von Wänden, das Herunterfallen von Klippen usw. zu tun?
David Cary
Niemand wird Wochen damit verbringen, die Geologie des 1 km langen Würfels zu entwerfen. Die Frage betrifft nicht die prozedurale Erzeugung von Geologie. Es geht um die Pfadplanung für Agenten in einem Innenkavernen- und Tunnelsystem. Dies bedeutet, nicht verloren zu gehen oder zwischen Pfaden zu wechseln.
Feuer

Antworten:

3

Um eine angemessene Leistung zu erzielen, erfordert die dynamische Pfadfindung einen speziell dafür geeigneten Algorithmus wie D * (Dynamic A *).

Darüber hinaus können Sie möglicherweise einen Weg finden, um eine hierarchische Pfadfindung durchzuführen. Auf diese Weise haben Sie einen einfacheren Pfad bei einer niedrigeren Auflösung und komplexere Unterpfade bei höheren Auflösungen. Indem Sie einen Pfadgraphen mit höherer Auflösung in den Mastergraphen mit niedrigerer Auflösung einsetzen, können Sie Ihren Pfad zu einer beliebigen Auflösung ausarbeiten.

Die Pfadfindung mit niedrigerer Auflösung ist offensichtlich großartig, da Sie nur eine minimale Pfadfindung durchführen können, bis Sie eine andere Unterregion betreten, und dann eine tiefere Pfadfindung auf der Subdiv-Ebene dieser Region durchführen können.

Was den eigentlichen Algorithmus betrifft, der zum Tunneln durch Ihren 3D-Raum verwendet wird, besteht das größte potenzielle Problem darin, 3D-Sackgassenbereiche zu betreten, aus denen Sie nicht herauskommen können, ohne eine andere Passage zu überqueren (Diagrammsegment). Siehe meinen letzten Monolog auf planaren Graphen Einbettungen hier .

Ingenieur
quelle
HPA * ist etwas performanter.
Feuer
Ich habe probabilistische Straßenkarten untersucht, wie sie bei Roboternavigationsproblemen verwendet werden.
Feuer
2
Sie können auch eine auf Mobilfunkautomaten basierende „Flutfüllung“ verwenden, um Ihre Kavernen und Tunnel auf eine viel kleinere Teilmenge von Räumen zu beschränken. Dies kann bei Verformung der Landschaft im Hintergrund wiederholt werden, wenn Ihre Karte irgendwie groß genug ist, um eine Verzögerung zu verursachen, oder wenn die Verformung der Karte konstant ist. (im Gegensatz zu Minecraft oder Zwergenfestung) Sobald Sie diesen untergeordneten Pfad haben, brauchen Sie nur noch einen Pfad dorthin, dann entlang und dann von dort. Ideal ist es, wenn alle offenen Räume eine Sichtlinie zum Teilmengenpfad haben.
DampeS8N
1

Wenn Sie unter zerstörbarem Gelände große Änderungen an der riesigen mehrstufigen Umgebung verstehen, wird dies höllisch schwierig, insbesondere für Laufeinheiten. Es wäre ratsam, fliegende und gehende Einheiten von Anfang an zu unterteilen, damit sie die separaten Grafiken haben.

Ich kann nicht sagen, dass ich eine endgültige Lösung für die Gehgeräte kenne. Abhängig von der Anzahl der Agenten, möglichen Geländeänderungen und der Auflösung des Würfelknotens möchten Sie möglicherweise D * verwenden oder nicht. Im Wesentlichen ist D * eine rohe Kraft A *. Wie Nick angedeutet hat, kann das brutale Erzwingen eines Schrittes voraus zu vielen "Sackgassen" führen, da Sie ohne den gesamten Pfad nicht sofort erkennen können, ob der nächste Knoten korrekt ist oder nicht. Außerdem müssen Sie über den Pfad-Cache und seine teilweise Ungültigmachung nachdenken, damit Sie nicht ständig pro Agent brutale Gewalt anwenden müssen. Insgesamt wird es nicht einfach und kann zu CPU-schwer werden.

Wenn Sie stattdessen mit A * arbeiten, ist es am einfachsten, die Zerstörung Ihres Geländes auf ein Minimum zu beschränken und hierarchische Pfadfindung wie "grobes" A * und eine Form der lokalen Vermeidung zu vermeiden. Ich denke, es ist keine Option, also können Sie versuchen, den Boden und die Wände Ihres Würfels in ein Navigationsnetz umzuwandeln und es dann Teil für Teil zu ändern. Die Navmesh-Berechnung ist natürlich nicht schnell, aber es gibt Raum für verschiedene Optimierungen, um eine vollständige Neuberechnung des Netzes bei einem Geländewechsel zu vermeiden. Die allgemeine Idee besteht darin, lokale Netzaktualisierungen durchzuführen, sodass nur die betroffenen Bereiche eines Navigationsnetzes geändert werden, wenn eine Geländezerstörung auftritt. Dies könnte durch Anpassung der Konstruktion des Voronoi-Diagramms geschehen, ist jedoch kein "gelöster Bereich". Es wird auch nicht einfach sein, da Sie die Neuberechnung des Navmesh beschleunigen müssen.

Die Grafik für Lufteinheiten ist viel einfacher. Grundsätzlich müssen Sie den gesamten "Luftraum" finden und in die Grafik umwandeln. Da Ihre Kavernen dynamisch sind, ist es am naheliegendsten, dieses Diagramm auf dem Octree eines Würfels zu basieren. Verwenden Sie Octree-Blattschwerpunkte (Punkt in der Mitte des Blattwürfels) als Grundlage für die Berechnung der Knoten und filtern Sie alle Schwerpunkte an den offensichtlich ungültigen Positionen heraus. Überprüfen Sie die resultierenden Zentroide, um alle unzugänglichen Elemente von ihren Nachbarn zu entfernen. Dies wird sehr schnell gehen, sodass Ihre Hauptanliegen bei der Bodenfindung bleiben.

Genug Tee
quelle
Sowohl Flug- als auch Gehmodi können aus dem Navmesh probieren. Dann können sie ihre eigenen Darstellungen erzeugen. Ich habe keine Ahnung, wie ich zwischen den Modi wechseln soll.
Feuer
In probabilistischen Straßenkarten besteht eine Methode darin, Voroni-Diagramme zu erstellen. Aber es hängt davon ab, dass Sie die Räume abdecken.
Feuer
1

Ich habe eine Open-Source-Implementierung der Pfadfindung in einem 3D-Raster als Teil meines Voxel-Spiel-SDK. Es ist eine Implementierung des A * -Algorithmus, der genau für Umgebungen im Minecraft-Stil und für Voxel-Terrain gedacht ist.

Es ist kein dynamischer Algorithmus, wie andere Leute vorgeschlagen haben, also kann ich Ihnen dort nicht helfen. Ich denke, es hängt davon ab, wie dynamisch deine Welt wirklich ist. Es könnte auch einige Leistungsverbesserungen gebrauchen, da es derzeit einige Sekunden dauern kann, bis ein Pfad gefunden wird, der möglicherweise 100 Voxel lang ist. Möglicherweise können Sie ihn jedoch auf einer heruntergesampelten Version Ihres Volumes ausführen (achten Sie darauf, dass das Downsampling gültig ist) Pfade können erstellt werden / verloren gehen).

Sie können es hier in Aktion sehen http://www.youtube.com/watch?v=C8y0OzL0zpM (das ist jedoch nicht mein Spiel) und die Quelle von http://www.thermite3d.org erhalten .

David Williams
quelle
Ich habe speziell 1 km Würfel angegeben, um die 100-Voxel-Pfadfindungsalgen auszuschließen.
Feuer
... können spärliche Voxeldarstellungen in dieser Größenordnung funktionieren? ;)
Will
Spärliche Voxel bedeuten, dass nur der Rumpf überprüft wird. Aber wir kümmern uns nur um den offenen Weg.
Feuer
hängt davon ab, ob Sie die Voxel oder die Lücken iterieren. Ich wurde nur müde von Ihrer Ungeduld in jeder einzelnen Antwort. In diesem Forum werden nicht so viele Fragen gestellt, wie Sie möchten.
Wird
Ich bin mit jeder Antwort sehr zufrieden. Stackexchange könnte viel schlimmer sein.
Feuer
1

Wenn Ihre Welt bereits aus diskreten Blöcken besteht, ist es sinnvoll, diese als Grundlage für Ihre Navigation zu verwenden.

Pfadfinder sind einfache, schnelle Pfadfinder, die etwas schwieriger sind. Der Weg zu folgen und auf die Veränderungen in der Welt zu reagieren, ist die wahre Bosheit.

Es gibt einige Fragen, die Ihnen helfen können, die mögliche Lösung einzugrenzen: - Welche Art von NPCs versuchen Sie zu simulieren? - Wie lange suchen Sie? - Wie genau brauchen Sie?

Wenn Sie kurze Wege haben und die Qualität "besser als lenken" in Ordnung ist, sind lokale Netze [1] eine gute Wahl. Sie sind super schnell, Sie können es sowohl 2D als auch 3D arbeiten lassen. Sie können lokale Rasterdaten direkt aus Ihren Volumendaten abrufen, sodass das Navigationsdiagramm problemlos mit den dynamischen Änderungen synchron bleiben sollte.

Das Problem mit lokalen Gittern besteht darin, dass der Agent möglicherweise stecken bleibt, wenn Sie lokale Minima in Ihrer Welt haben, die größer als Ihr lokales Gitter sind. Es ist möglich, Tricks wie das Hinzufügen von Brotkrumen an Orten auszuführen, an denen Sie lokale Minima erkennen, und diese Orte bei der Suche zu vermeiden.

Wenn Sie lange Wege benötigen, schlage ich eine Art hierarchisches Schema vor. HPA * sollte Ihnen gute Ideen geben, wie Sie spärliche Knoten im Raster einer Welt erstellen können. Lokale Gitter können die Pfadfindung zwischen den Knoten auf hoher Ebene lösen. Wenn Sie Änderungen an der Welt vornehmen, müssen Sie auch die groben Knoten lokal ändern. Sie können die Knoten auch verwenden, um dynamische Änderungen in der Spielwelt zu erkennen und den Pfad neu zu planen.

Wenn Sie eine dynamische Welt haben, wird die Pfadfindung zu einer Statistik. Es gibt keine Garantie mehr, ob der Agent seinen Weg findet. Es ist sehr schwierig, die Veränderungen in der Welt im Auge zu behalten, und die Neuplanung, wenn etwas schief geht, ist träge.

Eskil fährt mit dieser Idee in Love MMO, und sein Pfadfinder ist nur eine Zufallsstichprobe mit Utility-Funktion (ebenso wie seine Aktionsauswahl :)). Ich würde empfehlen, dies zuerst zu tun, wenn es zu Ihrem Spielstil passt.

[1] http://digestingduck.blogspot.com/2010/03/local-navigation-grids.html

user9780
quelle
0

Sie möchten ein Navigationsnetz verwenden, oder wenn die Welt in der Vertikalen besonders laut ist und nicht nur auf Plattformen, oder wenn der Flugmodus mehr als nur Springen oder Schweben ist, können Sie Navigationsvolumen verwenden.

Umleitung ist eine Bibliothek zur Pfadfindung, mit der Sie das Navigationsnetz live aktualisieren können. Ich habe es nie benutzt, ich weiß nicht, wie es auf Ihrer Skala funktioniert. Ein hierarchisches System scheint eine gute Idee zu sein.

Gute Lektüre, wenn Sie darüber nachdenken, Ihre eigenen zu schreiben, ist eine aktuelle Forschung von Brechen Symmetrie . Eine nachdenkliche Lektüre wert!

Es muss überlegt werden, ob Nebel des Krieges die Wegfindungsentscheidungen beeinflussen sollte. Es kann sein, dass sich eine Einheit in einer geraden Linie bewegt, bis sie auf Hindernisse stößt, wenn sie aufgefordert wird, sich in ein neues Gebiet zu bewegen, oder dass die Einheit eine Route mit vollständigem Kartenwissen erstellt. Das ist eine Spielwahl.

Spaß beim Lesen: Pfadfindung ein für alle Mal korrigieren

Wille
quelle
Recast / Detour voxelisiert das Gelände in ein Navmesh, erzeugt jedoch nur planare Polygone. Daher ist es nur für Bodenmodi nützlich. Sie können die dynamische Planung für die Neuplanung missbrauchen.
Feuer
Mikko gebenchmarkt hpa * und fand es 4-5 mal schneller als Detour der A * sein und verwendet 10-20 mal weniger Speicher (Graph - Knoten).
Feuer
Jemand irgendwo hat wahrscheinlich das BSD-lizenzierte Nav-Volume lib mit G-HPA * -JPS-Pfadfindung erstellt. @Fire du bist so gut gelesen, hast du einen Link dafür?
Wird
Tatsächlich ändert die oben genannte verallgemeinerte Version von HPA * die Neufassung / den Umweg und wird unter einer nicht viralen freien Lizenz veröffentlicht. Es werden jedoch nur planare Polygone verarbeitet. Ich würde dort anfangen.
Feuer