Navigationsnetz - Navigation mesh

Ein Navigationsnetz oder Navmesh ist eine abstrakte Datenstruktur, die in Anwendungen mit künstlicher Intelligenz verwendet wird, um Agenten bei der Wegfindung durch komplizierte Räume zu unterstützen. Dieser Ansatz ist seit mindestens Mitte der 1980er Jahre in der Robotik bekannt , wo er als Wiesenkarte bezeichnet wurde und im Jahr 2000 in der Videospiel-KI populär wurde .

Beschreibung

Ein Navigationsnetz ist eine Sammlung zweidimensionaler konvexer Polygone (ein Polygonnetz ), die definieren, welche Bereiche einer Umgebung von Agenten durchquert werden können. Mit anderen Worten, ein Charakter in einem Spiel kann frei in diesen Bereichen herumlaufen, ohne von Bäumen, Lava oder anderen Barrieren, die Teil der Umwelt sind, behindert zu werden. Benachbarte Polygone sind in einem Diagramm miteinander verbunden .

Die Pfadfindung innerhalb eines dieser Polygone kann trivial in einer geraden Linie erfolgen, da das Polygon konvex und durchquerbar ist. Die Pfadfindung zwischen Polygonen im Netz kann mit einem der zahlreichen Graphensuchalgorithmen wie A * erfolgen . Agenten auf einem Navmesh können somit rechenintensive Kollisionserkennungsprüfungen mit Hindernissen vermeiden , die Teil der Umgebung sind.

Die Darstellung von durchfahrbaren Bereichen in einer 2D-ähnlichen Form vereinfacht Berechnungen, die ansonsten in der "echten" 3D-Umgebung durchgeführt werden müssten. Im Gegensatz zu einem 2D-Raster sind jedoch durchfahrbare Bereiche möglich, die sich in unterschiedlichen Höhen über und unter überlappen. Die Polygone verschiedener Größen und Formen in Navigationsnetzen können beliebige Umgebungen mit größerer Genauigkeit darstellen als normale Gitter.

Schaffung

Navigationsnetze können manuell, automatisch oder durch eine Kombination aus beiden erstellt werden. In Videospielen kann ein Level-Designer die Polygone des Navmesh in einem Level-Editor manuell definieren . Dieser Ansatz kann sehr arbeitsintensiv sein. Alternativ könnte eine Anwendung erstellt werden, die die Ebenengeometrie als Eingabe verwendet und automatisch ein Navmesh ausgibt.

Es wird allgemein angenommen, dass die von einem Navmesh dargestellte Umgebung statisch ist - sie ändert sich nicht im Laufe der Zeit - und daher kann das Navmesh offline erstellt und unveränderlich sein. Es wurden jedoch einige Untersuchungen zur Online-Aktualisierung von Navigationsnetzen für dynamische Umgebungen durchgeführt.

Geschichte

In der Robotik wurde die Verwendung verknüpfter konvexer Polygone auf diese Weise als "Wiesenkartierung" bezeichnet, die in einem technischen Bericht von Ronald C. Arkin aus dem Jahr 1986 geprägt wurde .

Navigationsnetze in der künstlichen Intelligenz von Videospielen werden normalerweise Greg Snooks 2000er Artikel "Vereinfachte 3D-Bewegung und Wegfindung mithilfe von Navigationsnetzen" in Game Programming Gems zugeschrieben . Im Jahr 2001 beschrieb JMP van Waveren eine ähnliche Struktur mit konvexen und verbundenen 3D-Polygonen, die als "Area Awareness System" bezeichnet wird und für Bots in der Quake III Arena verwendet wird .

Anmerkungen

Verweise

  • Arkin, Ronald C. (1986). "Pfadplanung für einen visionären autonomen Roboter" (PDF) (Technischer Bericht). Universität von Massachusetts. Zitierjournal benötigt |journal= ( Hilfe )
  • Brand, Sandy (2009). Effiziente Hindernisvermeidung durch autonom erzeugte Navigationsnetze (PDF) (Masterarbeit). Technische Universität Delft . Abgerufen am 09.06.2015 .
  • Golodetz, Stuart (Oktober 2013). "Automatische Generierung von Navigationsnetzen im Konfigurationsbereich" . Überlastung . AKKU. 117 .
  • Snook, Greg (2000). "Vereinfachte 3D-Bewegung und Wegfindung mithilfe von Navigationsnetzen". In DeLoura, Mark (Hrsg.). Juwelen der Spielprogrammierung . Charles River Media. S. 288–304. ISBN   1-58450-049-2 .
  • Tozour, Paul (2002). "Erstellen eines nahezu optimalen Navigationsnetzes". In Rabin Steve (Hrsg.). AI Game Programming Weisheit . Charles River Media. pp.  171 -185. ISBN   1-58450-077-8 .
  • van Toll, Wouter G.; Cook IV, Atlas F.; Geraerts, Roland (2012). "Ein Navigationsnetz für dynamische Umgebungen" (PDF) . Computeranimation und virtuelle Welten . John Wiley & Sons. 23 (6): 535–546. doi : 10.1002 / cav.1468 . S2CID   2996937 . Abgerufen am 09.06.2015 .
  • van Waveren, JMP (28.01.2001). Der Quake III Arena Bot (PDF) (Diplomarbeit). Technische Universität Delft.

Externe Links