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 …

Asi pues Imaginen que tenemos un mapa o escenario, dónde encontraremos dos puntos A (Azul) y B (Rojo). Así como varios obstáculos (Negro), para resolver este problema  lo primero debemos hacer es representar este mapa a nivel lógico, por ello lo dividiremos en una cuadricula:

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.

Ejemplo:

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

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 :

ValorOrtogonal=10ValorDiagonal=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.

Si quieres saber o entender mejor este codigo puedes visitar  http://www.cristalab.com

Acerca del Autor