nomicon

    ↑ ↓ to move, Enter to open. Matches lesson text, headings and the labs' concept cards.

    Lesson 8

    Faster search: pruning, hierarchy and budgets

    A* on a big map touches thousands of cells per path. Four ways to touch fewer: Jump Point Search skips routes that are the same moves in another order, HPA* searches doors between tiles instead of cells, a reachability label answers "no path" without searching, and caches and budgets keep the cost of many units flat and deterministic.

    The previous lesson ended with A* and a good heuristic. On a big map that’s still a lot of work per path, and a game asks for many paths. A faster inner loop helps a little. Searching less of the map helps a lot. Here are the standard ways to do that, each with what it assumes.

    On a grid where every open cell costs the same, there are many equally short orderings of the same moves. Right, right, down-right and down-right, right, right reach the same cell for the same cost, and A* puts the cells of many of those routes through its open list.

    Jump Point Search (Harabor and Grastien, 2011) prunes them. From a node, it doesn’t queue each neighbour; it scans in a straight line (or diagonally, scanning straight lines off the diagonal as it goes) until something interesting happens: it reaches the goal, or a cell with a forced neighbour (a wall ends next to the line, so a cell beside it can only be reached cheaply by turning here). The cell where the scan stops, a jump point, is the only one that goes on the open list. Everything scanned past on the way is skipped: some other jump point reaches it at least as cheaply.

    Loading…

    On this town (80 × 50 cells), A* expands 854 cells, pushes 1,603 entries on the open list and has up to 634 on it at once. JPS expands 63 jump points, pushes 98, and its open list never holds more than 34. The path costs 107.05 either way: JPS is optimal. It isn’t free: it scanned 1,751 cells to find those jump points. But scanning a cell is a couple of reads, while queuing one is a heap push and a pop, which is where A*’s time goes on a grid.

    The catch is the assumption. Every open cell must cost the same, because the pruning argument is that two routes of the same moves cost the same. With terrain costs, they don’t, and JPS can return a wrong answer. The lab refuses to run it once terrain costs are on. Versions that preprocess the map (JPS+) go faster still, at the price of rebuilding when the map changes.

    Run A* and JPS side by side in the pathing lab →

    Hierarchy: plan on the doors

    On a big map the best way to touch fewer cells is to not plan in cells at all. HPA* (Botea, Müller and Schaeffer, 2004) cuts the map into square tiles. On each opening where a unit can cross a tile border it places a pair of doors, one on each side (a long opening gets more than one pair). Inside each tile it computes the cost of walking between every pair of that tile’s doors, once, and caches the route. A query then:

    1. connects the start and goal to the doors of their own tiles, with a small search inside each tile;
    2. runs A* over the door graph, whose edges are the cached routes inside tiles and the one-step border crossings;
    3. stitches together the cached cell routes of each hop for the full path.

    Loading…

    This 128 × 80 town is cut into 40 tiles of 16 × 16 cells, with 418 doors. A* expands 2,324 cells to find the cheapest path, cost 158.27. HPA* expands 145 doors, after touching 512 cells to connect the start and goal to their tiles’ doors. Its path costs 163.44, 3.3% more: it’s tied to crossing borders at doors, so it isn’t the cheapest. Smoothing (the next lesson) takes most of that back. The HPA* paper reports the same shape on game maps: up to 10 times faster than a highly optimised A*, with paths within 1% of optimal once smoothed. On the lab’s 256 × 160 town, HPA* expands 21 times fewer nodes than A*.

    The doors are where the remaining work goes, and two details from the lab are worth stealing. First, build each tile’s routes lazily, the first time a search reaches the tile: this query built 23 of the 40 tiles, and the rest stay unbuilt until something needs them. Second, door graphs have ties of their own (a straight line rarely crosses a border exactly at a door, so many door routes cost almost the same); a door-level heuristic weight of 1.05 breaks them, which is why the lab uses it.

    Compare A* and HPA* on the town in the pathing lab →

    A navmesh is the same idea taken further: instead of square tiles and doors, the walkable floor is cut into convex polygons and the search crosses their shared edges. That’s where this part ends up.

    Reachability: don’t search for what isn’t there

    An unreachable goal is A*’s worst case. It can’t say “no path” until it has expanded every cell it can reach, because any of them might have led there.

    Loading…

    Here the goal is a cell sealed inside a block of wall. A* expands all 3,362 cells of the town reachable from the start before it gives up. The fix is to label the connected areas once (a flood fill per unit size, updated when the map changes) and compare two labels before searching. Different labels: no path, and no search. Then send the unit to the nearest reachable point instead, or ask the decision layer for a different goal.

    It also settles what to do when a complete search fails: don’t retry with a different planner. A grid search that says no path is right, at the grid’s resolution, and a second planner would just burn its own budget failing.

    Caching and budgets

    Hierarchy works because its expensive parts don’t depend on the goal. That’s the general rule for caching paths: cache what every unit can use. Tile routes, door graphs, navmeshes and roadmaps serve every query. A whole path only helps a unit going exactly the same way, and per-goal structures (a Dijkstra field from the goal, a flow field) pay off only when many units share a goal. The lab’s caching card plans five units in turn: the grid search shares nothing, and lazy HPA* builds fewer tiles for each later unit.

    Then give every search a budget, and slice long ones across frames. An A* in progress is just its open list and its g and parent arrays, so it can stop after N expansions and pick up next frame:

    enum class Step { Running, Found, NoPath };

// Resumable A*: the search state lives in the job, not on the stack.
Step step(PathJob& job, int budget) {
    while (budget-- > 0) {
        if (job.open.empty()) return Step::NoPath;
        Node cur = job.open.pop();
        if (job.closed[cur]) { ++budget; continue; }    // stale entries don't count
        job.closed[cur] = true;
        if (cur == job.goal) return Step::Found;
        expand(job, cur);
    }
    return Step::Running;                                // more next tick
}

    Count the budget in expansions, not milliseconds. The same inputs then give the same paths on every machine, which networked games and replays depend on; wall-clock time should only decide when an answer arrives, never which answer it is. Apply finished paths at a fixed point in the tick, in unit order. The deadlines lesson covers the scheduling side, and Detour’s sliced pathfinding (initSlicedFindPath, then updateSlicedFindPath(maxIter, ...) each frame) is this loop.

    Takeaways

    • Search less of the map before making the loop faster.
    • JPS prunes routes that are the same moves in another order: optimal, a tiny open list, but only on uniform-cost grids.
    • HPA* searches doors between tiles, with routes inside tiles cached and built lazily: far fewer nodes, paths a few percent longer until smoothed.
    • Label connected areas once per unit size, and “no path” becomes one comparison instead of A*’s worst case.
    • Cache what doesn’t depend on the goal; budget searches in expansions and slice them across frames, so paths are deterministic.

    In the lab

    The lab’s Speed-ups and caching cards have each of these with a “Try it”, plus edits that dirty tiles and several units planning in turn.

    Open the unreachable goal, with the check off, in the pathing lab →

    Further reading