Algoritmo A* para encontrar el camino más corto en IA

El algoritmo Pathfindig A* (A estrella o A asterisco), es el más conocido de todos para encontrar el camino más corto entre un punto dado (A) y otro punto (B). Es muy usado en juegos, el primero en usarlo fue el famoso Pac-Man (Para los fantasmitas).

El método que explicaré esta "algo" retocado por mí, más que nada porque generalmente lo he usado en ActionScript y he querido mejor el rendimiento. Aunque esta MUY poco tocado, básicamente simplifique los valores de la fórmula y edité el uso de listas abiertas/cerradas para no guardar basura en la RAM.

No nos enfocaremos en código sino en la comprensión del Algoritmo. Hay algunos ejemplos de todas formas aquí en Clab.

Escenario base para el algoritmo A estrella o A asterisco

Imaginen tenemos un mapa o escenario, dónde encontraremos dos puntos A (Azul) y B (Rojo). Así como obstáculos (Negro).


Lo primero debemos hacer es representar este mapa a nivel lógico, por ello lo dividiremos en una cuadricula:


Cada cuadrado en la cuadricula es un punto de movimiento (El movimiento mínimo que podremos obtener). El sistema realmente puede usar cualquier figura geométrica poligonal. Los cuadrados son más fáciles.

Convertir nuestro escenario o mapa a datos

Ahora el problema es como representamos a nuestro código una cuadricula. Pues en realidad fácil, con una cuadricula o Array, donde señalaremos 0 para espacio vació, 1 espacio ocupado.

Para mi ejemplo:

Código :

[0,0,0,0,0,0]
[0,0,1,0,0,0]
[0,0,1,0,0,0]
[0,0,1,0,0,0]

Notarán no puse los puntos de espacio de A ni B, dado que podrían ser dinámicos. Esos los manejaremos con posición:

Código :

A = [0,0]
B = [5,2]

Algoritmo PathFinding A* explicado para humanos

La formula del Pathfinding A* es realmente simple:

Código :

Movimiento = Esfuerzo + Heurística

Primero que nada, debemos entender que solo podemos movernos hacia 8 direcciones: 2 Horizontales, 2 Verticales (Valores Ortogonales) y 4 Diagonales.

Cada movimiento le asignaremos un valor definido (El cálculo real usa raíces, pero no consume bastante más):

Código :

Valor Ortogonal = 10
Valor Diagonal = 14

Así que el esfuerzo será determinado según el movimiento que haremos, Ortogonal u Horizontal:


La variable Heurística en cambio, es una variable "a ojo". Como no sabemos el valor real, calcularemos la distancia entre A <-> B[Análisis] desde sus valores Ortogonales sin obstáculos. Lo cual es fácil, ya que sabemos la posición en la matriz de ambos objetos.

Código :

Heuristica desde Punto B (Inicial) = 7 * 10

O lo que es más correcto:

Código :

Heuristica = Distancia desde el punto de Analisis * 10

Hemos sumado 10 ya que tenemos una incertidumbre incierta, esto debería cubrirnos.

Este método de calcular la Heuristica se llama Manhattan.

Mejorar el rendimiento del Algoritmo A* estrella/asterisco

Siempre que uso el Pathfinding A* debo admitir no lo hago exactamente así, ya que nunca me ha gustado calcular 8 direcciones, cuando se para qué dirección quiero ir (Derecha o Izquierda).

Generalmente lo que hago es "eliminar" las posiciones de cálculo que no corresponden al lugar donde quiero ir. Esto lo hago calculando si mi posición desde B hacia A es negativa o positiva:

Código :

Direccion = Posicion B Horizontal - Posicion A Horizontal

Esto elimina una buena parte del cálculo (Ahora veremos porque esto nos preocupa).

Calcular el camino más corto

Antes que nada, debemos saber que calcularemos a la inversa, desde el punto B hacia el A (Por practicidad). Es lo mismo el path de ida que de venida, así que no afectará nada.

Para calcular debemos crear una progresión usando la fórmula que ya sabemos. Nos paramos en la posición B, y calculamos cual es el valor de B que más nos conviene tomar según la fórmula que ya conocemos.

Código :

Valor = G + H

Deberán ejecutar la fórmula pero evaluando que el cálculo sea posible, si el cuadrado es 0 (libre) o 1 (ocupado). En caso de 1 no valdrá el camino. Incluso pueden ejercer una regla, donde la diagonal no sea posible si su ortogonal esta ocupada (Es a criterio de cada uno).

Camino Final calculado por A*

Obviamente calcular el camino final implicará ir eligiendo el valor más corto y desde allí replicar la fórmula hasta llegar al punto A. Luego obviamente revertir la lista.


Resultado:

Código :

Movimiento 1 = [1][0]
Movimiento 2 = [2][0]
Movimiento 3 = [3][1]
Movimiento 4 = [4][2]

Aplicaciones del Pathfinding A*

Este algoritmo de Inteligencia Artificial es muy útil para calcular el camino óptimo entre el punto A y B. Aunque también nos sirve para estimar comparativas. Si sabemos cual es el valor de todo el movimiento del camino y sabemos el valor del camino que hizo el usuario, podemos estimar cual fue su eficiencia.

Si lo que queremos usar es mapas, este Algoritmo debe ser aplicado mediante Waypoints.

Espero les sirva

 

Tweet