The setting is shortest-path search on static, 8-connected grid maps in which each cell is traversable or blocked. Orthogonal moves cost 1 and diagonal moves cost the square root of 2, so many paths can have identical optimal cost because of grid symmetry. Jump Point Search removes much of this symmetry online, while Goal Bounding rules out directions that cannot lead to the chosen target. Existing high-performance combinations of these ideas require all-pairs auxiliary preprocessing, creating a major practical cost.
The first contribution is to precompute and store Goal Bounding information only for cells that are independent jump points rather than for every grid cell or edge. Because jump points are usually much fewer than all cells, the paper reports more than one order of magnitude of savings in preprocessing time and space, approaching two orders of magnitude on some benchmark cases. The second contribution is a set of online techniques—canonical orderings, partial expansion, and enhanced intermediate pruning—that make more effective use of the smaller database. These ideas yield three algorithms: the search-based JPS+BB+ and TOPS, and the path-extraction method Topping+, for which the paper gives theoretical completeness and optimality results.
Jump Point Search is built on A* and skips redundant intermediate cells by continuing in straight or diagonal directions until a jump point or another relevant event is reached. The proposed preprocessing first identifies independent straight and diagonal jump points, then associates Goal Bounding data with those points. Two forms of auxiliary data are considered: geometric containers represented as bounding boxes, and Compressed Path Databases. During a query, a frontier of candidate jump points is maintained; the JPS+BB+ variant uses a binary heap ordered by the usual A* f-cost and the standard octile heuristic. Goal Bounding removes successors that cannot reach the target, intermediate pruning eliminates candidates earlier in the recursive reasoning, partial expansion stops unnecessary successor generation, and start-successor pruning reduces work near the beginning of the search. TOPS combines A*-like search with two-oracle information, whereas Topping+ is based on extracting a path using compressed auxiliary information.
The evaluation has three parts: partial Goal Bounding with geometric containers, partial Goal Bounding with Compressed Path Databases, and broad comparisons against baseline algorithms. It uses benchmarks from Sturtevant’s repository and the complete set of problems from the 2014 Grid-based Path Planning Competition. The competition benchmark contains 132 maps and 347,868 instances, including game-derived maps and synthetic maps. Baselines include JPS+BB, Topping, the overall fastest competition entry, and other recent grid pathfinding methods; however, the supplied excerpt does not provide every baseline, hardware condition, metric definition, or result for every experiment.
The evidence indicates that reducing the offline database does not inherently degrade query performance. For the bounding-box variant, preprocessing time and space improve by more than one order of magnitude overall, with results close to two orders of magnitude on at least one benchmark, although the exact gain depends on map topology. The compressed-database variant shows the same general pattern: compression makes preprocessing somewhat slower than in the bounding-box experiment, but total space can improve by up to about two orders of magnitude and the databases can be several factors smaller than the comparison compressed representation. The excerpt does not establish that one proposed method is fastest on every map or against every baseline, so such a universal ranking should not be inferred.
A* is a standard shortest-path algorithm that prioritizes states using path cost plus a heuristic estimate to the goal. On an 8-connected grid, the octile distance is the standard heuristic consistent with the stated orthogonal and diagonal costs. Grid pathfinding often contains many symmetric paths with equal cost, and exploring all of them wastes effort. Jump Point Search is an online symmetry-breaking technique that keeps only strategically necessary jump points. Goal Bounding is a family of pruning methods that precomputes, for a directed search transition, the set or region of goals that can be reached through it, allowing other goals to be rejected during a query.
JPS and Goal Bounding provide complementary speedups, but previous combinations such as JPS+BB and Topping rely on an all-pairs preprocessing phase. That phase grows quadratically with map size and can require hours and hundreds of megabytes for one StarCraft map on one machine. A collection of maps can consequently require tens of gigabytes of auxiliary storage. Parallel CPUs can accelerate the many Dijkstra-style computations, but parallel hardware does not remove the storage burden. The paper therefore addresses the practical question of how to preserve fast queries without materializing Goal Bounding information everywhere.
The key observation is that a canonical optimal path can be represented through independent jump points, so Goal Bounding data need not be attached to every cell. Independent straight and diagonal jump points can be identified using local grid structure and distance-to-obstacle information, with a linear-time procedure described for the diagonal case. The implementation described in the excerpt uses two bytes per jump-distance label, but this is an implementation detail rather than a general memory requirement for every variant. Canonical tie-breaking makes equivalent choices consistent and can reduce both stored information and online work. The framework is deliberately compatible with both geometric bounding boxes and compressed path databases.
The geometric-container experiment compares JPS+BB, which stores a bounding-box label for every grid edge and performs full all-pairs preprocessing, with JPS+BB+, which stores information only for independent jump points. The compressed-database experiment compares Topping with the proposed TOPS and Topping+ designs, using compressed path information together with Jump Point Search. The broad evaluation covers maps and instances from the Sturtevant benchmark collection and all problems in the 2014 competition, including game maps, rooms, and mazes as well as synthetic cases. The implementations are based on code released by the original authors of JPS+BB and SRC, together with reference compressed-path-database code and competition submissions.
The supplied evidence supports substantial preprocessing reductions for JPS+BB+: more than one order of magnitude in time and space, with some benchmark results approaching two orders of magnitude. For the Compressed Path Database approach, total space improves by up to about two orders of magnitude; preprocessing times are somewhat larger because compression adds overhead, but the resulting databases are often several times smaller than the comparison compressed representation. Online pruning components reduce candidate successors and can stop recursive processing earlier, supporting query improvements despite the smaller auxiliary database. The excerpt gives a few aggregate and illustrative measurements, but it does not establish complete per-map query-time rankings, exact averages, confidence intervals, or a universally best method.
Goal Bounding and Jump Point Search exploit different sources of redundancy in static grid pathfinding, and their combination can be made more practical than earlier designs. Restricting auxiliary data to jump points removes much of the all-pairs preprocessing and storage burden. Stronger online reasoning then compensates for the reduced database, rather than treating smaller preprocessing as an unavoidable query-time loss. The paper presents JPS+BB+, TOPS, and Topping+ as complete and optimal algorithms with convincing empirical support across a broad benchmark collection.
The supplied excerpt omits many exact values, including full query-time distributions, hardware specifications, all memory measurements, and the detailed ranking of every baseline. Benefits depend on map topology and jump-point density; maps with relatively many jump points may obtain smaller preprocessing reductions. The approach assumes a static grid, so frequent obstacle changes would require updating or rebuilding auxiliary data. The excerpt also does not quantify the maintenance cost for dynamic environments or establish how the methods transfer to nonuniform costs, non-grid graphs, or approximate pathfinding. The paper identifies integration of symmetry breaking, Goal Bounding, and graph-based speedups as an area for future work.
This work addresses an important systems trade-off in repeated shortest-path queries: extremely fast online search can be unattractive if it requires hours of preprocessing and tens of gigabytes of stored data. The jump-point restriction offers a principled way to reduce that burden while preserving exactness. Its online techniques also show that a smaller database can be paired with stronger reasoning rather than simply accepting slower queries. The ideas are particularly relevant to games, robotics, and other applications that reuse a fixed map for many optimal-path requests.
The paper is most relevant to researchers working on exact pathfinding over static 8-connected grids, especially when preprocessing time or memory is a deployment constraint. It is useful for readers studying Jump Point Search, Goal Bounding, Compressed Path Databases, canonical tie-breaking, and empirical evaluation of grid path planners. Readers whose primary setting is dynamic maps, nonuniform edge costs, general graphs, or approximate planning should treat the stated assumptions as a limitation and assess transferability separately.