routing.pathfinding.finder.finder

The finders: one compiled best-first search over (cell, heading) states, its pricers, its target distance.

class routing.pathfinding.finder.finder.BoundedAttributePricer

Bases: MovePricer

BoundedAttributeRule: a move from a node whose attribute is out of bounds (NaN: no bound) weighs multiplier on the heuristic.

The attribute is read by name on the node, so the pricer works on the stand-ins.

attribute

lower

multiplier

upper

class routing.pathfinding.finder.finder.BoundedLengthPricer

Bases: MovePricer

BoundedCustomLengthRule: entering a cell without the attribute weighs multiplier unless the length spent with it is within bounds (NaN: no bound).

lower

multiplier

upper

class routing.pathfinding.finder.finder.ClampingPricer

Bases: MovePricer

ClampingConstraint: a stretch without a clampable cell longer than clamp_step weighs multiplier on the heuristic.

clamp_step

multiplier

exception routing.pathfinding.finder.finder.ExecutionRunsException

Bases: Exception

The search popped more states than the finder’s run limit.

exception routing.pathfinding.finder.finder.ExecutionTimeException

Bases: Exception

The search took longer than the finder’s time limit.

class routing.pathfinding.finder.finder.Finder

Bases: object

A finder: the best-first search over (cell, heading) states that pathfinding3D’s A* runs, in C.

The finder holds its policy (heuristic, diagonal movement, weighting, limits, and what makes it Dijkstra, Theta* or a greedy best-first) and runs one search per find_path() on the slot arrays it keeps between searches.

One state per cell and arrival heading makes the turn penalty exact: a single node per cell would let the cheapest arrival own the cell and misprice every later turn. Without turn penalty the search degenerates to one state per cell. The states live in slot arrays owned by the search — no node object is created — and the cells only keep what the next search reads after cleanup: cheapest_pushed (the dominance bound of their states) and h (their distance to the target). A state costing more than the cheapest cost pushed on its cell plus the turn penalty can do nothing the cheaper state cannot and is never pushed.

Costs are those the replay of a found path prices (SmartGridInterface.calc_path_cost), bit for bit: g, h and f are stored as floats like pathfinding3D’s nodes, the heading and straight length of a state are those the grid would have derived, the rules price each move in their order — natively for the rules the grid resolves, through the rule’s own methods on stand-in nodes otherwise.

With shortcuts the search is Theta*: one state per cell, and each neighbour is also relaxed straight from the state’s parent when the segment between them is clear, the cheaper of the two winning. A segment is one move whose direction is the reduced integer vector of the segment, priced on the mean weight of the cells it crosses and on the rules like any move.

The search ends on the first target popped. A single target is the ordinary case; a goal set (goals) makes any of its cells a target, and the heuristic becomes the index distance to the nearest goal, the priority factor left aside — the semantics of the goal-set search of the Python finders. Targets are served as the cell itself, whatever the heading they are entered with.

alternatives

clear_goals() → None

Disarm the goal-set search, back to the single target.

diagonal_movement

find_path(start: SmartGridNode, end: SmartGridNode, grid: object) → tuple

Find a path from start to end, or to any goal of the set, on grid.

grid is what the search walks, a SmartGrid or a SmartWorld: it opens the search states of its grids (search_states()) and names its turn_penalty. Returns the path as cells and the number of states popped; raises when the run or time limit is hit.

goal_nodes

heuristic_weight

largest_voxel_size

max_runs

multi_goal_capable

Whether the finder can search toward a set of goals (it can).

runs

set_goals(goal_nodes: list) → None

Arm the search with a set of goal nodes: any of them ends it.

shortcuts

time_limit

weighted

class routing.pathfinding.finder.finder.GravityPricer

Bases: MovePricer

GravityRule: no climbing, and a slope from the source within the rule’s bounds (NaN: no bound).

lower

multiplier

upper

class routing.pathfinding.finder.finder.GridSearchState

Bases: object

