Trucos de A* para encontrar rutas en videojuegos
Desarrolladores de videojuegos y entusiastas de algoritmos intercambian técnicas para hacer que el pathfinding con A* sea rápido, creíble y escalable en todo, desde pequeños juegos 2D hasta enormes batallas RTS y city builders. Exploran grafos jerárquicos, ajustes de heurística, estructuras de datos alternativas y enfoques híbridos (como flow fields, comportamientos de steering y rutas a nivel de grupo) para lidiar con obstáculos dinámicos, grandes cantidades de agentes y conocimiento limitado del mapa. Varios comentaristas también señalan métodos más avanzados o especializados —jerarquías de contracción, heurísticas diferenciales, enfoques basados en RL y planificación al estilo GOAP—, destacando cómo un problema “resuelto” como el pathfinding sigue ocultando un espacio profundo de diseño y optimización.
Aprendizaje por Refuerzo vs. Pathfinding Clásico
- Algunos se preguntan si una pequeña política de RL (NN o árbol de decisión) podría reemplazar a A*, posiblemente con menos casos límite hechos a mano.
- Otros argumentan que solo aprendería un A* peor, con fallos más difíciles de depurar, reflejando una inquietud más amplia sobre los sistemas aprendidos opacos.
Más allá de A* básico y direcciones de investigación
- Se mencionan múltiples métodos avanzados: jerarquías de contracción, variantes dependientes del tiempo, búsqueda jerárquica, A* bidireccional, landmarks, reach, transit nodes, arc flags, heurísticas diferenciales, etc.
- Se citan varios artículos de revisión, clases y charlas; algunos se califican de desactualizados, con la afirmación de que el campo ha avanzado rápidamente.
Trucos de comportamiento para enemigos “inteligentes”
- Retrasar el re-cálculo de ruta y aleatorizar los intervalos de actualización hace que los enemigos parezcan “titubear” o poder ser engañados, y además ahorra CPU.
- Apuntar a casillas por delante del jugador produce un comportamiento de “corte” (por ejemplo, como los fantasmas de Pac‑Man).
- Usar rutas de A* como guía para el steering (atajo por esquinas, suavizado) y breadcrumbs/caminos de feromonas produce un movimiento más orgánico.
Navegación jerárquica, a gran escala y multiagente
- Los grafos jerárquicos (ciudad / edificio / habitación, o calles frente a interiores) se usan ampliamente para mantener rápidas las consultas.
- Para muchos enemigos, se sugiere ejecutar Dijkstra desde el jugador y que cada enemigo siga los gradientes.
- En juegos de grandes formaciones (RTS, estilo Total War), se separa el pathfinding de largo alcance de la simulación local de multitudes; el A* por unidad se considera derrochador e irrealista.
- Se proponen flow fields y flocking/steering para el movimiento en grupo.
Optimización del rendimiento y de estructuras de datos
- Los trucos incluyen: colas de prioridad por cubetas, almacenar metadatos de búsqueda en los nodos, pathfinding asíncrono/fuera del hilo principal, limitar nodos por tick y el preprocesamiento de todos contra todos (por ejemplo, Floyd–Warshall en cuadrículas pequeñas).
- MPAA (multipath adaptive A*) es elogiado por su reutilización incremental; JPS (jump point search) recibe opiniones mixtas por su sobrecarga.
Representación del mapa, costes y casos límite
- Debate sobre búsqueda basada en píxeles frente a basada en tiles; los tiles reducen el trabajo cuando el movimiento está alineado a tiles, pero pueden ser necesarios píxeles más finos en caso contrario.
- Los metadatos precomputados (distancia al obstáculo más cercano, bitmasks de salida) aceleran las comprobaciones de colisión y el pathfinding.
- Manejar teletransportadores, costes de terreno variables, regiones convexas y múltiples modos de movimiento se considera complicado.
- La ruptura de empates de A*, los obstáculos en forma de C y las búsquedas de “nunca rendirse” se identifican como errores comunes, con bugs de juegos reales citados (por ejemplo, mobs o animales atascados para siempre).
A* más allá del movimiento
- A* y búsquedas relacionadas también se aplican a grafos de decisión/planificación (GOAP, búsqueda estratégica), no solo a mapas espaciales, dando una sensación unificada de “planificación” a la IA de los juegos.