routing.core.grid

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

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.

build_two_ports_path(solution: Solution) → list[GridPath]

Build a simple straight path between two ports.

Creates a minimal path connecting input and output ports using straight_path. Used as a fallback when pathfinding fails or when ports are very close together.

Parameters:

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

Returns:

List containing a single GridPath with the straight path between ports.

calc_cost(node: SmartGridNode, neighbor: SmartGridNode, weighted: bool = False) → float

Calculate the cost to move from node to neighbor.

Computes the routing cost for moving from node to neighbor, including: 1. Base distance (voxel distance between nodes) 2. Design rule costs (turn penalties, constraints, etc.) 3. Node weight (if weighted=True)

Also updates neighbor.p (priority/heuristic multiplier) based on design rule heuristics for use in pathfinding algorithms.

Parameters:

• node – Current SmartGridNode.

• neighbor – Neighbor SmartGridNode to move to.

• weighted – If True, multiplies distance by neighbor.weight and adds design rule costs. Defaults to False.

Returns:

Total cost to move from node to neighbor.

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

Clean up grid resources after pathfinding.

Resets grid state by calling parent cleanup and clearing processed nodes. This prepares the grid for the next pathfinding operation.

Returns:

None

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_node_neighbors_index(index: tuple[int, int, int], prospect_distance: int = 3, only_walkable: bool = False) → list[tuple[int, int, int]]

Get all neighbor indices within prospect_distance hops from a node.

Performs a breadth-first expansion from the starting index, collecting all nodes within prospect_distance steps. Optionally filters to only walkable nodes.

Parameters:

• index – Starting index (i, j, k) to expand from.

• prospect_distance – Maximum number of hops to expand. Defaults to 3.

• only_walkable – If True, returns only walkable nodes. Defaults to False.

Returns:

List of Index3D tuples representing neighbor indices within prospect_distance hops.

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.

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

Check if grid coordinates are within bounds.

Validates that the given coordinates are within the grid boundaries.

Parameters:

• x – X coordinate (width dimension).

• y – Y coordinate (height dimension).

• z – Z coordinate (depth dimension).

Returns:

True if coordinates are within bounds, False otherwise.

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.

neighbors(node: SmartGridNode, diagonal_movement: int = 2) → list[SmartGridNode]

Get valid neighbors for pathfinding with smart routing features.

Returns neighbors of a node with smart routing processing: 1. Gets all neighbors based on diagonal movement policy 2. If smart mode enabled:

• Updates node attributes (direction, straight length, custom attr lengths)

• Removes neighbors that violate hard constraints (if enabled)

3. Removes forbidden neighbors (blocked edges from k-shortest paths)

Parameters:

• node – SmartGridNode to get neighbors for.

• diagonal_movement – DiagonalMovement enum value. Defaults to never.

Returns:

List of valid SmartGridNode neighbors for pathfinding.

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

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

Returns the SmartGridNode at the specified grid coordinates, 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.

overwrite_weights(weights: ndarray) → None

Overwrite all node weights with new values.

Updates the weight and walkable status of all existing nodes in the grid. Nodes must already exist (not created if missing). Use update() to handle node creation/deletion.

Parameters:

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.

point_in_nodes(point: Point3D) → bool

Check if a 3D point is close enough to a grid node center.

Converts the point to grid coordinates and checks if it’s within 0.05 voxel units of a node center. Used to determine if a point can be considered “on” a node.

Parameters:

point – Point3D object with world coordinates.

Returns:

True if point is within 0.05 voxel units of a node center, False otherwise.

set_smartness(is_smart: bool) → None

Set smartness mode for the grid.

Enables or disables smart routing features like direction tracking, attribute accumulation, and design rule integration. Disabled for algorithms like ThetaStar that use line-of-sight optimization.

Parameters:

is_smart – True to enable smart routing features, False to disable.

Returns:

None

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.

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 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. For each voxel:

• 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

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(width: int, height: int, depth: int, design_rules: list[DesignRule], origin: tuple[float, float, float], voxel_size: float)

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 coordinate conversion, node access, and pathfinding helper methods.

Parameters:

• width – The grid width in voxels (x dimension).

• height – The grid height in voxels (y dimension).

• depth – The grid depth in voxels (z dimension).

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

• voxel_size – The size of each voxel in length units (same unit as origin).

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

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, GridPort]

Build pipe ends by extending ports into the grid.

Extends input and output ports into the grid to create start and end nodes for pathfinding. Sets port positions for design rules and creates GridPort objects with appropriate extension lengths.

Parameters:

solution – Solution object containing input_port, output_port, input_length, and output_length.