What one search keeps per grid: the grid and its pricers, the slot block of each touched cell, the cells touched.

grid

pricers

touched

class routing.pathfinding.finder.finder.Move

Bases: object

A move the search is about to price: the state it leaves and the cell it enters, as the pricers read them.

lengths points at the state’s attribute lengths, among them the head of each trail of values the path has held, which visited unrolls; node and neighbor_node stand in for the state and the entered state when a pricer works through the rule’s own methods (PythonPricer).

A move is a step for the searches that check every cell, and a segment for the ones that work on a line: crossed then holds the cells that line goes through, in order, from cell (excluded) to neighbor (last of the list). It is None for a step, whose only cell is neighbor.

cell

crossed

custom_heading

heading

neighbor

neighbor_node

node

straight

straight_length

visited

class routing.pathfinding.finder.finder.MovePricer

Bases: object

How one design rule prices a move for the compiled search: the cost it adds, the factor it puts on the heuristic.

The two questions of DesignRule.compute_cost and compute_heuristic, answered through C calls; a pricer overrides the one its rule answers. One subclass per rule the search prices natively, PythonPricer for the others; each rule builds its own (DesignRule.move_pricer). The same answers reach Python through compute_cost() and compute_heuristic(), on two nodes: a native rule’s own methods call them, so its pricing is written once.

compute_cost(node: SmartGridNode, neighbor: SmartGridNode, vector: tuple | None) → float

Price the step from node to neighbor along vector, read off the two nodes.

compute_heuristic(node: SmartGridNode, neighbor: SmartGridNode, vector: tuple | None) → float

Weigh the heuristic of the step from node to neighbor along vector, read off the two nodes.

stands_in

class routing.pathfinding.finder.finder.PoolingPricer

Bases: MovePricer

PoolingRule: a move taking on again a component of the harness the route has left costs penalty.

A cell names, through its label, the components whose corridors cover it (CorridorLabels, laid out as sorted runs: offsets bounds the run of a label in components). Keeping a component held is travelling along the harness and costs nothing; taking on a component never held is a bridge, free; taking on again a component the route has left is the loop the rule exists for.

compute_cost(node: SmartGridNode, neighbor: SmartGridNode, vector: tuple | None) → float

Price the step from node to neighbor, the labels the path has held read off node and its parents.

A search state keeps those labels as a chain; a node path keeps its parents, from which the chain is rebuilt, the search’s stand-ins reading theirs off the search.

penalty

class routing.pathfinding.finder.finder.PythonPricer

Bases: MovePricer

A rule the search does not price natively: its own compute_cost and compute_heuristic, called on the stand-in nodes.

The two methods are handed over as callables (node, neighbor, vector) -> float: the search prices through them and knows no rule.

class routing.pathfinding.finder.finder.SearchStateNode

Bases: SmartGridNode

A cell entered along one direction, standing in for a state of the search.

The search keeps its states in slot arrays; a rule it cannot price natively receives one of these instead: the cell’s geometry, weight, walkability and attributes, the state’s arrival direction, straight length, lengths and cost, and a pointer back to the cell. Its parent is the state’s parent, stood in for on demand: the path behind a state is read off the search, one stand-in per node read.

adopt(cell: SmartGridNode, direction: Index3D) → None

Stand in for the state (cell, direction): take the cell’s geometry, weight, walkability and attributes.

cell

parent

The stand-in of the state’s parent, read off the search when asked; None at the start of the path.

class routing.pathfinding.finder.finder.StraightLengthPricer

Bases: MovePricer

StraightLengthRule: a turn before min_value straight cells weighs multiplier on the heuristic.

min_value

multiplier

class routing.pathfinding.finder.finder.TurnPricer

Bases: MovePricer

TurnPenalizer: a move that leaves the state’s heading costs penalty.

penalty

routing.pathfinding.finder.finder.within_bounds(lower: cython.double, upper: cython.double, value: cython.double)

Whether lower <= value < upper, a NaN bound standing for none: the test of BoundedAttributeRule.