Dedicado a mis proyectos en Gambas ,un lenguaje de programación parecido al Visual Basic + Java pero ampliamente mejorado y...¡¡para gnu/linux!!.La potencia del gnu/linux sumada a la facilidad del Basic



Consultas, Desarrollo de programas y petición de presupuestos:



lunes, 10 de septiembre de 2012

A* Pathfinder Algoritmo A estrella: Usandolo en Gambas3 El León y la Gacela

 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.

Enlace de descarga código fuente: Descarga vesion inicial



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/