User Guide: The routing.pathfinding Module#

routing.pathfinding is the pathfinding engine of routing: one compiled search over the cells of 3D grids, of which A*, Dijkstra, Theta*, greedy best-first and breadth-first are policies. RoutePlanner runs it on the grids a CadMap builds; you can also run it on a grid of your own, built from a weight array, without any CAD file.

Module Structure #

The layout is pathfinding3D’s. The grid, its nodes and the search are compiled with Cython when the package is built.

routing.pathfinding/
├── core/
│   ├── grid.py              — Grid: the nodes of one grid, their walkable neighbours, line of sight
│   ├── node.py              — GridNode, SmartGridNode, AttributeMap (the layout and the state a path carries),
│   │                          VisitedValues, registry of the grid frames
│   ├── diagonal_movement.py — DiagonalMovement enum
│   └── heuristic.py         — heuristic functions
└── finder/
    ├── finder.py            — Finder: the search, the pricers of the design rules, SearchStateNode
    ├── a_star.py            — AStarFinder
    ├── dijkstra.py          — DijkstraFinder
    ├── theta_star.py        — ThetaStarFinder
    ├── best_first.py        — BestFirstFinder
    └── breadth_first.py     — BreadthFirstFinder

The finders search a SmartGrid — one grid, carrying the design rules — or a SmartWorld — several grids stitched together.

SmartGrid #

SmartGrid is built from a 3D weight array and the frame that places it in space:

import numpy as np
from routing.core.grid import SmartGrid

weights = np.ones((10, 10, 10))   # every cell walkable, weight 1
weights[5, 5, 5] = 0              # obstacle at the centre

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

Cell values:

0 or negative: obstacle — the cell has no node, grid.node(x, y, z) returns None
positive: walkable — the weight of the cell: entering it costs the length of the step times this weight

Constructor parameters:

Parameter	Default	Description
`weights`	required	3D array of shape (width, height, depth).
`voxel_size`	required	Edge length of a cell, in world units.
`origin`	required	World coordinates of the centre of cell `(0, 0, 0)`.
`design_rules`	`None`	Rules pricing each move, see Design Rules in the Search.
`toggled_attributes`	`None`	Boolean arrays of the grid’s shape, keyed by attribute name, that the rules read on the nodes (`node.get_custom_attr(name)`).
`grid_id`	`0`	Identifier of the grid, one per grid of a `SmartWorld`.

Building a grid registers its frame — grid_id, origin, voxel size — in a registry the search reads: the length of a step is counted in cells of the largest registered voxel size, and a node reads its position there. A grid built again under the same grid_id with another frame overwrites the entry, with a warning; routing.pathfinding.core.node.clear_all_grids() empties the registry. CadMap.to_world() empties it before building the grids of its map, so a map routes the same whatever was routed before it in the process. Read or pick the paths of a map before building the world of another one: their nodes read their position in the registry.

Nodes #

grid.node(x, y, z) gives the SmartGridNode of a cell:

node.x, node.y, node.z — indices in its grid
node.grid_id and node.identifier — its grid, and (x, y, z, grid_id)
node.position — world coordinates of the cell centre
node.weight — the weight of the cell
node.direction — the heading the path holds at this node
node.straight_length, node.get_length(attribute), node.get_length("no_<attribute>") — the state a path carries at this node: how far it has run straight, holding the attribute, lacking it; counted in cells of the node’s grid

Lengths are the grid’s working state, not a record of a route. write_found_path lays them on the nodes of a found path (derive_path_state, node after node) so the path can be priced; the next search on the grid rewrites and resets them. A found path keeps its own copy: GridPath.states, one PathState per node — the direction, the straight length and the attribute lengths read off the nodes when the path was found. Read those, not the nodes, once other searches have run.

The start node needs a direction. A search leaves its start with a heading — in the routing pipeline, the direction of the port. Set it before searching; SmartFinder also requires one on the end node. cleanup() resets both:

start = grid.node(0, 0, 0)
start.direction = (1, 0, 0)

Connecting nodes of two grids of a SmartWorld:

node_a.connect(node_b)   # one-way: node_b becomes a neighbour of node_a
node_b.connect(node_a)   # and the way back

DiagonalMovement #

DiagonalMovement controls which directions the pathfinder can move in:

