Electronic copies of the paper in which this idea was first described are available from my homepage. It forms part of my doctoral research into pathfinding at NICTA and The Australian National University. Please note: this work was developed in conjunction with Alban Grastien.

Further, it is easily combined with most existing speedup techniques - including abstraction and memory heuristics. Unlike other similar algorithms JPS requires no preprocessing and has no memory overheads. JPS is faster and more powerful than RSR: it can consistently speed up A* search by over an order of magnitude and more. In this article I describe Jump Point Search (JPS) : an online symmetry breaking algorithm which speeds up pathfinding on uniform-cost grid maps by “jumping over” many locations that would otherwise need to be explicitly considered.

Part two discusses Rectangular Symmetry Reduction (RSR) : a simple yet effective preprocessing algorithm that eliminates many path symmetries by decomposing a grid map into a set of empty rectangles.Part one introduces the notion of path symmetry: a property of uniform-cost grid maps which can significantly slow down search.This is the final article in my three-part look at symmetry reduction algorithms for speeding up pathfinding on uniform-cost grid maps.

Node spyparty