Resumen Técnico: Validación de Navmesh usando Geometría: Análisis Basado en Vóxeles con Exploración Priorizada

Enunciado del Problema

Las mallas de navegación (navmeshes) son fundamentales para el movimiento de los personajes no jugables (NPC) en videojuegos, definiendo las regiones transitables y la conectividad. Sin embargo, en el desarrollo de juegos a gran escala, los entornos son dinámicos; el terreno, los activos y la geometría de colisión cambian con frecuencia. En consecuencia, las navmeshes a menudo no se regeneran en perfecta sincronía con estos cambios, lo que genera discrepancias entre los datos de navegación y el espacio realmente transitable definido por la geometría subyacente.

Los métodos de validación automatizada existentes suelen depender de la exploración basada en agentes (por ejemplo, agentes de aprendizaje por refuerzo que navegan por el mundo) o del análisis del comportamiento en tiempo de ejecución. Estos enfoques infieren problemas indirectamente, como un agente que queda atrapado o falla al alcanzar un objetivo, en lugar de verificar explícitamente si la representación de navegación refleja con precisión la geometría real. Además, estos métodos son computacionalmente costosos, difíciles de integrar en pipelines automatizados y a menudo no detectan inconsistencias estructurales que no se manifiestan inmediatamente como fallos en tiempo de ejecución. Existe una falta de métodos directos y fuera de línea para validar la corrección de la navmesh independientemente de la simulación en tiempo de ejecución.

Metodología

El artículo propone un marco fuera de línea que trata la validación de navmesh como un problema de consistencia geométrica. En lugar de simular el comportamiento del agente, el sistema reconstruye de forma independiente el espacio transitable a partir de la geometría del entorno y lo compara con la navmesh generada por el motor. La metodología consta de tres componentes principales:

1. Reconstrucción del Espacio Transitable Basada en Vóxeles

El sistema reconstruye una referencia independiente del espacio transitable directamente desde el terreno y la geometría de colisión utilizando una representación basada en vóxeles:

• Voxelización: Los mapas de altura del terreno y las mallas de colisión de los activos se convierten en una cuadrícula 3D discreta de vóxeles.
• Clasificación Consciente de Restricciones: Cada vóxel se evalúa frente a restricciones de navegación (límites de pendiente, altura de escalón, radio del agente y despeje vertical) derivadas de la configuración del motor del juego. Los vóxeles que no cumplen estas restricciones se descartan.
• Grafo de Conectividad: Los vóxeles transitables restantes forman un grafo $G_v = (V_w, E)$, donde la adyacencia se determina por el radio de vecindad. Un algoritmo de relleno (flood-fill) extrae el componente conectado principal para eliminar artefactos aislados, dando como resultado un modelo de alcanzabilidad derivado de la geometría $R_{vox}$.

2. Exploración Priorizada Guiada por Aprendizaje

Dado que la validación exhaustiva de grandes espacios de vóxeles es computacionalmente prohibitiva, el marco formula la exploración como un problema de búsqueda priorizada:

• Aprendizaje por Refuerzo (RL): Una Red Doble Q-Profunda (DDQN) se entrena para guiar el proceso de muestreo. El agente de RL no simula la navegación; más bien, aprende una política para priorizar regiones con una mayor probabilidad de contener inconsistencias.
• Estado y Recompensa: El estado incluye el contexto geométrico local, la importancia semántica (por ejemplo, proximidad a rutas de patrulla o puntos de aparición) e historial de exploración. La función de recompensa fomenta la visita a regiones semánticamente importantes mientras penaliza los pasos redundantes y las re-visitas.
• Reproducción de Experiencia Priorizada: El proceso de entrenamiento utiliza reproducción de experiencia priorizada para centrarse en transiciones asociadas con regiones de alto valor o estructuralmente complejas, acelerando la convergencia.

3. Validación de Consistencia

Para cada ubicación muestreada por la política guiada por RL:

• El sistema consulta al motor para determinar la alcanzabilidad en la navmesh generada ($R_{nav}$).
• Compara $R_{nav}$ con la alcanzabilidad derivada de la geometría $R_{vox}$.
• Una discrepancia ($R_{nav} \neq R_{vox}$) señala una posible inconsistencia.
• Post-procesamiento: Las inconsistencias detectadas sufren un filtrado basado en tolerancia y agrupamiento espacial (análisis de componentes conectados) para eliminar artefactos menores causados por la discretización de vóxeles, reteniendo solo las regiones de defectos estructuralmente significativas.

Contribuciones Clave

1. Formulación de Consistencia Geométrica: El artículo formula la validación de navmesh como una comparación directa entre la transitabilidad derivada de la geometría y la conectividad de la navmesh, desacoplando la validación del comportamiento del agente y la simulación en tiempo de ejecución.
2. Modelo de Referencia Basado en Vóxeles: Introduce una representación basada en vóxeles consciente de restricciones que reconstruye el espacio transitable a partir de datos crudos de terreno y colisión, sirviendo como una verdad fundamental independiente para la validación.
3. Exploración Guiada por Aprendizaje: El trabajo demuestra el uso del aprendizaje por refuerzo no para la simulación de navegación, sino para priorizar la exploración. Este enfoque mejora significativamente la eficiencia de la validación al centrar el muestreo en regiones propensas a contener defectos, superando a las estrategias de muestreo uniforme y heurístico.
4. Pipeline Listo para Producción: El marco está diseñado como una herramienta fuera de línea integrada dentro del motor del juego, capaz de procesamiento paralelo e integración en flujos de trabajo automatizados de aseguramiento de calidad para entornos a gran escala y en evolución.

Resultados Experimentales

El marco fue evaluado en múltiples entornos de producción a gran escala utilizando tanto los motores Unity como Anvil de Ubisoft.

• Eficiencia: La estrategia priorizada guiada por aprendizaje requirió aproximadamente un 45% menos de muestras que la traversía exhaustiva (BFS/DFS) y un 24% menos de muestras que el muestreo basado en importancia heurística para lograr niveles de cobertura similares (85% de cobertura ponderada por importancia).
• Detección: Si bien las tasas de detección fueron comparables entre los métodos (oscilando entre ~87% y ~92.6%), el método propuesto logró la tasa de detección más alta (92.6%) con la menor cantidad de muestras (55% de la línea base).
• Falsos Positivos: El enfoque de RL priorizado mantuvo una tasa baja de falsos positivos (4.1%), comparable o mejor que otras estrategias, gracias al post-procesamiento de filtrado basado en tolerancia y agrupamiento.
• Escalabilidad: Se demostró que los tiempos de reconstrucción y validación son prácticos para su uso en producción, completando la validación completa de grandes regiones en 1–7 minutos.

Significado y Afirmaciones

El artículo afirma que este enfoque ofrece un método directo, determinista y repetible para validar la corrección de la navmesh. Al depender principalmente de la geometría y las consultas al motor, el método es adaptable a diferentes motores de juego con cambios mínimos.

El significado radica en cambiar el paradigma de "encontrar errores mediante fallos del agente" a "verificar la consistencia estructural mediante comparación geométrica". Esto permite la detección de errores de navegación que podrían no causar inmediatamente que un agente quede atrapado, pero que representan una discrepancia fundamental entre el diseño del mundo y los datos de navegación. El marco permite un aseguramiento de calidad automatizado y escalable que puede mantener el ritmo de los ciclos de iteración rápidos del desarrollo moderno de juegos de mundo abierto, garantizando que los datos de navegación permanezcan sincronizados con el entorno del juego en evolución sin requerir costosas simulaciones en tiempo de ejecución.