Jump point search

Jump point searchMain

Community hub

Jump point search

7 pages, 0 posts

0 subscribers

Recent from talks

Be the first to start a discussion here.

Recent from talks

Be the first to start a discussion here.

Contribute something

About hubMembersContent overviewUpdatesRules

Main reference articles

Jump point search

View on Wikipedia

from Wikipedia

In computer science, jump point search (JPS) is an optimization to the A* search algorithm for uniform-cost grids. It reduces symmetries in the search procedure by means of graph pruning,^[1] eliminating certain nodes in the grid based on assumptions that can be made about the current node's neighbors, as long as certain conditions relating to the grid are satisfied. As a result, the algorithm can consider long "jumps" along straight (horizontal, vertical and diagonal) lines in the grid, rather than the small steps from one grid position to the next that ordinary A* considers.^[2]

Jump point search preserves A*'s optimality, while potentially reducing its running time by an order of magnitude.^[1]

History

[edit]

Harabor and Grastien's original publication provides algorithms for neighbor pruning and identifying successors.^[1] The original algorithm for neighbor pruning allowed corner-cutting to occur, which meant the algorithm could only be used for moving agents with zero width, limiting its application to either real-life agents (e.g., robotics) or simulations (e.g., many games).

The authors presented modified pruning rules for applications where corner-cutting is not allowed the following year.^[3] This paper also presents an algorithm for pre-processing a grid in order to minimize online search times.

A number of further optimizations were published by the authors in 2014.^[4] These optimizations include exploring columns or rows of nodes instead of individual nodes, pre-computing "jumps" on the grid, and stronger pruning rules.

Future work

[edit]

Although jump point search is limited to uniform cost grids and homogeneously sized agents, the authors are placing future research into applying JPS with existing grid-based speed-up techniques such as hierarchical grids.^[4]^[5]

References

[edit]

^ ^a ^b ^c D. Harabor; A. Grastien (2011). Online Graph Pruning for Pathfinding on Grid Maps (PDF). 25th National Conference on Artificial Intelligence. AAAI.
^ Witmer, Nathan (5 May 2013). "Jump Point Search Explained". zerowidth positive lookahead. Archived from the original on 2014-03-10. Retrieved 10 March 2014.
^ D. Harabor; A. Grastien (2012). The JPS Pathfinding System. 26th National Conference on Artificial Intelligence. AAAI. Archived from the original on 2020-11-09. Retrieved 2015-07-11.
^ ^a ^b Harabor, Daniel; Grastien, Alban. "Improving Jump Point Search" (PDF). Australian National University College of Engineering and Computer Science. Association for the Advancement of Artificial Intelligence (www.aaai.org). Retrieved 11 July 2015.
^ Adi Botea; Martin Muller (2004). "Near Optimal Hierarchical Path-Finding" (PDF). University of Alberta.

v t e Graph and tree traversal algorithms
Search	α–β pruning A* IDA* LPA* SMA* Best-first search Beam search Bidirectional search Breadth-first search Lexicographic Parallel B* Depth-first search Iterative deepening D* Fringe search Jump point search Monte Carlo tree search SSS*
Shortest path	Bellman–Ford Dijkstra's Floyd–Warshall Johnson's Shortest path faster Yen's
Minimum spanning tree	Borůvka's Kruskal's Prim's Reverse-delete
List of graph search algorithms

Revisions and contributors Edit on Wikipedia Read on Wikipedia

View on Grokipedia

from Grokipedia

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:

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, [goal](/page/Goal)): // Key JPS modification successors = [] for direction in possible_directions(node): if is_jumpable(direction): jump_point = jump(node, direction, [goal](/page/Goal)) if jump_point is valid: successors.append(jump_point) return successors

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]

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|)

max(∣x2−x1∣,∣y2−y1∣)+(2

−1)min(∣x2−x1∣,∣y2−y1∣) 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 called jump, 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)$

