Pathfinding con NavMesh, A* y flow field para 200 agentes

Doscientos agentes atascados en una sola puerta

A finales del año pasado estaba trabajando en una escena de asedio: una única puerta de castillo y 200 instancias de NavMeshAgent corriendo hacia ella. La navegación en la IA de videojuegos se rompe justo en escenas así. La grabación que QA adjuntaba a la build nocturna se congelaba siempre en el mismo punto: a quince metros de la puerta, unos sesenta agentes se rozaban entre sí y temblaban, y algunos incluso caminaban hacia atrás. En los primeros diez segundos apenas unos cuarenta llegaban al patio que hay detrás de la puerta.

El tiempo de frame era de 11 ms mientras los agentes estaban lejos y subía a 26 ms cuando se acercaban a la puerta. Mi primera sospecha fue que A* se había desbordado. El profiler no me dio la razón: NavMesh.CalculatePath sumaba 3,2 ms mientras que la actualización interna del propio NavMeshAgent se quedaba en 9,8 ms. Es decir, el cuello de botella no estaba en la búsqueda, sino en el trabajo que cada agente hace en cada frame.

Había dos problemas distintos apareciendo a la vez y confundidos en uno solo: el coste de calcular la ruta global y el comportamiento de los agentes entre sí. Cualquier discusión que meta ambos bajo el mismo título se queda encallada, porque las soluciones viven en sitios completamente distintos. Hasta que no los separas, nunca sabes qué ajuste movió qué número. En nuestro caso la separación empezó con una costumbre: seguir por separado la línea de la búsqueda y la línea de actualización de agentes en el profiler.

Dónde mira realmente el NavMesh

Un NavMesh es una malla de triángulos horneada a partir de la superficie transitable de tu escena, retraída desde cada borde por el radio del agente. La zona por la que un agente puede caminar no es el suelo que ves en el viewport. Cuando llega un reporte de agente atascado, lo primero es hacer visible la malla en la ventana de Navigation y medir cuántos centímetros de pasillo sobreviven de verdad en el umbral de la puerta. Con el Voxel Size por defecto de 0,166 m he visto más de una vez desaparecer polígonos sueltos en esquinas cerradas.

El hueco de nuestra puerta era de 1,6 m y el Agent Radius de 0,5 m, lo que dejaba un único carril de 0,6 m: cabe un agente, no caben dos. Bajar el radio a 0,35 parecía la solución fácil, pero hacía que los agentes se metieran dentro de los muros en todo el mapa. Ensanchar la puerta a 2,4 m desde el lado del nivel fue el cambio correcto. El radio del agente no es un ajuste estético: es la unidad base de toda tu navegación.

La segunda trampa clásica es un destino que cae fuera de la malla. SetDestination devuelve false en ese caso y nadie comprueba el valor de retorno; o la ruta llega como NavMeshPathStatus.PathPartial, así que el agente camina hasta el punto alcanzable más cercano y se queda allí esperando. Desde fuera eso se lee como «atascado». Ajustar cada destino a la malla con NavMesh.SamplePosition en un radio de 2 m cerró la mayoría de esos reportes. Aplica la misma comprobación a los puntos de spawn; un agente que nace fuera de la malla está perdido desde su primer frame.

Las discontinuidades como escaleras, huecos y vanos necesitan off-mesh links. Los componentes OffMeshLink colocados a mano se comportan de forma mucho más predecible que los generados automáticamente. Con el coste por defecto de 1.0, 140 de nuestros 200 agentes intentaban embudarse por un único hueco de 1,2 m; poner costOverride a 5.0 empujó a la mayoría hacia la ruta más larga pero despejada. Mantén los dos extremos del link sobre la malla; un link con un extremo colgando en el aire se ignora en silencio.

El coste de A* y el pathfinding jerárquico

El coste del A* pathfinding crece con el número de nodos que expande. En un NavMesh de 41.000 polígonos, una petición de un extremo del mapa al otro costaba 0,35 ms. Doscientos agentes pidiendo en el mismo frame serían 70 ms, pero nunca ves un tirón así: Unity encola las peticiones, la ruta llega tres o cuatro frames tarde y mientras tanto los agentes siguen corriendo con el rumbo antiguo. El síntoma no es un parón, es un giro tardío.

El pathfinding jerárquico parte ese coste por la mitad dos veces. Divides el mapa en regiones y escribes las transiciones entre ellas en un grafo de portales; la búsqueda corre primero sobre un grafo grueso de 30-40 nodos (0,02 ms) y después un A* detallado llega solo hasta el siguiente portal. Nuestra petición media bajó de 0,35 ms a 0,06 ms, y nunca volvimos a calcular de golpe la ruta completa de un agente. El grafo grueso se construye una vez en el bake y solo se actualiza en tiempo de ejecución cuando un obstáculo dinámico cierra un portal.

