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

Overview

Eval results

Files

Utilities and Configuration

Name: tessl/pypi-pathfinding
Author: tessl

Utility functions for path processing, heuristic calculations, diagonal movement policies, and advanced path manipulation. These tools enhance pathfinding results with smoothing, ray tracing, and various distance calculations.

Capabilities

Heuristic Functions

Distance calculation functions used by pathfinding algorithms to estimate costs between nodes. Different heuristics work better for different movement patterns and grid types.

from pathfinding.core import heuristic

def null(dx, dy):
    """
    Null heuristic that always returns 0.
    Used by Dijkstra's algorithm.
    
    Parameters:
    - dx (float): X distance
    - dy (float): Y distance
    
    Returns:
    float: Always 0
    """

def manhattan(dx, dy):
    """
    Manhattan distance heuristic.
    Good for 4-directional movement (no diagonals).
    
    Parameters:
    - dx (float): X distance
    - dy (float): Y distance
    
    Returns:
    float: |dx| + |dy|
    """

def euclidean(dx, dy):
    """
    Euclidean distance heuristic.
    Good for free movement in any direction.
    
    Parameters:
    - dx (float): X distance  
    - dy (float): Y distance
    
    Returns:
    float: sqrt(dx² + dy²)
    """

def chebyshev(dx, dy):
    """
    Chebyshev distance heuristic.
    Good for 8-directional movement with equal diagonal cost.
    
    Parameters:
    - dx (float): X distance
    - dy (float): Y distance
    
    Returns:
    float: max(|dx|, |dy|)
    """

def octile(dx, dy):
    """
    Octile distance heuristic.
    Good for 8-directional movement with realistic diagonal costs.
    
    Parameters:
    - dx (float): X distance
    - dy (float): Y distance
    
    Returns:
    float: Octile distance accounting for diagonal movement cost
    """

Usage Example

from pathfinding.core.heuristic import euclidean, manhattan, octile
from pathfinding.finder.a_star import AStarFinder
from pathfinding.core.diagonal_movement import DiagonalMovement

# Choose heuristic based on movement type
grid_4way = AStarFinder(heuristic=manhattan, diagonal_movement=DiagonalMovement.never)
grid_8way = AStarFinder(heuristic=octile, diagonal_movement=DiagonalMovement.always)
free_movement = AStarFinder(heuristic=euclidean, diagonal_movement=DiagonalMovement.always)

# Compare heuristic estimates
dx, dy = 3, 4
print(f"Manhattan: {manhattan(dx, dy)}")    # 7
print(f"Euclidean: {euclidean(dx, dy)}")    # 5.0  
print(f"Chebyshev: {chebyshev(dx, dy)}")    # 4
print(f"Octile: {octile(dx, dy)}")          # ~6.24

Path Processing Functions

Functions for reconstructing and manipulating paths returned by pathfinding algorithms. These enable path optimization and format conversion.

from pathfinding.core.util import backtrace, bi_backtrace

def backtrace(node):
    """
    Reconstruct path by following parent links from end node.
    
    Parameters:
    - node (Node): End node with parent chain
    
    Returns:
    List[Node]: Path from start to end node
    """

def bi_backtrace(node_a, node_b):
    """
    Reconstruct path for bi-directional search.
    Combines paths from both search directions.
    
    Parameters:
    - node_a (Node): Meeting point from start search
    - node_b (Node): Meeting point from end search
    
    Returns:
    List[Node]: Complete path from original start to end
    """

Path Optimization Functions

Advanced path manipulation for creating smoother, more natural-looking paths by removing unnecessary waypoints and applying line-of-sight optimizations.

from pathfinding.core.util import smoothen_path, expand_path

def smoothen_path(grid, path, use_raytrace=False):
    """
    Smooth path by removing unnecessary waypoints.
    Uses line-of-sight checks to create more direct paths.
    
    Parameters:
    - grid (Grid): Grid for line-of-sight checking
    - path (List[Coords]): Path as coordinate list
    - use_raytrace (bool): Use raytrace vs bresenham for line-of-sight
    
    Returns:
    List[Coords]: Smoothed path with fewer waypoints
    """

