And if your maps don't change, you can use precomputation with A* , making it even faster than JPS+. 1. Preprocess the graph to make it smaller. Visibility gra

And if your maps don't change, you can use precomputation with A* , making it even faster than JPS+. 1. Preprocess the graph to make it smaller. Visibility graphs are a first step, but if you have grid movement you can remove the redundancies (e.g. N-N-W taking you to the same place as W-N-N) to make an even smaller pathfinding graph. Here's a library implementing one of many such algorithms: http://mikolalysenko.github.io/l1-path-finder/www/ http://mikolalysenko.github.io/l1-path-finder/www/ 2. Preprocess the graph to get better distance estimates. The closer your A* heuristic is to the actual distance, the faster A* will run. “Differential heuristics” use the triangle inequality: if you have exact distances to one point L, then you can say dist(A, B) >= dist(L, B) - dist(L, A). There are other approaches too. There's a recent paper http://www.cs.du.edu/~sturtevant/papers/GPPC-2014.pdf http://www.cs.du.edu/~sturtevant/papers/GPPC-2014.pdf that covers some of the optimizations for pathfinding on grids.