Tutorial: Smoother Paths with Theta*#

Standard A* produces paths that follow the voxel grid — each step moves to an adjacent cell. The resulting paths look like 3D staircases and often have more turns than necessary. Theta* (Theta-star) relaxes this constraint by allowing any-angle movement: instead of only moving to grid neighbours, it can jump directly to any node that is visible from the grandparent node (line-of-sight check).

This produces shorter, smoother paths with fewer direction changes — at a slight computational overhead compared to A*.

When to Use Theta*#

Situation

A*

Theta*

Open space, few obstacles

Grid-aligned path with unnecessary turns

Direct, smooth path

Dense obstacle field

Fine-grained grid navigation

Similar quality; slightly more computation

Path used for display or manufacturing

Needs post-processing smoothing

Often usable directly

Large grid, tight time budget

Faster

Slightly slower (line-of-sight checks)

As a rule of thumb: use A* for pathfinding within the full CAD routing pipeline (the optimizer handles smoothing), and use Theta* when you need smoother raw paths from the standalone pathfinding module.

Basic Usage#

ThetaStarFinder has the same interface as AStarFinder. Theta* always uses DiagonalMovement.always (any-angle requires it):

import numpy as np
from routing.pathfinding.core.grid import Grid
from routing.pathfinding.finder.theta_star import ThetaStarFinder

# 10×10×10 grid, wall of obstacles in the middle
matrix = np.ones((10, 10, 10))
matrix[4:6, :, 4:6] = 0    # wall obstacle

grid  = Grid(matrix=matrix)
start = grid.node(0, 0, 0)
end   = grid.node(9, 9, 9)

finder = ThetaStarFinder()   # diagonal_movement defaults to always
path, runs = finder.find_path(start, end, grid)

coords = [p.identifier for p in path]
print(f"Theta* path: {len(coords)} nodes, {runs} iterations")
print(coords)

Comparing A* and Theta*#

import numpy as np
from routing.pathfinding.core.diagonal_movement import DiagonalMovement
from routing.pathfinding.core.grid import Grid
from routing.pathfinding.finder.a_star import AStarFinder
from routing.pathfinding.finder.theta_star import ThetaStarFinder

matrix = np.ones((15, 15, 15))
matrix[5:10, 5:10, 0:12] = 0   # large obstacle block

# --- A* ---
grid_astar = Grid(matrix=matrix)
astar = AStarFinder(diagonal_movement=DiagonalMovement.always)
path_a, _ = astar.find_path(grid_astar.node(0, 0, 0), grid_astar.node(14, 14, 14), grid_astar)
coords_a = [p.identifier for p in path_a]

# --- Theta* ---
grid_theta = Grid(matrix=matrix)
theta = ThetaStarFinder()
path_t, _ = theta.find_path(grid_theta.node(0, 0, 0), grid_theta.node(14, 14, 14), grid_theta)
coords_t = [p.identifier for p in path_t]

print(f"A*     path: {len(coords_a)} nodes")
print(f"Theta* path: {len(coords_t)} nodes (typically shorter/smoother)")

Theta* paths typically have fewer nodes because the algorithm “shortcuts” through open space instead of hopping voxel-by-voxel.

Heuristic Choice#

Theta* accepts the same heuristic functions as A*. Since Theta* uses always diagonal movement, "octile" or "euclidean" are the most accurate estimates:

from routing.pathfinding.finder.theta_star import ThetaStarFinder

from routing.pathfinding.core.heuristic import euclidean

finder = ThetaStarFinder(heuristic=euclidean)

Heuristic

Recommendation

"euclidean"

Best for Theta*; matches the actual straight-line cost.

"octile"

Slightly faster to compute; accurate for grid-diagonal moves.

"manhattan"

Underestimates; safe (admissible) but may be suboptimal.

Using Theta* in the Full Routing Pipeline#

The full CAD routing pipeline exposes Theta* through SmartFinder:

from routing.core.finders import SmartFinder
from routing.core.route_planner import RoutePlanner

finder = SmartFinder(
    algorithm="ThetaStar",
    heuristic="euclidean",
    diagonal="always",    # required for Theta*
)

route_planner = RoutePlanner(cadmap, finder)
result = route_planner.generate(specifications=specifications, n_iterations=1)

Note

When using Theta* in the full pipeline, the geometry optimizer still runs afterwards. The smoother Theta* paths can reduce the optimizer’s workload and produce better final geometry.

Next Steps#