Wie kann ich zur Laufzeit ein 2D-Navigationsnetz in einer dynamischen Umgebung generieren?

9

Ich habe also verstanden, wie man A * zum Finden von Pfaden verwendet, und ich kann es in einem Raster verwenden. Meine Spielwelt ist jedoch riesig und ich habe viele Feinde, die sich auf den Spieler zubewegen, der sich bewegt. Daher ist ein Rastersystem zu langsam, um einen Pfad zu finden. Ich muss mein Knotendiagramm mithilfe eines Navigationsnetzes vereinfachen.

Ich verstehe das Konzept, wie ein Netz funktioniert (einen Pfad durch Knoten an den Eckpunkten und / oder den Mittelpunkten der Kanten von Polygonen finden).

Mein Spiel verwendet dynamische Hindernisse, die zur Laufzeit prozedural generiert werden.

Ich kann mich nicht so recht darum kümmern, wie man ein Flugzeug mit mehreren Hindernissen nimmt und den begehbaren Bereich programmatisch in Polygone für das Navigationsnetz aufteilt, wie im folgenden Bild.

Navigationsnetz

Wo soll ich anfangen? Woher weiß ich, wann ein Segment eines begehbaren Bereichs bereits definiert ist oder schlimmer noch, wenn mir klar wird, dass ich einen zuvor definierten begehbaren Bereich unterteilen muss, wenn der Algorithmus durch die Karte "geht"?

Ich verwende Javascript in NodeJS, wenn es darauf ankommt.

Stephen
quelle
1
Die dynamische Partitionierung, die Sie implementieren möchten, hängt von den Besonderheiten Ihrer Kartenelemente ab. Bestehen Ihre Hinderniselemente vollständig aus rasterausgerichteten Rechtecken, wie in Ihrem Beispiel gezeigt? Gedrehte Rechtecke? Unregelmäßige Polygone? Oder Nicht-Polygonformen mit vielen Kurven? Haben Sie Punkt- / Poly-Daten für die Form der Hindernisse? Wenn ja, handelt es sich um Formdaten in Form von Dreiecken, Rechtecken, ausschließlich konvexen Polygonen oder einer Mischung aus konvexen und konkaven Polygonen?
Matthew R
@Matthew Meine Welt besteht aus konvexen Polygonhindernissen, keinen Kurven und keinen konkaven Polygonen. Jedes Hindernis wird als Polygonobjekt mit Scheitelpunkten gespeichert, die durch Vektorobjekte dargestellt werden.
Stephen
1
Für das, was es wert ist, arbeite ich an einer Lösung, die auf diesem Papier basiert: gradworks.umi.com/3493710.pdf Wenn ich erfolgreich bin, werde ich meine Lösung veröffentlichen.
Stephen
1
Das Navigationsnetz ist nicht zu 100% da, um Ihnen zu sagen, ob Sie irgendwohin gehen können oder nicht. Es ist nur eine grundlegende Übersicht über begehbare Bereiche. Sie müssen immer noch Kollisionsprüfungen für dynamische Objekte durchführen. Bearbeiten: so ziemlich das, was Ray gesagt hat
Dreta
@ Stephen - Siehe Antwort mit langem Kommentar .
Matthew R

Antworten:

3