=(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:

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 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 then return n return jump(n, \vec{d}, s, g)

^[9] Here, 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$

successors(x) ← ∅ PruneNeighbours(x) for each neighbour n of x do jp ← Jump(x, Direction(x,n), s, g) if jp ≠ null then successors(x) ← successors(x) ∪ {jp} return successors(x)

Algorithm 2: Jump(x, ~d, s, g)
Input: Node

x

, direction ~d, start

s

, goal

g

Output: Nearest jump point from

x

in direction ~d, or null

n ← Step(x, ~d) if n is [obstacle](/page/Obstacle) or outside 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 components of ~d return Jump(n, ~d, s, g)

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]

Properties and Analysis

Optimality and completeness

Jump Point Search (JPS) maintains the optimality guarantees of the A* algorithm when applied to uniform-cost grid maps, provided the heuristic is admissible and consistent.^[1] By pruning symmetric paths that cannot lead to shorter routes, JPS eliminates suboptimal expansions without overlooking any potential optimal paths, ensuring the first solution found is the shortest in terms of path length.^[1] The optimality of JPS stems from its pruning rules, which preserve all necessary turning points on an optimal path. Specifically, each turning point along an optimal diagonal-first path is a jump point, allowing the algorithm to "jump" over straight-line segments that contain no deviations or better alternatives.^[1] This is formalized in the proof that jump point pruning always returns an optimal solution, as the jumped segments are symmetric and cannot hide shorter paths due to the uniform cost structure.^[1] JPS is also complete, meaning it will find a path if one exists between the start and goal in a finite, traversable grid. The algorithm explores all relevant directions from each jump point, ensuring exhaustive coverage of the search space without infinite loops in bounded environments. However, these guarantees hold only for uniform-cost grids; in non-uniform cost environments with varying edge weights, standard JPS may fail to produce optimal paths without modifications, as its pruning rules assume equal costs for traversable tiles.^[11] Adaptations such as Weighted Jump Point Search are required to restore optimality in such cases.^[11]

Computational complexity

Jump point search (JPS) shares the same worst-case time complexity as A* search, which is exponential in the depth of the solution path, denoted as

O(b^d)

where

b

is the branching factor and

d

is the depth, due to the potential for exploring a large portion of the state space in pathological cases.^[1] However, in practice, JPS achieves near-linear time complexity,

O(d)

, in open grid environments because the jumping mechanism allows traversal of long straight-line segments without expanding intermediate nodes, significantly reducing the number of expansions through symmetry breaking.^[1] The space complexity of JPS is equivalent to that of A* in the worst case,

O(b^d)

, as it maintains open and closed sets for priority queue operations.^[1] In typical scenarios, however, JPS stores fewer nodes overall—often on the order of

O(d)

—since pruning and jumping eliminate many redundant entries in the open list, resulting in lower memory usage without any additional overhead beyond standard A*.^[1] Empirical evaluations demonstrate substantial speedups for JPS over A* on large uniform grids. For instance, in benchmarks using maps from Baldur's Gate, JPS achieved up to 215 times fewer node expansions and 25-30 times faster search times compared to A* on 1000x1000 grids.^[1] Similar results hold for Dragon Age maps, with node expansion reductions of about 36 times, confirming 10-100x overall improvements in pathfinding efficiency on game-like terrains.^[1] Performance varies with environmental factors, particularly obstacle density. JPS excels in open areas where long jumps minimize expansions, but its benefits diminish in maze-like structures with high obstacle density and narrow corridors, where jumps are shorter and more forced neighbors increase computational overhead relative to A*.^[1]

Variants and Extensions

JPS+ and symmetric pruning

