En algún post anterior hemos visto como funciona el algoritmo
A* o ‘A Estrella’ pero aqui lo repasaremos aplicándolo a la noble
vía de la búsqueda de caminos.

El aprendiz de Samurai Informático no tiene porqué conocer ningún
detalle del pathfinding para aprender lo que aqui se contará.

En primer lugar nuestro entorno quedará dividido en casillas que
representarán las posiciones alcanzables de los elementos que van
a ser desplazados. Partimos de una posición inicial y buscamos una
la lista de casillas que nos llevan a la posición final.

En nuestro entorno encontraremos obstáculos que harán que el camino
pueda variar.

A partir de ahora cada uno de los elementos de la malla los llamaremos
nodos.

>El procedimiento de búsqueda

Empezamos a estudiar el comportamiento del algoritmo. El estudio y la práctica
hacen al maestro Samurai Informático.

Tenemos 3 elementos sobre los que trabajaremos, la katana, la
armadura y el arco de batalla del algoritmo A Star aplicado al Pathfinding:

- La lista abierta de nodos. Son las casillas que requieren ser tenidas en cuenta.
- El ancestro de un nodo es el nodo a través del que se accede a este último, esto
se hace para que una vez sepamos los nodos o casillas que intervienen podamos recuperar
el orden en el que tienen que ser visitados.
- La lista cerrada de nodos. Son aquellos nodos que no deben ser tratados por el momento.

Ahora el código Samurai a seguir, nuestro Giri del A*. Debemos seguir el Giri bajo cualquier concepto.
El Giri del A* será interiorizado por todos los verdaderos Samurais Informáticos.

- 1. Empezar desde el punto inicial y añadirlo a la lista abierta de casillas a tener en cuenta.

- 2. Mirar todos los cuadrados válidos adyacentes al punto de inicio,
pasando de los inalcanzables. Añádir a la lista abierta.
Por cada uno de esos cuadrados, guarda el punto A como su ancestro.

- 3. Sacar la casilla inicial de la lista de abiertos y ponerlos en la lista cerrada.

El auténtico Samurai puede extraer ya la dinámica de lo que va a ser nuestro algoritmo de búsqueda de
caminos. Ahora lo que nos queda es repetir el proceso pero no de cualquier manera sino dotando a nuestro
sistema de la intuición genuina ancestral, es decir, lo que llamamos el heurístico. Con el visitaremos
primero los nodos más prometedores, es decir, aquellos en los que la fuerza se detecte mayor.

> Midiendo la calidad de una casilla

La calidad de una casilla es el valor que le damos para comparar entre el resto y decidir cual es el camino
más probable que debemos ir visitando. Aqui entra algo del conocimiento ancestral oculto, solo alcanzable por
los Samurais más avanzados, las matemáticas.

Cada casilla tendra un valor que vendrá determinado por la función: F(x) = G(x) + h(x)

-Donde x es la casilla concreta.
-F(x) es el valor de la función para la casilla x.
-G(x) es el coste que podemos medir. La distancia al inicio del camino
-h(x) es la esencia del algoritmo, el Tao. Aquello que se siente pero no puede ser explicado. El Tao que puede
ser explicado no es el verdadero Tao. En general, es lo que nosotros pensamos que puede quedar para llegar, nosotros
podemos calcular este valor a partir de la intuición de lo que nos queda. Siempre pueden haber obstáculos en medio
que nos perjudiquen pero en general, nos guiará hacia el verdadero Camino.

Como medimos las distancias no es problema aqui. El Samurai Verdadero buscará estas respuestas en otras fuentes, lo
realmente interesante es comprender el funcionamiento de nuestra Técnica de Combate A Estrella. No nos preocuparemos
de mejorar la eficiencia de los cálculos por el momento, esto es tarea del Experto Samurai Informático y no entra aqui
ahora, todo a su debido tiempo.

> El estimador o herístico h(x)

Este valor puede calcularse de diferentes maneras bajo diferentes conceptos, orientados a obtener una respuesta rápida
o una respuesta precisa. Generalmente nos pelearemos por buscar un compromiso entre lo rápido y lo preciso.

