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.

Module Structure #

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 #

Grid represents a 3D occupancy map. Create it from a numpy array or a nested list:

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:

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:

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

grid.cleanup()

GridNode #

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

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

DiagonalMovement controls which directions the pathfinder can move in:

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.

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:

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 routing.pathfinding.core.heuristic:

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

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 Tutorial: Smoother Paths with Theta.
`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:

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 #

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

World is a container for multiple grids, enabling pathfinding across disconnected spaces linked by explicit node connections.

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 Tutorial: 3D Pathfinding with routing.pathfinding 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:
```
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 #

Tutorial: 3D Pathfinding with routing.pathfinding — hands-on tutorial (A* + multi-grid)
Tutorial: Smoother Paths with Theta* — smoother paths with Theta*
Tutorial: Routing Pipes Through a CAD Assembly — integrate pathfinding with the full CAD routing pipeline

User Guide: The routing.pathfinding Module#

This Page