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
algorithms.mddocs/
Pathfinding Algorithms
Seven different pathfinding algorithms providing optimal paths for various scenarios and performance requirements. All algorithms inherit from the base Finder class and implement the same interface for easy switching between strategies.
Capabilities
A* Algorithm
A* pathfinding using heuristics to guide search toward the goal. Provides optimal paths when using admissible heuristics and supports weighted nodes and various diagonal movement policies.
class AStarFinder:
def __init__(self, heuristic=None, weight=1, diagonal_movement=DiagonalMovement.never,
time_limit=TIME_LIMIT, max_runs=MAX_RUNS):
"""
Create A* pathfinder.
Parameters:
- heuristic (function): Heuristic function (defaults to manhattan/octile based on diagonal_movement)
- weight (int): Edge weight multiplier for weighted A*
- diagonal_movement (int): Diagonal movement policy
- time_limit (float): Maximum execution time in seconds
- max_runs (int): Maximum algorithm iterations
"""
def find_path(self, start, end, grid):
"""
Find optimal path using A* algorithm.
Parameters:
- start (Node): Starting node
- end (Node): Target node
- grid (Grid|Graph): Search space
Returns:
Tuple[List[Node], int]: (path_nodes, runs_count)
"""Usage Example
from pathfinding.core.grid import Grid
from pathfinding.core.diagonal_movement import DiagonalMovement
from pathfinding.finder.a_star import AStarFinder
from pathfinding.core.heuristic import euclidean
# Create grid and finder
grid = Grid(matrix=[[1,1,1],[1,0,1],[1,1,1]])
finder = AStarFinder(
heuristic=euclidean,
diagonal_movement=DiagonalMovement.always,
weight=2 # Weighted A* for faster, suboptimal paths
)
# Find path
path, runs = finder.find_path(grid.node(0,0), grid.node(2,2), grid)
print(f"Path length: {len(path)}, Runs: {runs}")Dijkstra Algorithm
Dijkstra's algorithm for finding shortest paths by exploring nodes in order of distance from start. Guarantees optimal paths and works well with weighted edges but doesn't use heuristics.
class DijkstraFinder:
def __init__(self, weight=1, diagonal_movement=DiagonalMovement.never,
time_limit=TIME_LIMIT, max_runs=MAX_RUNS):
"""
Create Dijkstra pathfinder.
Parameters:
- weight (int): Edge weight multiplier
- diagonal_movement (int): Diagonal movement policy
- time_limit (float): Maximum execution time in seconds
- max_runs (int): Maximum algorithm iterations
"""
def find_path(self, start, end, grid):
"""
Find optimal path using Dijkstra's algorithm.
Parameters:
- start (Node): Starting node
- end (Node): Target node
- grid (Grid|Graph): Search space
Returns:
Tuple[List[Node], int]: (path_nodes, runs_count)
"""Usage Example
from pathfinding.core.graph import Graph
from pathfinding.finder.dijkstra import DijkstraFinder
# Create weighted graph
edges = [
[1, 2, 10], [1, 3, 15], [2, 3, 12],
[2, 4, 15], [3, 4, 10]
]
graph = Graph(edges=edges, bi_directional=True)
# Find shortest path
finder = DijkstraFinder()
path, runs = finder.find_path(graph.node(1), graph.node(4), graph)
# Extract path
node_path = [node.node_id for node in path]
print(f"Shortest path: {node_path}")Best-First Search
Best-first search using only heuristic values to guide search. Fast but doesn't guarantee optimal paths. Good for scenarios where speed is more important than optimality.
class BestFirst:
def __init__(self, heuristic=None, weight=1, diagonal_movement=DiagonalMovement.never,
time_limit=TIME_LIMIT, max_runs=MAX_RUNS):
"""
Create Best-First pathfinder.
Parameters:
- heuristic (function): Heuristic function (defaults to manhattan/octile)
- weight (int): Edge weight multiplier
- diagonal_movement (int): Diagonal movement policy
- time_limit (float): Maximum execution time in seconds
- max_runs (int): Maximum algorithm iterations
"""
def find_path(self, start, end, grid):
"""
Find path using Best-First search.
Parameters:
- start (Node): Starting node
- end (Node): Target node
- grid (Grid|Graph): Search space
Returns:
Tuple[List[Node], int]: (path_nodes, runs_count)
"""Bi-directional A*
Bi-directional A* searching simultaneously from start and end until paths meet. More efficient for long paths but doesn't support weighted nodes.
class BiAStarFinder:
def __init__(self, heuristic=None, weight=1, diagonal_movement=DiagonalMovement.never,
time_limit=TIME_LIMIT, max_runs=MAX_RUNS):
"""
Create Bi-directional A* pathfinder.
Parameters:
- heuristic (function): Heuristic function (defaults to manhattan/octile)
- weight (int): Edge weight multiplier
- diagonal_movement (int): Diagonal movement policy
- time_limit (float): Maximum execution time in seconds
- max_runs (int): Maximum algorithm iterations
"""
def find_path(self, start, end, grid):
"""
Find path using bi-directional A*.
Parameters:
- start (Node): Starting node
- end (Node): Target node
- grid (Grid|Graph): Search space
Returns:
Tuple[List[Node], int]: (path_nodes, runs_count)
"""Breadth-First Search
Breadth-first search exploring nodes level by level from the start. Guarantees shortest path in unweighted graphs but can be slow for large spaces.
class BreadthFirstFinder:
def __init__(self, heuristic=None, weight=1, diagonal_movement=DiagonalMovement.never,
time_limit=TIME_LIMIT, max_runs=MAX_RUNS):
"""
Create Breadth-First pathfinder.
Parameters:
- heuristic (function): Ignored (BFS doesn't use heuristics)
- weight (int): Edge weight multiplier
- diagonal_movement (int): Diagonal movement policy
- time_limit (float): Maximum execution time in seconds
- max_runs (int): Maximum algorithm iterations
"""
def find_path(self, start, end, grid):
"""
Find path using Breadth-First search.
Parameters:
- start (Node): Starting node
- end (Node): Target node
- grid (Grid|Graph): Search space
Returns:
Tuple[List[Node], int]: (path_nodes, runs_count)
"""IDA* (Iterative Deepening A*)
Memory-efficient iterative deepening A* using successive depth limits. Provides optimal paths with minimal memory usage but can be slower than regular A*.
class IDAStarFinder:
def __init__(self, heuristic=None, weight=1, diagonal_movement=DiagonalMovement.never,
time_limit=TIME_LIMIT, max_runs=MAX_RUNS, track_recursion=True):
"""
Create IDA* pathfinder.
Parameters:
- heuristic (function): Heuristic function (defaults to manhattan/octile)
- weight (int): Edge weight multiplier
- diagonal_movement (int): Diagonal movement policy
- time_limit (float): Maximum execution time in seconds
- max_runs (int): Maximum algorithm iterations
- track_recursion (bool): Track recursion for visualization
"""
@property
def nodes_visited(self) -> int:
"""Statistics counter for nodes visited during search."""
def find_path(self, start, end, grid):
"""
Find path using IDA* algorithm.
Parameters:
- start (Node): Starting node
- end (Node): Target node
- grid (Grid|Graph): Search space
Returns:
Tuple[List[Node], int]: (path_nodes, runs_count)
"""Usage Example
from pathfinding.finder.ida_star import IDAStarFinder
# Memory-efficient pathfinding for large grids
finder = IDAStarFinder(track_recursion=False) # Disable tracking for performance
path, runs = finder.find_path(start, end, large_grid)
print(f"Nodes visited: {finder.nodes_visited}")Minimum Spanning Tree
Pathfinding via minimum spanning tree generation. Useful for finding paths in graphs where you need to connect all nodes with minimum total cost.
class MinimumSpanningTree:
def __init__(self, *args, **kwargs):
"""Create Minimum Spanning Tree pathfinder."""
def find_path(self, start, end, grid):
"""
Find path via minimum spanning tree.
Parameters:
- start (Node): Starting node
- end (Node): Target node
- grid (Grid|Graph): Search space
Returns:
Tuple[List[Node], int]: (path_nodes, runs_count)
"""
def tree(self, grid, start):
"""
Generate complete minimum spanning tree.
Parameters:
- grid (Grid|Graph): Search space
- start (Node): Root node for tree
Returns:
List[Node]: All nodes in spanning tree order
"""
def itertree(self, grid, start):
"""
Generator for spanning tree nodes.
Parameters:
- grid (Grid|Graph): Search space
- start (Node): Root node for tree
Yields:
Node: Next node in spanning tree
"""Base Finder Class
All pathfinding algorithms inherit from the base Finder class, providing common functionality and interface consistency.
class Finder:
def __init__(self, heuristic=None, weight=1, diagonal_movement=DiagonalMovement.never,
weighted=True, time_limit=TIME_LIMIT, max_runs=MAX_RUNS):
"""
Base pathfinder class.
Parameters:
- heuristic (function): Heuristic function
- weight (int): Edge weight multiplier
- diagonal_movement (int): Diagonal movement policy
- weighted (bool): Whether algorithm supports weighted nodes
- time_limit (float): Maximum execution time in seconds
- max_runs (int): Maximum algorithm iterations
"""
def apply_heuristic(self, node_a, node_b, heuristic=None, graph=None):
"""
Calculate heuristic distance between nodes.
Parameters:
- node_a (Node): Start node
- node_b (Node): End node
- heuristic (function): Heuristic function to use
- graph (Grid|Graph): Search space context
Returns:
float: Heuristic distance
"""
def find_neighbors(self, grid, node, diagonal_movement=None):
"""
Find neighboring nodes.
Parameters:
- grid (Grid|Graph): Search space
- node (Node): Center node
- diagonal_movement (int): Diagonal movement policy
Returns:
List[Node]: Neighboring nodes
"""
def keep_running(self):
"""
Check if algorithm should continue running.
Returns:
bool: True if within time and iteration limits
"""Exceptions
class ExecutionTimeException(Exception):
"""Raised when pathfinding exceeds time limit."""
class ExecutionRunsException(Exception):
"""Raised when pathfinding exceeds maximum runs."""Constants
TIME_LIMIT = 10.0 # Default maximum execution time in seconds
MAX_RUNS = 100000 # Default maximum algorithm iterationsAlgorithm Selection Guide
Choose A* when:
- You need optimal paths
- You have a good heuristic function
- Memory usage is acceptable
- Grid/graph has moderate size
Choose Dijkstra when:
- You need guaranteed optimal paths
- No good heuristic is available
- Graph has weighted edges
- You need to find shortest paths to multiple targets
Choose Best-First when:
- Speed is more important than optimality
- You have a good heuristic
- Approximate solutions are acceptable
Choose Bi-directional A* when:
- Paths are typically long
- You need optimal paths
- Graph/grid is large
- Start and end are far apart
Choose Breadth-First when:
- Graph is unweighted
- You need shortest path (by number of steps)
- Graph is relatively small
Choose IDA* when:
- Memory is very limited
- You need optimal paths
- Grid/graph is large
- You can tolerate slower execution
Choose MSP when:
- You need to connect all nodes
- Total connection cost matters more than individual paths
- Working with network design problems
Usage Patterns
Algorithm Comparison
from pathfinding.core.grid import Grid
from pathfinding.finder.a_star import AStarFinder
from pathfinding.finder.dijkstra import DijkstraFinder
from pathfinding.finder.breadth_first import BreadthFirstFinder
grid = Grid(matrix=large_maze)
start = grid.node(0, 0)
end = grid.node(99, 99)
algorithms = [
("A*", AStarFinder()),
("Dijkstra", DijkstraFinder()),
("BFS", BreadthFirstFinder())
]
for name, finder in algorithms:
grid.cleanup() # Important: clean between runs
path, runs = finder.find_path(start, end, grid)
print(f"{name}: path length {len(path)}, runs {runs}")Performance Monitoring
import time
from pathfinding.finder.a_star import AStarFinder
# Set time and iteration limits
finder = AStarFinder(time_limit=5.0, max_runs=10000)
start_time = time.time()
try:
path, runs = finder.find_path(start, end, grid)
elapsed = time.time() - start_time
print(f"Found path in {elapsed:.2f}s with {runs} runs")
except ExecutionTimeException:
print("Pathfinding timed out")
except ExecutionRunsException:
print("Pathfinding exceeded maximum runs")Install with Tessl CLI
npx tessl i tessl/pypi-pathfinding