¿Como lo hacemos? Tenemos varias opciones.

-Primera opción. Sabemos donde estamos y donde queremos llegar, lo de en medio es una incognita. Pues bien, calcularemos la distancia
en línea recta desde nuestro punto al punto final. A esto se le llama distancia Euclidea y sin entrar en detalles será
algo del estilo d(x,y) = sqrt((y1-x1)^2 + (y2-x2)^2), es decir la raiz cuadrada de la suma de los cuadrados de las diferencias
entre las coordenadas correspondientes. Los Samurais que comprendan este concepto adquieren automáticamente una grado
adicional en materia de ‘Combate Matematico’.

-Segunda opción. Lo hacemos más sencillo. Utilizamos lo que se llama la distancia Manhattan. Es decir, calculamos lo
que nos costaría llegar si recorrieramos el tablero siguiendo las lineas de las mallas como si fueran las calles de
una ciudad dividida en manzanas. A efectos prácticos sería algo por el estilo dM(x, y) = abs(y1-x1) + abs(y2-x2), es decir
el valor absouto de la distancia en coordenadas X (pongamosle horizontal) y coordenadas y (pongamosle vertical).

En la foto las distancias marcadas con color amarillo, azul y rojo son las que representan la distancia Manhattan, cualquiera de ellas es válida. Para el cálculo nos quedamos con la amarilla o la roja (suma de distancia vertical y de distancia horizontal o al revés).
-Otras formas. Para aquellos Samurais más versados comentar que existen más métodos que intentan mejorar la eficacia y
eficiencia de este cálculo, ya que en definitiva es un estimador de lo buena que creemos que es la solución. Una de ellas
es el uso de la distancia Euclidea cuadrada, d2(x,y) = (y1-x1)^2 + (y2-x2)^2 donde se elimina el cálculo de la raiz. Esta
no es propiamente la distancia entre los puntos x e y pero al aplicarlo sobre todos los elementos, el valor relativo de
cada uno sigue representando la calidad estimada y por tanto nos sirve para guiar a la Espada del A Estrella hacia su objetivo.

> Seguimos la búsqueda.

De entre todos los bloques que hemos insertado en la lista de abiertos elegimos el que menos valor tenga en F, es decir,
el que la suma de la distancia al origen G y la distancia estimada h sea menor. Con esto dirigiremos la búsqueda.

Ahora el Samurai Informático novicio adquirirá los conceptos necesarios para ampliar definitivamente su conocimiento en
materia de IA para Juegos por lo que se recomienda atención.

Primero – Sacar este elemento de la lista de abiertos y añadir a la lista de cerrados.

Segundo – Repetir el paso de añadir los adyacentes que sean transitables pasando de los que están en la lista de cerrados
Añadirlos a la lista de abiertos si no están ya y poner al cuadro actual como Ancestro de los nuevos cuadros.

Tercero – Si el cuadro adyacente ya está en la lista de abiertos, mira si el camino a ese cuadro es mejor que este.
es decir, si la G de ese cuadro es más baja que la del que estamos usando para ir allí (llegamos más rápido por aqui)
. Si el coste G del nuevo camino es más bajo, cambia el ancestro del cuadro adyacente al cuadro seleccionado
y recalcula la F y la G de ese cuadrado.

Este paso es el que representa el mayor desafio al Samurai novicio, una vez superado le servirá tanto para generar
caminos como para otras muchas cosas en su vida de Samurai Informático.

Para terminar, comentaros que esta es la base del aprendizaje. A partir de aqui se puede trabajar en mejorar las soluciones
creando caminos más suaves, haciendo cálculos más rápidos y adaptando la solución a nuestro problema en concreto por ejemplo con
diferentes tamaños de unidades y diferentes tipos de terreno transitable (arena/asfalto/etc…).

Aqui teneis el código fuente del A* para el Pathfinding provisto por el Samurai Informático Experto Patrick Lester.

Disfrutadlo!