Ao experimentar o applet abaixo, vi que esse algoritmo de localização de caminhos chamado Jump Point Search produz resultados significativamente mais rápidos que o A * e o Dijkstra.
http://qiao.github.io/PathFinding.js/visual/
A *: 46 segundos
Dijkstra: 1 minuto e 39 segundos
Pesquisa de Jump Point: Menos de 3 segundos
Escusado será dizer que estou bastante surpreso com o resultado. Da representação visual, a Jump Point Search parece fazer muitas suposições aleatórias (provavelmente muito inteligentes) ao encontrar o caminho (pelo menos na seleção de blocos), mas ainda não encontrei um caso de teste em que esse algoritmo tenha piorado resultados que A * e Dijkstra.
Como esse algoritmo funciona? Como é tão eficiente em comparação com A * e Dijkstra?
fonte
Respostas:
A idéia básica é que o JPS permita descartar muitos caminhos candidatos antecipadamente, reduzindo assim a quantidade de cálculos necessários.
Em muitos mapas, vários caminhos com o mesmo custo levam ao mesmo destino, como um mapa de jogo com grandes áreas abertas. O JSP permite remover esses caminhos.
Uma explicação detalhada pode ser encontrada aqui .
fonte
Com a versão mais recente da ferramenta, o JPS é realmente mostrado mais lento que o A * para muitos tipos de gráficos, porque agora também mostram a recursão do JPS.
Isso também é verdade no mundo real; enquanto o JPS geralmente enfileira muito menos nós, ele geralmente examina muitos mais. Se isso resulta em uma aceleração real depende do gráfico.
fonte