Al probar el applet a continuación, vi que este algoritmo de búsqueda de ruta llamado Jump Point Search produce resultados significativamente más rápidos que A * y Dijkstra.
http://qiao.github.io/PathFinding.js/visual/
A *: 46 segundos
Dijkstra: 1 minuto 39 segundos
Búsqueda de punto de salto: menos de 3 segundos
No hace falta decir que estoy bastante asombrado por el resultado. A partir de la representación visual, Jump Point Search parece estar haciendo muchas suposiciones aleatorias (probablemente muy inteligentes) para encontrar la ruta (al menos desde la selección de bloques), pero aún no he encontrado un caso de prueba en el que este algoritmo haya empeorado resultados que A * y Dijkstra.
¿Cómo funciona este algoritmo? ¿Cómo es tan eficiente en comparación con A * y Dijkstra?
fuente
Respuestas:
La idea básica es que JPS permite descartar muchas rutas candidatas temprano, lo que reduce la cantidad de cálculos necesarios.
En muchos mapas, múltiples rutas con el mismo costo conducen al mismo destino, como un mapa de juego con grandes áreas abiertas. JSP permite podar esos caminos.
Una explicación en profundidad se puede encontrar aquí .
fuente
Con la última versión de la herramienta, JPS en realidad se muestra más lento que A * para muchos tipos de gráficos, porque ahora también muestran la recursividad de JPS.
Esto también es cierto en el mundo real; mientras que JPS generalmente pondrá en cola muchos menos nodos, generalmente examina muchos más. Si eso da como resultado una aceleración real depende del gráfico.
fuente