Pathfinder Algoritmo A Star A estrella A*
El algoritmo A estrella (A*), se usa para hallar el camino más corto (de menor coste) entre dos puntos de un mapa dado, teniendo encuentra los obstáculos. (ver wiki ). Se usa mucho por ejemplo en los juegos gráficos.
Explicación gráfica del Algoritmo:
Documento donde se describre la resolución del diagrama: Descarga Hoja de Calculo
He encontrado un blog ( ver fuente) , donde su autor lo codifica en javascript.
Lo he podido traducir a Gambas3, haciendo un pequeño ejemplo, donde se crea el mapa de forma aleatoria y la posición inicial (un león) y la posición final (una gacela), imprimiéndose el camino que une a los dos, e informando de cuando pasos se dán.
Versión: 2.2
He mejorado algunas cosas:
-> Ahora incluyo en el mapa celdas que dejan pasar pero con dificultades (hierva y agua). El arbol no deja pasar al leon, como en la primera versión.
-> Puedes ver distintas funciones heuristicas (Por defecto, Manhathan, Euclidea o sin uso de función), y se puede ver el coste de cada opción (valoración del camino) y un parámetro que mide el número de operaciones que se realizan (exactamente no es eso), pero sirve para darse cuenta cuanto "trabaja" el ordenador para encontrar la solución.
-> La ruta es marcada con flechas, indicando la dirección que toma el león hasta llegar la Gacela.
Enlace de descarga código fuente: fuente 2.2
Enlace Version 3.2: fuente 3.2
Corregido el algoritmo, ya que no daba el camino más óptimo.
Espero que os sea útil, sobre todo para el desarrollo de juegos !!!
Paginas web fuente o de referencia:
http://46dogs.blogspot.com.es/2009/10/star-pathroute-finding-javascript-code.html
http://devpro.it/code/137.html
iconos: http://animales.m-y-d-s.com/animal/