Returns:

Tuple of (GridPort, GridPort) for input and output ports extended into the grid.

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

Calculate total cost of path and collect rule feedback.

Computes the total routing cost for a path by: 1. Summing base costs: distance * weight for each edge 2. Adding design rule costs (turn penalties, constraints, etc.) 3. Adding heuristic penalties (500.0) when rules indicate violations 4. Collecting feedback: indices where each rule applied costs/penalties

The cost represents the total “expense” of routing through this path, incorporating distance, weights, and all design rule constraints.

Parameters:

path – List of SmartGridNode objects representing the path.

Returns:

Tuple of (total_cost, rule_feedback) where: - total_cost: Sum of all costs and penalties - rule_feedback: Dictionary mapping rule class names to lists of

node indices where that rule applied costs or penalties

static 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_in_grid(coords: tuple[float, float, float]) → tuple[float, float, float]

Convert global coordinates to grid-local coordinates.

Converts world coordinates to grid-local coordinates (in voxel units) by subtracting origin and dividing by voxel_size.

Parameters:

coords – Tuple of (x, y, z) world coordinates.

Returns:

Tuple of (x, y, z) grid-local coordinates in voxel units.

coord_in_grid_npy(coords: ndarray) → ndarray

Convert global coordinates to grid-local coordinates using numpy arrays.

Converts world coordinates to grid-local coordinates (in voxel units) by subtracting origin and dividing by voxel_size. Vectorized operation for efficiency with numpy arrays.

Parameters:

coords – Array of shape (…, 3) containing (x, y, z) world coordinates.

Returns:

Array of same shape containing grid-local coordinates in voxel units.

coord_to_index(coords: tuple[float, float, float]) → tuple[int, int, int]

Convert global coordinates to grid indices.

Converts world coordinates to discrete grid indices by converting to grid-local coordinates and rounding to nearest integer.

Parameters:

coords – Tuple of (x, y, z) world coordinates.

Returns:

Tuple of (i, j, k) grid indices as integers.

coord_to_index_npy(coords: ndarray) → ndarray

Convert global coordinates to grid indices using numpy arrays.

Converts world coordinates to discrete grid indices by converting to grid-local coordinates and rounding to nearest integer. Vectorized operation for efficiency.

Parameters:

coords – Array of shape (…, 3) containing (x, y, z) world coordinates.

Returns:

Array of same shape containing (i, j, k) grid indices as integers.

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.

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.

index_to_coord(index: tuple[int, int, int]) → tuple[float, float, float]

Convert grid indices to global coordinates.

Converts discrete grid indices to world coordinates by multiplying by voxel_size and adding origin.

Parameters:

index – Tuple of (i, j, k) grid indices.

Returns:

Tuple of (x, y, z) world coordinates.

index_to_coord_npy(index: ndarray) → ndarray

Convert grid indices to global coordinates using numpy arrays.

Converts discrete grid indices to world coordinates by multiplying by voxel_size and adding origin. Vectorized operation for efficiency.

Parameters:

index – Array of shape (…, 3) containing (i, j, k) grid indices.

Returns:

Array of same shape containing (x, y, z) world coordinates.

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

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.

path_to_pipe_path(path: list[SmartGridNode], grid_start: GridPort, 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.

static 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

set_smartness(is_smart: bool) → None

Set smartness mode for the grid.

Abstract method that must be implemented by subclasses. Smartness mode enables advanced routing features like direction tracking, attribute accumulation, and design rule integration. Disabled for algorithms like ThetaStar that use line-of-sight optimization.

Parameters:

is_smart – True to enable smart routing features, False to disable.

Returns:

None

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]

Get grid dimensions.

Returns the grid size in each dimension as a tuple.

Returns:

Tuple of (width, height, depth) in voxels.

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

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

Process found path by updating nodes with direction and parent information.

Processes a path found by pathfinding algorithm by: 1. Cleaning up all nodes in the path 2. Setting direction on the first node from port orientation 3. For each edge, setting parent relationship and updating node attributes:

• Direction (from previous node)

• Straight length (consecutive straight segments)

• Custom attribute lengths (for constraint tracking)

This prepares the path for cost calculation and constraint checking.

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_lengths_dict(toggled_attributes: dict[str, ndarray]) → dict[str, float]

Build a dictionary of length counters for toggled attributes.

Creates a dictionary with entries for each toggled attribute and its corresponding “no_” prefix version. These counters track the length of path segments with or without the attribute set.

Parameters:

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

Returns:

Dictionary with keys for each attribute and “no_{attribute}”, all initialized to 0.0. Returns empty dict 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.