User Guide: The routing.pathfinding Module
===========================================

``routing.pathfinding`` is a standalone 3D grid pathfinding library. You can use it
independently of the full CAD routing pipeline — for any problem that needs to find
shortest paths through a discrete 3D space represented as a numpy array.

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


Module Structure
----------------

.. code-block:: text

   routing.pathfinding/
   ├── core/
   │   ├── grid.py          — Grid, GridNode
   │   ├── world.py         — World (multi-grid container)
   │   ├── diagonal_movement.py — DiagonalMovement enum
   │   └── heuristic.py     — heuristic functions
   └── finder/
       ├── a_star.py        — AStarFinder
       ├── theta_star.py    — ThetaStarFinder
       ├── dijkstra.py      — DijkstraFinder
       ├── bi_a_star.py     — BiAStarFinder
       ├── best_first.py    — BestFirstFinder
       ├── ida_star.py      — IDAStarFinder
       ├── breadth_first.py — BreadthFirstFinder
       └── msp.py           — MinimumSpanningTree


Grid
----

:class:`~routing.pathfinding.core.grid.Grid` represents a 3D occupancy map. Create it
from a numpy array or a nested list:

.. code-block:: python

   import numpy as np
   from routing.pathfinding.core.grid import Grid

   # From a numpy array (shape: width × height × depth)
   matrix = np.ones((10, 10, 10))    # all cells walkable (cost = 1)
   matrix[5, 5, 5] = 0              # obstacle at centre

   grid = Grid(matrix=matrix)

   # From explicit dimensions (all cells walkable by default)
   grid = Grid(width=10, height=10, depth=10)

**Cell values:**

- ``0`` or negative: **obstacle** — not traversable
- ``1``: walkable with default cost
- ``> 1``: walkable with that cost (higher = more expensive to traverse)

**Constructor parameters:**

.. list-table::
   :header-rows: 1
   :widths: 20 15 65

   * - Parameter
     - Default
     - Description
   * - ``matrix``
     - ``None``
     - 3D numpy array or nested list. Overrides ``width``, ``height``, ``depth``
       if provided.
   * - ``width``, ``height``, ``depth``
     - 0
     - Grid dimensions. Only used when ``matrix`` is not provided.
   * - ``grid_id``
     - 0
     - Integer identifier for the grid. Required for multi-grid routing.
   * - ``inverse``
     - ``False``
     - If ``True``, non-zero values are obstacles and 0 is walkable (inverse convention).

**Accessing nodes:**

.. code-block:: python

   # Get a node by (x, y, z) index
   start = grid.node(0, 0, 0)
   end   = grid.node(9, 9, 9)

After calling ``find_path()``, the grid stores visited state. Call ``cleanup()`` to
reset it before reusing the grid for another search:

.. code-block:: python

   grid.cleanup()


GridNode
--------

:class:`~routing.pathfinding.core.node_compiled.GridNode` is a single cell in the grid.
You usually get nodes via ``grid.node(x, y, z)`` rather than constructing them directly.

**Key attributes:**

- ``node.x``, ``node.y``, ``node.z`` — integer coordinates
- ``node.walkable`` — ``True`` if the cell is traversable
- ``node.weight`` — traversal cost for this cell
- ``node.identifier`` — ``(x, y, z)`` for single-grid; ``(x, y, z, grid_id)`` for
  multi-grid

**Connecting nodes (multi-grid):**

.. code-block:: python

   # Create a one-way connection from node A (in grid 0) to node B (in grid 1)
   node_a.connect(node_b)

   # Bidirectional connection
   node_a.connect(node_b)
   node_b.connect(node_a)


DiagonalMovement
----------------

:class:`~routing.pathfinding.core.diagonal_movement.DiagonalMovement` controls which
directions the pathfinder can move in:

.. list-table::
   :header-rows: 1
   :widths: 40 60

   * - Value
     - Behaviour
   * - ``DiagonalMovement.never``
     - Only axis-aligned moves (6 directions: ±X, ±Y, ±Z). Fastest; staircase paths.
   * - ``DiagonalMovement.always``
     - All 26 directions (faces + edges + corners). Shortest Euclidean paths; may
       cut through obstacle corners.
   * - ``DiagonalMovement.only_when_no_obstacle``
     - Diagonal moves only when neither adjacent face cell is an obstacle. Safe paths
       without corner-cutting.
   * - ``DiagonalMovement.if_at_most_one_obstacle``
     - Diagonal moves when at most one adjacent face cell is an obstacle. Allows limited
       corner-cutting through single-cell obstacles.

.. code-block:: python

   from routing.pathfinding.core.diagonal_movement import DiagonalMovement

   finder = AStarFinder(diagonal_movement=DiagonalMovement.only_when_no_obstacle)


Heuristics
----------

Heuristic functions estimate the remaining cost from a node to the goal. The right
choice depends on your movement model:

