Wie funktioniert die Wegfindung in Navigation Mesh?

27

Ich möchte verstehen, wie Navmeshes funktionieren, wie sie implementiert werden und warum sie besser sind als andere Arten von Pfadsystemen.

algorithm path-finding Feuer
quelle
Dies stellte sich im Verlauf meiner morgendlichen Internet-Streifzüge heraus: aigamedev.com/open/reviews/alienswarm-node-graph Könnte lesenswert sein :-)
coderanger
Dieses Tutorial kann für Unity-Benutzer nützlich sein, die auf diesen Beitrag stoßen
MichaelHouse

Antworten:

6

Es ist dasselbe wie Wegpunkt-Pfadfindung, nur dass Sie anstelle von Wegpunkten Wegpolygone haben und Sie daraus einige Dinge über Navimesh schließen können:

  • Wegepolygone sind Bereiche, in denen Entitäten sicher gehen können
    • andere Bereiche sollten wahrscheinlich nicht berücksichtigt werden
    • Wegpunkte müssen einen Glaubenssprung in den Raum zwischen ihnen machen; Erinnerst du dich an NPCs, die in Wänden stecken? Es war an Orten, an denen zwei Wegpunkte nicht direkt miteinander verbunden waren.
  • Es gibt möglicherweise weniger Knoten (weil Polygone größer sind)
    • Daher ist es höchstwahrscheinlich schneller
    • Daher ist der Speicherbedarf möglicherweise geringer
  • Es ist realistischer (weil die Fläche des Polygons theoretisch unendlich viele Punkte enthält)
user712092
quelle
2

Im Allgemeinen werden sie mit einer Art erweitertem A * -Algorithmus verwendet (berücksichtigt Jump- oder Fly-Links für die 3D-Pfadfindung). Auf diese Weise ist es nicht wirklich ein anderes System als alles andere, sondern eher eine Möglichkeit, ein normales Pfadfindungsnetzwerk direkt aus einer hochpolitischen (relativ gesehen) Umgebung oder einem Gelände zu generieren. Aus welchem ​​Grund auch immer wir sie hier als Beacons bezeichnen, aber die Idee ist dieselbe: Auf jeder Karte wird eine Art automatisierter Prozess ausgeführt, der eine einfache Reihe von Verbindungen erzeugt, auf denen in einem angemessenen Zeitraum A * ausgeführt werden kann. Wenn Sie versuchen würden, anhand der zugrunde liegenden Rohdaten einen Pfad zu finden, wäre dies aufgrund der Netzdichte zu langsam für ein Spiel.

coderanger
quelle
Ist das nicht ein Wegpunktdiagramm, außer wenn es auf einem vereinfachten Netz erstellt wurde? Ich dachte, mit Navmeshes kannst du auf Polygonen wandern.
Feuer
Mit dem vereinfachten Diagramm können Sie über große Entfernungen navigieren. Die kurze Reichweite wird normalerweise auf andere Weise behandelt. Es sieht so aus, als ob das Valve-System die Mesh-Daten für beide auf unterschiedliche Weise verwendet (Supernode-Routing vs. lokale Einschränkungen).
Coderanger
Ein einfacher Satz von Verbindungen ist doch kein Navmesh, oder? Ich dachte, es heißt navmesh, weil man auf Polygonen wandert.
Feuer
Ich denke nicht, dass lokale oder globale Navigation hier relevant ist.
Feuer
1
Eine Reihe benachbarter Polygone ist immer noch eine Grafik, genau wie eine Reihe von Wegpunkten, und Sie können A * auf die gleiche Weise darauf ausführen. Der einzige Unterschied besteht darin, dass Sie die Linien unterschiedlich zeichnen, sobald Sie wissen, durch welche Polygone Sie sich bewegen werden.
Coderanger
0

Es gibt viele Möglichkeiten, dies zu tun. Ein * und so ist eine gute Option, aber es fehlt an Dokumentation. Sie könnten Knoten quasi zufällig auf der Karte platzieren und prüfen, welche Knoten sich sehen können, und ein kleines Netz von Knoten aufbauen. Nicht das Optimalste, aber leicht zu verstehen.


quelle