Jump point search
Jump Point Search (JPS) is a pathfinding algorithm that optimizes the A* search method for uniform-cost grid maps by selectively expanding only specific nodes known as "jump points," thereby pruning symmetric paths on the fly to achieve optimal solutions without preprocessing or additional memory overhead.[1] Developed by Daniel Harabor and Alban Grastien, it was introduced in 2011 as an online symmetry-breaking technique specifically designed for grids supporting cardinal and diagonal movements with costs of 1 and √2, respectively.[1][1] The core mechanism of JPS involves a macro-step operator that allows the search to "jump" from a node in a fixed direction—either straight or diagonal—until it reaches a jump point or encounters an obstacle, skipping intermediate nodes that would inevitably lie on any optimal path.[1] Jump points are identified through local pruning rules based on forced neighbors (obstacles that constrain movement) or proximity to the goal, ensuring that no optimal path is overlooked.[1] This approach guarantees optimality, as proven in the original formulation, while reducing the search space dramatically compared to standard A*.[1] In empirical evaluations on benchmark grid maps such as those from the Moving AI Lab (including Adaptive Depth, Baldur’s Gate, Dragon Age, and Rooms datasets), JPS demonstrated speedups over A* ranging from 20.37 times on Adaptive Depth to 215.36 times on Baldur’s Gate, with corresponding reductions in node expansions.[1] It also outperformed other symmetry-exploiting methods like Swamps (up to 20.37x vs. 1.89x speedup) and was competitive with hierarchical techniques such as HPA* (e.g., 35.95x vs. 9.63x on Dragon Age).[1] Subsequent improvements, including online and offline optimizations, have further enhanced its efficiency for applications in robotics, video games, and artificial intelligence planning.[2]Overview
Definition and purpose
Jump Point Search (JPS) is an optimized pathfinding algorithm designed for uniform-cost grid environments, serving as a symmetry-reducing enhancement to the A* search algorithm by expanding only specific nodes known as "jump points" rather than all neighboring cells.[1] This approach identifies and prunes redundant paths that arise due to the symmetric structure of grids, where multiple equivalent routes exist between points, thereby focusing the search on directionally significant nodes that could lead to optimal paths.[1] The primary purpose of JPS is to efficiently compute optimal paths in obstacle-filled rectangular grids, minimizing computational overhead while preserving the optimality and completeness guarantees of A*.[1] By exploiting the inherent symmetries in grid maps—such as straight-line traversals where intermediate nodes offer no unique routing advantages—JPS skips over these redundant expansions, potentially accelerating searches by an order of magnitude in large, open spaces compared to standard A*.[1] It assumes a uniform-cost model where cardinal movements (up, down, left, right) cost 1 unit and diagonal movements cost √2 units, operating on undirected grids with cells designated as either traversable or obstacles, and allowing up to eight possible neighbors per cell.[1] For instance, consider a simple 2D grid scenario with no obstacles, where the start point is at the bottom-left and the goal is at the top-right, forming a straight diagonal line. In standard A*, the algorithm would expand every intermediate cell along this path. JPS, however, identifies the direction of travel and "jumps" directly to the next jump point—such as the goal itself or a point where a deviation becomes possible—bypassing the in-between nodes and adding only the jump point as a successor.[1] This illustrates how JPS reduces the search space in symmetric, linear traversals without missing the optimal route.Relation to A* search
Jump point search (JPS) is an optimized variant of the A* algorithm specifically designed for uniform-cost grid maps, retaining A*'s core best-first search framework, including the use of open and closed sets to manage explored nodes and an admissible heuristic such as the Euclidean or Manhattan distance to guide the search toward the goal.[1] This integration allows JPS to inherit A*'s guarantees of optimality and completeness when the heuristic is consistent, without altering the fundamental evaluation function f(n) = g(n) + h(n), where g(n) is the path cost from the start to node n and h(n) is the estimated cost from n to the goal.[1] The primary modification in JPS lies in the successor generation phase, where instead of expanding all neighboring nodes (typically up to 8 in a grid), the algorithm applies symmetry-breaking pruning rules to identify only "jumpable" directions and advances directly to the next relevant node, known as a jump point, thereby skipping intermediate symmetric nodes that would not lead to optimal paths.[1] This jumping mechanism dramatically reduces the number of node expansions compared to standard A*, often achieving speedups of an order of magnitude or more in open terrains by eliminating redundant searches along straight-line or diagonal paths.[1] Heuristic consistency is preserved in JPS by ensuring that the admissible heuristic remains unchanged and that pruned nodes do not affect the monotonicity required for optimality, allowing the algorithm to find the shortest path without relaxation or approximation.[1] At a high level, JPS integrates with A* by replacing the standard successor function with a specialized one that incorporates pruning and jumping, as illustrated in the following pseudocode outline:This structure maintains A*'s efficiency while leveraging grid-specific optimizations, ensuring that only nodes where paths can deviate or encounter obstacles are fully expanded.[1]function JPS(start, goal): open_set = PriorityQueue() // prioritized by f(n) = g(n) + h(n) closed_set = Set() g_scores = {start: 0} open_set.insert(start, h(start)) while open_set is not empty: current = open_set.extract_min() if current == goal: return reconstruct_path(current) closed_set.add(current) for successor in identify_successors(current, goal): // JPS-modified: prunes and jumps tentative_g = g_scores[current] + distance(current, successor) if successor in closed_set or tentative_g >= g_scores[successor]: continue came_from[successor] = current g_scores[successor] = tentative_g f_score = tentative_g + h(successor) open_set.insert_or_update(successor, f_score) function identify_successors([node](/page/Node), [goal](/page/Goal)): // Key JPS modification successors = [] for [direction](/page/Direction) in possible_directions([node](/page/Node)): if is_jumpable([direction](/page/Direction)): jump_point = jump([node](/page/Node), [direction](/page/Direction), [goal](/page/Goal)) if jump_point is valid: successors.append(jump_point) return successorsfunction JPS(start, goal): open_set = PriorityQueue() // prioritized by f(n) = g(n) + h(n) closed_set = Set() g_scores = {start: 0} open_set.insert(start, h(start)) while open_set is not empty: current = open_set.extract_min() if current == goal: return reconstruct_path(current) closed_set.add(current) for successor in identify_successors(current, goal): // JPS-modified: prunes and jumps tentative_g = g_scores[current] + distance(current, successor) if successor in closed_set or tentative_g >= g_scores[successor]: continue came_from[successor] = current g_scores[successor] = tentative_g f_score = tentative_g + h(successor) open_set.insert_or_update(successor, f_score) function identify_successors([node](/page/Node), [goal](/page/Goal)): // Key JPS modification successors = [] for [direction](/page/Direction) in possible_directions([node](/page/Node)): if is_jumpable([direction](/page/Direction)): jump_point = jump([node](/page/Node), [direction](/page/Direction), [goal](/page/Goal)) if jump_point is valid: successors.append(jump_point) return successors
Background
Grid-based pathfinding
Grid-based pathfinding refers to the process of finding the shortest path between two points in a discrete 2D lattice composed of cells, where certain cells are designated as obstacles that cannot be traversed.[3] This approach models the environment as a graph, with each free cell (or grid point) serving as a node and possible movements between adjacent cells as edges.[4] It is commonly applied in domains such as robotics, video games, and simulations to enable navigation around barriers while minimizing path length or cost.[3] Movement in grid-based pathfinding is governed by specific models that define allowable directions and associated costs. The cardinal (or 4-neighbor) model permits movement only in four orthogonal directions—north, south, east, and west—resulting in uniform costs for horizontal and vertical steps.[3] The 8-directional (or octile) model extends this by including four diagonal directions, allowing for more natural, shorter paths in open spaces, with costs of 1 for orthogonal moves and √2 for diagonal moves.[1] These models assume a regular lattice structure where each cell connects to its immediate neighbors based on the chosen connectivity. Grids are typically represented using 2D arrays to store cell states, with free spaces marked as traversable and obstacles as impassable to prevent expansion into blocked areas.[5] Adjacency can be implicitly defined through array indexing for efficiency, or explicitly via lists that enumerate neighbors according to the movement model, facilitating graph search operations.[3] This representation simplifies implementation but requires careful handling of boundary conditions and obstacle integration. A key challenge in grid-based pathfinding arises from the potentially high node count in large environments, such as expansive maps with thousands of cells, which can generate exponential search spaces during exploration without targeted optimizations.[5] Obstacles further complicate this by fragmenting the space and increasing the branching factor, demanding efficient pruning or heuristic guidance to maintain computational feasibility.[3] A* search serves as a standard informed method for addressing these issues in grid environments.[6]Limitations of standard A* on grids
In uniform-cost grid maps, the standard A* algorithm encounters substantial inefficiencies stemming from the inherent symmetry of the grid structure. Numerous paths between the start and goal nodes are equivalent in cost but differ merely in the sequence of moves, prompting A* to generate and evaluate a large number of redundant states. This symmetry arises because uniform edge weights make detours and alternative routings indistinguishable in terms of path length until later in the search, causing the algorithm to explore unnecessary branches that do not contribute to the optimal solution.[1] A key manifestation of this issue occurs during straight-line pathfinding, where A* expands intermediate nodes along the route while checking all possible symmetric continuations, such as diagonal or orthogonal deviations that could be pruned if grid topology were better exploited. In an empty grid without obstacles, for instance, A* generates a diamond-shaped expansion front (under Manhattan distance) or approximately elliptical front (under octile distance), evaluating every node within the bounding ellipse defined by the goal's initial f-value and wasting effort on backtracking or circuitous paths that symmetry renders suboptimal. This leads to excessive node generations, as dominated states—those reachable via multiple equivalent routes—are not inherently identified and discarded.[1] The expansion overhead exacerbates these problems, with A* routinely examining up to 8 neighbors per node in 8-connected grids, resulting in a worst-case time complexity of O(b^d), where b = 8 is the branching factor and d is the solution depth. Even when employing consistent and admissible heuristics like the octile distance—which computes \max(|x_2 - x_1|, |y_2 - y_1|) + (\sqrt{2} - 1) \min(|x_2 - x_1|, |y_2 - y_1|) to provide a tight lower bound on costs in grids allowing diagonal traversal with costs of 1 and \sqrt{2}—A* fails to prune symmetric successors, as the heuristic does not leverage the grid's regular structure to eliminate equivalent paths on the fly.[1][7][8] These limitations motivate symmetry-breaking techniques, such as Jump Point Search, which address redundant expansions by pruning successors based on grid-specific rules.[1]Core Algorithm
Successor pruning
Successor pruning in Jump Point Search (JPS) is a symmetry-reduction technique applied during node expansion to eliminate redundant successor candidates in grid-based pathfinding, focusing only on "natural" neighbors that cannot be reached via equally optimal symmetric paths from the node's parent.[9] This pruning leverages the uniform cost structure of grids, where intermediate nodes along straight, obstacle-free paths are unnecessary to expand individually, as optimal paths would not deviate symmetrically.[10] By discarding these dominated successors, JPS significantly reduces the branching factor from up to 8 neighbors in standard A* to as few as 4, enhancing efficiency without sacrificing optimality.[9] Natural neighbors are the direct adjacent cells that remain after applying pruning rules, representing the minimal set required to preserve all possible optimal paths; these are typically the cells in the four cardinal directions (up, down, left, right) relative to the expansion direction, unless symmetry allows further reduction.[10] In contrast, forced neighbors are additional successors that must be considered due to obstacles blocking alternative symmetric paths; these arise when the path through the current node is strictly shorter than any detour around obstacles, ensuring no optimal path is overlooked.[9] For instance, in an open grid, forced neighbors are rare, but near walls or barriers, they can appear in up to four positions, such as when a diagonal move is compelled by an adjacent blockage.[10] Pruning rules differ by movement type. For horizontal or vertical (cardinal) moves, a neighbor is pruned if an alternative path from the parent to that neighbor exists with length less than or equal to the path via the current node, which occurs in straight-line scenarios without obstacles; thus, only the immediate neighbor in the direction away from the parent typically survives as natural.[9] For diagonal moves, pruning is stricter: a neighbor is eliminated if an alternative path of equal length includes an earlier diagonal step, or if a shorter path exists; this often leaves up to three natural diagonal neighbors, but forced ones may be retained if cardinal paths adjacent to the diagonal are obstructed.[10] Algorithmically, during the expansion of a node with parent p, JPS first identifies the incoming direction from p and applies the rules to generate only natural and forced successors in the eight possible directions, skipping pruned ones entirely.[9] This step checks for obstacle-induced forces by verifying if adjacent cells block symmetric alternatives, ensuring the search proceeds only to viable candidates before identifying jump points as the endpoints of these pruned paths.[10]Jump point identification
Jump points in Jump Point Search (JPS) are defined as nodes from which an optimal path can first deviate from the straight-line direction inherited from its parent node, typically due to obstacles, the goal, or branching opportunities that force a turn.[9] Specifically, a node y is a jump point from a node x in direction \vec{d} if y = x + k \vec{d} for some positive integer k that minimizes k, and y satisfies one of the following: it is the goal node; it has a forced neighbor (a neighbor not reachable via a natural extension of the incoming direction); or, if \vec{d} is diagonal, a successor in one of the cardinal directions from y leads to another jump point.[9] This definition ensures that only these pivotal nodes are considered for expansion, allowing the search to skip intermediate symmetric nodes along straight-line paths.[9] The identification of jump points relies on a recursive scanning function calledjump, which traverses the grid in a specified direction until a jump point is encountered or the scan terminates without finding one.[9] The function takes as input the current node x, the direction vector \vec{d} (one of eight possible moves: four cardinal or four diagonal), the start node s, and the goal g.[9] Directions are represented by unit vectors, such as (1,0) for right or (1,1) for northeast.[9] For diagonal directions, the function also considers the two orthogonal cardinal components \vec{d_1} and \vec{d_2} (e.g., right and up for northeast) to check for potential deviations.[9] Pruning ensures that only these identified jump points are added to the open set during search.[9]
Step-by-step, the jump function proceeds as follows: from the current node x, it advances to the next node n by stepping in direction \vec{d}; if n is an obstacle or outside the grid boundaries, it returns null to indicate no jump point; if n is the goal, it returns n; if n has any forced neighbor (a neighbor that cannot be reached symmetrically from the parent direction), it returns n as the jump point; for diagonal \vec{d}, it recursively calls jump on n in directions \vec{d_1} and \vec{d_2}, returning n if either yields a non-null result indicating a deviation; otherwise, it recurses on n in the original direction \vec{d}.[9] This process continues linearly until a termination condition is met, effectively "jumping" over non-branching cells.[9]
For example, consider a grid with a wall blocking a straight path; starting from node x moving northeast (\vec{d} = (1,1)), the scan proceeds diagonally until reaching a node y adjacent to the wall, where a forced neighbor (e.g., a cell around the wall's corner) exists, making y the jump point just before the obstacle forces a turn.[9]
The pseudocode for the jump function is as follows:
[9] Here,Function jump(x, \vec{d}, s, g): n ← step(x, \vec{d}) // Advance one step in direction \vec{d} if n is [obstacle](/page/Obstacle) or outside [grid](/page/The_Grid) then return [null](/page/Null) if n = g then return n if ∃ n' ∈ neighbors(n) such that n' is forced then return n if \vec{d} is diagonal then for i ∈ {1, 2} do if jump(n, \vec{d_i}, s, g) ≠ [null](/page/Null) then return n return jump(n, \vec{d}, s, g)Function jump(x, \vec{d}, s, g): n ← step(x, \vec{d}) // Advance one step in direction \vec{d} if n is [obstacle](/page/Obstacle) or outside [grid](/page/The_Grid) then return [null](/page/Null) if n = g then return n if ∃ n' ∈ neighbors(n) such that n' is forced then return n if \vec{d} is diagonal then for i ∈ {1, 2} do if jump(n, \vec{d_i}, s, g) ≠ [null](/page/Null) then return n return jump(n, \vec{d}, s, g)
step computes the adjacent node, neighbors checks the eight possible adjacent cells, and a neighbor is "forced" if it lies in a direction not aligned with the incoming \vec{d}.[9]
Overall search procedure
Jump Point Search (JPS) operates as a variant of the A* algorithm, where the core search loop remains similar—maintaining an open set prioritized by the evaluation function f(n) = g(n) + h(n), where g(n) is the cost from the start to node n and h(n) is a heuristic estimate to the goal—but the successor generation is replaced by a specialized procedure that identifies and jumps to relevant jump points rather than enumerating all immediate neighbors.[9] This integration allows JPS to prune symmetric paths on-the-fly during the search, expanding only nodes that represent necessary turning points or the goal.[9] The high-level steps begin with initializing the open set to contain the start node, setting its g-score to 0 and parent to null. While the open set is not empty, the node with the lowest f-score is dequeued as the current node. If the current node is the goal, the search terminates successfully, and the path is reconstructed by backtracking through parent pointers. Otherwise, successors are generated by first pruning the eight possible neighbors of the current node based on direction from the parent to avoid revisiting symmetric paths, then for each unpruned neighbor direction, invoking a jump function to identify the next jump point in that direction, which may span multiple grid cells. These identified jump points are then evaluated: if they offer a better or equal path cost and have not been processed with a lower cost, they are added to or updated in the open set with updated g-scores, f-scores, and parents pointing back to the current node.[9] In 8-directional grids, the procedure explicitly handles both cardinal (up, down, left, right) and diagonal movements, with diagonal steps costing \sqrt{2} times the cardinal cost. Pruning ensures that only promising directions are explored, and the jump function checks for forced neighbors or goal convergence separately for diagonal cases by briefly scanning perpendicular cardinal directions to detect potential jump points that would force a deviation.[9] This maintains consistency across movement types without altering the underlying A* priority mechanism. The search terminates upon dequeuing the goal node, yielding an optimal path via reconstruction, or when the open set empties, indicating no path exists. Edge cases include scenarios where the start coincides with the goal, resulting in an immediate trivial path of length zero; where the start or goal is an obstacle, in which case the search either fails immediately or cannot reach the goal, respectively; and grids with no feasible path due to obstacles, exhausting the open set without success.[9] The complete procedure can be expressed through the following key components integrated into A*, as detailed in the original formulation:[9] Algorithm 1: IdentifySuccessors(x, s, g)Input: Current node x, start s, goal g
Output: Set of jump point successors of x
Algorithm 2: Jump(x, ~d, s, g)successors(x) ← ∅ PruneNeighbours(x) for each neighbour n of x do jp ← [Jump](/page/Jump)(x, [Direction](/page/Direction)(x,n), s, g) if jp ≠ null then successors(x) ← successors(x) ∪ {jp} return successors(x)successors(x) ← ∅ PruneNeighbours(x) for each neighbour n of x do jp ← [Jump](/page/Jump)(x, [Direction](/page/Direction)(x,n), s, g) if jp ≠ null then successors(x) ← successors(x) ∪ {jp} return successors(x)
Input: Node x, direction ~d, start s, goal g
Output: Nearest jump point from x in direction ~d, or null
These functions are invoked within the A* loop for each expanded node, ensuring that only verifiable jump points are enqueued, with the parent of each jump point set to the originating node x rather than intermediate steps.[9]n ← Step(x, ~d) if n is [obstacle](/page/Obstacle) or outside [grid](/page/Grid) then return null if n = g then return n if HasForcedNeighbour(n, ~d) then return n if ~d is diagonal then if Jump(n, ~d1, s, g) ≠ null or Jump(n, ~d2, s, g) ≠ null then return n // where ~d1, ~d2 are [cardinal](/page/Cardinal) components of ~d return Jump(n, ~d, s, g)n ← Step(x, ~d) if n is [obstacle](/page/Obstacle) or outside [grid](/page/Grid) then return null if n = g then return n if HasForcedNeighbour(n, ~d) then return n if ~d is diagonal then if Jump(n, ~d1, s, g) ≠ null or Jump(n, ~d2, s, g) ≠ null then return n // where ~d1, ~d2 are [cardinal](/page/Cardinal) components of ~d return Jump(n, ~d, s, g)