JPS+ represents an advanced variant of the Jump Point Search (JPS) algorithm, designed for static uniform-cost grids, where it employs offline precomputation to accelerate pathfinding by eliminating runtime recursion in jump identification. By precomputing the distance to the nearest jump point or wall in each of the eight possible directions from every grid cell, JPS+ enables constant-time successor generation during search, significantly reducing computational overhead compared to the online jumping of base JPS. This preprocessing step, which requires quadratic time but linear space, allows jumps to be resolved instantly, pruning more aggressively and minimizing the number of nodes expanded.^[12]^[13] A key enhancement in JPS+ involves integrating goal bounding, which incorporates the goal's direction into the pruning process to further reduce false positives in jump point detection. For each potential jump, goal bounding checks whether the goal lies within an axis-aligned bounding box associated with the jump direction from the current node; if not, the jump is pruned early, ensuring that only goal-relevant paths are explored. This goal-aware mechanism builds on base JPS's successor pruning by adding directional constraints, effectively narrowing the search space in open areas while maintaining optimality.^[14]^[13] Symmetric pruning, a foundational technique extended in JPS+ variants, exploits the inherent symmetries of uniform grids to avoid redundant explorations of equivalent paths, such as those that mirror each other across axes. In base JPS, this pruning discards successors that cannot lead to shorter paths due to grid uniformity, focusing expansions on "forced" neighbors near obstacles; JPS+ enhances this by precomputing symmetric equivalents during preprocessing, allowing runtime checks to skip mirrored explorations entirely. For instance, if a path segment is symmetric to another already evaluated, it is pruned without further scanning, preventing duplicate work in bidirectional or multi-query scenarios.^[15]^[12] The primary differences between JPS+ and base JPS lie in their handling of computation: base JPS performs online symmetry breaking via recursive scans, while JPS+ shifts this to offline precomputation with goal-aware jumps, and symmetric pruning adds runtime mirroring checks to both for duplicate avoidance. JPS+ requires static maps unsuitable for dynamic environments, whereas symmetric pruning can be applied online without preprocessing. These distinctions make JPS+ ideal for repeated queries on fixed grids, with symmetric pruning providing orthogonal optimizations for efficiency.^[12]^[13] In benchmarks on game maps like those from StarCraft and Dragon Age, JPS+ achieves up to 10x speedup over base JPS and over 100x over standard A* in open terrains, with symmetric pruning contributing an additional 20-50% reduction in expansions by eliminating mirrored paths. Performance gains are less pronounced in maze-like maps, where gains drop to 2-2.5x over A*, but remain significant for real-time applications.^[12]^[13]

Adaptations for 3D and non-uniform grids

Jump Point Search (JPS) has been extended to three-dimensional (3D) environments, particularly cubic voxel grids that support 26-directional movement, encompassing orthogonal, face-diagonal, and space-diagonal neighbors. In this adaptation, known as JPS-3D, jump point identification occurs across three axes by detecting forced neighbors that break path symmetries, allowing the algorithm to skip over symmetric regions while preserving optimality. Pruning in 3D shifts from linear scans in 2D to volumetric explorations, where unnecessary successor expansions are eliminated by limiting scan depths adaptively, resulting in significant speedups—often over an order of magnitude compared to standard A* on large 3D maps.^[16] For non-uniform or weighted grids, where cell traversal costs vary (e.g., due to terrain elevation or material differences), Weighted Jump Point Search (JPSW) modifies the original JPS by incorporating a tiebreaking policy to handle asymmetric costs and adjusting jump costs accordingly. Heuristics are updated to reflect weighted distances, ensuring the algorithm remains admissible and optimal. This adaptation has demonstrated substantial performance gains, reducing expanded nodes by orders of magnitude relative to weighted A* in benchmarks on game-like weighted maps.^[17] Recent extensions as of 2025 include improvements to JPS for weighted maps using artificial potential fields to further enhance efficiency in complex terrains, and adaptations for conflict-free 3D path planning in multi-unmanned aerial vehicle (UAV) scenarios with incremental updates to handle dynamic environments.^[18]^[19] Extensions to other grid types include adaptations for hexagonal grids, where JPS rules are reformulated to account for the six-directional connectivity and rotational symmetries, enabling efficient pathfinding in environments like strategy games or terrain modeling. For dynamic obstacles, JPS supports online recomputation by incrementally updating jump points upon environmental changes, avoiding full replanning in time-sensitive scenarios such as UAV navigation.^[20]^[21] Adapting JPS to 3D introduces challenges due to the exponential increase in directions (from 8 in 2D to 26 in 3D), leading to higher computational overhead in jump identification and symmetry pruning. Partial solutions, such as lazy evaluation of jumps—where full successor scans are deferred until necessary—help mitigate this by reducing immediate processing demands, though they require careful implementation to maintain completeness.

