tessl/pypi-pathfinding
Path finding algorithms for Python including A*, Dijkstra, Best-First, Bi-directional A*, Breadth First Search, IDA*, and Minimum Spanning Tree
—
Pending
core-structures.mddocs/
Core Data Structures
Essential data structures that form the foundation of the pathfinding library. These include Grid for 2D pathfinding, Graph for network pathfinding, specialized Node classes, and World for managing multiple connected environments.
Capabilities
Grid Class
2D grid structure for pathfinding with support for obstacles, weighted nodes, and various movement policies. Grids can be created from matrices or dimensions and support wraparound borders.
class Grid:
def __init__(self, width=0, height=0, matrix=None, grid_id=None, inverse=False):
"""
Create a new grid for pathfinding.
Parameters:
- width (int): Grid width in cells
- height (int): Grid height in cells
- matrix (List[List[int]]): Optional 2D matrix (>0=walkable, ≤0=obstacle by default)
- grid_id (int): Optional identifier for multi-grid worlds
- inverse (bool): When True, ≤0 values are walkable and >0 values are obstacles
"""
def node(self, x, y):
"""
Get node at coordinates.
Parameters:
- x (int): X coordinate
- y (int): Y coordinate
Returns:
GridNode: Node at specified position
"""
def inside(self, x, y):
"""
Check if coordinates are inside grid bounds.
Parameters:
- x (int): X coordinate
- y (int): Y coordinate
Returns:
bool: True if coordinates are inside grid
"""
def walkable(self, x, y):
"""
Check if position is walkable.
Parameters:
- x (int): X coordinate
- y (int): Y coordinate
Returns:
bool: True if position can be traversed
"""
def neighbors(self, node, diagonal_movement=DiagonalMovement.never):
"""
Get neighboring nodes.
Parameters:
- node (GridNode): Center node
- diagonal_movement (int): Diagonal movement policy
Returns:
List[GridNode]: List of accessible neighboring nodes
"""
def cleanup(self):
"""Reset all nodes for reuse in pathfinding."""
def update_node(self, x, y, *, weight=None, walkable=None):
"""
Update node properties.
Parameters:
- x (int): X coordinate
- y (int): Y coordinate
- weight (float): New weight value
- walkable (bool): New walkable state
"""
def calc_cost(self, node_a, node_b, weighted=False):
"""
Calculate movement cost between adjacent nodes.
Parameters:
- node_a (GridNode): Start node
- node_b (GridNode): End node
- weighted (bool): Whether to include node weights
Returns:
float: Movement cost
"""
def set_passable_left_right_border(self):
"""Enable horizontal wraparound borders."""
def set_passable_up_down_border(self):
"""Enable vertical wraparound borders."""
@property
def min_weight(self):
"""
Get minimum weight value in the grid.
Returns:
float: Minimum weight among all walkable nodes
"""
def grid_str(self, path=None, start=None, end=None, border=True,
start_chr='s', end_chr='e', path_chr='x', empty_chr=' ',
block_chr='#', show_weight=False):
"""
Generate ASCII representation of grid.
Parameters:
- path (List[GridNode]): Path to highlight
- start (GridNode): Start node to mark
- end (GridNode): End node to mark
- border (bool): Create border around grid
- empty_chr (str): Character for walkable cells
- block_chr (str): Character for obstacles
- start_chr (str): Character for start position
- end_chr (str): Character for end position
- path_chr (str): Character for path cells
- show_weight (bool): Show node weights instead of symbols
Returns:
str: ASCII grid representation
"""Graph Class
Graph structure for network-based pathfinding with support for weighted edges and bi-directional connections. Graphs are defined by edges and automatically generate nodes.
class Graph:
def __init__(self, edges=None, nodes=None, bi_directional=False):
"""
Create a new graph for pathfinding.
Parameters:
- edges (List): Edge definitions [from_node, to_node, cost]
- nodes (Dict): Pre-existing nodes dictionary
- bi_directional (bool): Whether edges work in both directions
"""
def node(self, node_id):
"""
Get node by identifier.
Parameters:
- node_id: Node identifier (any hashable type)
Returns:
GraphNode: Node with specified identifier
"""
def neighbors(self, node, **kwargs):
"""
Get neighboring nodes connected by edges.
Parameters:
- node (GraphNode): Source node
Returns:
List[GraphNode]: List of connected neighboring nodes
"""
def calc_cost(self, node_a, node_b, _weighted=False):
"""
Calculate edge cost between connected nodes.
Parameters:
- node_a (GraphNode): Start node
- node_b (GraphNode): End node
- _weighted (bool): Ignored (for compatibility)
Returns:
float: Edge cost or infinity if not connected
"""
def cleanup(self):
"""Reset all nodes for reuse in pathfinding."""
def generate_nodes(self):
"""Generate nodes from edge definitions."""Node Classes
Specialized node classes that store pathfinding state and position information for different data structures.
@dataclasses.dataclass
class Node:
"""Base node class with pathfinding attributes."""
h: float = 0.0 # Heuristic cost to goal
g: float = 0.0 # Cost from start
f: float = 0.0 # Total cost (g + h)
opened: int = 0 # Open list status
closed: bool = False # Closed list status
parent: 'Node' = None # Parent for backtracking
retain_count: int = 0 # Recursion tracking
tested: bool = False # Used by IDA* and JPS
def cleanup(self):
"""Reset all calculated values."""
@dataclasses.dataclass
class GridNode(Node):
def __init__(self, x=0, y=0):
"""
Create a grid node.
Parameters:
- x (int): X coordinate
- y (int): Y coordinate
"""
x: int = 0 # X coordinate
y: int = 0 # Y coordinate
walkable: bool = True # Whether node can be traversed
weight: float = 0.0 # Weight for weighted algorithms
grid_id: int = None # Grid identifier for multi-grid worlds
connections: list = None # Connections to other nodes
def connect(self, other_node):
"""
Connect to another node.
Parameters:
- other_node (GridNode): Node to connect to
"""
@dataclasses.dataclass
class GraphNode(Node):
def __init__(self, node_id):
"""
Create a graph node.
Parameters:
- node_id: Identifier for the node (any hashable type)
"""
node_id: any # Node identifierWorld Class
Multi-grid environment manager for pathfinding across connected grids with different properties. Enables complex scenarios like multi-level buildings or connected game areas.
class World:
def __init__(self, grids):
"""
Create a world with multiple connected grids.
Parameters:
- grids (Dict[int, Grid]): Dictionary of grids by ID
"""
def cleanup(self):
"""Clean all grids in the world."""
def neighbors(self, node, diagonal_movement):
"""
Get neighbors across grids.
Parameters:
- node (Node): Source node
- diagonal_movement (int): Diagonal movement policy
Returns:
List[Node]: Neighbors including cross-grid connections
"""
def calc_cost(self, node_a, node_b, weighted=False):
"""
Calculate cost between nodes, including cross-grid costs.
Parameters:
- node_a (Node): Start node
- node_b (Node): End node
- weighted (bool): Whether to include node weights
Returns:
float: Movement cost
"""Diagonal Movement Policies
Configuration constants that control how pathfinding algorithms handle diagonal movement in grids.
class DiagonalMovement:
"""Diagonal movement policy constants."""
always = 1 # Allow diagonal movement always
never = 2 # Never allow diagonal movement
if_at_most_one_obstacle = 3 # Allow diagonal if ≤1 obstacle
only_when_no_obstacle = 4 # Allow diagonal only when no obstaclesUsage Examples
Creating and Using a Grid
from pathfinding.core.grid import Grid
from pathfinding.core.diagonal_movement import DiagonalMovement
# Create grid from matrix
matrix = [
[1, 1, 1, 0],
[1, 0, 1, 1],
[1, 1, 0, 1],
[0, 1, 1, 1]
]
grid = Grid(matrix=matrix)
# Access nodes
start = grid.node(0, 0)
end = grid.node(3, 3)
# Check properties
print(f"Start walkable: {start.walkable}")
print(f"Grid contains (2,2): {grid.inside(2, 2)}")
# Get neighbors with diagonal movement
neighbors = grid.neighbors(start, DiagonalMovement.always)
print(f"Start has {len(neighbors)} neighbors")
# Update node properties
grid.update_node(1, 1, walkable=True, weight=2.5)Creating and Using a Graph
from pathfinding.core.graph import Graph
# Define weighted edges
edges = [
['A', 'B', 4],
['A', 'C', 2],
['B', 'C', 1],
['B', 'D', 5],
['C', 'D', 8],
['C', 'E', 10],
['D', 'E', 2]
]
# Create bi-directional graph
graph = Graph(edges=edges, bi_directional=True)
# Access nodes
node_a = graph.node('A')
node_e = graph.node('E')
# Get neighbors
neighbors = graph.neighbors(node_a)
neighbor_ids = [n.node_id for n in neighbors]
print(f"Node A connects to: {neighbor_ids}")
# Calculate edge costs
cost = graph.calc_cost(node_a, graph.node('B'))
print(f"Cost A->B: {cost}")Multi-Grid World
from pathfinding.core.grid import Grid
from pathfinding.core.world import World
# Create multiple grids
ground_floor = Grid(width=10, height=10, grid_id=0)
second_floor = Grid(width=8, height=8, grid_id=1)
# Create world
world = World(grids={0: ground_floor, 1: second_floor})
# Nodes can connect between grids via their connections attribute
stair_bottom = ground_floor.node(5, 5)
stair_top = second_floor.node(1, 1)
stair_bottom.connect(stair_top)
# World can find neighbors across grids
neighbors = world.neighbors(stair_bottom, DiagonalMovement.never)Install with Tessl CLI
npx tessl i tessl/pypi-pathfinding