Was sind die Nachteile und / oder Einschränkungen von Navigationsnetzen? [geschlossen]

8

Ich habe viele Materialien zu Navigationsnetzen, was sie sind, ihre Vorteile gegenüber Grafiken, die aus Wegpunkten bestehen usw. Ich habe jedoch außer der offensichtlichen Zeit nicht viele Informationen über die Einschränkungen und Nachteile der Verwendung von Navigationsnetzen gesehen Sie müssen manuell erstellt werden (was durch Neufassung relativ gelöst wird).

Sicherlich ist dies keine völlig "magische" Technik, die sich ohne Nachteile präsentiert? Könnte jemand bitte erklären, welche Vor- und Nachteile die Verwendung eines Navigationsnetzes gegenüber einem Diagramm mit Wegpunkten hat? Oder mich in die richtige Richtung weisen?

path-finding navmesh Ray Dey
quelle

Antworten:

8

Nav-Netze stellen eine qualitative Verbesserung gegenüber Wegpunktgraphen dar, genauso wie A * eine natürliche Weiterentwicklung des Dijkstra-Algorithmus ist. In jedem Fall hat sich Ersteres aufgrund der Mängel des Letzteren weiterentwickelt und ist für die meisten Anwendungen ein völlig nützlicherer Algorithmus. Das Manko ist natürlich die Komplexität (Zeit und / oder Raum). Aber ich muss sagen, dass der Kompromiss zwischen Navigationsnetzen und Wegpunktgraphen gering ist (dh die Rechenkomplexität kann zunehmen, jedoch nicht um eine Größenordnung).

Der einzige praktische Vorteil bei der Verwendung von Wegpunktdiagrammen besteht darin, dass Sie die Bewegung tatsächlich auf exakte Linien anstatt auf Bereiche beschränken möchten. Wegpunktgraphen = Infinitesimalpunkte und Linien, während Navigationsnetze nur mit (konvexen) polygonalen Bereichen, die einen gültigen Raum beschreiben, der als "Territorium dieser Zelle" betrachtet wird, ähnlich sind. In beiden Fällen interpolieren Sie die Position einer KI-Entität von einem Knoten zum anderen. Der einzige Unterschied zu Navmeshes besteht darin, dass Sie dies von einem Punktort zum anderen tun, während Sie es bei Wegpunktdiagrammen von einem Punkt zum anderen tun und möglicherweise die Kante berücksichtigen, die die Knoten A und B trennt. Und natürlich Aus Sicht der Komplexität ist leicht zu erkennen, dass Wegpunktdiagramme in der Bedienung moderat billiger sind.

Im Laufe der Zeit scheinen Verbesserungen "kostenlos" zu sein (aus der individuellen Perspektive). Deshalb ist ein Computer, den Sie heute für X US-Dollar kaufen, um ein Vielfaches schneller als ein Computer, den Sie vor zehn Jahren zum gleichen Preis kaufen konnten. Der Punkt ist, es ist nicht wirklich kostenlos - irgendwo hat jemand F & E-Anstrengungen unternommen. Gleiches gilt für Algorithmen. Und deshalb bleibt ältere Technik meist auf der Strecke.

Ingenieur
quelle
3
Ihre Antwort ist größtenteils gut, aber ich würde wirklich gerne ein Zitat für "Selbst auf der Ebene der tierischen Neuronen wird [Pfadfindung] als eine Art Grafik dargestellt, die die Idee eines Ortes mit der Idee eines anderen durch Assoziation verbindet, und bald." Es ist eine sehr starke Behauptung, die ich noch nie gehört habe.
1
"Sind darstellbar" und "sind darstellbar" sind überhaupt nicht dasselbe. Die Beziehung zwischen Denken und Neuronenstruktur ist keine direkte Abbildung (offensichtlich - Neuronen, die rot signalisieren, sind selbst nicht rot). Wie auch immer, Ihre Bearbeitung ist eine weitaus einfachere Behauptung.
Vielen Dank für die informative Antwort. Mir ist klar, dass alle praktischen Beispiele für die Pfadfindung Diagramme verwenden, und ich habe vermutet, dass möglicherweise ein Problem mit der Zeit- / Speicherkomplexität vorliegt. Ich habe mich jedoch gefragt, ob es einen Randfall gibt, in dem man ein Navmesh nicht effektiv nutzen kann - im Nachhinein denke ich, dass ich das vielleicht überlegt habe. Wenn Sie nach den Einschränkungen von Navigationsnetzen fragen, werden Sie höchstwahrscheinlich nach den Einschränkungen eines Diagramms als Form der Weltdarstellung gefragt. Nur noch eine Sache, wenn Sie möglicherweise auf ein Beispiel für kollaborative Diffusion verweisen könnten, würde ich es wirklich schätzen! Danke noch einmal.
Ray Dey
-1, weil du die Frage nicht wirklich beantwortet hast. Sie sagten, Navmeshes seien eine qualitative Verbesserung, aber das Originalplakat wollte wissen, was diese Eigenschaften sind.
Kylotan
@Kylotan: Nein, in der Tat heißt es in der Frage "Ich habe viele Materialien zu Navigationsnetzen [und] deren Vorteilen".
0

Navigationsnetze sind auf Oberflächen beschränkt, während Wegpunkte überall platziert werden können und eine beliebige Anzahl von Verbindungen (Kanten) in jede Richtung herstellen können. So können Wegpunkte eine allgemeinere und flexiblere Lösung bieten, beispielsweise für Spiele mit abstrakten oder außergewöhnlichen Einheiten oder Umgebungen.

Acey
quelle