The idea: let a cell's parent be any cell in sight
A* on a grid moves from a cell to one of its 8 neighbours, so every path it finds is made of steps in 8 directions. To reach a goal at any other angle it has to zig-zag: a few diagonal steps, then a few straight ones. The path is longer than the straight line and has turns a unit would never make.
Any-angle path planning keeps the grid for the search but lets the path leave it. Theta* does this with one change to A*: the parent of a cell does not have to be a neighbour. It can be any earlier cell from which the new cell is in line of sight. The path is then a few long straight segments that turn only at wall corners.
Both grids show the same map, and both finders run at the same time: each step expands one cell on the left and one on the right. Grey lines are parent pointers. Green and red lines are the line-of-sight checks of that step (green: clear ✓, red: blocked ✗); they disappear at the next step.
Why A*'s grid paths zig-zag
In the open field (Demo: open field, A* vs Theta*) S is at (2,9) and G at (17,2): 15 columns and 7 rows apart. A* takes 7 diagonal steps and 8 straight ones. Its cost is 7·√2 + 8 = 17.90, which is the best any 8-direction path can do. The straight line is √(15² + 7²) = 16.55, so the grid path is 8.1% longer and has a turn. Theta* finds the straight line itself: one segment, no turn.
Costs here are exact: a straight move costs 1, a diagonal move √2, and a Theta* segment its Euclidean length. A* uses the octile distance as its heuristic (the exact cost on an empty 8-direction grid). Theta* uses the straight-line distance, because its paths can be that short.
Theta*: path 1 and path 2
Theta* is A* except for the update of a neighbour s' of the expanded cell s:
expand s:
for each neighbour s' of s that is not closed:
if line_of_sight(parent(s), s'): // path 2
candidate = g(parent(s)) + dist(parent(s), s')
if candidate < g(s'): parent(s') = parent(s); g(s') = candidate
else: // path 1, as in A*
candidate = g(s) + dist(s, s')
if candidate < g(s'): parent(s') = s; g(s') = candidate
Path 2 skips s: it goes straight from s's parent to s'. By the triangle inequality it is never longer than path 1, so whenever the line is clear Theta* takes it. The parent pointers you see stretch out across the grid; following them back from G gives the path, already as straight segments.
The price is the checks: up to 8 line-of-sight tests per expansion. In the rooms map Theta* makes 438 of them for 136 expansions (Demo: rooms with doors).
Line of sight on cell centres
This page uses the cell-centre convention: paths join the centres of cells. (The Theta* paper uses cell corners; the idea is the same.) Two centres are in line of sight when the straight segment between them does not touch any wall cell, not even at a single corner point. This is a conservative supercover test: every cell the segment passes through or touches must be free.
For two neighbouring cells this is exactly A*'s move rule: a diagonal step may not cut the corner of a wall. So every A* move has line of sight too, and all four finders build paths out of segments that never touch a wall. The test is exact: in doubled coordinates cell centres are odd integers and cell corners even ones, so a wall cell is missed only if all four of its corners lie strictly on one side of the line, which is integer arithmetic.
A* + post-smoothing
The older way to get any-angle paths is to run A* and straighten its path afterwards (string pulling). Keep S; then walk along the path, and as long as the next path cell is still in sight from the last kept vertex, skip the current one. When the sight is blocked, keep the current cell as a turn. That costs one line-of-sight check per path cell.
Smoothing can only remove turns from the route A* chose. If A* went around an obstacle on the side that is shorter in 8 directions but longer in a straight line, smoothing cannot move it to the other side. With scattered walls (seed 10) A* + smoothing ends at 19.95 with 3 turns, while Theta* finds 19.70 with 1 turn, the shortest path (Demo: A* + smoothing vs Theta*).
Lazy Theta*: check later, check less
Most line-of-sight checks in Theta* are for cells that are never expanded. Lazy Theta* takes path 2 for every neighbour without checking. When a cell is expanded it checks once, from the cell to its assumed parent. If that is blocked, the cell takes the closed neighbour that gives it the smallest g as its parent instead. You can see the red check and then the parent pointer jumping to a neighbour.
In the rooms map Lazy Theta* makes 136 checks instead of 438 and finds a path of 27.98 instead of 27.79 (Demo: Theta* vs Lazy Theta*). The paths are usually as short as Theta*'s, sometimes a little longer, sometimes a little shorter.
Theta* is not guaranteed to be the shortest
Theta* only considers two parents for s': s and parent(s). An earlier cell that would see s' is never tried. In Demo: Theta* is not optimal the straight line from S to G passes between two short walls, so the shortest path has no turn and length 16.55. But the gap is narrow. The first cell Theta* reaches inside it, (7,6), is not in sight of S, so it gets its neighbour (7,7) as parent, and every cell beyond the gap inherits parents from there: (7,7), then (8,5). S, which would see G, is never tried again. Theta* ends with 17.11 and 2 turns, 3.4% longer. A* + smoothing does worse here (17.90).
This is the usual case on cluttered maps: on random maps Theta* is often a few percent above the shortest path, and almost always far shorter than A*'s grid path. On 300 random maps checked for this page, Theta* and A* + smoothing were never longer than A*'s grid path; Lazy Theta* was, once (by 0.59), because a parent it assumed turned out to be blocked.
The reference: shortest path through cell centres
The "shortest" line (purple, drawn where a finder missed it) is the shortest path whose turning points are cell centres with line of sight between them. It is found by Dijkstra on the visibility graph: every free cell centre is a vertex, and every pair in sight is an edge with its straight-line length. Every finder on this page builds such a path, so none can be shorter. In the continuous plane the true shortest path would turn at wall corners rather than cell centres and can be slightly shorter still.
What to compare
| Demo | Left | Right | Shortest |
|---|---|---|---|
| open field | A*: 17.90, 1 turn, 16 expansions | Theta*: 16.55, no turn, 24 expansions, 135 checks | 16.55 |
| pillars | A*: 22.49, 8 turns, 86 expansions | Theta*: 21.14, 3 turns, 81 expansions, 289 checks | 20.97 |
| rooms with doors | A*: 29.56, 10 turns, 136 expansions | Theta*: 27.79, 6 turns, 136 expansions, 438 checks | 27.46 |
| scattered walls (seed 8) | A*: 21.90, 7 turns, 87 expansions | Theta*: 20.45, 4 turns, 74 expansions, 257 checks | 20.35 |
| A* + smoothing vs Theta* (seed 10) | A* + smoothing: 19.95, 3 turns, 39 expansions, 17 checks | Theta*: 19.70, 1 turn, 30 expansions, 128 checks | 19.70 |
| Theta* vs Lazy Theta* (rooms) | Theta*: 27.79, 6 turns, 438 checks | Lazy Theta*: 27.98, 7 turns, 136 checks | 27.46 |
| Theta* is not optimal | Theta*: 17.11, 2 turns | A* + smoothing: 17.90, 1 turn | 16.55 |
| no path (closed door) | A*: no path after 140 expansions | Theta*: no path after 140 expansions, 431 checks | none |
A turn is a change of heading along the path. Expansions are a fair clock for both sides, but a Theta* expansion also pays for its line-of-sight checks, each of which walks the cells along a line.
What the page leaves out
- Field D* and Accelerated A*, other any-angle planners, and ANYA, which is optimal on grids but more complex.
- The corner-point (vertex) convention of the paper, and cells of different traversal cost.
- Running time in milliseconds: on a 20 × 12 grid every finder takes well under a millisecond.
- Lazy Theta*'s 3D use, which is where saving line-of-sight checks matters most.
See also Grid Pathfinding Side by Side (Dijkstra, A*, BFS, Jump Point Search racing on the same map) and Grid Pathfinding (one finder with its open list in full detail).