def expand_path(path):
    """
    Interpolate compressed path to include all intermediate points.
    
    Parameters:
    - path (List[Coords]): Compressed path coordinates
    
    Returns:
    List[Coords]: Expanded path with all intermediate points
    """

Line Algorithm Functions

Geometric algorithms for line-of-sight calculations and path interpolation between points.

from pathfinding.core.util import raytrace, bresenham

def raytrace(coords_a, coords_b):
    """
    Ray-casting line algorithm for line-of-sight calculations.
    
    Parameters:
    - coords_a (Coords): Start coordinates
    - coords_b (Coords): End coordinates
    
    Returns:
    List[Coords]: Points along line from A to B
    """

def bresenham(coords_a, coords_b):
    """
    Bresenham line algorithm for integer grid line drawing.
    
    Parameters:
    - coords_a (Coords): Start coordinates
    - coords_b (Coords): End coordinates
    
    Returns:
    List[Coords]: Grid points along line from A to B
    """

Usage Example

from pathfinding.core.util import smoothen_path, expand_path, raytrace
from pathfinding.core.grid import Grid
from pathfinding.finder.a_star import AStarFinder

# Find initial path
grid = Grid(matrix=maze_matrix)
finder = AStarFinder()
path, runs = finder.find_path(grid.node(0,0), grid.node(10,10), grid)

# Convert to coordinates
coords = [(node.x, node.y) for node in path]

# Smooth the path  
smooth_coords = smoothen_path(grid, coords, use_raytrace=True)
print(f"Original path: {len(coords)} points")
print(f"Smoothed path: {len(smooth_coords)} points")

# Check line of sight between two points
line_points = raytrace((0, 0), (5, 3))
print(f"Line passes through: {line_points}")

Module Exports and Import Patterns

The pathfinding library exposes its API through structured module exports:

# Main package exports
pathfinding.__all__ = ['core', 'finder']

# Core module exports  
pathfinding.core.__all__ = ['diagonal_movement', 'graph', 'grid', 'heuristic', 'node', 'util']

# Finder module exports
pathfinding.finder.__all__ = ['a_star', 'best_first', 'bi_a_star', 'breadth_first', 'dijkstra', 'finder', 'ida_star']

Note: The world, heap, and msp modules are available but not included in __all__ exports.

Constants and Types

Common constants and type definitions used throughout the library.

# Mathematical constants
SQRT2 = 1.4142135623730951    # Square root of 2 for diagonal distances

# Type definitions
Coords = Tuple[float, float]   # Coordinate pair type
PathResult = Tuple[List[Node], int]  # Return type for find_path methods

# Algorithm limits
TIME_LIMIT = 10.0             # Default maximum execution time in seconds
MAX_RUNS = 100000             # Default maximum algorithm iterations

Heap Implementation

Internal priority queue implementation optimized for pathfinding with efficient node removal and ordering.

class SimpleHeap:
    def __init__(self, node, grid):
        """
        Create priority queue for pathfinding nodes.
        
        Parameters:
        - node (Node): Example node for type inference
        - grid (Grid|Graph): Grid or graph reference for compatibility checking
        """
    
    def push_node(self, node):
        """
        Add node to priority queue.
        
        Parameters:
        - node (Node): Node to add with f-value for priority
        """
    
    def pop_node(self):
        """
        Remove and return node with lowest f-value.
        
        Returns:
        Node: Node with minimum f-value
        """
    
    def remove_node(self, node, f):
        """
        Mark node as removed without restructuring heap.
        
        Parameters:
        - node (Node): Node to remove
        - f (float): F-value when node was added
        """
    
    def __len__(self):
        """
        Get number of active nodes in heap.
        
        Returns:
        int: Count of non-removed nodes
        """

Configuration and Best Practices

