A* PathFinding parte 2 (A*+ buen trabajo!)

[Prompt]

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 :)

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!

[Prompt]

Hay que apuntar que el movimiento no está restringido, como en el post anterior y no hay nada optimizado, uso std::vector no heap :P

[Leoheart]

Interesante. Estoy dando todo esto ahora en clase de IA y tenía unas dudillas.

Como heurística has utilizado Manhattan pero premiando las posiciones que menos cambian la direccion del camino que lleva. ¿Es eso?

Según me han explicado en clase ( corrigeme si estoy equivocado) cuando estas ramificando los posibles movimientos a partir de un estado en concreto tienes el coste actual hasta llegar a ese nodo, a cada nodo que te sale al ramificar en el que estas le aplicas una heurística ( en este caso Manhattan) que es una aproximacion de lo que te queda. Si es así, ¿ Cómo premias las posiciones más rectas?
¿Eligiendo primero las que siguen en la misma dirección antes que las otras que tienen menos coste?

Saludos y muchas gracias.

[Prompt]

Perdona por no haberte respondido antes.

Veamos:
- Como hacer que eliga un camino "mas natural". Como digo en los comentarios usando el producto escalar. Coges un "pack" de celdas adyacentes, las puntuas con manhattan, es decir, todas tienen la misma puntuación y las diagonales no se analizan ya que sino no seria manhattan. "Rechaza imitaciones" xD

Una vez tienes puntuadas las celdas a 1 (por ejemplo), que es coste que te produce ir desde tu celda a la adyacente, mides la distancia que hay entre esa celda adyacente y el punto al que quieres llegar.

Una vez tienes todo eso, aplicas otra pasada de puntuaciones, sumale el producto escalar que hay entre esa celda y la celda final. Ahí puntuarás mejor las celdas que sean más paralelas al objetivo.

Esto se llama Tie Breaking... (sino recuerdo mal). Yo lo que hice y no me acuerdo bien como es hacer una camino de menor calidad (ver la imagen 1ª y la ultima) pero con un computo absurdo, se pueden ver las celdas verdes que son las que miro como posibles para ir por ahí.

Basicamente eso es todo. Un saludo!