A * manhattan distancia

Question

Busqué el algoritmo/pseudocódigo de A * I lo seguí y lo codifiqué. Utilicé la distancia de Manhattan para h (n). (F (n) = g (n) + h (n)) Y este es el resultado,

Esto sucede siempre cuando no hay paredes que bloquean el camino, pero cuando puse mucho de paredes, parece que está tomando el camino más corto. ¿Este es el camino más corto? Quiero decir por qué no es como este a continuación?

Este también es A * Manhattan, y tienen el mismo tamaño (19x19). Esto es de http://qiao.github.com/PathFinding.js/visual/

Answer 1

Ambos caminos tienen la misma distancia de Manhattan. Por lo tanto, depende de la implementación qué camino se elige. Para decir por qué se eligió esta parte específica, tendríamos que mirar el código de esta implementación A * específica.

Sugerencia: cada ruta desde una fuente a una celda objetivo que usa solo Von Neumann neighborhood (es decir, no camina en diagonal) y no da un paso en la dirección "incorrecta" (es decir, nunca camina hacia la izquierda en su ejemplo) tiene la misma distancia de Manhattan. Por lo tanto, si se encuentra en Nueva York, no importa qué encrucijada tome para llegar a cierto lugar en Manhattan :)

Answer 2

Con la distancia de Manhattan, la primera es la ruta más corta. Simplemente cuenta el número de pasos horizontales y verticales tomados. Si quieres algo que se parezca más al camino más corto en la distancia euclidiana, puedes intentar cambiar tu algoritmo para que cuando tenga la opción de moverse horizontal o verticalmente en un punto, elija el horizontal si la distancia horizontal es mayor que la vertical uno y viceversa

Answer 3

Debe proyectar una línea de visión (pitagórica/euclídea) desde el punto de partida hasta cada punto (del resultado manhattan/A *) hasta finalizar. Si el obstáculo bloquea o bloquea una línea hasta cierto punto, se usa el punto anterior lanzado y se comienza a lanzar otra línea desde ese punto bloqueado y luego hacia delante hasta el final. Un punto bloqueado es cuando un punto está oculto por la línea de visión del punto inicial del segmento/línea. así que es como:

Primera Línea: Inicio ---------> S + N (punto antes bloqueado)

Segunda/Medio Line/s: Bloqueado Punto ------ ----> S + N (antes de otro punto bloqueado) repetir nuevamente (nueva línea/segmento) hasta que establezca una línea de visión para el objetivo.

última línea: Point Bloqueado -------------> Goal

Conecte todas las líneas y usted tiene un camino más corto mucho más corto. Puede ejecutar nuevamente, pero a la inversa para agregar otra precisión, de modo que la línea de visión comenzará en la meta hasta el inicio.