routing.core.grid

Grid-related classed for 3D pathfinding with design rules and port extensions.

class routing.core.grid.GridForcedZone(name: str, inside: set[tuple[int, tuple[int, int, int]]])

Bases: object

A forced zone laid on the grids of the map: the cells a route must pass through, as the search sees them.

The grid-side twin of GridPort: a port is extended into a node, a zone into its cells.

Parameters:

• name – The zone name.

• inside – The cells of the zone, as (grid id, index) pairs.

MIN_DOORS = 2

doors(grid: SmartGridInterface, offsets: tuple[tuple[int, int, int], ...]) → list[SmartGridNode]

Return the doors of the components of the zone a route can cross on grid.

A component gathers the open cells of the zone the search can step between by offsets or across grids. A door is one of its cells opening on an open cell outside the zone; the component can be crossed when it holds at least two doors: a route reaching one of them leaves the zone by another, never back through its own cells. A pocket the pooling halos enclose has one door at most and is never targeted.

classmethod from_zone(zone: ForcedZone, rooms: list[RoutingVoxelization]) → GridForcedZone

Lay zone on the room voxelizations, the grid id of each being its rank in rooms.

holds(node: SmartGridNode) → bool

Return whether node is a cell of the zone.

class routing.core.grid.GridPort(node: SmartGridNode, port: Port, length: float)

Bases: object

A class representing a port extended into the grid for pathfinding.

This class connects a Port (input/output connection point) with a SmartGridNode in the routing grid. It extends the port into the grid by a specified length and sets up the node’s direction based on the port’s orientation.

Parameters:

• node – SmartGridNode where the port is extended to in the grid.

• port – Port object containing position and orientation information.

• length – Length of the port extension in length units.

property direction: tuple[int, int, int]

Get the direction vector from port orientation.

Converts the port’s orientation vector to a discrete 3D direction tuple (i, j, k) where each component is -1, 0, or 1. This direction represents the routing direction from the port into the grid.

Returns:

Direction vector as tuple of integers (i, j, k).

property identifier: tuple

Get the global identifier of the node.

property index: tuple[int, int, int]

Get the index of the node in its grid.

set_node_direction() → None

Set the node’s direction from the port orientation.

Updates the SmartGridNode’s direction attribute to match the port’s orientation. This direction is used by pathfinding algorithms to apply routing constraints (turn penalties, straight length requirements).

Returns:

None

class routing.core.grid.SmartGrid(weights: ndarray, voxel_size: float, origin: tuple[float, float, float], design_rules: list[DesignRule] | None = None, toggled_attributes: dict[str, ndarray] | None = None, grid_id: int = 0)

Bases: Grid, SmartGridInterface

A class representing a smart grid implementation for pathfinding with design rules.

This class inherits from Grid and SmartGridInterface, and extends the base Grid with routing-specific features including design rule integration for cost computation, attribute toggling for constraint checking, multi-grid support with grid IDs, and dynamic weight updates.

Parameters:

• weights – The 3D numpy array (width x height x depth) containing weight values for each voxel. Positive values indicate traversable voxels.

• voxel_size – The size of each voxel in length units.

• origin – The origin point in global coordinates as (x, y, z) tuple.

• design_rules – The optional list of DesignRule objects for computing costs and heuristics during pathfinding. Defaults to None.

• toggled_attributes – The optional dictionary mapping attribute names to boolean matrices (same shape as weights) for constraint checking. Defaults to None.

• grid_id – The unique identifier for this grid (for multi-grid routing). Defaults to 0.

static calc_path_length(path: list[SmartGridNode], voxel_size: float) → float

Calculate total path length in world coordinates.

Computes the total length of a path by multiplying the number of nodes by voxel_size. This gives an approximate length assuming each edge is one voxel unit.

Parameters:

• path – List of SmartGridNode objects representing the path.

• voxel_size – Size of a voxel in length units.

Returns:

Total path length in world coordinates (length units).

cleanup() → None

Reset the search state of the nodes written since the last cleanup, so the next search starts clean.

static get_discrete_length(min_length: float, voxel_size: float) → int

Convert minimum length to discrete voxel units.

Converts a minimum length requirement from world coordinates to voxel units by dividing by voxel_size and rounding up. Used for constraint rules that require minimum distances.

Parameters:

• min_length – Minimum length in world coordinates (length units).

• voxel_size – Size of a voxel in length units.

Returns:

