Lesson 9

Better paths: any angle, smoothing and unit size

A grid path is the shortest path on the grid, which isn't the path a person would walk. Shortcutting after the search, Theta* and Lazy Theta* during it, why neither is truly shortest, and clearance: one distance map that lets every unit size use the same grid. Then the step from grids to navmeshes.

The first lesson found the cheapest path on an 8-way grid. That’s the cheapest path through cell centres moving in 8 directions, and a person walking across a room doesn’t move in 8 directions. Grid paths run at 0° and 45° and turn where the grid makes them, not where the walls do. This lesson makes them shorter and straighter, then makes them fit units bigger than a cell.

Smoothing after the search

The cheapest fix runs after the search. Walk along the path; from each point you keep, look ahead for the furthest later point you can reach in a straight line, and jump straight to it. Everything in between is dropped.

// Shortcutting ("string pulling" on a grid): keep a point only where the line of sight breaks.
std::vector<Cell> shortcut(const Grid& grid, const std::vector<Cell>& path) {
    std::vector<Cell> out{path.front()};
    for (size_t i = 0; i + 1 < path.size();) {
        size_t j = path.size() - 1;
        while (j > i + 1 && !grid.line_of_sight(path[i], path[j])) --j;
        out.push_back(path[j]);
        i = j;
    }
    return out;
}

Line of sight walks every cell the segment passes through (a DDA traversal, as in a voxel raycast). If the segment passes exactly through a cell corner, both cells beside it must be open, the same rule the search uses for diagonal steps; otherwise the shortcut could clip the corner of a wall, or slip between two walls that touch only at that corner.

Loading…

On this map of rooms and doors, A*’s grid path is 60.97 long with 7 turns. Shortcutting it gives 58.63, with 5. Smoothing can only remove points from the path the search chose, so it can’t fix a path that went the wrong way round an obstacle; and with terrain costs, a straight line across mud may be shorter but not cheaper, so the line-of-sight test has to compare costs too.

Any-angle search: Theta*

Theta* (Nash, Daniel, Koenig and Felner, 2007) does the shortcutting during the search. It’s A* with one change at the point where a neighbour is reached: if the neighbour can see the current node’s parent, it takes that parent as its own, with the straight-line cost, instead of going through the current node. Parent links then stretch across open floor, and the path comes out as a few long segments at any angle. Tick show the search tree above to see them.

Here Theta*’s path is 58.46 long, slightly shorter than the smoothed one, because the search knew it could cut corners while it was still choosing between routes. The price is a line-of-sight check for almost every neighbour of every expansion: 2,653 of them. Lazy Theta* (Nash, Koenig and Tovey, 2010) assumes the line of sight holds when it reaches a neighbour, and checks only when that neighbour is expanded, falling back to the best expanded neighbour if the check fails. Most neighbours are never expanded, so it made 729 checks here, for the same path.

Neither is the true shortest path, though. That would come from a visibility graph (every pair of wall corners that can see each other), which is exact and expensive to build and keep up to date. Theta* can miss the true shortest path because a parent can only be one already found; smoothing can miss it because it’s stuck with the route A* picked. Which one wins depends on the map: on the scattered map from the first lesson, the smoothed A* path is 61.82 long and Theta*’s 63.88. In practice both look right, and that’s what matters.

Compare Theta* with smoothed A* in the pathing lab →

Clearance: one map for every unit size

So far the unit has been a point at a cell centre. A troll isn’t. The standard trick is to plan in configuration space: grow every wall by the unit’s size, and the unit can be planned as a point again. On a grid you can do that for every size at once.

For every open cell, measure its clearance: how many chessboard steps it is to the nearest wall or the map’s edge (a cell next to a wall has clearance 1). Two raster passes over the grid, forward then backward, compute it exactly: a chessboard version of the Euclidean distance transform in the terrain lesson. A cell with clearance k has a clear (2k−1) × (2k−1) square centred on it. So a 1×1 unit can stand where clearance is at least 1, a 3×3 unit where it’s at least 2, and a 5×5 unit at 3: one map, a different threshold per size. The search doesn’t change. Its “is this cell passable?” test reads the clearance map, and so does the line-of-sight test, so smoothed paths keep the same distance from walls.

Loading…

On this town the 1×1 unit’s path costs 158.27. A 3×3 unit can’t use the narrowest gaps and walks 168.23, 6.3% further; a 5×5 unit walks 176.43, 11.5% further. On the lab’s rooms map, where the doors are one cell wide, a 3×3 unit can’t get through any of them, and the map falls apart into 16 separate areas: the reachability labels from the previous lesson are per unit size for this reason.

Open the 3×3 unit with clearance numbers in the pathing lab →

From grids to navmeshes

Look at what these lessons have been doing. JPS skipped the cells in the middle of open floor. HPA* replaced cells with a few doors. Theta* and smoothing threw away almost every cell of the path, keeping only the corners. Clearance shrank the walkable floor by the unit’s size. All of them were working around the grid: most of the map is open floor where any straight move is fine, and a grid spends its cells describing it anyway.

Sampling planners take the opposite route and build no description of the floor at all. A probabilistic roadmap (PRM) scatters random free points and joins the ones that can see each other into a graph every query reuses; a rapidly-exploring random tree (RRT) grows a tree from one start toward random points until it reaches the goal, and is thrown away after that one query. They shine where any grid would be astronomically large, such as a robot arm with seven joints. On a 2D floor they mostly lose: a doorway is a tiny fraction of the space, so random samples rarely land in it. In the lab, PRM with 1,000 samples misses the one-cell doors of the rooms map, while a roadmap with its nodes placed at wall corners finds the path. And a sampler can never prove there’s no path, only fail to find one.

Placing nodes where paths actually turn is the better idea, and a navigation mesh takes it all the way: it describes the walkable floor directly, as convex polygons. Inside one polygon any straight move is valid, so a few polygons cover a room that would be hundreds of cells. The search runs over polygons, crossing their shared edges (portals), which is HPA*’s doors without the tiles. The funnel algorithm then pulls the route tight through those portals, which is smoothing done exactly on the corridor the search chose. And the mesh is built shrunk by the agent’s radius, which is clearance: one mesh per unit size.

The next two lessons are about the navmesh most games use. Inside Recast steps through how it’s built, from triangles to polygons; Detour, or your own planner covers searching it, keeping paths valid in a changing world, and vehicles that can’t turn on the spot. Navmeshes assume a floor; for agents that fly, Octrees and flying runs the same A* through a sparse octree of 3D space.

Put a navmesh and a grid side by side in the pathing lab →

Takeaways

A grid path is cheapest on the grid: 8 directions, turning at cell centres.
Shortcutting after the search is cheap and removes most of the zig-zag; it can’t change which way round an obstacle the path went.
Theta* shortcuts during the search; Lazy Theta* gets the same paths with a fraction of the line-of-sight checks. Neither is guaranteed shortest; in practice both look right.
Clearance (chessboard distance to the nearest wall) lets one grid serve every unit size: a (2k−1)-square unit needs clearance k.
A navmesh builds all of this in: big open polygons, portals as doors, the funnel as exact smoothing, and the agent’s radius baked in.