Una malla de navegación , o navmesh , es una estructura de datos abstracta utilizada en aplicaciones de inteligencia artificial para ayudar a los agentes a encontrar caminos a través de espacios complicados. Este enfoque se conoce desde al menos mediados de la década de 1980 en robótica , donde se le ha llamado mapa de pradera , y se popularizó en la IA de videojuegos en 2000.
Descripción
Una malla de navegación es una colección de polígonos convexos bidimensionales (una malla poligonal ) que definen qué áreas de un entorno pueden atravesar los agentes. En otras palabras, un personaje en un juego podría caminar libremente dentro de estas áreas sin obstáculos por árboles, lava u otras barreras que son parte del entorno. Los polígonos adyacentes están conectados entre sí en un gráfico .
La búsqueda de caminos dentro de uno de estos polígonos se puede hacer de manera trivial en línea recta porque el polígono es convexo y transitable. La búsqueda de caminos entre polígonos en la malla se puede realizar con uno de los muchos algoritmos de búsqueda de gráficos , como A * . [1] Los agentes en un navmesh pueden evitar así comprobaciones computacionalmente costosas de detección de colisiones con obstáculos que forman parte del entorno.
La representación de áreas transitables en forma de 2D simplifica los cálculos que de otro modo tendrían que realizarse en el entorno 3D "verdadero", sin embargo, a diferencia de una cuadrícula 2D, permite áreas transitables que se superponen arriba y abajo a diferentes alturas. [2] Los polígonos de varios tamaños y formas en las mallas de navegación pueden representar entornos arbitrarios con mayor precisión que las cuadrículas regulares. [3]
Creación
Las mallas de navegación se pueden crear de forma manual, automática o mediante una combinación de ambas. En los videojuegos, un diseñador de niveles puede definir manualmente los polígonos de navmesh en un editor de niveles . Este enfoque puede ser bastante laborioso. [4] Alternativamente, se podría crear una aplicación que tome la geometría del nivel como entrada y genere automáticamente un navmesh.
Se asume comúnmente que el entorno representado por un navmesh es estático (no cambia con el tiempo) y, por lo tanto, el navmesh se puede crear fuera de línea y ser inmutable. Sin embargo, se ha investigado la actualización en línea de navmeshes para entornos dinámicos. [5]
Historia
En robótica, el uso de polígonos convexos enlazados de esta manera se ha denominado "mapeo de praderas", [6] acuñado en un informe técnico de 1986 por Ronald C. Arkin . [7]
Las mallas de navegación en la inteligencia artificial de los videojuegos generalmente se atribuyen al artículo de Greg Snook de 2000 "Movimiento 3D simplificado y búsqueda de rutas mediante mallas de navegación" en Game Programming Gems . [8] En 2001, JMP van Waveren describió una estructura similar con polígonos 3D convexos y conectados, apodado el "Sistema de Conciencia de Área", utilizado para bots en Quake III Arena . [9]
Notas
- ^ Snook 2000 , p. 294–295.
- ^ Snook 2000 , p. 289.
- ^ Marca 2009 , p. 4.
- ^ Marca 2009 , p. 10.
- ^ van Toll, Cook IV y Geraerts 2012 .
- ^ Tozour 2002 , p. 171.
- ^ Arkin 1986 .
- ^ Golodetz 2013 .
- ↑ van Waveren , 2001 , p. 24–46.
Referencias
- Arkin, Ronald C. (1986). "Planificación de ruta para un robot autónomo basado en la visión" (PDF) (Informe técnico). Universidad de Massachusetts. Cite journal requiere
|journal=
( ayuda ) - Marca, Sandy (2009). Evitación eficiente de obstáculos mediante mallas de navegación generadas de forma autónoma (PDF) (Tesis de maestría). Universidad Tecnológica de Delft . Consultado el 9 de junio de 2015 .
- Golodetz, Stuart (octubre de 2013). "Generación automática de mallas de navegación en el espacio de configuración" . Sobrecarga . ACCU. 117 .
- Snook, Greg (2000). "Movimiento 3D simplificado y búsqueda de caminos mediante mallas de navegación". En DeLoura, Mark (ed.). Gemas de programación de juegos . Charles River Media. págs. 288-304. ISBN 1-58450-049-2.
- Tozour, Paul (2002). "Construyendo una malla de navegación casi óptima". En Rabin, Steve (ed.). Sabiduría de programación de juegos de IA . Charles River Media. pp. 171 -185. ISBN 1-58450-077-8.
- van Toll, Wouter G .; Cook IV, Atlas F .; Geraerts, Roland (2012). "Una malla de navegación para entornos dinámicos" (PDF) . Animación por ordenador y mundos virtuales . John Wiley e hijos. 23 (6): 535–546. doi : 10.1002 / cav.1468 . S2CID 2996937 . Consultado el 9 de junio de 2015 .
- van Waveren, JMP (28 de enero de 2001). The Quake III Arena Bot (PDF) (tesis de maestría). Universidad Tecnológica de Delft.
enlaces externos
- UDK: referencia de malla de navegación
- Unidad: mallas de navegación
- Motor de origen: mallas de navegación
- Urho3D: Navegación
- Navegación del motor Godot
- Navegación e inteligencia artificial Cry Engine