Minimum length in voxel units (integer, rounded up).

get_reachable_nodes(node: SmartGridNode, depth: int, diagonal_movement: int = 2) → set[SmartGridNode]

Get all nodes reachable from a starting node within a given depth.

Performs a breadth-first search from the starting node, collecting all nodes reachable within the specified number of hops. The starting node itself is not included in the results.

Parameters:

• node – Starting SmartGridNode to search from.

• depth – Maximum number of hops from starting node (depth of search).

• diagonal_movement – DiagonalMovement enum value for neighbor selection. Defaults to never.

Returns:

Set of SmartGridNode objects reachable within depth hops.

property grids: dict[int, SmartGrid]

The grids by id, as a world exposes them: this one alone.

property nbytes: int

Calculate the total memory usage in bytes of the SmartGrid.

Computes memory usage by summing: - Memory for all SmartGridNode objects - Memory for design rules - Memory for attribute map

Returns:

Total memory usage in bytes.

node(x: int, y: int, z: int) → SmartGridNode | None

Get node at grid indices (x, y, z).

property priced_rules: list[tuple[DesignRule, MovePricer]]

The rules pricing moves on this grid, each with its pricer, in the rules’ order.

A rule redefining its pricing methods is priced through them (DesignRule.prices_moves, PythonPricer), any other through its compiled pricer (DesignRule.move_pricer()); a rule with neither prices nothing and is left out.

property pricers: list[MovePricer]

The pricers of priced_rules, what a search hands the finder for this grid.

search_state() → GridSearchState

Open what one search keeps of this grid: the grid and its pricers; the cells touched go to processed_nodes.

search_states() → dict[int, GridSearchState]

Open the search states of the grids a search from here may walk: this one.

set_source_and_target(source: SmartGridNode, target: SmartGridNode) → None

Set source and target nodes for pathfinding.

Stores the start and end nodes for pathfinding algorithms. Both nodes must have their direction attribute set (typically from port orientation).

Parameters:

• source – Starting SmartGridNode for pathfinding.

• target – Target SmartGridNode for pathfinding.

Returns:

None

Raises:

ValueError – If source or target direction is not defined.

update(design_rules: list[DesignRule], toggled_attr: dict[str, ndarray], weights: ndarray) → None

Update grid with new design rules, attributes, and weights.

Dynamically updates the grid state:

1. Updates design rules (converted to voxel units)

2. Updates attribute map if attributes changed

3. Reconciles every voxel whose weight changed since the last update (all voxels on first update or attribute-map change):

   • Creates new nodes if weight > 0 and node doesn’t exist

   • Updates existing nodes with new weights and attributes

   • Deletes nodes if weight <= 0 and no connections exist

4. Refreshes the attributes of the other nodes whose toggled attributes changed

This allows the grid to adapt to changing routing conditions without full reconstruction.

Parameters:

• design_rules – List of DesignRule objects to apply.

• toggled_attr – Dictionary mapping attribute names to boolean arrays (same shape as weights).

• weights – 3D numpy array (width x height x depth) with new weight values. Must match grid shape.

Returns:

None

Raises:

ValueError – If weights shape doesn’t match grid shape.

update_design_rules(design_rules: list[DesignRule]) → None

Update design rules with voxelized versions.

Replaces the grid’s design rules with new ones, converting them to voxel units using the grid’s voxel_size.

Parameters:

design_rules – List of DesignRule objects to apply.

Returns:

None

walkable(x: int, y: int, z: int) → bool

Check if node at (x, y, z) is walkable.

Returns True if the node exists and is walkable (not an obstacle). Optimized version that doesn’t check bounds (assumes has_node() called first).

Parameters:

• x – X coordinate (width dimension).

• y – Y coordinate (height dimension).

• z – Z coordinate (depth dimension).

Returns:

True if node exists and is walkable, False otherwise.

class routing.core.grid.SmartGridInterface(frame: VoxelFrame)

Bases: object

A class representing an interface for SmartGrid-like objects used in pathfinding.

This class defines the common interface for grid objects used by pathfinding algorithms. It provides node access and pathfinding helper methods on top of the VoxelFrame its nodes are sampled on.

Parameters:

frame – The chart between world coordinates and the grid’s node indices.

Implementations own design_rules: SmartGrid holds copies voxelized at its own step and refreshed by SmartGrid.update(), SmartWorld reads them back from its sub-grids.

block_port_tail(grid_port: GridPort, radius: float) → None

