Why Jump Point Search Lost to a Lookup Table

The warehouse optimizer used Jump Point Search before it used lookup tables. That choice made sense in the original system: JPS is a good algorithm for uniform-cost grid pathfinding, and the production code used the JavaScript pathfinding library to compute rack-to-rack distances before handing the distance matrix to a TSP solver.

The Rust and WebAssembly route core kept pulling on the same thread. Out of academic interest, while learning Rust and WebAssembly, I hand-wrote a Rust JPS module that never got fully wired into the production path, built a compile-time grid generator, and kept enough curiosity to ask a question production validation cannot answer by itself: which parts of the design were actually paying rent?

The answer was uncomfortable in the useful way. JPS made individual shortest-path queries faster than a naive cold runtime implementation. But the warehouse did not need a clever online pathfinder. It needed repeated distance lookups among 97 fixed points on a 527-cell grid, under both uniform and physically weighted distance lenses. Once I measured the actual workload, a table beat the search.

What JPS Was Good At

Jump Point Search is an A* optimization for uniform-cost grids. It prunes symmetric paths: if moving right then down costs the same as moving down then right, the search does not need to explore every equivalent ordering. It jumps along straight or diagonal directions until it reaches the goal, an obstacle, or a forced neighbor that must be considered to preserve optimality¹.

That idea is genuinely well matched to open grid maps. It can reduce node expansions by pruning repeated versions of the same path. It also matched the mental model I had for the warehouse: long corridors, regular rack blocks, many symmetric paths around obstacles.

The benchmark changed the unit of work I cared about. I had been thinking about one shortest path from A2 to H5. The optimizer instead fills a cost matrix for every selected slot in an order, then runs route construction and local search on top of that matrix. A single order can trigger hundreds of distance queries. Across the whole warehouse, there are only 97 named positions including the door.

That is a small, fixed universe. Fixed universes are where precomputation earns its keep.

The Benchmark Ladder

I kept the solver as a six-stage ladder. Each stage pins one heuristic profile and one distance backend, then measures the result against the same exact route-ordering referee. That structure matters because it prevents the usual benchmark fog where storage changes, heuristic changes, and input changes all move at once.

All figures below are cold per-order solves on the exact-solvable retro-core scenarios, uniform lens, measured on Apple Silicon. Mean gap is the average extra route length versus the exact shortest route for the same picked slots. A gap of 0.00% means the benchmarked routes matched the exact answer at the reported precision.

Cold-start numbers make JPS look useful. Warm-process numbers explain why it lost. The memoized runtime backend eventually answered repeated solves in about 35 microseconds, while JPS still recomputed paths at about 951 microseconds per order.

JPS looks good against a cold string-keyed implementation. 1.00 ms instead of 4.91 ms is a real speedup. That comparison is fair but incomplete because the string-keyed backend has a memo and JPS has no such memory. The clever search lost once the process had seen enough pairs.

The other problem is correctness under the weighted lens. JPS’s pruning assumes uniform movement costs. The benchmark also needed physical distances: rack bays at 2.7 m, corridors at 1.2 m, and therefore non-uniform traversal costs. That weighted mode is exactly the kind of detail a warehouse model eventually wants. The JPS stage is recorded as unsupported there, not silently skipped.

The grid itself undermined the pruning too. JPS shines on large open maps, where whole regions collapse into a handful of jump points. A warehouse floor is the opposite: corridor-dense, with racks forcing a decision at nearly every cell. When almost every cell is a jump point, the pruning skips very little, and the mental model of “many symmetric paths to prune” turns out to be exactly backwards. The visualizer above runs on the real floor plan, so you can watch how little gets skipped.

Maintenance sealed the verdict. The hand-written JPS module was roughly 430 lines of subtle pruning logic, the kind where a wrong forced-neighbor rule silently returns a suboptimal path. The replacement is a textbook Dijkstra inside build.rs. Only one of those two is easy to review.

Precompute the Floor