La alternativa que probamos y descartamos fue una caché de rutas compartida. Redondeábamos los destinos a celdas de 4 m y entregábamos una sola ruta a todos los agentes que iban a la misma celda. La tasa de acierto era del 70% contra objetivos estáticos, pero caía al 18% persiguiendo al jugador, y la lógica de invalidación devolvía más de lo que la caché ahorraba. Borramos el código. Compartir rutas solo se gana su sitio donde el destino se queda quieto durante decenas de frames.

Un solo flow field para toda la multitud

Si 200 agentes comparten destino, lanzar 200 búsquedas separadas no tiene sentido. Un flow field ejecuta una única propagación de coste hacia atrás desde el objetivo y luego escribe en cada celda un vector de dirección que apunta a su vecino más barato. El nuestro era una rejilla de 128x128 con celdas de 0,5 m, y una reconstrucción completa costaba 4,1 ms. La propagación rellena todas las celdas en una sola pasada, así que el coste es completamente independiente de cuántos agentes tengas.

Lo importante es que esos 4,1 ms se pagan cuando cambia la celda objetivo, no en cada frame. Mientras el jugador corría eso pasaba tres o cuatro veces por segundo, o sea unos 14 ms por segundo. El coste por agente se desploma hasta dos muestreos bilineales: 0,004 ms, es decir 0,8 ms para los 200 agentes. La misma multitud costaba 12 ms con A* jerárquico.

El límite es nítido: cada destino distinto significa otro campo. Pasados tres o cuatro objetivos, la memoria y el coste de reconstrucción superan al A*. Por eso nos quedamos en un híbrido, con los NPC con nombre y los agentes jefe en A* y la simulación de multitud en el flow field. Ambos se apoyan en los mismos triángulos del NavMesh; solo cambia el origen del rumbo. La separación vive en un único bool en el código y un diseñador puede cambiarla desde el prefab.

El local avoidance no es navegación global

RVO, y ORCA que deriva de él, hace una sola cosa: cada agente lee la posición y la velocidad de sus vecinos, recorta con semiplanos las velocidades que llevan a una colisión y elige, dentro de lo que queda, lo más parecido a su velocidad preferida. Su horizonte es de uno o dos segundos y no sabe nada de la geometría del nivel. Es una corrección de rumbo, no navegación. Deja a un agente a solas con él y RVO nunca lo llevará al objetivo.

Por eso esperar una solución global del local avoidance está mal desde el principio. Contra un muro de patio en forma de U, RVO pega el agente a la pared y dos agentes que se encuentran de frente se bloquean. Poner obstacleAvoidanceType en HighQuality no lo arregla; solo se come 6,2 de los 9,8 ms repartidos entre 200 agentes. Bajarlo a Good lo dejó en 3,9 ms sin ninguna diferencia visible a distancia de cámara.

La victoria real estaba en el campo avoidancePriority. Con todos los agentes en el valor por defecto de 50, la situación se mantiene simétrica y nadie cede el paso. Repartir una prioridad aleatoria entre 0 y 99 en el spawn redujo el atasco en la puerta de 4,2 segundos a 1,1 segundos. Fue un cambio de una línea.

Obstáculos dinámicos y presupuesto de peticiones

Los obstáculos dinámicos usan NavMeshObstacle con carving, pero el carving vuelve a hornear el tile en cada movimiento. Con 12 barriles rodando por la escena veíamos picos regulares de 5,8 ms. Subir carvingMoveThreshold a 0,5 m y activar carveOnlyStationary dejó esa misma escena en 0,9 ms. Nunca conviertas en obstáculo algo que se mueve de forma continua; eso es trabajo del local avoidance.

La parte del presupuesto es simple: fija cuántas peticiones de ruta completa se permiten por frame. La nuestra son 12. Los agentes piden con un intervalo de 0,45 segundos más un desfase aleatorio de 0 a 0,15 segundos, porque sin ese jitter la oleada de spawn mete todas las peticiones en el mismo frame. Cuando el presupuesto está lleno la petición no se cancela, se desliza al frame siguiente, y nadie lo nota porque mientras tanto el agente sigue caminando por su ruta actual. Mide ese presupuesto en tu hardware objetivo; los 12 que usamos en consola se quedan cómodamente en 30 en escritorio.

En esta escena el tiempo total de frame pasó de 26 ms a 13,4 ms y la parte del pathfinding de 13 ms a 2,1 ms, y la victoria más barata de todas fue el cambio de prioridad de una línea. Ordena el trabajo así: primero verifica con tus propios ojos la geometría del NavMesh, después pon un presupuesto de peticiones por frame, después mueve la multitud a un flow field y toca los ajustes de local avoidance al final. Ve en orden inverso y se te irán las horas en parámetros de ORCA mientras el vano de 0,6 metros sigue exactamente donde estaba. No cambies un ajuste que no hayas medido; todos los números de aquí salieron del profiler, ninguno de una suposición.