Block voxels along the port extension tail to prevent routing conflicts.

Closes (marks as non-traversable) voxels in a cylinder from the port position to the grid port extension node. This prevents paths from passing too close to the port connection, ensuring proper clearance.

The blocked region: - Starts from port position (included) - Ends at grid_port.index (excluded, so the extension node remains open) - Has radius around the line connecting these points - Lies in this grid: on a decomposed map, the part of the tail in a neighbouring grid stays open

Parameters:

• grid_port – GridPort with tail to block. The tail is the line from port position to the extension node.

• radius – Radius in length units around the tail line to block. Converted to voxel units internally.

Returns:

None

block_ports_tail(start: GridPort, end: GridPort, radius: float) → None

Block voxels along both start and end port extension tails.

Convenience method that blocks the tail regions for both input and output ports to prevent routing conflicts near port connections.

Parameters:

• start – Starting GridPort (input port).

• end – Ending GridPort (output port).

• radius – Radius in length units around the tail lines to block.

Returns:

None

build_pipe_ends(solution: Solution) → tuple[GridPort, list[GridPort]]

Extend the solution’s terminals into the grid: the departure and the goals a route may end at.

The departure is the start port extended over its straight length. The goals are what the terminals give: the end port extended, or the cells a tee reaches its tap ports from (_tap_goals()). The design rules are told the departure and the goal nearest to it.

Returns:

The departure and the goals, each a GridPort carrying the port it stands for.

calc_path_cost(path: list[SmartGridNode]) → tuple[float, dict[str, list[tuple[int, int, int]]]]

Price a found path as the search did, and tell where each rule weighed: the figures a route is judged on.

Per move, the step length times the weight of the cells crossed, plus what each rule adds (compute_cost); a rule weighing on the heuristic of a move (compute_heuristic) counts one violation, the start’s own move aside. The rules are priced by the pricers of the grid hosting each move (SmartGrid.priced_rules), built once per grid for the whole path.

Parameters:

path – The nodes of the path, the start first.

Returns:

The cost, and per rule class name the indices of the nodes its moves were charged at.

cancel_node(node: SmartGridNode) → None

Cancel a node by marking it as closed.

Marks the node as closed, preventing pathfinding from exploring it. Used to block nodes from root paths in k-shortest paths algorithm.

Parameters:

node – SmartGridNode to cancel.

Returns:

None

cleanup() → None

Clean up grid state after pathfinding.

Abstract method that must be implemented by subclasses. Resets grid state between pathfinding operations, including: - Clearing processed nodes - Resetting node attributes (closed, forbidden, direction, etc.) - Cleaning up temporary pathfinding data

This should be called before each new pathfinding operation to ensure a clean state.

Returns:

None

coord_to_node(coords: tuple[float, float, float] | ndarray) → SmartGridNode | None

Get the node hosting a global coordinate, or None if that coordinate falls outside the grid.

property depth: int

Grid depth in voxels (z dimension).

extend_port(port: Port, port_length: float) → SmartGridNode

Extend port in its orientation direction by given length.

Finds the best grid node to connect a port by: 1. Computing extended coordinate along port orientation 2. Finding candidate nodes near the extended position 3. Filtering candidates by direction alignment and cylinder constraint 4. Selecting the closest valid node

The method ensures the port extension follows the port’s orientation and connects to an active (walkable) voxel in the grid.

When the extension stays within the voxel containing the port and that voxel is walkable, it is returned directly without searching, so a confined port never escapes its enclosure through an obstacle. A port lying outside the grid has no such voxel and always goes through the search below.

Parameters:

• port – Port object with position and orientation.

• port_length – Length to extend the port in length units.

Returns:

SmartGridNode where the port is extended to, with direction set from port orientation.

finest_node_at(coords: tuple[float, float, float] | ndarray) → SmartGridNode | None

Get the node hosting a global coordinate at the finest scale in use: the grid’s own cell here.

property finest_voxel_size: float

The finest step in use: a single grid has one.

grid_hosting(node: SmartGridNode) → SmartGrid

Give the grid whose cells node belongs to.

has_node(x: int, y: int, z: int) → bool

Check if grid coordinates are within bounds.

property height: int

Grid height in voxels (y dimension).

initialize_on_spur_node(spur_node: SmartGridNode, spur_index: int, spur_direction: tuple[int, int, int], root_path: list[SmartGridNode], shortest_paths: list[GridPath], grid_end: GridPort) → None

