Jump point search
An optimization of A* on uniform grids that jumps straight over uninteresting cells and only stops at the points where a path can actually turn.
On an open grid, A* wastes enormous time evaluating thousands of equivalent cells — there are many equal-length paths between two points. Jump point search prunes that symmetry: from a cell it "jumps" in a direction until it hits the goal, an edge or a so-called jump point where an obstacle forces a choice. Only the jump points go on the queue, not every intermediate step.
Daniel Harabor and Alban Grastien published the method in 2011. It needs no preprocessing, returns exactly the same optimal path as A*, and is often an order of magnitude faster on open terrain. The limitation is clear: it assumes a uniform-cost grid and does not apply directly to a navmesh or a weighted graph.