The paper studies path planning on 8-connected grid maps containing traversable and non-traversable cells. Orthogonal and diagonal moves are allowed, but diagonal moves may not cut corners: the two adjacent orthogonal cells must also be traversable. This model is common in video games and is also used as a simplification for robot motion planning and multi-agent path finding. The central practical requirement is to answer many path queries quickly while keeping paths reasonably close to optimal. Tree Cache already addresses latency by preprocessing a shortest-path tree from a root and connecting a start and target through their first common tree node, but it does not guarantee solution quality.
The first contribution is JSTS, a jump-point version of the Tree Cache idea. Its spanning tree bypasses ordinary intermediate grid cells when JPS identifies a natural successor, so parent links refer to jump points and online paths contain fewer segments. The second contribution is BJSTS, which uses a JSTS path as an upper bound inside a JPS+-style search and guarantees a path no longer than a chosen factor w times the optimal path length. The supplied excerpt does not establish that either method dominates every prior method on every map or query.
The preprocessing phase constructs a shortest-path tree rooted at a selected grid cell. During expansion, JPS pruning rules distinguish natural and forced successors; when a successor is natural and the current node is not the root, the construction bypasses the current node and assigns the successor to the current node's parent jump point. For an online query, JSTS follows the tree from the start and target toward the root, stops at their first shared node, and concatenates the two partial paths, reversing the result when necessary. BJSTS initializes an incumbent with the JSTS route, searches jump-point successors with lower-bound values, and returns a route when the search conditions certify the requested multiplicative bound. The approach therefore trades preprocessing and possible route-quality loss for extremely small query work.
The algorithms were implemented in Rust using the mkpath pathfinding library. Experiments used Ubuntu 22.04 on an AMD Ryzen 9 5950X at 4.5 GHz with 16 GB of DDR4 memory. The benchmarks were the standard Moving AI grid maps and the Iron Harvest grid-map benchmarks, grouped into Game, Street, Maze, Random, Room, and Iron Harvest categories. The primary metrics were tree construction time, average search time per path, and suboptimality factor; average search time was computed from the real time to solve all instances on a map, divided by the number of instances and repeated 100 times. Comparisons included JPS+, a weighted-heuristic JPS+ variant without re-expansions, JPS+BB+, Tree Cache, and an idealized oracle that reads an optimal path directly, although the excerpt does not provide every individual measurement.
JSTS obtains its speed by reducing the number of path segments and making an online query resemble a compact tree read rather than a conventional search. The cost is that JSTS has neither an optimality guarantee nor a fixed finite suboptimality guarantee; the conclusion reports roughly 20 percent worse paths on average and three to five times worse paths at the 99th percentile on grids from real application domains. The trade-off depends strongly on map structure: jumping helps on Game, Street, and Iron Harvest maps, is largely ineffective on Random maps, and does not always produce sub-microsecond queries on narrow-corridor mazes. Staircase bypassing can reduce the number of segments while increasing runtime on Maze, Room, and Random maps, plausibly because of favorable or unfavorable CPU-cache behavior caused by node layout. BJSTS addresses the quality problem but necessarily spends more search effort, and future work is proposed on improving path quality without sacrificing too much speed.
Jump Point Search is an optimal grid-search algorithm that removes symmetries among paths and is described as typically much faster than A* without preprocessing. JPS+ adds preprocessing in the form of clearance information that records the distance to the next jump point in each grid direction. Tree Cache instead computes a shortest-path spanning tree from a root and answers queries by joining the tree paths from the two endpoints. JSTS combines the latter structure with the former pruning principle.
A map is a W-by-H grid in which each cell is either traversable or blocked. A valid move connects orthogonally or diagonally adjacent cells, with the no-corner-cutting rule applying to diagonal moves. A path is represented as a sequence of valid grid segments, and its cost is the sum of the Euclidean lengths of the move vectors. The paper seeks very low query latency for this problem while controlling the difference from an optimal path. The excerpt does not establish that dynamic obstacles, map updates, or multi-agent collision avoidance were directly evaluated.
In ordinary Tree Cache, a node points to an immediate tree parent; in JSTS, natural-successor pruning can make a node point directly to a parent jump point. This reduces tree depth and the number of segments that must be assembled at query time. Root selection affects route quality: the supplied results state that the mean suboptimality with the Midpath choice did not exceed 1.4 on any reported graph. BJSTS uses the JSTS route as an upper bound and searches jump-point successors to certify a requested factor. The excerpt does not give all implementation details needed to reproduce every bound or configuration.
The evaluation covers Moving AI and Iron Harvest maps, including game, city-street, maze, room, random, and Iron Harvest categories. For JSTS, the study compares the standard method, a version without staircase bypassing, Tree Cache, and an idealized optimal-path oracle using time per path, path-segment count, and geometric-mean suboptimality. BJSTS is compared with JPS+, a weighted-heuristic JPS+ variant without re-expansions, and JPS+BB+. The supplied excerpt does not specify the number of queries per map or list every value of the bound parameter w.
The summary table reports average times of 89,979 microseconds for A*, 536 for JPS, 349 for JPS+, 85 for JPS+ with DH, 54 for CH-JPD, 24 for JPS+BB+, 4 for Tree Cache, and 0.3 for JSTS. JSTS is below one microsecond per path on every reported map category except narrow-corridor mazes, and it substantially reduces search time and path-segment count relative to Tree Cache, with an average path-cost increase of up to 5 percent in the described comparison. It is faster than the idealized oracle on Game, Street, and Iron Harvest maps, competitive with it on Maze, and gains little from jumping on Random maps. The conclusion summarizes JSTS as providing up to five orders of magnitude over conventional grid A* and BJSTS as providing up to four orders of magnitude while offering near-optimal bounded quality, but the excerpt does not establish those improvements for every possible condition.
JSTS is presented as a preprocessing-based grid planner whose preprocessing is linear in the map size and typically takes only a few seconds even on large maps. Its online query cost can be on the order of a few hundred clock cycles, making it attractive for large numbers of path or distance queries in relatively static game maps. When unbounded path-quality loss is unacceptable, BJSTS uses JSTS within a bounded-suboptimal search and can provide a specified quality guarantee at single-digit-microsecond average performance. The main conclusion is that preprocessing and controlled tolerance for non-optimal paths can move grid path planning close to the output complexity of an idealized oracle.
JSTS can return arbitrarily suboptimal paths, so a favorable average does not protect individual queries or high-percentile behavior. Its performance and quality depend on map topology, root-selection heuristics, the effectiveness of jumping, staircase layout, and processor-cache behavior. BJSTS supplies a bound but requires additional search, and the excerpt emphasizes that accurate heuristics are important for reducing the remaining gap. The supplied evidence does not fully establish memory usage, update costs for changing maps, behavior in dynamic environments, fairness of all baseline implementations, or direct performance in multi-agent collision-aware planning.
The work is important because it treats the cost of producing the path itself as a primary performance limit rather than measuring only the amount of search avoided. The claim that JSTS can approach, and sometimes beat, an idealized oracle that simply reads an optimal path challenges conventional assumptions about the practical ceiling of grid planning. The paper also connects this speed to high-level game AI, where many pathfinding calls may evaluate distances or plans without ever being physically followed. For MAPF researchers, JSTS is a potentially useful low-level route-generation or distance-query component, although its single-agent guarantees and assumptions must not be confused with multi-agent conflict handling.
This paper is recommended for researchers working on single-agent grid planning, game AI, preprocessing, JPS-style symmetry reduction, and speed-versus-optimality trade-offs. It is especially relevant when maps change infrequently and applications issue many short-latency path or distance queries. MAPF and robotics readers should use it as evidence about a fast single-agent primitive, not as a complete treatment of dynamic obstacles, agent interactions, or collision avoidance. Readers interested in reproducibility should consult the implementation information and remember that the supplied excerpt omits some per-map measurements and experimental conditions.