algorithm
A * Algoritmo de búsqueda de rutas

Introducción

Ejemplo simple de A * Pathfinding: un laberinto sin obstáculos

Digamos que tenemos la siguiente cuadrícula de 4 por 4:

Supongamos que esto es un laberinto . Sin embargo, no hay paredes / obstáculos. Solo tenemos un punto de inicio (el cuadrado verde) y un punto de finalización (el cuadrado rojo). Supongamos también que para pasar de verde a rojo, no podemos movernos en diagonal. Entonces, comenzando desde el cuadrado verde, veamos a qué cuadrados podemos movernos y resáltalos en azul:

Con el fin de elegir a qué cuadrado pasar, debemos tener en cuenta 2 heurísticas:

1. El valor "g": esta es la distancia a la que se encuentra este nodo del cuadrado verde.
2. El valor "h": esta es la distancia a la que se encuentra este nodo del cuadrado rojo.
3. El valor "f" - Esta es la suma del valor "g" y el valor "h". Este es el número final que nos dice a qué nodo movernos.

Para calcular estas heurísticas, esta es la fórmula que usaremos: distance = abs(from.x - to.x) + abs(from.y - to.y)

Esto se conoce como la fórmula "Manhattan Distance" .

Calculemos el valor "g" para el cuadrado azul inmediatamente a la izquierda del cuadrado verde: abs(3 - 2) + abs(2 - 2) = 1

¡Genial! Tenemos el valor: 1. Ahora, intentemos calcular el valor "h": abs(2 - 0) + abs(2 - 0) = 4

Perfecto. Ahora, obtengamos el valor "f": 1 + 4 = 5

Entonces, el valor final para este nodo es "5".

Hagamos lo mismo para todos los otros cuadrados azules. El número grande en el centro de cada cuadrado es el valor "f", mientras que el número en la parte superior izquierda es el valor "g", y el número en la parte superior derecha es el valor "h":

Hemos calculado los valores de g, h y f para todos los nodos azules. Ahora, ¿cuál recogemos?

El que tenga el valor f más bajo.

Sin embargo, en este caso, tenemos 2 nodos con el mismo valor de f, 5. ¿Cómo seleccionamos entre ellos?

Simplemente, elija uno al azar o establezca una prioridad. Generalmente prefiero tener una prioridad como esta: "Derecha> Arriba> Abajo> Izquierda"

Uno de los nodos con el valor f de 5 nos lleva en la dirección "Abajo", y el otro nos lleva a "Izquierda". Como Down tiene una prioridad más alta que Left, elegimos el cuadrado que nos lleva "Down".

Ahora marca los nodos para los que calculamos las heurísticas, pero no nos movimos a, como naranja, y el nodo que elegimos como cian:

Bien, ahora calculemos las mismas heurísticas para los nodos alrededor del nodo cian:

Nuevamente, elegimos el nodo que baja desde el nodo cian, ya que todas las opciones tienen el mismo valor f:

Calculemos las heurísticas para el único vecino que tiene el nodo cian:

Muy bien, ya que seguiremos el mismo patrón que hemos estado siguiendo:

Una vez más, calculemos las heurísticas para el vecino del nodo:

Vayamos allí:

Finalmente, podemos ver que tenemos una casilla ganadora a nuestro lado, por lo que nos movemos allí y hemos terminado.