Initialize grid for pathfinding from a spur node (Yen’s algorithm).

Prepares the grid to find an alternative path from a spur node by: 1. Cleaning up previous pathfinding state 2. Setting direction on spur node and end port 3. Blocking edges and nodes from previous shortest paths to avoid duplicates

This method is called during k-shortest paths computation to ensure each new path is truly different from previous ones.

Parameters:

• spur_node – SmartGridNode where the spur path starts.

• spur_index – Index of spur_node in the previous path.

• spur_direction – Direction vector from which spur_node was reached.

• root_path – Path segment from start to spur node.

• shortest_paths – List of previously found shortest paths to avoid.

• grid_end – Ending GridPort with target node.

Returns:

None

static is_open(node: SmartGridNode) → bool

Return whether the search can step on node: walkable, weighted, not closed.

neighbours_of(node: SmartGridNode, offsets: tuple[tuple[int, int, int], ...]) → list[SmartGridNode]

Return the cells one step from node: by offsets on its grid, and its connections to other grids.

node(x: int, y: int, z: int) → SmartGridNode | None

Get node at given grid coordinates.

Abstract method that must be implemented by subclasses. Returns the SmartGridNode at the specified grid indices, or None if the coordinates are out of bounds or the node is an obstacle.

Parameters:

• x – X coordinate (width dimension).

• y – Y coordinate (height dimension).

• z – Z coordinate (depth dimension).

Returns:

SmartGridNode at (x, y, z), or None if not available.

property origin: tuple[float, float, float]

The centre of voxel (0, 0, 0) in world coordinates.

path_to_pipe_path(path: list[SmartGridNode], grid_start: GridPort, grid_end: GridPort | None, solution: Solution, runs: int = 0, runtime: float = -1) → GridPath

Convert pathfinding result to GridPath with cost and metadata.

Processes a path found by pathfinding algorithm into a GridPath object with complete routing information: 1. Processes path nodes (direction, parent, attributes) 2. Calculates total cost and rule feedback 3. Creates GridPath with all metadata (ports, pipe type, statistics)

If path is empty, returns an invalid GridPath with high cost.

Parameters:

• path – List of SmartGridNode objects from pathfinding, or empty list.

• grid_start – Starting GridPort for path processing.

• solution – Solution object with input_port, output_port, pipe_type.

• runs – Number of pathfinding iterations performed. Defaults to 0.

• runtime – Pathfinding execution time in seconds. Defaults to -1.

Returns:

GridPath object with complete routing information, or invalid GridPath (cost=1e16) if path is empty.

pooling_distance(type_: str, other_type: str) → float

Return the clearance the pooling rule keeps between two pipe types; none without a pooling rule.

reach_node(port: Port, length: float, push_limit: float) → SmartGridNode | None

Return the open cell whose centre stands at least length along port, within the push.

A tap port stands on the axis of a conduit whose packs close the cells up to the pooling halo around it: the cell is looked for at length, then pushed outward by the finest step up to push_limit, never beyond, where a closed cell is CAD. Its centre must stand at length or more along the port: the leg from the cell down to the port keeps the junction length, which a cell hosting the reach point but centred short of it would not. None when no such cell is open.

remove_edge(node_a: SmartGridNode, node_b: SmartGridNode) → None

Remove edge between two nodes by marking them as forbidden.

Bidirectionally marks nodes as forbidden to each other, preventing pathfinding from traversing this edge. Used in k-shortest paths algorithm to block edges from previous paths.

Parameters:

• node_a – First SmartGridNode.

• node_b – Second SmartGridNode.

Returns:

None

remove_forbidden_path(spur_index: int, root_path: list[SmartGridNode], shortest_paths: list[GridPath]) → None

Remove forbidden paths from the grid for k-shortest paths algorithm.

Blocks edges and nodes to prevent finding duplicate paths:

1. For each previous shortest path that shares the same root_path up to spur_index, blocks the edge from spur_node to the next node

2. Cancels all nodes in the root_path to prevent reusing them

This ensures that spur paths are truly different from previous paths.

Parameters:

• spur_index – Index of the spur node in the path.

• root_path – Path segment from start to spur node (list of nodes).

• shortest_paths – List of previously found shortest paths to avoid.

Returns:

None

restart_from(node: SmartGridNode, direction: tuple[int, int, int], forbidden: list[SmartGridNode]) → None

Clean the search residues, then set the next search off from node along direction, forbidden cells closed.