Diagonal Movement Selection

from pathfinding.core.diagonal_movement import DiagonalMovement

# Choose based on your needs:
movement_configs = {
    "grid_based_games": DiagonalMovement.always,
    "realistic_movement": DiagonalMovement.only_when_no_obstacle,  
    "turn_based_strategy": DiagonalMovement.if_at_most_one_obstacle,
    "simple_pathfinding": DiagonalMovement.never
}

Heuristic Selection Guide

# Match heuristic to movement pattern
heuristic_guide = {
    DiagonalMovement.never: manhattan,           # 4-directional
    DiagonalMovement.always: octile,             # 8-directional realistic
    DiagonalMovement.only_when_no_obstacle: octile,  # 8-directional constrained
    DiagonalMovement.if_at_most_one_obstacle: octile  # 8-directional relaxed
}

Path Post-Processing Workflow

from pathfinding.core.util import smoothen_path, expand_path

def optimize_path(grid, raw_path, smooth=True, expand=False):
    """Complete path optimization workflow."""
    # Convert nodes to coordinates
    coords = [(node.x, node.y) for node in raw_path]
    
    # Smooth path if requested
    if smooth:
        coords = smoothen_path(grid, coords, use_raytrace=True)
    
    # Expand path if requested  
    if expand:
        coords = expand_path(coords)
    
    return coords

# Usage
optimized_coords = optimize_path(grid, path, smooth=True, expand=False)

Performance Optimization

from pathfinding.core.grid import Grid

def setup_efficient_pathfinding(matrix):
    """Setup grid for optimal pathfinding performance."""
    # Create grid once, reuse multiple times
    grid = Grid(matrix=matrix)
    
    # Pre-compute expensive operations if possible
    # (This library handles most optimizations internally)
    
    return grid

def pathfind_efficiently(grid, start_pos, end_pos, finder):
    """Efficient pathfinding with proper cleanup."""
    # Always cleanup between runs on same grid
    grid.cleanup()
    
    # Get nodes
    start = grid.node(*start_pos)
    end = grid.node(*end_pos)
    
    # Find path
    path, runs = finder.find_path(start, end, grid)
    
    return path, runs

Memory Management

# For repeated pathfinding on same grid
grid = Grid(matrix=large_matrix)
finder = AStarFinder()

for start_pos, end_pos in path_requests:
    # Critical: cleanup between runs
    grid.cleanup()
    
    path, runs = finder.find_path(
        grid.node(*start_pos), 
        grid.node(*end_pos), 
        grid
    )
    
    # Process path immediately to avoid memory buildup
    process_path(path)

Error Handling

from pathfinding.finder.finder import ExecutionTimeException, ExecutionRunsException

def robust_pathfinding(finder, start, end, grid):
    """Pathfinding with proper error handling."""
    try:
        grid.cleanup()
        path, runs = finder.find_path(start, end, grid)
        
        if not path:
            return None, "No path found"
        
        return path, f"Success: {runs} runs"
        
    except ExecutionTimeException:
        return None, "Pathfinding timed out"
        
    except ExecutionRunsException:
        return None, "Too many iterations"
        
    except Exception as e:
        return None, f"Unexpected error: {e}"

Install with Tessl CLI

npx tessl i tessl/pypi-pathfinding

docs

tessl/pypi-pathfinding

utilities.md.css-3qkkll{font-size:var(--chakra-font-sizes-sm);font-weight:var(--chakra-font-weights-normal);color:var(--chakra-colors-gray-300);}docs/

Utilities and Configuration

Capabilities

Heuristic Functions

Usage Example

Path Processing Functions

Path Optimization Functions

Line Algorithm Functions

Usage Example

Module Exports and Import Patterns

Constants and Types

Heap Implementation

Configuration and Best Practices

Diagonal Movement Selection

Heuristic Selection Guide

Path Post-Processing Workflow

Performance Optimization

Memory Management

Error Handling

utilities.mddocs/