or run

npx @tessl/cli init
Log in

Version

Tile

Overview

Evals

Files

docs

algorithms.mdcore-structures.mdindex.mdutilities.md
tile.json

tessl/pypi-pathfinding

Path finding algorithms for Python including A*, Dijkstra, Best-First, Bi-directional A*, Breadth First Search, IDA*, and Minimum Spanning Tree

Workspace
tessl
Visibility
Public
Created
Last updated
Describes
pypipkg:pypi/pathfinding@1.0.x

To install, run

npx @tessl/cli install tessl/pypi-pathfinding@1.0.0

index.mddocs/

Pathfinding

A comprehensive Python library implementing 7 different pathfinding algorithms for 2D grids and graphs. Pathfinding provides optimal path calculation with support for weighted nodes, diagonal movement policies, and multiple data structures including grids, graphs, and multi-level worlds.

Package Information

  • Package Name: pathfinding
  • Language: Python
  • Installation: pip install pathfinding

Core Imports

import pathfinding

Common imports for grid-based pathfinding:

from pathfinding.core.grid import Grid
from pathfinding.core.diagonal_movement import DiagonalMovement
from pathfinding.finder.a_star import AStarFinder

Common imports for graph-based pathfinding:

from pathfinding.core.graph import Graph
from pathfinding.finder.dijkstra import DijkstraFinder

Additional imports for advanced features:

from pathfinding.core.world import World
from pathfinding.core.heuristic import manhattan, euclidean, octile
from pathfinding.core.util import backtrace, smoothen_path
from pathfinding.finder.msp import MinimumSpanningTree

Basic Usage

Grid-based Pathfinding

from pathfinding.core.grid import Grid
from pathfinding.core.diagonal_movement import DiagonalMovement
from pathfinding.finder.a_star import AStarFinder

# Create grid from matrix (positive values=walkable, 0 or negative=obstacle)
matrix = [
    [1, 1, 1],
    [1, 0, 1], 
    [1, 1, 1]
]
grid = Grid(matrix=matrix)

# Get start and end nodes
start = grid.node(0, 0)
end = grid.node(2, 2)

# Create finder and find path
finder = AStarFinder(diagonal_movement=DiagonalMovement.always)
path, runs = finder.find_path(start, end, grid)

# Extract coordinates from path
coords = [(node.x, node.y) for node in path]
print(f"Path: {coords}")
print(f"Algorithm runs: {runs}")

Graph-based Pathfinding

from pathfinding.core.graph import Graph
from pathfinding.finder.dijkstra import DijkstraFinder

# Define edges: [from_node, to_node, cost]
edges = [
    [1, 2, 7],
    [1, 3, 9], 
    [2, 3, 10],
    [2, 4, 15],
    [3, 4, 11]
]

# Create bi-directional graph
graph = Graph(edges=edges, bi_directional=True)

# Find path between nodes
finder = DijkstraFinder()
path, runs = finder.find_path(graph.node(1), graph.node(4), graph)

# Extract node IDs from path
node_ids = [node.node_id for node in path]
print(f"Path: {node_ids}")

Grid Cleanup (Important)

# Always cleanup between pathfinding runs on the same grid
grid.cleanup()
path, runs = finder.find_path(start, end, grid)

Architecture

The pathfinding library follows a modular design with clear separation of concerns:

  • Core Module: Provides fundamental data structures (Grid, Graph, Node classes) and utilities (heuristics, path processing)
  • Finder Module: Implements pathfinding algorithms with a common interface inheriting from the base Finder class
  • Node Hierarchy: Specialized node types (GridNode, GraphNode) extend the base Node class with algorithm-specific attributes
  • Strategy Pattern: All finders implement the same interface, allowing easy algorithm switching

This design enables flexible pathfinding across different data structures while maintaining consistent APIs and supporting advanced features like weighted paths, diagonal movement policies, and multi-grid worlds.

Capabilities

Core Data Structures

Essential data structures including Grid for 2D pathfinding, Graph for network pathfinding, specialized Node classes, and World for multi-level environments. These form the foundation for all pathfinding operations.

class Grid:
    def __init__(self, width=0, height=0, matrix=None, grid_id=None, inverse=False): ...
    def node(self, x, y): ...
    def neighbors(self, node, diagonal_movement=DiagonalMovement.never): ...
    def cleanup(self): ...
    def update_node(self, x, y, *, weight=None, walkable=None): ...

class Graph:
    def __init__(self, edges=None, nodes=None, bi_directional=False): ...
    def node(self, node_id): ...
    def neighbors(self, node, **kwargs): ...
    def cleanup(self): ...

class World:
    def __init__(self, grids): ...
    def neighbors(self, node, diagonal_movement): ...
    def cleanup(self): ...

class GridNode:
    def __init__(self, x=0, y=0): ...
    def connect(self, other_node): ...

class GraphNode:
    def __init__(self, node_id): ...

Core Data Structures

Pathfinding Algorithms

Seven different pathfinding algorithms including A*, Dijkstra, Best-First, Bi-directional A*, Breadth-First Search, IDA*, and Minimum Spanning Tree. Each algorithm provides optimal paths for different scenarios and performance requirements.

class AStarFinder:
    def __init__(self, heuristic=None, weight=1, diagonal_movement=DiagonalMovement.never, 
                 time_limit=TIME_LIMIT, max_runs=MAX_RUNS): ...
    def find_path(self, start, end, grid): ...

class DijkstraFinder:
    def __init__(self, weight=1, diagonal_movement=DiagonalMovement.never,
                 time_limit=TIME_LIMIT, max_runs=MAX_RUNS): ...
    def find_path(self, start, end, grid): ...

class BreadthFirstFinder:
    def __init__(self, diagonal_movement=DiagonalMovement.never,
                 time_limit=TIME_LIMIT, max_runs=MAX_RUNS): ...
    def find_path(self, start, end, grid): ...

class MinimumSpanningTree:
    def __init__(self, *args, **kwargs): ...
    def find_path(self, start, end, grid): ...
    def tree(self, grid, start): ...

Pathfinding Algorithms

Utilities and Configuration

Utility functions for path processing, heuristic calculations, diagonal movement policies, and advanced path manipulation including smoothing and ray tracing for optimized paths.

class DiagonalMovement:
    always = 1
    never = 2
    if_at_most_one_obstacle = 3
    only_when_no_obstacle = 4

def manhattan(dx, dy): ...
def euclidean(dx, dy): ...
def backtrace(node): ...
def smoothen_path(grid, path, use_raytrace=False): ...

Utilities and Configuration

Types

# Core types used across the library
Coords = Tuple[float, float]

# Return type for all pathfinding operations
PathResult = Tuple[List[Node], int]  # (path, runs)