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*.

.. contents:: On this page
   :local:
   :depth: 1


When to Use Theta*
------------------

.. list-table::
   :header-rows: 1
   :widths: 30 35 35

   * - 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
-----------

:class:`~routing.pathfinding.finder.theta_star.ThetaStarFinder` has the same interface
as :class:`~routing.pathfinding.finder.a_star.AStarFinder`. Theta* always uses
``DiagonalMovement.always`` (any-angle requires it):

.. code-block:: python

   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*
-----------------------

.. code-block:: python

   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:

.. code-block:: python

   from routing.pathfinding.finder.theta_star import ThetaStarFinder

   from routing.pathfinding.core.heuristic import euclidean

   finder = ThetaStarFinder(heuristic=euclidean)

.. list-table::
   :header-rows: 1
   :widths: 20 80

   * - 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
:class:`~routing.core.finders.SmartFinder`:

.. code-block:: python

   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
----------

- :doc:`pathfinding_basic` — A* and multi-grid pathfinding tutorial
- :doc:`../user_guide/pathfinding_module` — complete pathfinding module reference
- :doc:`basic_routing` — full CAD routing pipeline