3 ms·

Check out JPS+ if you need to go "over 100 times faster than A*" https://www.gdcvault.com/play/1022094/JPS-Over-100x-Faster-than https://www.gdcvault.com/play/

• amitp 8y ago
  Also check out A* if you want to go 1000 times faster than JPS ;------) A* does well when it is given a graph of all the decision points that matter. An unweighted grid is full of locations where it doesn't matter — e.g. whether you go N,N,E or E,N,N or N,E,N. JPS searches for better decision points on unweighted grids. There are lots of other A* optimizations for unweighted grids (subgoal graphs, contraction hierarchies, differential heuristics, bucketed priority queues, etc.) — see Table 2 in this paper [1]. JPS is notable for using no precomputation, which is very useful when the map is changing often. If you can afford analyzing the grid ahead of time, you can build a much better graph than using the grid directly — the Tree entry listed in Table 2 takes 30 sec of precomputation to bring A* down to 0.029 ms on average, compared to JPS which takes 62.524 ms on average. [1] https://www.aaai.org/ocs/index.php/SOCS/SOCS15/paper/view/11290 https://www.aaai.org/ocs/index.php/SOCS/SOCS15/paper/view/11...