Si eres un desarrollador de juegos, puede que siempre hayas querido implementar A* como pathfinding de personajes (o enemigos). Sé que hace un par de años lo hice, pero con mi nivel de programación en ese momento tuve problemas con los artículos actuales que hay. Quería escribir esto como una introducción fácil con un claro ejemplo de código fuente a A* pathfinding para que cualquiera pueda fácilmente recogerlo y utilizarlo en su juego.
Un aspecto importante de A* es f = g + h. Las variables f, g y h están en nuestra clase Node y se calculan cada vez que creamos un nuevo nodo. Rápidamente voy a repasar lo que significan estas variables.
- F es el coste total del nodo.
- G es la distancia entre el nodo actual y el nodo inicial.
- H es la heurística – distancia estimada del nodo actual al nodo final.
Echemos un vistazo a un gráfico rápido para ayudar a ilustrar esto.
Increíble! Digamos que node(0) es nuestra posición inicial y node(19) es nuestra posición final. Digamos también que nuestro nodo actual está en el cuadrado rojo node(4).
G
G es la distancia entre el nodo actual y el nodo inicial.
Si contamos hacia atrás podemos ver que node(4) está a 4 espacios de nuestro nodo inicial.
También podemos decir que G es 1 más que nuestro nodo padre (node(3)). Así que en este caso para node(4), currentNode.g = 4.
H
H es la heurística – distancia estimada del nodo actual al nodo final.
Así que vamos a calcular la distancia. Si echamos un vistazo veremos que si pasamos 7 espacios y subimos 3, hemos llegado a nuestro nodo final (node(19)).
¡Apliquemos el Teorema de Pitágoras! a² + b² = c². Después de aplicarlo, veremos que currentNode.h = 7² + 3². O currentNode.h = 58.
¿Pero no tenemos que aplicar la raíz cuadrada a 58? No. Podemos omitir ese cálculo en cada nodo y seguir obteniendo la misma salida. Inteligente!
Con una heurística, tenemos que asegurarnos de que realmente podemos calcularla. También es muy importante que la heurística sea siempre una subestimación del camino total, ya que una sobreestimación llevará a A* a buscar a través de nodos que pueden no ser los ‘mejores’ en términos de valor f.
F
F es el coste total del nodo.
Así que sumemos h y g para obtener el coste total de nuestro nodo. currentNode.f = currentNode.g + currentNode.h. O currentNode.f = 4+ 58. O currentNode.f = 62.
Tiempo de usar f = g + h
Muy bien, así que eso fue un montón de trabajo. Ahora, con todo ese trabajo, ¿para qué voy a usar este valor f?
Con este nuevo valor f, podemos mirar todos nuestros nodos y decir: «Oye, ¿es este el mejor nodo que puedo elegir para avanzar ahora mismo?». En lugar de recorrer todos los nodos, podemos elegir los que tienen más posibilidades de llevarnos a nuestro objetivo.
Aquí tenemos un gráfico para ilustrarlo. Arriba tenemos el Algoritmo de Dijkstra, que busca sin este valor f, y abajo tenemos A* que sí utiliza este valor f.
Algoritmo de Dijkstra
Así que echando un vistazo al algoritmo de Dijkstra, vemos que sólo sigue buscando. No tiene ni idea de qué nodo es el ‘mejor’, así que calcula caminos para todos ellos.
Algoritmo A*
Con A*, vemos que una vez superado el obstáculo, el algoritmo prioriza el nodo con la menor f y la ‘mejor’ probabilidad de llegar al final.