miércoles, 22 de abril de 2015

Mi implementación del algoritmo Fringe Search para la búsqueda de caminos que tienden a ser óptimos en gráficos de maya.

El algoritmo Fringe Search propuesto en http://webdocs.cs.ualberta.ca/~holte/Publications/fringe.pdf por Yngvi Bjornsson Markus Enzenberger, Robert C. Holte y Jonathan Schaeffer produce caminos que tienden a ser óptimos, pero mejoran la velocidad de ejecución de A* de una manera significativa. Pongo a disposición de todos el código fuente usado en mi tesis titulada: "El Algoritmo Fringe Search como solución superior a A* en la búsqueda de caminos sobre gráficos de malla" presentada en la UNAM, en el cual implemento este algoritmo en lenguaje C. Espero sea útil. 


El código puede ser descargado o clonado desde: https://github.com/pywirrarika/fringesearch

miércoles, 8 de abril de 2015

Mi implementación del algoritmo A* para gráficos de malla.

Dejo a disposición de todo aquel interesado mi repositorio de GitHub donde se puede encontrar el código de mi implementación del algoritmo A* escrito en C. He usado una skiplist para la lista cerrada junto con arreglos de punteros para un acceso rápido y un buen nivel de optimización para mejorar el tiempo de ejecución. El programa lee un archivo
BMP del cual cargará las partes negras como obstáculos o como nodos intransitables. Como salida genera un archivo BMP nuevo donde se representa el área en la cual se ha buscado y el mejor camino del nodo de inicio al nodo de destino.

Para obtener el código simplemente será necesario introducir el siguiente comando en la terminal:

git clone https://github.com/pywirrarika/astarmesh

O descargarlo directamente de la página: https://github.com/pywirrarika/astarmesh