routed_solutions: list[Solution]

search_states() → dict[int, GridSearchState]

Open the search states (SmartGrid.search_state()) of the grids a search may walk, by grid id.

set_source_and_target(source: SmartGridNode, target: SmartGridNode) → None

Set source and target nodes for pathfinding.

Stores the start and end nodes for pathfinding algorithms. Both nodes must have their direction attribute set (typically from port orientation).

Parameters:

• source – Starting SmartGridNode for pathfinding.

• target – Target SmartGridNode for pathfinding.

Returns:

None

Raises:

ValueError – If source or target direction is not defined.

property shape: tuple[int, int, int]

Grid dimensions as (width, height, depth) in voxels.

static straight_path(start: SmartGridNode, end: SmartGridNode) → tuple[list[SmartGridNode], int, float]

Create a straight path between two nodes.

Returns a minimal path containing only start and end nodes. Used when nodes are very close (Manhattan distance <= 3) to avoid unnecessary pathfinding computation.

Parameters:

• start – Starting SmartGridNode.

• end – Target SmartGridNode.

Returns:

Tuple of (path, runs, runtime) where: - path: List containing [start, end] - runs: 0 (no pathfinding iterations) - runtime: -1 (not measured)

update(design_rules: list[DesignRule], toggled_attr: dict[str, ndarray], weights: ndarray) → None

Update grid with design rules and weights.

Abstract method that must be implemented by subclasses. Applies design rules and updates node weights and attributes based on routing constraints.

Parameters:

• design_rules – List of DesignRule objects to apply (constraints, costs, heuristics).

• toggled_attr – Dictionary mapping attribute names to boolean arrays indicating which voxels have the attribute set.

• weights – 3D weight array of shape (width, height, depth) containing routing costs for each voxel.

Returns:

None

property voxel_size: float

The edge length of a voxel, in world units.

property width: int

Grid width in voxels (x dimension).

write_found_path(start_port: Port, path: list[SmartGridNode]) → None

Write on the nodes of a found path the state the search held along it, so the path can be priced.

The start leaves along the port’s heading; each node after it takes its parent, its direction and, through the cells the move crosses (a Theta* segment’s, not its end alone), the straight length and attribute lengths the search derived (SmartGridNode.derive_path_state()).

The start itself is left as cleanup leaves it, lengths and straight length at zero, where the search starts from unbounded ones (AttributeMap.start_path_state): the reported cost of a route has always counted a rule’s violation at the move right after the start, which the search never prices, and keeps doing so until that count is decided.

Parameters:

• start_port – Starting Port with orientation for initial direction.

• path – List of SmartGridNode objects representing the found path.

Returns:

None

routing.core.grid.build_attribute_map(toggled_attributes: dict[str, ndarray]) → AttributeMap

Build an AttributeMap from toggled attributes dictionary.

Creates an AttributeMap object that defines which attributes nodes can track. The AttributeMap is used by SmartGridNode to manage attribute state (like history, clampable, etc.) during pathfinding.

Parameters:

toggled_attributes – Dictionary mapping attribute names to boolean arrays indicating which voxels have the attribute set. Keys are attribute names (e.g., ‘history’, ‘clampable’).

Returns:

AttributeMap object containing the list of attribute names. Returns empty AttributeMap if toggled_attributes is empty.

routing.core.grid.build_nodes(attribute_map: AttributeMap, width: int, height: int, depth: int, matrix: list[list[list[int]]] | ndarray | None = None, grid_id: int = 0) → list[list[list[SmartGridNode]]]

Build a 3D grid of SmartGridNode objects.

Creates a 3D array of nodes where each node represents a voxel in the grid. Nodes are walkable if their weight > 0, otherwise they are obstacles (None).

Weight interpretation: - Values <= 0: Obstacle (node is None) - Values > 0: Walkable cell with that weight value - Higher weights indicate higher traversal cost

Parameters:

• attribute_map – AttributeMap defining which attributes nodes can track.

• width – Grid width in voxels (x dimension).

• height – Grid height in voxels (y dimension).

• depth – Grid depth in voxels (z dimension).

• matrix – Optional 3D weight matrix. If None, all nodes have weight=1. Shape must be (width, height, depth).

• grid_id – Identifier for this grid (used in multi-grid scenarios). Defaults to 0.

Returns:

3D nested list structure [x][y][z] containing SmartGridNode objects for walkable cells, or None for obstacles.