Modelo VI: Pathfinding y aplicaciones

[Güarmigue]

Hoy voy ha hablar un poco del algoritmo A*, utilizado para pathfinding y de posibles aplicaciones de éste y otros algoritmos que resuelvan el mismo problema en los videojuegos.

Definición: los algoritmos de pathfinding o búsqueda de caminos son aquellos que encuentran un camino válido desde un punto A a otro B en un terreno con obstáculos.

Estos obstáculos pueden ser bien infranqueables o simplemente aumentar el coste del camino. Los algoritmos de pathfinding son en realidad algoritmos de búsqueda de caminos en grafos, pero veamos un pequeño boceto de principio a fin:

Lo primero que haremos para poder aplicar el algoritmo es dividir el terreno o escenario en cuadrantes (nodos del grafo) y clasificar cada uno de ellos como obstáculo o terreno libre. Como comentaba antes esta división no tiene por qué ser binaria, podemos asignar a cada cuadrante un entero que indique su coste en ser atravesado (por encima de un máximo arbitrario el cuadro se considerará infranqueable). A la hora de estimar el coste del camino tendremos en cuenta estos enteros y podremos elegir el camino más ventajoso o rápido.

Una vez tenemos los nodos, el algoritmo A* es un algoritmo voraz que va creando un árbol cuyos nodos son los posibles nodos del camino y va escogiendo siempre el que estima mejor. ¿Cómo hacemos ésto? Pues para cada nivel introducimos un nodo nuevo por cada casilla o cuadro alcanzable del terreno, en el primer nivel estos nodos serán todos los adyacentes al cuadro en el que se encuentre el personaje que desea moverse.

Una vez introducidos, evaluamos, con un heurístico optimista, la distancia del camino desde cada uno de estos nodos al nodo meta, lo que nos da un valor de su bondad. Un heurístico de estimación optimista quiere decir que todos los caminos posibles desde ese nodo tendrán un costo igual o mayor al calculado en la función heurística. Además para que podamos llamar a nuestro algoritmo A* esta función debe ser monótona, lo que quiere decir que el coste desde el nodo actual no puede ser mayor que el coste en el nodo actual no puede ser mayor que el coste desde un sucesor del nodo actual más lo que nos cueste alcanzar al sucesor. En nuestro ejemplo se suele utilizar la distancia del punto al destino sin obstáculos. De este modo cumplimos ambas restricciones, somos optimistas (el camino sin obstáculos siempre será más corto que con obstáculos) y monótonos, ya que en el mejor de los casos (si no sorteamos ningún obstáculo) El coste desde un sucesor a la meta más el coste en llegar al sucesor será igual al coste estimado.

Cuando hayamos calculado la bondad de cada nodo podremos escoger el mejor y desechar todos los demás gracias a lo que nuestra heurística cumple las condiciones comentadas.

Desde el nuevo nodo realizaremos la misma operación hasta alcanzar el nodo destino.

El camino encontrado es óptimo y ya solo tendremos que mover el personaje de un nodo al siguiente de la lista hasta alcanzar el destino.

Para aquellos que no os haya quedado muy claro o queráis ampliar o conocer otros algoritmos de pathfinding al final pondré algunos enlaces.

Aplicaciones:

En el mundo de los videojuegos existen muchas aplicaciones para este tipo de algoritmos. Son necesarios siempre que tengamos un escenario o nivel con objetos sólidos o infranqueables en los que queramos que el computador mueva un objeto de un punto a otro del escenario. Esto ocurre como todos sabemos en los juegos de estrategia y de rol, donde le decimos a las tropas donde deben moverse y ellas se las apañan para alcanzar ese punto a través del terreno. Pero también cuando el ordenador necesita mover un enemigo de un punto a otro del escenario necesitará de un pathfinding.

El problema del algoritmo que he comentado es que no es dinámico, y por tanto si queremos que, por ejemplo, un enemigo persiga a un jugador tendríamos que recalcular el camino a seguir por el pnj cada poco tiempo, lo que puede resultar demasiado costoso.

Pero para estos casos podemos usar técnicas mixtas. Por ejemplo en un arcade los enemigos (verde) podrían utilizar el pathfinding para ir a la habitación en la que está el jugador (azul), o a determinados puntos de control dentro de esa habitación (amarillo) donde su posición sea ventajosa. Una vez con el jugador "a tiro" simplemente deberían orientarse en la dirección del vector que apunta desde ellos al jugador.



Para ampliar:
A* para principiantes: una explicación muy sencilla, con varios gráficos, que nos dejará el algoritmo A* bien clarito.
A* en la wikipedia - A la derecha tenéis enlaces a algoritmos relacionados así como el pseudocódigo del algoritmo y un pequeño análisis de su complejidad.
The Game AI Page: Pathfinding - enlaces a algoritmos y papers sobre búsqueda de caminos.

[Alexpi]

Ya que estas a ver si peudes contestarmeuna duda :)

En los juegos como rpg en 3º persona y mmorpg donde los mapas son enormes y sin zonas de carga, como suelen hacer para calcular el pathfinding en tiempo real? Me refiero sobre todo al movimiento de los propios jugadores, haciendo click en un lugar del terreno al que quieren ir y ya el pj se mueve solo hasta alli.

Al se rmapas tan grandes, no creo que sea posible tener precalculado un mapa de nodos para identificar los lugares por donde se puede pasar y por donde no.