@ Stephen - Langer Kommentar - Das Papier scheint eine Lektüre wert zu sein, wenn ich etwas Zeit habe. Grundsätzlich hätte ich etwas in Anlehnung an den Hertel-Mehlhorn-Algorithmus vorgeschlagen, der in der Veröffentlichung erwähnt wird (eine Referenz für diesen speziellen Algorithmus finden Sie hier http://www.bringyou.to/compgeom/ ) durch Unterteilen der Kartenseiten (außerhalb der Grenze des Spielbereichs) einige Zeit, um das Auftreten mehrerer kleiner Dreiecke in den Ecken zu verringern. Diese kleinen Dreiecke können problematisch sein, da sie kleiner sein können als das, wofür Sie die Pfadfindung durchführen. Das Hertel-Mehlhorn dient zur Reduktion der durch eine dreieckige Unterteilung erzeugten Polygone, wenn Sie sich hier mehr für Triangulation interessieren:http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/PolyPart/polyPartition.htm .

Wenn Sie das Rad lieber nicht neu erfinden möchten, wird diese Bibliothek meiner Meinung nach alles tun, was Sie brauchen: http://code.google.com/p/polypartition/ . Es führt die Triangulationen und Reduktionen mit einer von verschiedenen Optionen durch, einschließlich Hertel-Mehlhorn. Es ist eine MIT-Lizenz, was bedeutet, dass sie für Closed-Source- und kommerzielle Projekte verwendet werden kann, wenn dies ein Problem darstellt.

Wenn Sie sich entschließen, weiter an Ihrer eigenen Implementierung zu arbeiten, würde ich gerne sehen, was Sie sich einfallen lassen.

Matthew R.
quelle
1
Tolle Antwort, @Mathew. Und das sollten Sie unbedingt lesen! Es ist einfach zu befolgen und erklärt eine großartige Technik (insbesondere Anhang A, in dem es um die agentenbasierte Erkennung / Generierung des Netzes geht). Ich codiere eine Version dieses Algorithmus für Javascript, und es kommt gut voran. Ich werde es als Antwort posten, wenn es fertig ist.
Stephen
@ Stephen würde gerne diese Arbeit sehen
kevzettler
@ Stephen Ich suche auch eine Javascript-Version
Apolo
6

Anstelle eines Netzes können Sie auch einen hierarchischen A * -Ansatz in Betracht ziehen. Der größte Vorteil eines Netzes besteht darin, mit Spielwelten umzugehen, die nicht am Raster ausgerichtet sind, anstatt die Komplexität eines Rasters zu verringern.

Mit einem hierarchischen Ansatz unterteilen Sie Ihre Welt wiederholt (ähnlich wie bei einem Quad-Baum) und generieren Konnektivitätsinformationen zwischen den Knoten. Sie können dann schnell einen Pfad zwischen großen Teilen der Welt generieren und nur das hochauflösende Raster verwenden, um innerhalb eines größeren Teils einen Pfad zu finden.

Der hierarchische Ansatz führt zu einer um Größenordnungen besseren Leistung, während ein Netz bestenfalls eine kleine lineare Verbesserung bewirkt.

Der naive Ansatz besteht darin, Ihre Welt einfach in X x X größere, gitterausgerichtete Blöcke zu unterteilen und die Konnektivitätsinformationen zwischen ihnen zu generieren (z. B. gibt es einen Pfad zwischen dem Block 2x1 von 3x1 bis 2x2 und den Abstand des durchschnittlichen Pfads). .

Beachten Sie, dass Sie mit diesem Ansatz unter bestimmten Umständen möglicherweise nicht immer ideale Pfade erhalten. Das Erzeugen von Chunk-Schichten mit variabler Größe lindert das Problem, aber ehrlich gesagt ist es normalerweise viel einfacher, die jemals gemachten Fehler mit den Problempfaden zu vermeiden und sich auf die Tatsache zu verlassen, dass der Spieler höchstwahrscheinlich keine Feinde bemerkt, die suboptimale Pfade nehmen, außer in den am degeneriertesten von Fällen.

Sean Middleditch
quelle
1
Ich sollte weiter erklären: Mein Spiel ist nicht gitterorientiert. Ich habe ein Raster in einem Bereich von 800 x 600 Pixel erstellt, wobei jedes Pixel ein Leerzeichen im Raster ist (ich habe immer noch A * herausgefunden, also habe ich noch nicht über die Leistung nachgedacht). Ich habe Hindernisse, die nicht so einfach sind wie die im obigen Beispielbild. Ich habe nur versucht, das Problem zu veranschaulichen. Offensichtlich musste ein solches Spielfeld überarbeitet werden, und nach einigen Recherchen denke ich, dass ein Navigationsnetz der richtige Weg wäre.
Stephen
3

Ich denke, Sie könnten dies überkomplizieren. Sie müssen wahrscheinlich keine Navigationsnetze im laufenden Betrieb generieren. Verwenden Sie stattdessen ein statisches Navigationsnetz für Ihre Basiswelt.

Das Umgehen von Hindernissen kann mithilfe des Lenkverhaltens gelöst werden (Hindernisvermeidung verwenden). Wenn Ihr Hindernis bei der Off-Chance so groß ist, dass es die Fahrt von einem Navi-Poly zum nächsten ausfüllt oder vollständig blockiert, können Sie auf diese Weise nach diesem Randfall suchen und den Pfad zwischen dem Poly, in dem Sie sich gerade befinden, und dem neu berechnen eine, von der du abgesperrt bist.

Ray Dey
quelle