0
# Pathfinding
1

2
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.
3

4
## Package Information
5

6
- **Package Name**: pathfinding
7
- **Language**: Python
8
- **Installation**: `pip install pathfinding`
9

10
## Core Imports
11

12
```python
13
import pathfinding
14
```
15

16
Common imports for grid-based pathfinding:
17

18
```python
19
from pathfinding.core.grid import Grid
20
from pathfinding.core.diagonal_movement import DiagonalMovement
21
from pathfinding.finder.a_star import AStarFinder
22
```
23

24
Common imports for graph-based pathfinding:
25

26
```python
27
from pathfinding.core.graph import Graph
28
from pathfinding.finder.dijkstra import DijkstraFinder
29
```
30

31
Additional imports for advanced features:
32

33
```python
34
from pathfinding.core.world import World
35
from pathfinding.core.heuristic import manhattan, euclidean, octile
36
from pathfinding.core.util import backtrace, smoothen_path
37
from pathfinding.finder.msp import MinimumSpanningTree
38
```
39

40
## Basic Usage
41

42
### Grid-based Pathfinding
43

44
```python
45
from pathfinding.core.grid import Grid
46
from pathfinding.core.diagonal_movement import DiagonalMovement
47
from pathfinding.finder.a_star import AStarFinder
48

49
# Create grid from matrix (positive values=walkable, 0 or negative=obstacle)
50
matrix = [
51
    [1, 1, 1],
52
    [1, 0, 1], 
53
    [1, 1, 1]
54
]
55
grid = Grid(matrix=matrix)
56

57
# Get start and end nodes
58
start = grid.node(0, 0)
59
end = grid.node(2, 2)
60

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

65
# Extract coordinates from path
66
coords = [(node.x, node.y) for node in path]
67
print(f"Path: {coords}")
68
print(f"Algorithm runs: {runs}")
69
```
70

71
### Graph-based Pathfinding
72

73
```python
74
from pathfinding.core.graph import Graph
75
from pathfinding.finder.dijkstra import DijkstraFinder
76

77
# Define edges: [from_node, to_node, cost]
78
edges = [
79
    [1, 2, 7],
80
    [1, 3, 9], 
81
    [2, 3, 10],
82
    [2, 4, 15],
83
    [3, 4, 11]
84
]
85

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

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

93
# Extract node IDs from path
94
node_ids = [node.node_id for node in path]
95
print(f"Path: {node_ids}")
96
```
97

98
### Grid Cleanup (Important)
99

100
```python
101
# Always cleanup between pathfinding runs on the same grid
102
grid.cleanup()
103
path, runs = finder.find_path(start, end, grid)
104
```
105

106
## Architecture
107

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

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

115
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.
116

117
## Capabilities
118

119
### Core Data Structures
120

121
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.
122

123
```python { .api }
124
class Grid:
125
    def __init__(self, width=0, height=0, matrix=None, grid_id=None, inverse=False): ...
126
    def node(self, x, y): ...
127
    def neighbors(self, node, diagonal_movement=DiagonalMovement.never): ...
128
    def cleanup(self): ...
129
    def update_node(self, x, y, *, weight=None, walkable=None): ...
130

131
class Graph:
132
    def __init__(self, edges=None, nodes=None, bi_directional=False): ...
133
    def node(self, node_id): ...
134
    def neighbors(self, node, **kwargs): ...
135
    def cleanup(self): ...
136

137
class World:
138
    def __init__(self, grids): ...
139
    def neighbors(self, node, diagonal_movement): ...
140
    def cleanup(self): ...
141

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

146
class GraphNode:
147
    def __init__(self, node_id): ...
148
```
149

150
[Core Data Structures](./core-structures.md)
151

152
### Pathfinding Algorithms
153

154
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.
155

156
```python { .api }
157
class AStarFinder:
158
    def __init__(self, heuristic=None, weight=1, diagonal_movement=DiagonalMovement.never, 
159
                 time_limit=TIME_LIMIT, max_runs=MAX_RUNS): ...
160
    def find_path(self, start, end, grid): ...
161

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

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

172
class MinimumSpanningTree:
173
    def __init__(self, *args, **kwargs): ...
174
    def find_path(self, start, end, grid): ...
175
    def tree(self, grid, start): ...
176
```
177

178
[Pathfinding Algorithms](./algorithms.md)
179

180
### Utilities and Configuration
181

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

184
```python { .api }
185
class DiagonalMovement:
186
    always = 1
187
    never = 2
188
    if_at_most_one_obstacle = 3
189
    only_when_no_obstacle = 4
190

191
def manhattan(dx, dy): ...
192
def euclidean(dx, dy): ...
193
def backtrace(node): ...
194
def smoothen_path(grid, path, use_raytrace=False): ...
195
```
196

197
[Utilities and Configuration](./utilities.md)
198

199
## Types
200

201
```python { .api }
202
# Core types used across the library
203
Coords = Tuple[float, float]
204

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