Theta*, in depth: any-angle paths on grids, an exact line-of-sight test, Lazy Theta* and measured distance to optimal

Why grid paths zigzag

On a grid with 8 moves, the cost of reaching a point dx across and dy up (dx at least dy) is the octile distance: (dx - dy) + sqrt(2) dy. Divide by the Euclidean distance and the ratio is worst when the direction is 22.5 degrees off an axis, where it reaches about 1.082. So a grid path can be up to 8.2 percent longer than the straight line, even with no obstacles at all. In open terrain with scattered obstacles the average loss is smaller but real; on our test maps it was 2.9 percent.

A grid path also changes heading at almost every node. String pulling after the search (drop any node whose neighbours see each other) removes the turns but stays on the same side of every obstacle A* chose. Theta* uses visibility during the search, so corridors are compared by true length.

The one change to A*

Theta* searches over grid vertices, the corners of cells, rather than cell centres. Each vertex keeps the usual A* fields: g (best cost found so far), a parent pointer, and a key g + h in the open list. The heuristic is straight-line distance to the goal, which never overestimates any path, so it stays admissible and consistent.

The only change is in how a neighbour t of the expanded vertex s gets its cost. A* considers one candidate, which Theta* calls path 1: go to s, then step to t. Theta* first tries path 2: skip s and go straight from parent(s) to t, if that segment is unobstructed. Because a straight segment is never longer than a two-segment detour through s (triangle inequality), path 2 wins whenever it is legal.

update_vertex(s, t):
    if line_of_sight(parent(s), t):                      # path 2
        candidate = g(parent(s)) + dist(parent(s), t)
        via = parent(s)
    else:                                                 # path 1, plain A*
        candidate = g(s) + dist(s, t)
        via = s
    if candidate < g(t):
        g(t) = candidate
        parent(t) = via
        push or decrease-key t in OPEN with g(t) + dist(t, goal)

Two consequences follow. First, a parent is no longer a neighbour; it can be any vertex that sees the child. Second, the path is read back by following parents as usual, and every parent link is already a straight segment, so no smoothing is needed afterwards.

Line of sight on a corner grid

Everything depends on the line-of-sight test, and most bugs live there. We need explicit rules about what a segment between two corners may touch. The rules below match what 8-connected A* with no corner cutting allows, so the two searches agree on which unit moves are legal:

1. Cell (i, j) covers the square from (i, j) to (i + 1, j + 1). A segment is blocked if it passes through the interior of a blocked cell.
2. A segment that runs along a cell edge is blocked only if the cells on both sides of that edge are blocked. Walking beside a wall is fine.
3. A segment that passes exactly through a vertex where two blocked cells touch diagonally is blocked. No squeezing between them.
4. Cells outside the map count as blocked, so the rim follows rule 2.

The test walks the segment one column strip at a time. Inside the strip from x = i to x = i + 1, the segment covers a y-interval, and the cells whose interior it crosses are exactly those whose row overlaps that open interval. Exact fractions remove any rounding question about whether a segment grazes a corner. The cost is linear in the segment length, like the Bresenham-style test in the original paper.

import math
from fractions import Fraction as F

def line_of_sight(a, b, blocked):
    (x0, y0), (x1, y1) = a, b
    if x0 == x1:                                     # vertical: an edge run
        return all(not ((x0 - 1, j) in blocked and (x0, j) in blocked)
                   for j in range(min(y0, y1), max(y0, y1)))
    if x0 > x1:
        x0, y0, x1, y1 = x1, y1, x0, y0
    slope = F(y1 - y0, x1 - x0)
    for i in range(x0, x1):
        ya = y0 + slope * (i - x0)
        yb = ya + slope
        lo, hi = min(ya, yb), max(ya, yb)
        if lo == hi:                                 # horizontal
            if lo.denominator == 1:                  # along an edge
                if (i, int(lo) - 1) in blocked and (i, int(lo)) in blocked:
                    return False
            elif (i, math.floor(lo)) in blocked:
                return False
        elif any((i, j) in blocked for j in range(math.floor(lo), math.ceil(hi))):
            return False                             # crosses a blocked interior
        if i + 1 < x1 and yb.denominator == 1 and slope != 0:
            x, y = i + 1, int(yb)                    # passes exactly through a vertex
            if slope > 0 and (x - 1, y) in blocked and (x, y - 1) in blocked:
                return False
            if slope < 0 and (x - 1, y - 1) in blocked and (x, y) in blocked:
                return False
    return True

Unit-test each rule in both orientations, and use the same function for the 8 unit moves so A* and Theta* agree on what is legal.

A complete implementation

With the test in place the search is A* with the update rule swapped in. A single mode flag lets the same function run A*, Theta* and Lazy Theta*, which makes comparisons honest. For rule 4, add a ring of blocked cells around the map to the blocked set before calling it.

import heapq

def search(start, goal, W, H, blocked, mode="theta"):
    dist = lambda a, b: math.hypot(a[0] - b[0], a[1] - b[1])
    def nbrs(v):
        for dx in (-1, 0, 1):
            for dy in (-1, 0, 1):
                u = (v[0] + dx, v[1] + dy)
                if (dx or dy) and 0 <= u[0] <= W and 0 <= u[1] <= H \
                        and line_of_sight(v, u, blocked):
                    yield u
    g, parent, closed = {start: 0.0}, {start: start}, set()
    open_ = [(dist(start, goal), start)]
    while open_:
        _, s = heapq.heappop(open_)
        if s in closed:
            continue                                  # stale heap entry
        if mode == "lazy" and s != start and not line_of_sight(parent[s], s, blocked):
            best = min((u for u in nbrs(s) if u in closed),
                       key=lambda u: g[u] + dist(u, s))
            parent[s], g[s] = best, g[best] + dist(best, s)
        closed.add(s)
        if s == goal:
            path = [s]
            while path[-1] != start:
                path.append(parent[path[-1]])
            return g[s], path[::-1]
        for t in nbrs(s):
            if t in closed:
                continue
            ps = parent[s]
            ok = line_of_sight(ps, t, blocked) if mode == "theta" else mode == "lazy"
            cand, via = (g[ps] + dist(ps, t), ps) if ok else (g[s] + dist(s, t), s)
            if cand < g.get(t, math.inf):
                g[t], parent[t] = cand, via
                heapq.heappush(open_, (cand + dist(t, goal), t))
    return math.inf, None