The replacement is less glamorous and easier to reason about. A build.rs script parses grid.txt, validates the floor plan, and runs Dijkstra from every named position at compile time. It emits two all-pairs distance tables: one uniform, one weighted. At runtime, asking for the distance between two rack positions is one index calculation.

let from = from_slot.rack_index();
let to = to_slot.rack_index();
let distance = DISTANCES[from * POSITION_COUNT + to];

This design moves work to the phase where failures are cheap. If a rack is unreachable, the build fails. If a row in the grid has the wrong length, the build fails. If a scaled distance no longer fits in the chosen integer type, the build fails. A malformed warehouse layout should not reach production and then explain itself as a slow request.

The first table version used u32 entries and label lookups. It was already fast: 45.8 microseconds per solve in the ladder. Then two small facts made it smaller.

First, no scaled distance in this warehouse needs 32 bits, so u16 is enough. That halves the table: 73.6 KB for two u32 tables became 36.8 KB for two u16 tables. Second, labels like G11.12 carry three bounded fields: aisle, rack, shelf. They fit in a u16.

#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct SlotId(u16);

impl SlotId {
    #[inline]
    pub fn aisle(&self) -> u8 { ((self.0 >> 8) & 0xF) as u8 + b'A' }

    #[inline]
    pub fn rack(&self) -> u8 { ((self.0 >> 4) & 0xF) as u8 + 1 }

    #[inline]
    pub fn shelf(&self) -> u8 { (self.0 & 0xF) as u8 + 1 }
}

The layout is deliberately readable in hex:

u16 layout: [ 4 unused | aisle:4 | rack:4 | shelf:4 ]

"G11.12" -> aisle_idx=6, rack_idx=10, shelf_idx=11
          -> (6 << 8) | (10 << 4) | 11
          -> 0x06AB

I considered a flat dense index. It packs too, but decoding needs division and modulo. The fixed 4-bit fields decode with shifts and masks, and when a route dump contains 0x06AB, I can read aisle 6, rack 10, shelf 11 without a calculator. That kind of debuggability is not theoretical when you are the person on the hook for the system.

The Referee

Optimizing the distance backend says nothing about route quality. Through the first four stages, the mean quality gap stayed at 11.53% because the route was still nearest neighbor. It was faster at producing the same greedy mistakes.

I needed a referee. For route ordering, I used an integer linear program with Miller-Tucker-Zemlin subtour elimination². The ILP is too slow and too dependency-heavy for the live WASM path, but that is fine. Its job is to grade the fast heuristic, not sit behind a barcode scan. The exact solver’s job was simple: for the same chosen slots, find the shortest possible order to visit them and return to the door, even when proving that answer took up to an hour.

With binary variables $x_{ij}$ for whether the route travels directly from position $i$ to position $j$, and costs $c_{ij}$ from the precomputed table, the objective is:

Degree constraints give every node one predecessor and one successor. MTZ ordering variables prevent disconnected subtours. A warehouse route is an open path from the door through the picks and back, so I add a virtual end node and charge the final edge with the cost of walking back to the door.

That return edge sounds like a detail until it breaks the heuristic. A route optimizer that ignores the walk back tends to strand the operator in a far corner. Making 2-opt aware of the return leg closed the mean gap from 11.53% to 0.00% on the exact-solvable scenario pack. A final or-opt pass, which relocates short runs of one to three stops, kept the exact-match result while adding only about 3 microseconds per solve in the headline ladder.

I validated the ILP with brute force on 8-node instances: all $7! = 5{,}040$ orderings, compared against the solver output. The benchmark excludes scenarios where the exact solver needs hours and still times out, and those go into a separate stress pack. That is the boring part of the work, and the part that makes the headline numbers defensible.

The Lesson I Kept

JPS was a reasonable tool for the system I had at the time. The benchmark changed the problem statement. Once distances were among a small fixed set of positions, and once weighted physical distances mattered, build-time Dijkstra tables fit better than online pathfinding.

This is the lesson I care about beyond warehouses: a heuristic without a referee is only a story about intent. The ILP did not make the production solver faster. It made the speed meaningful.