De hecho algunos mmorpgs, hasta el propio entorno es dinamico, donde los GMs pueden incluir objetos como muros o casas en cualquier momento y el pathfinding los esquiva sin problemas :?

[matriax]

No te mucha idea, pero supongo que en caso de ese rpg, sera porque digamos todo va en tiles. Y unos tiles son muros y demas que no se pueden traspasar, y luego hay tiles de suelo y tal por donde si se puede.

Lo que hace es ver el cuadro donde esta el personaje, y el cuadro donde le has pichado y selecciona una serie de tiles de suelo entre el jugador y el sitio indicado, y el jugador va hasta alli o al menos eso tengo entendido.

[Güarmigue]

Pues veamos, al final siempre es más o menos igual, todo es dividir el espacio y acotar el problema:

El tener un mapa muy grande no nos tiene porqué afectar. Igual que en el ejemplo de los enemigos que se dirigen a una habitación que te he comentado, tu siempre sabes dónde se encuentra el jugador, en qué sección exacta del mapa. En los MMORPG de hecho no están cargados todos los pjs del mundo, cuando te mueves a una zona poblada en WOW verás como aparecen los personajes poco a poco, ya que el ordenador ha detectado que has entrado por ejemplo en la plaza de un pueblo y te carga todos los personajes de esa plaza.

De la misma forma, teniendo dividido el mapa en secciones y como sabemos en cual se encuentra el jugador, ya hemos acotado el problema a algo tal y como lo que yo he contado. Si el master introdujo cualquier obstáculo nuevo en el mapa, igual que tu lo ves gráficamente, el mapa de durezas también fue actualizado y el algoritmo calculará la ruta con todos los objetos que tu puedas ver en ese momento.

Resumiendo, no es que estén todos los nodos o todas las rutas posibles precalculadas. Solo tenemos un mapa de durezas complementario al mapa normal, algo parecido al dibujo que he puesto, y cuando tu haces click se calculan los nodos del camino y se destruyen en cuanto llegas.

[Vicente]

Si el pathfinding tiene obstaculos dinámicos puedes hacer dos cosas:

- los atraviesas (en muchos mmorpgs los avatares se atraviesan).
- usas A* para búsquedas de alto nivel pero al moverte usas otra cosa (steering behaviors por ejemplo). O podrías usar otro algoritmo como D*.

Un saludo!

Vicente

[Güarmigue]

En los enlaces que he puesto aparece D*, pero la verdad es que no lo conocía y no me dio tiempo a leerlo y entenderlo. Si eso otro día me pongo y hago un pathfinding II para búsqueda de caminos con elementos dinámicos ;)

[Vicente]

En los enlaces que he puesto aparece D*, pero la verdad es que no lo conocía y no me dio tiempo a leerlo y entenderlo. Si eso otro día me pongo y hago un pathfinding II para búsqueda de caminos con elementos dinámicos ;)

Yo combinaría una búsqueda con A* para planificar el camino y luego otro algoritmo para moverte entre los nodos del camino  (D* es un poco pasarse :p).

Un saludo!

Vicente

[Güarmigue]

Tomo nota ^^

Al final de la entrada yo también hablaba de usar técnicas mixtas, al final casi siempre hay que combinar soluciones ya que los algoritmos nunca se adecúan exactamente a nuestras necesidades... Pero gracias por prevenir sobre el D* ;)

[shephiroth]

Buenas. La verdad que este tema me interesa sobremanera, puede parecer muy elemental, pero para los novatos como yo se agradece todas las explicaciones.

Pero me ha surgido una duda, estais comentando un pathfinding teniendo en cuenta un coste fisico (tiempo que se tarda, por ejemplo), pero cuando se utilizan diferentes tipos de coste.....como se haria??

Por ejemplo, en un juego tipo sims, un grafo en el que tenemos 4 cuartos, de la cocina se va al comedor, del comedor al cuarto estar, del cuarto estar al dormitorio, y del dormitorio a la cocina (un cuadrado vamos). Imaginemos que quiero ir del dormitorio al pasillo. Si voy por la cocina me sube el health, mientras que si voy por el cuarto estar me baja el cansancio. Como segundo caso, estoy envenenado y en el pasillo esta el antidoto, y por cada coste de movimiento pierdo vida. Como se elaboraria un pathfinding que cuadrase en ambas situaciones???

[Güarmigue]

Pues supongo que lo que tendrías que hacer en el primer caso es construir los nodos con costes en función de esos atributos que hablas en lugar del coste en distancia.

La habitación de la cocina tendría un bonus por subir salud, la del dormitorio otro por subir comodidad, etc. A la hora de elegir el nodo elegiríamos el de mayor bonus acumulado, en lugar del coste mínimo. También podrías normalizar todos los bonus e invertirlos (eso se hace dividiendo cada uno de ellos por el mayor y luego tomando el inverso -1/n-) y tendrías números reales que medirían el coste de cada nodo, y ya podrías aplicar el A* normalmente ya que al escoger el coste menor estaría escogiendo la mayor suma de bonus...

En el caso del antídoto no veo diferencia con el A* normal, salvo que si la distancia final es mayor a la vida el pj muere irremediablemente y sino se salva siempre... no sé si el ejemplo no expresa yo que buscabas o yo no lo entiendo.