The paper studies optimal pathfinding on eight-neighbor grid maps with blocked and unblocked cells. Jump Point Search and Subgoal Graphs both remove redundant symmetric paths, but they do so in different practical ways: JPS prunes successors during search, whereas SG identifies important vertices and builds an abstraction during preprocessing. The authors argue that the relationship between the methods, including their respective strengths and weaknesses, had not been sufficiently understood. Their work formalizes the common structure and evaluates the resulting methods against each other and against established grid-pathfinding techniques.
The first contribution is a graph-theoretic description showing that JPS, like SG, connects vertex pairs through a direct reachability relation. The second is the extraction of a graph containing all jump points, called a Jump Point Graph or JP, which makes JPS compatible with preprocessing-based speedups. The paper also describes a Diagonal Merged Jump Point Graph variant, JPD, whose additional jump points allow diagonal-first scans to terminate earlier. The excerpt states that JPD can be constructed with time and space proportional to the product of the map width and height. Finally, the study combines JP and its variants with bidirectional search and Contraction Hierarchies, and compares them with SG and other leading methods. The authors present this as the first way to incorporate JPS-style pruning into abstraction-based speedup techniques.
The underlying problem is an eight-neighbor grid graph derived from a map. Cardinal moves cost one and diagonal moves cost the square root of two; diagonal moves are legal only when the adjacent-corner condition prevents corner cutting. The Octile distance in obstacle-free space is used as the heuristic. JPS retains successors that allow a taut continuation of the current path and cause diagonal moves to occur as early as possible, pruning other symmetric alternatives without losing optimality. To make this behavior explicit, the paper defines a direction-extended graph in which each grid cell is represented once for each possible move direction. Edges in this expanded graph encode the local conditions for cardinal and diagonal-first, taut continuation. JP uses the resulting jump-point connectivity as a preprocessed search structure. At query time, the start and target are connected to suitable jump points, followed by a Connect-Search-Refine procedure similar in spirit to SG. Clearances are precomputed distances to relevant cells in a direction; they support both SG successor identification and JPS jump generation. JP stores forward and backward clearance information, while the reported SG implementations store eight directional clearances per cell.
The evaluation uses standard grid-based pathfinding benchmarks from Sturtevant’s repository, game-derived instances from the 2014 Grid-based Path Planning Competition, and the full set of instances from that competition. The principal comparison includes SG, JP, JPD, and Contraction Hierarchies applied to each of them as CH-SG, CH-JP, and CH-JPD. CH-G, a fast Contraction Hierarchies implementation using bidirectional Dijkstra, stall-on-demand, and midpoint-based path unpacking, serves as an important reference. The reported measures include graph edge counts, expanded vertices, branching factor, runtime, storage, and preprocessing time. All searches use the Octile heuristic and a binary-heap priority queue. The supplied excerpt gives the hardware and broad outcomes, but it does not provide every measurement, every map-level breakdown, the number of queries, or measures of variance.
On game-map instances, JP is reported to have substantially fewer edges than SG, to expand fewer nodes, to have a smaller branching factor, and to run faster by several factors. Adding Contraction Hierarchies reduces the gap between the JP and SG variants, but CH-JP and CH-SG are both reported to be faster than CH-G in the relevant comparison. The paper attributes most of CH-JP’s advantage over CH-SG to faster Search and Refine stages; their Connect stages are comparable. Although JP target insertion has a worst-case linear-time requirement, the authors report that it is fast in practice. These benefits are not universal: JP can be much slower than CH-G on random maps, and the full GPPC aggregate is also unfavorable. Further optimizations for JP or JPD combined with Contraction Hierarchies are identified as future work.
JPS and SG are successful symmetry-breaking approaches for speeding up optimal pathfinding on grids. JPS prunes unnecessary successors during search and jumps along directions, whereas SG selects distinguished subgoal vertices during offline preprocessing and builds an abstraction for fast and optimal pathfinding in directed weighted graphs. Both methods rely on a direct notion of reachability between important locations, even though their implementations and query procedures look different. This paper places them in a shared framework rather than treating JPS only as an online pruning rule.
Given a grid map, the task is to find a minimum-cost path from a start cell to a target cell while respecting blocked cells and the no-corner-cutting rule. A shortest path in the obstacle-free grid is called a freespace-shortest path, and it is usable on the actual graph only when all of its moves remain unblocked. The computational challenge is to preserve optimality while avoiding the many paths that differ only by reordering equivalent cardinal and diagonal moves. A practical solution must also keep preprocessing, storage, query connection, search, and path-refinement costs manageable.
The direction-extended graph represents each cell-direction state separately, allowing the search space induced by JPS to be described explicitly. A jump-point graph records the meaningful direct connections produced by cardinal scans and diagonal-first scans. The diagonal-merged variant adds jump points at suitable convex corners so that scans can stop sooner; the excerpt states that JPD can be constructed with time and space proportional to the product of the map width and height. During a query, cardinal successors of the start can be obtained through constant-time clearance lookups, while diagonal expansion performs further clearance checks. The same clearance idea appears in SG, but it is used to identify subgoal successors rather than to generate JPS jumps.
The experiments run on a 3.6 GHz Intel Core i7-7700 system with 32 GB of RAM. The implementations are in C++ and are derived from a common CH-SG code base, except for CH-G. SG and CH-SG store clearance values in all eight directions for each grid cell, while JP and CH-JP store forward and backward clearances, totaling sixteen values per cell; each value occupies one byte, with longer distances retrieved in multiple steps. The searches use the Octile heuristic and a binary heap. The supplied material does not establish the complete query protocol, repetitions, per-map sample sizes, or statistical uncertainty.
For the game-derived GPPC instances, the paper reports that JP has many fewer edges than SG, expands many fewer nodes, has a smaller branching factor, and is faster by several factors. The advantage of CH-JP over CH-SG is mainly associated with Search and Refine, while Connect is comparable; both are reported to outperform CH-G in that comparison. In a comparison with JPS+BB on GPPC benchmarks, the excerpt reports that CH-JP is 4.83 times faster than CH-G, uses 49 percent less storage, and has 51 percent shorter preprocessing. It describes JPS+BB as 2.42 times faster than CH-G, with 16 percent less storage and 3.14 times longer preprocessing. The paper also reports unfavorable cases: on all GPPC instances JP is 7.48 times slower than CH-G, and on random maps JP is two orders of magnitude slower. These figures are quoted from the supplied excerpt; the complete experimental conditions are not established there.
The paper concludes that JPS and SG have a common reachability structure and that JPS can therefore be represented as a preprocessing-based jump-point graph. JP enables JPS-style pruning to be combined with Contraction Hierarchies and related speedups for the first time in the paper’s account. The authors state that JP is uniformly better than SG, including on random maps where it may contain more jump points than subgoals, and that the combination improves the state of the art for game-map path planning. The reported results support strong benefits on some benchmarks, but they also document substantial disadvantages on random maps and on the full GPPC aggregate.
The supplied text omits substantial intermediate material, so the complete definitions, proofs, theorem assumptions, and full 提案手順c procedures cannot be verified from the excerpt alone. It summarizes many results at the benchmark-set level without providing all per-map values, query counts, variance measures, or statistical tests. JP has worst-case linear-time target insertion and requires directional clearance storage. Most importantly, the reported results are for single-agent grid pathfinding; direct performance or correctness consequences for MAPF or MAPD are not established by the supplied evidence.
The main significance is conceptual as well as empirical: the paper turns a search-time pruning method into an explicit, preprocessable graph representation. That bridge opens the use of Contraction Hierarchies and other abstraction-based techniques for jump-point search while preserving the goal of optimal grid paths. The study also clarifies that fewer expansions and faster searches do not guarantee the best total performance on every map family, making storage, preprocessing, connection, and refinement costs important design variables.
This paper is a good fit for researchers studying optimal grid pathfinding, JPS, Subgoal Graphs, Contraction Hierarchies, and symmetry-breaking search. It is especially useful for readers who want to understand how online directional pruning can be converted into a reusable abstraction and how that abstraction behaves on game and random maps. MAPF and MAPD researchers should treat it as a single-agent low-level planning foundation rather than as evidence of multi-agent performance, since the supplied paper excerpt does not evaluate those settings.