.. list-table::
   :header-rows: 1
   :widths: 25 30 45

   * - Function
     - Import
     - When to use
   * - ``heuristic.manhattan``
     - ``from routing.pathfinding.core.heuristic import manhattan``
     - Axis-aligned movement only (``DiagonalMovement.never``). Exact estimate.
   * - ``heuristic.euclidean``
     - ``from routing.pathfinding.core.heuristic import euclidean``
     - Free movement in any direction. Good default for ``always``.
   * - ``heuristic.octile``
     - ``from routing.pathfinding.core.heuristic import octile``
     - Diagonal movement on a grid. More accurate than Manhattan for ``always``.
   * - ``heuristic.chebyshev``
     - ``from routing.pathfinding.core.heuristic import chebyshev``
     - Diagonal movement where diagonal = horizontal cost. Rare use case.

Pass a heuristic function (callable) imported from :mod:`routing.pathfinding.core.heuristic`:

.. code-block:: python

   from routing.pathfinding.core.heuristic import octile

   finder = AStarFinder(heuristic=octile, diagonal_movement=DiagonalMovement.always)


Available Finders
-----------------

All finders share the same interface: ``find_path(start, end, grid_or_world)``.

.. list-table::
   :header-rows: 1
   :widths: 40 60

   * - Class
     - Description
   * - ``AStarFinder``
     - A* — fast, general-purpose. Best default choice.
   * - ``ThetaStarFinder``
     - Theta* — any-angle movement; produces smoother, more direct paths. Slightly
       slower than A*. See :doc:`../tutorials/theta_star`.
   * - ``DijkstraFinder``
     - Dijkstra — always optimal; slower on large grids (no heuristic).
   * - ``BiAStarFinder``
     - Bidirectional A* — searches from both endpoints simultaneously; faster on
       long paths.
   * - ``BestFirstFinder``
     - Greedy best-first — very fast but not guaranteed optimal.
   * - ``IDAStarFinder``
     - IDA* (iterative-deepening A*) — memory-efficient; slow on large grids.
   * - ``BreadthFirstFinder``
     - BFS — uniform cost; treats all cells as equal regardless of weight.
   * - ``MinimumSpanningTree``
     - Builds a minimum spanning tree connecting multiple nodes.

Import pattern:

.. code-block:: python

   from routing.pathfinding.finder.a_star import AStarFinder
   from routing.pathfinding.finder.theta_star import ThetaStarFinder
   from routing.pathfinding.finder.dijkstra import DijkstraFinder
   from routing.pathfinding.finder.bi_a_star import BiAStarFinder
   from routing.pathfinding.finder.best_first import BestFirstFinder
   from routing.pathfinding.finder.ida_star import IDAStarFinder
   from routing.pathfinding.finder.breadth_first import BreadthFirstFinder
   from routing.pathfinding.finder.msp import MinimumSpanningTree


Running a Search
----------------

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

   matrix = np.ones((10, 10, 10))
   matrix[3:7, 3:7, :] = 0    # wall of obstacles

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

   finder = AStarFinder(diagonal_movement=DiagonalMovement.always)
   path, runs = finder.find_path(start, end, grid)

   # Convert to list of (x, y, z) tuples
   coords = [p.identifier for p in path]
   print(f"Found path of {len(coords)} nodes in {runs} iterations")

   # IMPORTANT: cleanup before reusing the grid
   grid.cleanup()


World (Multi-Grid)
------------------

:class:`~routing.pathfinding.core.world.World` is a container for multiple grids,
enabling pathfinding across **disconnected spaces linked by explicit node connections**.

.. code-block:: python

   from routing.pathfinding.core.world import World

   grid0 = Grid(matrix=space0, grid_id=0)
   grid1 = Grid(matrix=space1, grid_id=1)

   # Create a bidirectional bridge between grids
   grid0.node(9, 9, 9).connect(grid1.node(0, 0, 0))
   grid1.node(0, 0, 0).connect(grid0.node(9, 9, 9))

   # Wrap in a World
   world = World({0: grid0, 1: grid1})

   # Find a cross-grid path
   finder = AStarFinder()
   path, runs = finder.find_path(grid0.node(0, 0, 0), grid1.node(9, 9, 9), world)

   # Node identifiers are (x, y, z, grid_id) for multi-grid paths
   coords = [p.identifier for p in path]
   path_in_grid0 = [c[:3] for c in coords if c[3] == 0]
   path_in_grid1 = [c[:3] for c in coords if c[3] == 1]

See :doc:`../tutorials/pathfinding_basic` for a step-by-step walkthrough of both
single-grid and multi-grid pathfinding.


Performance Tips
----------------

- **Prefer** ``DiagonalMovement.never`` for the fastest searches (fewest neighbours
  per node).
- **Use** ``DiagonalMovement.only_when_no_obstacle`` for slightly longer paths but no
  corner-cutting through obstacles.
- **Pre-load large maps** from ``.npy`` files rather than recomputing them each run:

  .. code-block:: python

     matrix = np.load("my_environment.npy")

- **Reuse the Grid object** across multiple ``find_path`` calls by calling
  ``grid.cleanup()`` between searches.
- **For large grids** (> 200³ voxels) and memory-constrained environments, prefer
  ``IDAStarFinder`` over ``AStarFinder`` to reduce memory usage.


Next Steps
----------

- :doc:`../tutorials/pathfinding_basic` — hands-on tutorial (A* + multi-grid)
- :doc:`../tutorials/theta_star` — smoother paths with Theta*
- :doc:`../tutorials/basic_routing` — integrate pathfinding with the full CAD routing pipeline