Hola a todos, paso a relatar los últimos y aparentemente definitivos avances para mi A*

Aclaraciones:
– A* Es sin heuristica, pero comúnmente se le llama a toda busqueda de caminos basada en A*… “A Star”
– He utilizado un applet Java de James Macgill donde el implementa su version de pathFinding añadiendo un modificador a la heuristica con un producto escalar y haciendo que puntue mejor los puntos que estan más paralelos entre el PJ y el PUNTO FINAL. Así se consigue unos caminos más naturales y no tan rectos.

– Celda verde, ha sido evaluada.
– Celda azul, camino que se ha seguido finalmente despues de evaluar.

Bien, volvi a las bases, a aplicar heuristicas basadas en Manhattan, la verdad es que no tengo ganas de que se “cuelen” unidades entre muros por las diagonales, esto daría problemas en un juego de tablero.

Veamos los resultados con mi A* básico son los siguientes:

Como veis no quito celdas “basura” y tengo un alto coste de computación, el path es más natural y en el mismo número de pasos. Es una simple prueba preparatoria para el “modificador de paralelismo”.

Sigamos, otra situacion

mi A* básico:

referencia:

Ambos en 18 pasos. El mio sigue aplicando algo más de naturalidad.

Veamos, aplicando en su totalidad la heuristica. Tie Breaking, cross product para puntuar el paralelismo. Me llevé una sorpresa al conseguir un costo tan bajo de computo y un resultado tan parecido, solo en los casos que voy a presentar he conseguido “putearlo” y encontrar diferencias.

En los demás casos la lista cerrada, celdas verdes, no existen, esto es que siempre que da un paso acierta y escoje la celda más optima al sumar la puntuación por paralelismo al valor heuristico.

Veamoslo:

Referencia:

Mi A*+ en 20 pasos, el original 17 pasos. Pero con un calculo muchisimo mayor al mio y un movimiento nada natural, muy rectilineo.

Otra situación:

mi A*+

Mi A*+ en 18 pasos, el original en 20. Mi movimiento sigue conservando la naturalidad y el costo es mucho menor al de la implementación original.

En definitiva estoy muy contento del resultado que he obtenido Smile

Para mostraros lo que comentaba antes, aquello de que en las situaciones simples, normales, sin obstaculos nunca daba pasos en falso y el computo era “perfecto”, aqui lo teneis:

AStar:

Fudge de James Macgill, tie breaking, el original:

Mi A*+, basado en la idea de James Macgill:

*Nota el 1er verde es de donde empieza.

Pagina muy buena de referencia para todo esto:
http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

También mejoro los resultados de computo de la pagina donde lei sobre todo esto ^^

Bueno, espero que os haya gustado y os de ideas para vuestros proyectos, ya me contareis que tal!

Un saludooooooooo!