Grid & robotics pathfinding

Theta*

A* that cuts corners: straight-line shortcuts for natural-looking paths.

Interactive demo coming soon — read the theory below

The idea

Theta* is a variant of A* for grids that produces "any-angle" paths. Regular A* can only step between neighboring cells, so its routes look blocky and zig-zag along 45-degree diagonals. Theta* adds one trick: when it reaches a new cell, it checks whether that cell can "see" its grandparent in a straight line (line-of-sight). If it can, it skips the intermediate cell and links directly to the grandparent, giving a shorter, more natural path at any angle.

How it works

Set up like A*: put the start cell in the OPEN priority queue with g(start)=0, and set the start as its own parent.
Pop the cell with the lowest f = g + h (cost so far plus straight-line estimate to the goal). If it is the goal, rebuild and return the path.
Move that cell to CLOSED (done) and look at each of its grid neighbors that are walkable.
PATH 2 (the shortcut check): test line-of-sight from the neighbor to the current cell's PARENT. If the straight line is clear of obstacles, try connecting the neighbor directly to that parent, using straight-line distance as the cost.
PATH 1 (the A* fallback): if there is no line-of-sight to the parent, connect the neighbor to the current cell the normal A* way.
Whichever connection is cheaper: if it beats the neighbor's best known g, update its g, set its parent accordingly, and push it into OPEN.
Repeat popping the best cell until the goal is reached or OPEN is empty (no path).
Follow parent pointers back from the goal to read off the final any-angle path.

OPEN, CLOSED & the data structures

OPEN: a priority queue of frontier cells ordered by f = g + h. CLOSED: the set of already-expanded cells. g[cell]: best known cost from start to that cell. parent[cell]: the cell it connects back to — crucially, this parent may be a NON-adjacent cell (the grandparent shortcut), which is what makes paths any-angle. A line-of-sight routine (typically a grid supercover / Bresenham-style walk) that returns true when the straight segment between two cells crosses no blocked cell.

Pseudocode

function ThetaStar(start, goal):
    g[start] = 0;  parent[start] = start
    OPEN = priority queue;  push start with f = h(start)
    while OPEN not empty:
        s = pop lowest-f cell from OPEN
        if s == goal: return reconstruct(goal)
        add s to CLOSED
        for each walkable neighbor n of s not in CLOSED:
            if lineOfSight(parent[s], n):            # Path 2: shortcut
                p = parent[s]
                newG = g[p] + dist(p, n)             # straight-line cost
            else:                                    # Path 1: normal A*
                p = s
                newG = g[s] + dist(s, n)
            if newG < g[n]:                          # found a cheaper way
                g[n] = newG;  parent[n] = p
                push/update n in OPEN with f = newG + h(n)
    return failure                                   # no path

At a glance

Complete?Complete. Like A*, it explores the whole reachable grid systematically; if a path exists it will find one, and if none exists OPEN empties and it reports failure.

Optimal?Not guaranteed optimal, but very close. Basic Theta* finds paths that are almost always the true shortest any-angle path and are never longer than A*'s grid path. The line-of-sight shortcut can occasionally miss the exact globally shortest route (a variant called Lazy Theta* trades a bit more of this for speed; the provably optimal any-angle method is the heavier A*-with-post-smoothing / Anya).

TimeComparable to A* per search, plus a line-of-sight check on each edge relaxation. Line-of-sight costs up to O(grid width) cells traced, so it is a constant-factor overhead on top of A*'s node expansions.

SpaceSame order as A*: it stores g, parent, and the OPEN/CLOSED sets, so O(number of grid cells) in the worst case. Memory-heavy on large open grids, just like A*.

👍 When to use it

You want realistic, natural-looking routes (game agents, robots) instead of blocky 45-degree zig-zags.
Movement is not truly restricted to grid edges — the grid is just how you stored the map, but real motion can be any angle.
You already use A* on a grid and want shorter, smoother paths for little extra code.
Open areas with sparse obstacles, where straight-line shortcuts pay off the most.

⚠️ Watch out for

Line-of-sight is the heart of it — a buggy LOS check silently corrupts every shortcut, so test it carefully.
It is any-angle, not optimal: do not claim it always returns the mathematically shortest path.
Diagonal costs must be real distances (about 1.414 for a diagonal step), not 1, or the shortcuts will be mis-priced.
The parent of a node can be far away, not a neighbor — beginners often assume parents are always adjacent (that assumption is exactly what Theta* breaks).
LOS checks add overhead; on dense mazes with few clear sightlines you pay for shortcuts you rarely get to use.
It smooths against static obstacles; it does not by itself account for agent width or moving obstacles.