A * Jump Point Search: ¿cómo funciona realmente la poda?

Question

Me he encontrado con Jump Point Search, y me parece muy dulce. Sin embargo, no estoy seguro de cómo funcionan realmente sus reglas de poda. Más específicamente, en la Figura 1, se establece que

podemos podar inmediatamente a todos los vecinos grises ya que estos pueden ser alcanzados de manera óptima desde el padre de X sin tener que ir a través del nodo x

Sin embargo, esto parece algo en desacuerdo. En la segunda imagen, se puede llegar al nodo 5 pasando primero por el nodo 7 y omitiendo x completamente a través de una ruta simétrica, es decir, 6 -> x -> 5 parece ser simétrica a 6 -> 7 -> 5. Esto sería igual a cómo se puede llegar al nodo 3 sin pasar por x en la primera imagen. Como tal, no entiendo cómo estas dos imágenes no son totalmente equivalentes, y no solo versiones giradas entre sí.

En segundo lugar, me gustaría entender cómo este algoritmo podría generalizarse a un volumen de búsqueda tridimensional.

Answer 1

Entiendo que esto se trata de prioridades. Para enumerar cada camino no simétrico, debe enumerar todos los nodos, pero realmente no importa qué camino elija, porque son simétricos. Entonces los autores decidieron ir con diagonal-primero, es decir, cualquier movimiento diagonal siempre aparece antes de cualquier movimiento recto en un camino. Es por eso que la recta tiene más nodos podados, porque debe estar ocurriendo después de que se hayan tenido en cuenta todas las diagonales.

Answer 2

La segunda imagen se muestra incorrectamente. Si echa un vistazo al texto que lo acompaña: "En ambos casos, podemos podar inmediatamente todos los vecinos grises, ya que se pueden alcanzar de manera óptima desde el padre de x sin pasar por el nodo x".

Énfasis en 'ambos casos'.

En términos de aplicar el concepto a un espacio tridimensional (o diablos, incluso un espacio n-dimensional), este algoritmo no es diferente de A * en que es simplemente una malla de nodos y conexiones. La dimensionalidad es completamente a su discreción.

Answer 3

Sí, JPS es dulce, pero limitado a los mapas con limitaciones específicas:

1. El mapa debe representar una cuadrícula.
2. Todas las celdas accesibles en la cuadrícula deben tener el mismo costo transversal.
3. El agente móvil debe tener 8 direcciones de viaje posibles: 4 direcciones cardinales y 4 diagonales.

La clave para el algoritmo es que esas limitaciones permiten algunas suposiciones clave:

1. La ruta geométrica más corta entre dos puntos (en ausencia de obstrucciones) es también ruta un mínimo costo.
2. Una ruta de costo mínimo entre dos puntos (en ausencia de obstrucciones) no necesita tener más de un cambio de dirección.

Estos supuestos permiten que el algoritmo de hacer caso omiso de opciones de ruta simétricas y operan de la siguiente manera:

1. Al viajar en una dirección cardinal sólo tiene que considerar un cambio de dirección cuando se encuentra un obstáculo en una de las posiciones ilustradas en los documentos. Estos puntos donde se debe considerar un cambio de dirección son los "Puntos de salto".
2. Cuando se viaja diagonalmente, solo se debe considerar un cambio de dirección cuando se puede "ver" un punto de salto en una de las dos direcciones cardinales de "avance", como se ilustra en los documentos.