Applications

Video game AI

Jump point search (JPS) has been implemented in third-party plugins and assets for popular game engines such as Unity and Unreal Engine to enhance non-player character (NPC) navigation in grid-based level designs, particularly through preprocessing of static environments to identify key jump points and reduce search space during runtime.^[22]^[23] In these implementations, developers preprocess uniform-cost grids to store directional data, enabling faster A* searches for NPC pathfinding around obstacles in tile-based worlds.^[13] The primary benefits of JPS in video game AI include real-time performance on large-scale maps, such as those in open-world games, where it achieves up to 100 times the speed of standard A* by pruning symmetric paths and minimizing node expansions.^[13] This efficiency supports low CPU overhead for coordinating multiple agents, ensuring smooth gameplay without frame drops during intensive AI computations. For instance, in indie titles like a 2D zombie survival game, JPS facilitates rapid unit movement around dynamic obstacles, optimizing paths in real-time scenarios.^[24] A key trade-off involves reliance on precomputation for static levels, which excels in unchanging environments but requires additional runtime processing for dynamic elements, such as destructible terrain, potentially reverting closer to A* costs without full preprocessing.^[13] JPS maintains optimality on uniform grids, ensuring AI paths are as fair and direct as possible for competitive or cooperative gameplay.^[10] In robotics and autonomous navigation, Jump Point Search (JPS) is applied to physical systems where environments are approximated as discrete grids to facilitate efficient path planning. Sensor data from LiDAR or sonar is discretized into occupancy grids, with cells classified as free (value 0) or occupied (value 1) based on detected obstacles, providing a structured input for JPS to identify optimal jump points while avoiding unnecessary node expansions.^[25] This mapping process enables robots to navigate complex indoor or outdoor spaces by converting continuous sensor measurements into a searchable 2D or 3D lattice representation.^[25] JPS supports real-time path planning in mobile robots, such as warehouse automation bots, where it enables rapid obstacle avoidance by pruning symmetric paths and focusing on key decision points, achieving computation times under 500 ms on maps up to 2000×2000 cells.^[25] It is frequently combined with localization methods like Simultaneous Localization and Mapping (SLAM) to update grids dynamically as the robot moves, ensuring robust navigation in partially unknown or changing environments.^[26] JPS has been applied in wheeled mobile robot navigation, with improvements like bidirectional search for enhanced efficiency in complex environments.^[25] Extensions to 3D grids support volumetric navigation for aerial robots in confined spaces.^[27]

History

Initial development

Jump Point Search (JPS) was developed by Daniel Harabor and Alban Grastien at the National ICT Australia (NICTA) laboratory between 2011 and 2012.^[9] The algorithm emerged as a response to the inefficiencies of the A* search algorithm in uniform-cost grid environments, where A* often expands numerous redundant nodes due to the inherent symmetries of grid maps.^[9] The primary motivation for JPS stemmed from the need to accelerate pathfinding in applications such as video games and AI planning, drawing inspiration from techniques for symmetry reduction in graph search problems.^[9] Harabor and Grastien aimed to prune symmetric paths online during the search process without compromising the optimality of the resulting paths, addressing a key bottleneck in real-time navigation scenarios.^[9] The first prototype of JPS was designed specifically for 2D uniform grids supporting 8-directional movement, with initial testing conducted on benchmark maps derived from video game levels, such as those from Baldur's Gate and Dragon Age.^[9] Early development focused on identifying "jump points" to skip over symmetric regions efficiently, demonstrating significant speedups over standard A* in these environments.^[9] A central challenge in this initial phase was maintaining path optimality while aggressively pruning the search space, requiring formal proofs that the reduced graph preserved all shortest paths.^[9] The researchers successfully addressed this by ensuring that jump points represented the only necessary expansion points, thus guaranteeing completeness and optimality under uniform costs.^[9]