Value	Behaviour
`DiagonalMovement.never`	Only axis-aligned moves (6 directions: ±X, ±Y, ±Z). Fewest neighbours per cell; staircase paths.
`DiagonalMovement.always`	All 26 directions (faces + edges + corners), to any walkable neighbour. May cut through obstacle corners.
`DiagonalMovement.only_when_no_obstacle`	A diagonal move only when every cell it passes by is walkable: the axis cells it combines, and for a corner move the three face cells as well. No corner-cutting.
`DiagonalMovement.if_at_most_one_obstacle`	A diagonal move when at most one of the cells it passes by is an obstacle.

from routing.pathfinding.core.diagonal_movement import DiagonalMovement
from routing.pathfinding.finder.a_star import AStarFinder

finder = AStarFinder(diagonal_movement=DiagonalMovement.only_when_no_obstacle)

Heuristics #

A heuristic estimates the remaining cost from the absolute offsets (dx, dy, dz) to the target, counted in cells of the coarsest grid. 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`). Default without diagonals.
`heuristic.octile`	`from routing.pathfinding.core.heuristic import octile`	Diagonal movement on the grid. Default with diagonals.
`heuristic.euclidean`	`from routing.pathfinding.core.heuristic import euclidean`	Any-angle movement (Theta*): never overestimates a straight segment.
`heuristic.chebyshev`	`from routing.pathfinding.core.heuristic import chebyshev`	Diagonal movement where a diagonal step costs as much as an axis step. Rare use case.

Pass the function itself; any callable (dx, dy, dz) -> float is accepted, these four and null (no heuristic) being computed without calling back into Python:

from routing.pathfinding.core.heuristic import octile

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

Available Finders #

All finders share one interface: find_path(start, end, grid_or_world) returns the path as a list of nodes, from start to end (empty when there is none), and the number of iterations.

Class	Description
`AStarFinder`	A* — the default choice. Exact on turns: with a `TurnPenalizer` the search keeps one state per cell and arrival heading.
`DijkstraFinder`	Dijkstra — the cheapest path, no heuristic.
`ThetaStarFinder`	Theta* — any-angle paths through line-of-sight shortcuts. Diagonals by default. Serves one path per conduit. See Tutorial: Smoother Paths with Theta*.
`BestFirstFinder`	Greedy best-first — the heuristic outweighs the cost a million times. Fast, not optimal.
`BreadthFirstFinder`	Breadth-first — the shortest path in length (in steps without diagonals), weights and rules aside.

Every finder also takes time_limit (seconds) and max_runs (iterations), unlimited by default; hitting one raises ExecutionTimeException or ExecutionRunsException from routing.pathfinding.finder.finder.

Import pattern:

from routing.pathfinding.finder.a_star import AStarFinder
from routing.pathfinding.finder.best_first import BestFirstFinder
from routing.pathfinding.finder.breadth_first import BreadthFirstFinder
from routing.pathfinding.finder.dijkstra import DijkstraFinder
from routing.pathfinding.finder.theta_star import ThetaStarFinder

Running a Search #

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

weights = np.ones((10, 10, 10))
weights[3:7, 3:7, :] = 0    # a column of obstacles

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 = AStarFinder(diagonal_movement=DiagonalMovement.always)
path, runs = finder.find_path(start, end, grid)

cells = [(node.x, node.y, node.z) for node in path]
print(f"Found a path of {len(cells)} cells in {runs} iterations")

# IMPORTANT: cleanup before searching the grid again
grid.cleanup()

Goal sets. A finder armed with set_goals ends on the first goal it reaches, any of them; clear_goals returns it to the single target:

finder.set_goals([grid.node(9, 0, 0), grid.node(0, 9, 0)])
start.direction = (1, 0, 0)
path, runs = finder.find_path(start, grid.node(9, 0, 0), grid)
finder.clear_goals()
grid.cleanup()

Design Rules in the Search #

The design rules of a SmartGrid price every move the search considers: a rule adds a cost to the move (compute_cost), or weighs on the heuristic of the cell the move enters (compute_heuristic), in the order of the list.

from routing.core.design_rules import TurnPenalizer

grid = SmartGrid(weights, voxel_size=1.0, origin=(0.0, 0.0, 0.0),
                 design_rules=[TurnPenalizer(cost=5.0)])

TurnPenalizer, StraightLengthRule, GravityRule, BoundedAttributeRule, BoundedCustomLengthRule, ClampingConstraint and PoolingRule are priced by compiled code — the pricer DesignRule.move_pricer(attribute_map) builds — which their compute_cost and compute_heuristic call; a subclass keeping them is priced the same way. A rule writing its own compute_cost or compute_heuristic — a subclass of these, or a rule of your own — is priced by calling them at every move (DesignRule.prices_moves tells which): there is nothing to declare and nothing to compile. SmartGrid.priced_rules lists the rules of a grid, each with the pricer it got.

The node such a rule receives is a SearchStateNode: the cell entered along the state’s direction, with the straight length and the attribute lengths of that state; its parent is read off the search on demand, so the path behind a state can be walked. Under Theta*, a rule priced through its own methods judges a shortcut on its two ends, where the compiled pricers count every cell the segment crosses: the path found can differ from the one the compiled rule finds.

A found path is priced again by calc_path_cost: the step lengths times the weights, what each rule adds through compute_cost, and one violation penalty of 500 per move a rule weighs on through compute_heuristic. GridPath.indicators keeps, per rule, the nodes it charged. See CostRule (base class) and the ConstraintRule section of User Guide: Design Rules Reference.

SmartWorld (Multi-Grid)#

SmartWorld searches several grids linked by node connections as one space. Each grid keeps its own frame, possibly its own voxel size; the world takes a frame at the coarsest voxel size covering them all:

from itertools import product
from routing.core.world import SmartWorld

coarse = SmartGrid(np.ones((3, 3, 1)), voxel_size=1.0, origin=(0.5, 0.5, 0.5), grid_id=0)
fine = SmartGrid(np.ones((4, 12, 4)), voxel_size=0.25, origin=(3.125, 0.125, 0.125), grid_id=1)

# each coarse cell of the last column faces 4 × 4 fine cells: connect them both ways
for y in range(3):
    for fine_y, fine_z in product(range(4 * y, 4 * y + 4), range(4)):
        coarse.node(2, y, 0).connect(fine.node(0, fine_y, fine_z))
        fine.node(0, fine_y, fine_z).connect(coarse.node(2, y, 0))

world = SmartWorld(grids={0: coarse, 1: fine}, world_matrix_shape=(4, 3, 1),
                   world_origin=(0.5, 0.5, 0.5), voxel_size=1.0)

start = coarse.node(0, 1, 0)
start.direction = (1, 0, 0)
path, runs = AStarFinder().find_path(start, fine.node(3, 4, 0), world)

cells = [node.identifier for node in path]   # (x, y, z, grid_id)
world.cleanup()                              # cleans every grid

A step into another grid keeps the heading it arrived with: crossing a change of scale is not priced as a turn. In the routing pipeline you do not build the world yourself: CadMap.to_world() builds it, one grid per region of the map, stitched at their borders (see User Guide: Multi-Scale and Multi-Grid Routing).

See Tutorial: 3D Pathfinding with routing.pathfinding for a step-by-step walkthrough of both single-grid and multi-grid pathfinding.

SmartFinder #

SmartFinder is the finder the routing pipeline takes. It names the algorithm, the heuristic and the diagonal policy by strings, and holds the engine’s finder as SmartFinder.finder:

from routing.core.finders import SmartFinder

finder = SmartFinder("AStar", "manhattan", "never")
route_planner = RoutePlanner(cadmap, finder)

`algorithm`	Engine finder
`"AStar"` (also `"astar"`, `"a*"`)	`AStarFinder`
`"Dijkstra"`	`DijkstraFinder`
`"ThetaStar"` (also `"theta"`, `"theta*"`)	`ThetaStarFinder`
`"BestFirst"` (also `"best"`)	`BestFirstFinder`
`"BreadthFirst"`	`BreadthFirstFinder`

An unknown name raises ValueError. heuristic names a function of routing.pathfinding.core.heuristic (None for the finder’s default) and diagonal a DiagonalMovement value ("never", "always", "only_when_no_obstacle", "if_at_most_one_obstacle").

SmartFinder.find_path(start, end, grid) returns (path, runs, runtime) and requires a direction on both nodes. A SmartFinder always searches weighted: its breadth-first prices weights and rules, as Dijkstra does.

Performance Tips #

Prefer DiagonalMovement.never for the fastest searches (fewest neighbours per cell).
Use DiagonalMovement.only_when_no_obstacle for slightly longer paths but no corner-cutting through obstacles.
Reuse the grid across searches: cleanup() resets only the nodes written since the last cleanup, and a weight update (SmartGrid.update) rebuilds only the cells whose weight changed.
Pre-load large maps from .npy files rather than recomputing them each run:
```
weights = np.load("my_environment.npy")
```

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