Hispanopedia WikiUna malla de navegación , o navmesh , es una estructura de datos abstracta que se utiliza en aplicaciones de inteligencia artificial para ayudar a los agentes a encontrar rutas en espacios complicados. Este enfoque se conoce desde al menos mediados de los años 1980 en robótica , donde se lo ha llamado mapa de pradera [1] , y se popularizó en la IA de los videojuegos en el año 2000.
Descripción
Una malla de navegación es una colección de polígonos convexos bidimensionales (una malla poligonal ) que define qué áreas de un entorno pueden atravesar los agentes. En otras palabras, un personaje de un juego podría caminar libremente dentro de estas áreas sin obstáculos de árboles, lava u otras barreras que forman parte del entorno. Los polígonos adyacentes están conectados entre sí en un gráfico .
La búsqueda de rutas dentro de uno de estos polígonos se puede realizar de manera trivial en una línea recta porque el polígono es convexo y transitable. La búsqueda de rutas entre polígonos en la malla se puede realizar con uno de los numerosos algoritmos de búsqueda de grafos , como A* . [2] De este modo, los agentes en una malla de navegación pueden evitar comprobaciones de detección de colisiones con obstáculos que forman parte del entorno, que requieren un gran esfuerzo computacional .
La representación de áreas transitables en una forma similar a la 2D simplifica los cálculos que de otro modo se tendrían que realizar en el entorno 3D "real", pero a diferencia de una cuadrícula 2D, permite áreas transitables que se superponen arriba y abajo a diferentes alturas. [3] 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. [4]
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 la malla de navegación en un editor de niveles . Este enfoque puede requerir mucho trabajo. [5] Como alternativa, se puede crear una aplicación que tome la geometría del nivel como entrada y genere automáticamente una malla de navegación.
Se suele suponer que el entorno representado por una malla de navegación es estático (no cambia con el tiempo) y, por lo tanto, la malla de navegación se puede crear sin conexión y es inmutable. Sin embargo, se han realizado algunas investigaciones sobre la actualización en línea de mallas de navegación para entornos dinámicos. [6]
Historia
En robótica, el uso de polígonos convexos vinculados de esta manera se ha denominado "mapeo de pradera", [1] 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 suelen atribuirse al artículo de Greg Snook de 2000 "Simplified 3D Movement and Pathfinding Using Navigation Meshes" en Game Programming Gems . [8] En 2001, JMP van Waveren describió una estructura similar con polígonos 3D convexos y conectados, denominada "Area Awareness System", utilizada para bots en Quake III Arena . [9]
Notas
- ^Ab Tozour 2002, pág. 171.
- ^ Snook 2000, págs. 294-295.
- ^ Snook 2000, pág. 289.
- ^ Marca 2009, pág. 4.
- ^ Marca 2009, pág. 10.
- ^ van Toll, Cook IV y Geraerts 2012.
- ^ Arkin 1986.
- ^ Golodetz 2013.
- ^ van Waveren 2001, pág. 24–46.
Referencias
- Arkin, Ronald C. (1986). "Planificación de trayectorias para un robot autónomo basado en visión" (PDF) (Informe técnico). Universidad de Massachusetts.
{{cite journal}}: Requiere citar revista|journal=( ayuda ) - Brand, 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 malla de navegación en el espacio de configuración". Sobrecarga . 117 . ACCU.
- Snook, Greg (2000). "Movimiento 3D simplificado y búsqueda de rutas mediante mallas de navegación". En DeLoura, Mark (ed.). Joyas de la programación de juegos . Charles River Media. págs. 288–304. ISBN 1-58450-049-2.
- Tozour, Paul (2002). "Construcción de una malla de navegación casi óptima". En Rabin, Steve (ed.). Sabiduría sobre programación de juegos de IA . Charles River Media. págs. 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 . 23 (6). John Wiley & Sons: 535–546. doi :10.1002/cav.1468. S2CID 2996937 . Consultado el 9 de junio de 2015 .
- van Waveren, JMP (28 de enero de 2001). El robot de Quake III Arena (PDF) (tesis de maestría). Universidad Tecnológica de Delft.
Enlaces externos
- UDK: Referencia de malla de navegación
- Unity: descripción general de la navegación
- Motor de origen: mallas de navegación
- Urho3D: Navegación
- Navegación con el motor Godot
- Navegación y IA con Cry Engine