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. It defaults to DiagonalMovement.always; another policy restricts its steps to fewer neighbours, its shortcuts staying any-angle:

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

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

grid  = SmartGrid(weights, voxel_size=1.0, origin=(0.0, 0.0, 0.0))
start = grid.node(0, 0, 0)
end   = grid.node(9, 9, 9)
start.direction = (1, 0, 0)

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

cells = [(node.x, node.y, node.z) for node in path]
print(f"Theta* path: {len(cells)} cells, {runs} iterations")
print(cells)
grid.cleanup()

Consecutive cells of a Theta* path are in line of sight, not necessarily neighbours: here [(0, 0, 0), (6, 4, 4), (9, 9, 9)].

Comparing A* and Theta*#

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

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

grid = SmartGrid(weights, voxel_size=1.0, origin=(0.0, 0.0, 0.0))


def search(finder):
    """Route corner to corner, then clean the grid for the next search."""
    start = grid.node(0, 0, 0)
    start.direction = (1, 0, 0)
    path, _ = finder.find_path(start, grid.node(14, 14, 14), grid)
    grid.cleanup()
    return path


def length(path):
    return sum(np.linalg.norm(np.subtract(after.position, before.position))
               for before, after in zip(path, path[1:]))


path_a = search(AStarFinder(diagonal_movement=DiagonalMovement.always))
path_t = search(ThetaStarFinder())

print(f"A*     path: {len(path_a)} cells, length {length(path_a):.2f}")
print(f"Theta* path: {len(path_t)} cells, length {length(path_t):.2f}")

Expected output:

A*     path: 20 cells, length 27.66
Theta* path: 3 cells, length 25.63

Theta* paths have fewer cells because the algorithm “shortcuts” through open space instead of hopping voxel-by-voxel, and they are shorter because a shortcut is not bound to the 26 grid directions.

Heuristic Choice#

Theta* accepts the same heuristic functions as A*; without one it takes octile. A shortcut is a straight segment, which only euclidean never overestimates:

from routing.pathfinding.finder.theta_star import ThetaStarFinder

from routing.pathfinding.core.heuristic import euclidean

finder = ThetaStarFinder(heuristic=euclidean)

On the comparison example above:

Heuristic

Path length

Iterations

Recommendation

euclidean

25.27

315

Never overestimates a shortcut: the shortest paths, the most iterations.

octile (default)

25.63

247

Exact for grid-diagonal steps; overestimates a shortcut, so fewer iterations.

manhattan

26.83

20

Overestimates every diagonal step and shortcut: fastest, longest paths.

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",    # SmartFinder's default is "never"
)

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

In the pipeline Theta* searches under the design rules like A*: a shortcut is one move, priced on the mean weight of the cells it crosses, and a turn penalty is charged at each bend. It serves one path per conduit — n_iterations yields no alternative paths.

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#