- Para implementar la persecución de monstruos en un juego de 8 bits con vista cenital al estilo Zelda, no basta con un movimiento simple en línea recta, así que se comparan Dijkstra y A* para encontrar un punto medio práctico para el pathfinding en juegos
- El movimiento en línea recta se detiene al chocar con una pared, pero al añadir wall-sliding se puede seguir moviéndose a lo largo de la pared, lo que mejora la sensación de control y también puede crear elementos estratégicos al atrapar monstruos con el terreno
- El algoritmo de Dijkstra garantiza la ruta más corta, pero explora ampliamente alrededor del nodo inicial, por lo que en juegos donde el objetivo cambia en cada frame termina haciendo más cálculos de los necesarios para decidir la siguiente dirección
- A* prioriza la búsqueda según la distancia hasta el objetivo, así que primero revisa la dirección del objetivo y, si encuentra una pared, inspecciona los nodos cercanos sin volver a visitar los ya vistos, lo que le permite encontrar rutas alternativas
- En mapas de juego, se puede ajustar la velocidad y la dificultad de implementación usando un grafo implícito sin construir de antemano una lista de adyacencia, búsqueda por tiles y heurísticas basadas en la geometría como límites de profundidad por iteración
Contexto del juego y requisitos básicos
- En un juego de 8 bits con vista cenital al estilo Zelda basado en PPU466, los monstruos debían perseguir al jugador
- PPU466, al igual que una consola de fantasía como PICO-8, tiene restricciones de gráficos de 8 bits, 4 colores por tile, fondo fijo y una cantidad reducida de sprites
- El objetivo era que los monstruos siguieran al jugador sin quedarse simplemente bloqueados por una pared ni atrapados de formas no deseadas
Movimiento en línea recta y wall-sliding
- La forma más simple es trazar una línea recta entre el monstruo y el jugador y mover al monstruo en esa dirección
- Si solo se usa este método, el monstruo se detiene en cuanto toca una pared
- Al aplicar wall-sliding, en lugar de detenerse al chocar con una pared, se desplaza a lo largo de ella
- En el movimiento del jugador, es una técnica que hace más responsivos los controles cerca de paredes y esquinas, y se usa en casi todos los juegos
- Se ha usado desde Pac-Man, y Pac-Man Championship Edition DX+ incluso añade un efecto de chispas cuando el jugador hace wall-slide
- Si se combina wall-sliding con el movimiento en línea recta, es posible atrapar monstruos en ciertas formaciones del terreno
- Algunos juegos lo usan como elemento estratégico; un ejemplo es el safespotting de Runescape
- En este juego no era el comportamiento deseado, así que se evaluó un algoritmo de pathfinding real
Limitaciones del algoritmo de Dijkstra
- El algoritmo de Dijkstra es fácil de implementar y garantiza la ruta más corta
- El problema es que hace mucho más trabajo del necesario
- Encuentra la ruta más corta desde el nodo inicial hasta todos los demás nodos del grafo
- Puede detenerse al encontrar el nodo objetivo, pero no tiene forma de orientar la exploración hacia una dirección específica del destino
- En los videojuegos, el jugador se mueve constantemente, así que el objetivo del monstruo cambia en cada frame
- Lo que el monstruo necesita no es tanto la ruta completa, sino saber hacia qué dirección moverse ahora mismo
- Se pueden precalcular las rutas más cortas para todos los píxeles o tiles del mapa, pero eso consume mucha memoria
- En plataformas legacy o con recursos limitados, Dijkstra no resulta adecuado
Por qué A* encaja mejor en el pathfinding para juegos
- El algoritmo de búsqueda A* usa la distancia entre el nodo inicial y el destino para definir la prioridad de exploración
- En el primer paso, intenta priorizar la dirección que va en línea recta hacia el destino
- A diferencia de Dijkstra, no gasta mucho tiempo explorando la dirección opuesta si no hace falta
- Si una pared bloquea la ruta, examina los nodos cercanos para intentar rodearla
- Igual que Dijkstra, no vuelve a visitar nodos ya vistos, así que incluso si hace falta retroceder bastante, al final puede encontrar una ruta alternativa
- En el ejemplo, el monstruo que usa A* no se queda atrapado detrás de una pared
Estructura de datos de grafo implícito
- En los grafos de manual, los nodos se representan con una lista de nodos y una matriz de adyacencia o lista de adyacencia, pero en juegos se pueden definir nodos adyacentes de forma más flexible
- Por ejemplo, en una pantalla de 256×240 píxeles, cada coordenada de píxel puede considerarse un nodo
- Los píxeles adyacentes son arriba, abajo, izquierda, derecha y las 4 diagonales, es decir, 8 direcciones
- El costo de moverse en vertical u horizontal es 1, y el costo diagonal es √2, aproximadamente 1.4
- En lugar de construir de antemano una lista de adyacencia enorme, se puede generar sobre la marcha solo para los nodos que realmente se visitan
- Los píxeles sobre una pared o ocupados por otros sprites no son posiciones válidas para el monstruo, así que se excluyen dinámicamente de la lista de adyacencia
- Con este enfoque no hace falta excluir manualmente los nodos no transitables en el editor de mapas
Heurísticas que reflejan la geometría del mapa
- Algunas partes de A* se pueden ajustar directamente según la estructura geométrica del mapa
-
Tamaño de paso
- En lugar de usar píxeles como nodos, en un juego 2D basado en tiles se puede usar cada tile como nodo
- La búsqueda por tiles reduce mucho la cantidad de iteraciones necesarias para encontrar una ruta hasta el jugador y acelera la búsqueda
- En este caso, la ruta no es tanto una lista exacta de movimientos frame por frame, sino más bien una secuencia de direcciones que el monstruo debe seguir
- Como normalmente el monstruo no se mueve a una velocidad de 1 tile por frame, incluso con una ruta basada en tiles lo que realmente se necesita es la dirección para poder alcanzar al jugador
- Una ruta basada en píxeles también tiene ese mismo carácter, ya que el monstruo quizá no se mueve 1 píxel por frame ni en cantidades enteras de píxeles
-
Profundidad de iteración
- En A*, cuando un nodo sale de la cola de prioridad, ese nodo representa el último paso de la mejor ruta encontrada hasta ese momento
- Si se detiene el algoritmo tras una cantidad fija de iteraciones, se obtiene la mejor estimación actual de la ruta más corta hasta el destino
- No hace falta ejecutar el algoritmo hasta el final para obtener una dirección de avance razonable
- La profundidad máxima de iteración debe ajustarse a la geometría del nivel
- Si la profundidad es demasiado pequeña, el monstruo puede seguir quedándose atrapado detrás de una pared
- En el ejemplo, con una profundidad fija de 30 tiles, según la posición del jugador el monstruo queda atrapado y no puede avanzar
- Como A* se vuelve a calcular en cada frame, pueden aparecer bucles
- En el primer frame al llegar a la pared, calcula que debe ir hacia abajo
- En el siguiente frame, calcula que debe ir hacia arriba
- Al repetirse esto, el monstruo queda atrapado en un bucle
- Cuando el jugador entra en el rango de búsqueda del monstruo, ya se puede encontrar la ruta correcta
- Con una profundidad fija de
1, este fenómeno se vuelve todavía más extremo, y el monstruo sigue regresando al píxel con menor distancia euclidiana respecto al jugador
El punto medio del precálculo
- Para hacerlo más refinado, se puede precalcular la profundidad máxima que A* necesita para encontrar una ruta desde cualquier posición del mapa
- A diferencia del precálculo completo de rutas al estilo Dijkstra, solo hace falta almacenar ese valor máximo
- Con esa profundidad máxima, A* puede encontrar una ruta válida en tiempo real
1 comentarios
Comentarios de Hacker News
Trucos que usé con A* en un MMO en producción: 1) si tenés grafos jerárquicos, como a nivel de ciudad, entre habitaciones dentro de un edificio y dentro de una habitación, podés buscar una ruta desde un punto en una habitación de cierto edificio de cierta ciudad hasta otro punto en una fracción de milisegundo
2) Si guardás los metadatos de la búsqueda A* actual en los propios nodos del grafo, no hace falta mantener un arreglo asociativo separado
3) Es mejor no seguir la ruta resultante tal cual, sino usarla como entrada para un comportamiento de dirección que intente recortar esquinas hacia el siguiente nodo de la ruta cuando sea posible. Si la ruta va hacia otro personaje, hacé que el personaje objetivo vaya dejando “migas de pan” y agregalas a la ruta cuando la nueva posición no sea alcanzable en línea recta desde el último nodo de la ruta
2b) Esto se comprime en una máscara de bits de 16 bits. Son 8 fragmentos de 2 bits, es decir, 8 direcciones, y se guardan en una tabla hash
2c) Cada fragmento de bits tiene cuatro estados: FULL_BLOCK (pared), HARD_BLOCK (objeto grande que impide atravesar el tile desde cualquier dirección), SOFT_BLOCK (objeto pequeño que bloquea el paso por una esquina), NO_BLOCK (tile vacío o con un objeto muy pequeño)
Con esto, cuando una unidad dentro de un edificio busca una ruta, no tiene que revisar obstáculos en cada tile. Si el objeto no es enorme y, por su rotación, no bloquea las esquinas de entrada y salida, se puede atravesar incluso un tile con un objeto. Por último, para que la simulación no se rompa cuando el jugador se olvida de colocar puertas, los agentes también pueden atravesar paredes
https://store.steampowered.com/app/2287430/Metropolis_1998/
Mientras el personaje esté dentro de esa “burbuja”, se puede omitir por completo la detección de colisiones con el mundo
En la universidad no entendía por qué A* era tan difícil en los RTS, pero cuando vi la explicación de que, para que las unidades no se atraviesen entre sí, todo lo que se mueve tiene que esquivar constantemente a todas las demás unidades y recalcular rutas, empecé a respetar mucho más a Command & Conquer
Personalmente lo evitaría salvo que hubiera una razón muy fuerte
Pensé mucho en búsqueda de rutas rápida para acelerar una IA de Quoridor hecha en Scala, y estos son los trucos que aprendí
MPAA (A* adaptativo de múltiples rutas) es bueno cuando se agregan obstáculos y hay que volver a explorar varias veces la misma zona. Se pueden inyectar resultados de búsquedas anteriores para acelerar la búsqueda de rutas
JPS (Jump Point Search, búsqueda de puntos de salto) es atractivo en teoría porque puede reducir mucho la cantidad de “nodos” a considerar, pero el overhead de encontrar los puntos de salto era alto y en la práctica no hubo mejora de velocidad. Tal vez haya una forma de combinar las ideas de MPAA y JPS, pero cuando uno empieza a tocar creativamente los algoritmos, detalles conceptuales mínimos pueden salir caros. Por ejemplo, si usás
>cuando necesitás>=, en ciertas situaciones podrías no garantizar la ruta verdaderamente más cortaPara guardar nodos abiertos, en lugar de un heap propiamente dicho, si el valor máximo de prioridad es un entero relativamente pequeño, vale la pena considerar una cola de prioridad por buckets. Como el arreglo interno se indexa por prioridad, insertar y extraer se vuelve bastante rápido
Quoridor se juega en una cuadrícula de 9x9, y para determinar qué tan cerca está un jugador de su objetivo y si puede alcanzarlo, la búsqueda repetida de rutas es esencial. Para evaluar las jugadas posibles desde una posición concreta, hay que comprobar que ninguna jugada haga imposible llegar al objetivo. Planeo publicarlo en unos meses e incluirá al menos 3 “motores” de toma de decisiones: mtdf (una variante de minimax), MCTS (una versión paralela con algunos trucos) y un híbrido con catboost
Lo bueno es que esto se puede usar como tabla de consulta para la función heurística en lugar de la distancia en línea recta habitual. Por ejemplo, al comienzo de cada turno se puede inicializar esta tabla con el algoritmo de Floyd-Warshall reflejando las paredes ya colocadas. En un problema parecido, esta técnica aceleró bastante A* y fue muy simple. Eso sí, era A* puro, sin MPAA ni JPS
Hace varios años agregué a la implementación de JPS de PathFinding.js una función para visualizar la búsqueda recursiva que encuentra nodos de salto. La demo en línea está aquí: https://qiao.github.io/PathFinding.js/visual/
Si hay más de un enemigo, puede convenir ejecutar Dijkstra una sola vez desde la perspectiva del jugador y hacer que cada monstruo consulte la ruta óptima hasta el jugador
El costo de cómputo se vuelve más predecible cuando cambia la cantidad de monstruos
El problema de que la profundidad sea demasiado pequeña en la última animación se ve como un comportamiento interesante. Parece que el monstruo “espera para ver hacia qué lado vas a ir”.
¿No podrías engañarlo fingiendo ir hacia un lado y luego cambiando de dirección? Por suerte, los humanos somos bastante indulgentes con estas cosas, y parece que modelamos cualquier cosa como si tuviera inteligencia.
Básicamente, habría que hacer que el enemigo actualice la ruta solo después de un breve retraso, no en cada frame. Entonces, por la “inercia”, seguiría la ruta anterior y el jugador podría engañarlo.
Como uso interesante de A* en el contexto de juegos, había un programador que tuvo que crear el oponente controlado por computadora para un juego de principios de los 2000.
Abstrajo las opciones que tenía la IA en el juego e hizo que A* encontrara la distancia más cercana en ese grafo. Lo interesante fue que no lo usó para el caso tradicional de búsqueda de rutas en el mundo, sino para buscar rutas sobre una representación de las decisiones que la computadora podía tomar, de modo que la ruta más corta representara la mejor estrategia posible.
0 - https://www.gamedeveloper.com/design/building-the-ai-of-f-e-...
1 - https://web.archive.org/web/20230804100329/https://alumni.me...
También hay recursos de referencia (no son míos): https://github.com/agoose77/goap-resources
Los humanos parecen asumir que ellos mismos y otros humanos usan patrones de pensamiento similares y una profundidad de razonamiento parecida para actividades totalmente distintas, como planear una ruta, evaluar riesgos/recompensas o planificar un evento dentro de seis meses. Si se pueden codificar distintos “espacios de búsqueda” como grafos adecuados para un algoritmo común, se vuelve plausible que, durante el estado de inmersión al jugar, la IA parezca reflexiva y casi como una persona.
Cuando estaba aprendiendo A* en la universidad, al mismo tiempo nos encontramos con ese problema particular en un servidor compartido de Minecraft.
El servidor iba con muchísimo lag, así que al hacer tracing descubrimos que los zombis estaban atrapados en un bucle intentando encontrar un camino para entrar a una aldea completamente bloqueada por una gran cerca. Es decir, la implementación de entonces era ingenua y nunca se rendía.
Recuerdo que había un reporte de bug que explicaba con bastante detalle cómo solucionarlo.
Podía tener un impacto muy visible en los fps, especialmente cuando varios animales intentaban pasar por entradas que no podían cruzar. Claro que, si lo ves como el comportamiento de un gato exigiendo con enorme insistencia pasar por una puerta cerrada, también se podría decir que es tremendamente realista. ¡Sería aún más realista si, en cuanto le abres la puerta, el gato cambiara inmediatamente de opinión y perdiera el interés en pasar!
Quizá te interese este artículo sobre sistemas multiagente que usan A* en terreno desconocido: https://www.researchgate.net/publication/333917261_Implement...
Hay buenos trucos en este artículo y en el hilo de HN. Todavía no he tenido mucha ocasión de usar A*, pero sé que existe una buena biblioteca de Haskell: https://hackage.haskell.org/package/astar-monad-0.3.0.0#read...