Dead Channel

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.