Home/Pathfinding/Theta*
Search algorithmsCTRL K

Theta*

· any-angle A* · parents by line of sight
/pathfinding/theta-star
EXPANDED
0
closed cells
OPEN SET
1
candidates in the heap
SHORTCUTS
0
links straight to a grandparent
RELAXED
0
distances improved
PATH
—
length once the goal is reached
closedopencurrentpathstart / goal
44×20 · 28% walls · seed 7 · euclidean · 640 steps
step 0 / 639
Walls28
theta_star.ts
1
function thetaStar(grid: Grid, start: Cell, goal: Cell) {
2
  const open = new MinHeap<Cell>([start]), distance = new Map([[start, 0]]), parent = new Map([[start, start]]);
3
  while (open.size > 0) {
4
    const current = open.pop(); // lowest distance + straight line to the goal
5
    if (current === goal) return rebuild(parent, current);
6
    for (const neighbor of neighbors(grid, current)) {
7
      const grandparent = parent.get(current)!;
8
      const via = lineOfSight(grid, grandparent, neighbor) ? grandparent : current;
9
      const candidate = distance.get(via)! + euclid(via, neighbor);
10
      if (candidate >= (distance.get(neighbor) ?? Infinity)) continue;
11
      distance.set(neighbor, candidate); parent.set(neighbor, via);
12
      open.push(neighbor, candidate + euclid(neighbor, goal));
13
    }
14
  }
15
}
CURRENT STEP
line 2

Start at (12, 1), goal at (5, 42). Like A*, but a cell's parent may be any earlier cell it can see in a straight line.

// how it works

Understanding Theta*

Theta* · paths that cut across the grid instead of hugging it
01

The idea

A* on a grid returns paths made of grid moves, so a diagonal crossing of open ground becomes a staircase up to 41% longer than the straight line. Theta* fixes that in one place: when it relaxes a neighbour, it first checks whether the neighbour can see the current cell's parent in a straight line, and if so links it straight to that parent instead.

Paths become sequences of a few waypoints joined by straight segments, with Euclidean lengths, while the search itself is still A* over the same cells. It is not guaranteed optimal among all any-angle paths, but it is within a percent or two of the true shortest in practice.

02

The four stages

1
poplowest distance + straight line to the goal
2
line of sightcan the neighbour see the current cell's parent?
3
relaxlink to the grandparent if visible, else to the current cell
4
pathfollow parents back to the start
03

Complexity

best
O(d)the goal is visible from the start
average
O(E log V · L)A* plus a line-of-sight check of length L per relaxation
worst
O(E log V · L)long sight lines on an open map
space
O(V)same as A*
04

Versus its siblings

PATH LENGTH · 44×20 OPEN FIELD, DIAGONAL CROSSING
theta*
48
straight line
47
a* 8-way
52
a* 4-way
62
dfs
141
the 4-way staircase is 30% longer than the straight line Theta* nearly matches
05

Pseudocode

THETA*(start, goal)
  open ← {start}; dist[start] ← 0; parent[start] ← start
  while open not empty
    current ← the open cell with the lowest dist + euclid(current, goal); if it is the goal: rebuild the path
    for each neighbour of current
      via ← parent[current] if it can see neighbour in a straight line, else current
      if dist[via] + euclid(via, neighbour) < dist[neighbour]: update dist, parent[neighbour] ← via, add neighbour to open
06

When to use

Units that move freely in the world but plan on a grid: games, drones, robots with a smooth controller.
Whenever the staircase path of A* looks wrong on screen and a post-smoothing pass is not enough.
07

Pitfalls

The line-of-sight test must cover every cell the segment touches; a corner-cutting test lets paths clip walls.
Each relaxation pays a line-of-sight check, so Theta* is slower per expansion than A*; Lazy Theta* defers the check to the pop.
The heuristic must be Euclidean, not Manhattan, or the any-angle costs are overestimated.
08

History

Alex Nash, Kenny Daniel, Sven Koenig and Ariel Felner introduced Theta* in 2007 as the first any-angle search that runs at A* speed; Lazy Theta* followed in 2010. Anya, from 2013, finally gave an optimal any-angle algorithm, at the cost of a more complex search space.

Back to Pathfinding