grid-pathfinding

High-performance 3D grid pathfinding with A* and HPA* algorithms.

Features

• A* - Optimal pathfinding with heuristic search
• HPA* (Hierarchical Pathfinding A*) - Fast pathfinding on large grids
• Dynamic Replanning - Handle temporary obstacles during path execution
• Custom Heuristics - Manhattan, Euclidean, or create your own
• Movement Patterns - 6-directional (3D) or custom patterns
• Cost Functions - Support for terrain costs, congestion, etc.
• Path Caching - LRU cache with automatic invalidation
• Pure Python - No external dependencies (NumPy optional for dense storage)

Installation

pip install grid-pathfinding

Or with uv:

uv pip install grid-pathfinding

Quick Start

from grid_pathfinding import Grid, find_path

# Create a 10x10x1 grid
grid = Grid(10, 10, 1)

# Find a path from (0, 0, 0) to (9, 9, 0)
path = find_path(grid, (0, 0, 0), (9, 9, 0))

# Iterate over waypoints
for pos in path:
    print(pos)

# Get path statistics
print(f"Cost: {path.total_cost}")
print(f"Time: {path.computation_time_ms}ms")
print(f"Nodes explored: {path.nodes_explored}")

Examples

With Obstacles

from grid_pathfinding import Grid, find_path

grid = Grid(20, 20, 1)

# Add some obstacles
for x in range(5, 15):
    grid.set_obstacle(x, 10, 0)

path = find_path(grid, (0, 10, 0), (19, 10, 0))
# Path navigates around the wall

Using HPA* for Large Grids

from grid_pathfinding import Grid, find_path

# Large grid - HPA* is faster
grid = Grid(200, 200, 10)

path = find_path(grid, (0, 0, 0), (199, 199, 9), algorithm="hpastar")

Dynamic Replanning

from grid_pathfinding import Grid, find_path
from grid_pathfinding.algorithms import DynamicReplanner, ReplanStrategy

grid = Grid(50, 50, 1)
replanner = DynamicReplanner(strategy=ReplanStrategy.REPAIR)

# Get initial path
path = find_path(grid, (0, 0, 0), (49, 49, 0))

# New obstacle appears during execution
grid.set_obstacle(25, 25, 0, True)

# Replan from current position
new_path = replanner.replan(grid, path, (24, 25, 0))

With Path Caching

from grid_pathfinding import Grid, find_path
from grid_pathfinding.cache import PathCache

grid = Grid(100, 100, 10)
cache = PathCache(max_size=100)

# First call computes the path
path1 = cache.get_or_compute(grid, (0, 0, 0), (99, 99, 9))

# Second call returns cached result (much faster)
path2 = cache.get_or_compute(grid, (0, 0, 0), (99, 99, 9))

print(cache.stats)
# {'hits': 1, 'misses': 1, 'evictions': 0, 'size': 1, 'hit_rate': 0.5}

API Reference

Core Classes

Grid

grid = Grid(width, height, depth, storage_type=StorageType.SPARSE)

• is_obstacle(x, y, z) - Check if a cell is blocked
• set_obstacle(x, y, z, is_obstacle=True) - Set obstacle state
• get_cost(x, y, z) - Get movement cost for a cell
• set_cost(x, y, z, cost) - Set movement cost
• memory_usage - Property: memory used in bytes

Path

# Result from find_path()
path.waypoints        # List of (x, y, z) tuples
path.total_cost       # Total path cost
path.computation_time_ms  # Time to find path (ms)
path.nodes_explored  # Nodes searched

# Path operations
len(path)            # Number of waypoints
for pos in path: ... # Iterate waypoints
path.compress()      # Remove collinear waypoints
path.segments()      # Get as list of segments

Algorithms

AStar

from grid_pathfinding import AStar, ManhattanDistance, Cardinal3D

algo = AStar(
    heuristic=ManhattanDistance(),
    movement=Cardinal3D()
)
path = algo.find_path(grid, start, goal)

HPAStar

from grid_pathfinding import HPAStar

algo = HPAStar(cluster_size=(10, 10, 2))
path = algo.find_path(grid, start, goal)

Heuristics

• ManhattanDistance(use_3d=True) - L1 distance (6-dir movement)
• EuclideanDistance(use_3d=True) - L2 distance (26-dir movement)

Movement Patterns

• Cardinal3D - 6 directions (±X, ±Y, ±Z)

Performance

Benchmarks on typical hardware:

Grid Size	Algorithm	Time	Memory
100×100×10	A*	~1.5ms	<1MB
200×200×10	HPA*	~2-3ms	<2MB

Requirements

• Python 3.9+
• No external dependencies for sparse grids
• NumPy (optional) for dense grid storage

Development

# Install dev dependencies
uv pip install -e ".[dev]"

# Run tests
uv run pytest

# Run tests with coverage
uv run pytest --cov=grid_pathfinding

# Run benchmarks
uv run pytest --benchmark-only

License

MIT