Key publications and advancements

The foundational work on Jump Point Search (JPS) was introduced in the 2011 paper "Online Graph Pruning for Pathfinding on Grid Maps" by Daniel Harabor and Alban Grastien, presented at the AAAI Conference on Artificial Intelligence, which proposed an online symmetry-reduction technique for A* search on uniform-cost grids, demonstrating speedups of up to two orders of magnitude on standard game maps. This was followed by their 2012 paper "The JPS Pathfinding System," published in the International Symposium on Combinatorial Search (SoCS), which formalized the JPS algorithm, including detailed successor pruning rules and empirical validation showing consistent performance gains over A* on diverse grid benchmarks. A significant advancement came in 2014 with the paper "Improving Jump Point Search" by Harabor and Grastien at the International Conference on Automated Planning and Scheduling (ICAPS), introducing JPS+ as an offline preprocessing variant that precomputes jump points to further accelerate searches on static maps, achieving up to 5-10 times faster query times compared to online JPS while maintaining optimality.^[2] Extensions to three-dimensional environments were detailed in the 2022 SoCS paper "The JPS Pathfinding System in 3D" by Daniel Harabor, Thomas K. Nobes, Michael Wybrow, and Simon D. C. Walsh, adapting the pruning rules for cubic grids and reporting reduced node expansions by factors of 10-100 on 3D benchmarks, enabling efficient pathfinding in volumetric spaces like urban simulations.^[28] More recent optimizations include the 2023 work "Reducing Redundant Work in Jump Point Search" by Shizhe Zhao, Daniel Harabor, and Peter J. Stuckey, published on arXiv and at SoCS, which proposes techniques to eliminate duplicate jumps in complex terrains, yielding 20-50% runtime reductions on large-scale grids without sacrificing completeness.^[29] In 2023, the AAAI paper "Optimal Pathfinding on Weighted Grid Maps" by Mark Carlson, Sajjad K. Moghadam, Daniel D. Harabor, Peter J. Stuckey, and Morteza Ebrahimi introduced Weighted Jump Point Search (JPSW), extending JPS to non-uniform cost grids while preserving optimality.^[30] Empirical evaluations of JPS and its variants have been extensively conducted using the Moving AI Lab's benchmark datasets, comprising real-world game maps (e.g., from Dragon Age and Starcraft), where JPS consistently demonstrates speedups of 10-100 times over standard A* in terms of expanded nodes and search time, particularly on sparse obstacle layouts. Open-source implementations, such as the C++ library jps3d on GitHub, have facilitated widespread adoption and further experimentation, supporting both 2D and 3D variants with modular extensions for custom grids.^[31] Ongoing research explores integrating JPS with learning-based planners, as seen in the 2019 paper "Integrating a Path Planner and an Adaptive Motion Controller for Navigation in Dynamic Environments" by J. Zhang, L. Qin, Y. Huang, Q. Yang, and C. Huang in Applied Sciences, which combines JPS for global paths with reinforcement learning for local adjustments, achieving high success rates in dynamic robotics scenarios.^[32] Efforts toward scalability on massive grids continue, with hybrid approaches addressing high-dimensional environments through precomputation and neural guidance to handle grids exceeding 10^6 cells efficiently.

History

Jump point search

Recent from talks

Recent from talks

Contribute something

Contribute something

Media Pages

Timelines

Articles

Notes collections

Notes

Notes

Days in Chronicle

Jump point search

History

Future work

References