Stale heap entries replace decrease-key. Closed vertices are never reopened, which is safe for A* and one reason Theta* is not guaranteed optimal.

Worked example

The figure is a real run. From (0, 0) to (12, 7), 8-connected A* returns 12 moves of length 14.899. Theta* returns four segments: (0, 0) to (4, 1), which passes under the wall and touches its bottom corner; (4, 1) to (7, 4), between the two wall blocks; (7, 4) to (10, 5), over the second block; and (10, 5) to (12, 7). Its length is 14.356, 3.6 percent shorter. A brute-force check that runs Dijkstra over every obstacle corner with the same visibility rules gives 14.356 as well, so on this map Theta* found the true shortest path.

Trace the start of the run to see the mechanism. The start is expanded first, then (1, 1). Expanding (1, 1) offers (2, 1); the start sees (2, 1), so (2, 1) takes the start as its parent with g = sqrt(5) = 2.236 instead of 1.414 + 1 = 2.414 via (1, 1). The parent stays (0, 0) as the search spreads: vertex (4, 1) is generated by expanding vertex (3, 1) but takes parent (0, 0) with g = sqrt(17) = 4.123, because that segment only touches the corner of blocked cell (3, 1), which rule 1 allows. When (4, 1) is expanded, the start cannot see (5, 2), so (5, 2) takes path 1 with parent (4, 1) and g = 5.537. Vertex (4, 1) is now the anchor: (7, 4) later gets parent (4, 1) and g = 8.366 when (6, 3) is expanded.

Work done: Theta* expanded 25 vertices against 35 for A* and made 115 any-angle line-of-sight checks. Lazy Theta* found the same path with 28 expansions and 27 checks.

Measured on 40 random maps

To go beyond one map, the code above ran on 40 random 40 x 40 grids with 20 percent of cells blocked, from corner to corner, with the exact visibility-graph optimum as the reference. One map had no path; the table averages the other 39. LOS calls count only any-angle checks (path 2 and the lazy check), not the unit-move checks all three methods share.

Theta* closes most of the gap to the optimum with about a quarter as many segments, but is usually not exactly optimal. Lazy Theta* needs roughly a quarter of the line-of-sight checks for a slightly longer path; since each check can span the map, that saving dominates on large grids.

Lazy Theta*

Basic Theta* checks visibility for every neighbour of every expanded vertex, about eight checks per expansion, and most of those neighbours are never expanded. Lazy Theta* (Nash, Koenig and Tovey, 2010) assumes path 2 is legal when it generates a neighbour, and checks only when the vertex is popped for expansion. If the check fails, the vertex repairs itself: its parent becomes the closed neighbour that gives the lowest g + distance, which is path 1 from the best expanded neighbour. One check per expansion instead of eight.

The repair always finds a candidate: the expanded neighbour that generated the vertex is closed. Optimistic g values occasionally lead to a worse parent, hence slightly longer paths. Use it when line-of-sight tests are expensive: large maps or 3D grids.

Where Theta* is not optimal

Theta* is not guaranteed to find the shortest any-angle path, and the table shows it missing by up to 0.84 percent. The cause is that parents are always chosen among the parent of s or s itself. The true shortest path may bend at a vertex that is never the parent of the vertex being expanded, and closed vertices are never revisited with a better parent. On our maps it was exactly optimal on only 5 of 39.

For exact answers, a visibility graph over obstacle corners is exact but costly to build; see the visibility graph article. Anya (Harabor and Grastien) searches intervals of grid rows and is optimal on grids, at the cost of a harder implementation. For most robotics and game work, Theta* or Lazy Theta* is the right default.

Operational guidance

• Decide the corner rules first and use one function for unit moves and long segments.
• Use exact arithmetic, or integer-only stepping. Floating-point stepping misjudges segments through corners, exactly where Theta* paths go.
• Inflate obstacles for real robots. Theta* paths hug corners. Plan on a costmap inflated by the robot radius plus a margin, or the robot clips walls.
• Bound the search. Stop on an expansion budget and return the best partial path, so one unreachable goal cannot stall a frame or a control loop.

Failure modes

Trade-offs

A* plus string pulling is simplest but locked to A*'s corridor. Theta* is near optimal for extra visibility work; Lazy Theta* cuts that work for a small loss in length; visibility graphs and Anya are exact but costlier. The A* variants article covers the speed-oriented family (JPS, ARA*, D* Lite), and the grid shortest-path variants page covers the 4- and 8-connected choices that Theta* builds on.

What to do next

1. Copy the line-of-sight function and its unit tests, then make your A* use it for unit moves so both searches share one definition of legal.
2. Add the path 2 rule and compare path length and segment count against your current A* plus smoothing on 20 of your real maps.
3. If line-of-sight time dominates a profile, switch to the lazy variant and re-measure.
4. Build the visibility-graph reference on small maps once, so you know how far from optimal you are rather than guessing.
5. Inflate obstacles by the agent radius and add an expansion budget before shipping.
6. Review the A* basics in A* pathfinding and the Dijkstra foundations in Dijkstra, in depth.