0
# Pathfinding Algorithms
1

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

4
## Capabilities
5

6
### A* Algorithm
7

8
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.
9

10
```python { .api }
11
class AStarFinder:
12
    def __init__(self, heuristic=None, weight=1, diagonal_movement=DiagonalMovement.never, 
13
                 time_limit=TIME_LIMIT, max_runs=MAX_RUNS):
14
        """
15
        Create A* pathfinder.
16
        
17
        Parameters:
18
        - heuristic (function): Heuristic function (defaults to manhattan/octile based on diagonal_movement)
19
        - weight (int): Edge weight multiplier for weighted A*
20
        - diagonal_movement (int): Diagonal movement policy
21
        - time_limit (float): Maximum execution time in seconds
22
        - max_runs (int): Maximum algorithm iterations
23
        """
24
    
25
    def find_path(self, start, end, grid):
26
        """
27
        Find optimal path using A* algorithm.
28
        
29
        Parameters:
30
        - start (Node): Starting node
31
        - end (Node): Target node  
32
        - grid (Grid|Graph): Search space
33
        
34
        Returns:
35
        Tuple[List[Node], int]: (path_nodes, runs_count)
36
        """
37
```
38

39
#### Usage Example
40

41
```python
42
from pathfinding.core.grid import Grid
43
from pathfinding.core.diagonal_movement import DiagonalMovement
44
from pathfinding.finder.a_star import AStarFinder
45
from pathfinding.core.heuristic import euclidean
46

47
# Create grid and finder
48
grid = Grid(matrix=[[1,1,1],[1,0,1],[1,1,1]])
49
finder = AStarFinder(
50
    heuristic=euclidean,
51
    diagonal_movement=DiagonalMovement.always,
52
    weight=2  # Weighted A* for faster, suboptimal paths
53
)
54

55
# Find path
56
path, runs = finder.find_path(grid.node(0,0), grid.node(2,2), grid)
57
print(f"Path length: {len(path)}, Runs: {runs}")
58
```
59

60
### Dijkstra Algorithm
61

62
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.
63

64
```python { .api }
65
class DijkstraFinder:
66
    def __init__(self, weight=1, diagonal_movement=DiagonalMovement.never,
67
                 time_limit=TIME_LIMIT, max_runs=MAX_RUNS):
68
        """
69
        Create Dijkstra pathfinder.
70
        
71
        Parameters:
72
        - weight (int): Edge weight multiplier
73
        - diagonal_movement (int): Diagonal movement policy
74
        - time_limit (float): Maximum execution time in seconds
75
        - max_runs (int): Maximum algorithm iterations
76
        """
77
    
78
    def find_path(self, start, end, grid):
79
        """
80
        Find optimal path using Dijkstra's algorithm.
81
        
82
        Parameters:
83
        - start (Node): Starting node
84
        - end (Node): Target node
85
        - grid (Grid|Graph): Search space
86
        
87
        Returns:
88
        Tuple[List[Node], int]: (path_nodes, runs_count)
89
        """
90
```
91

92
#### Usage Example
93

94
```python
95
from pathfinding.core.graph import Graph
96
from pathfinding.finder.dijkstra import DijkstraFinder
97

98
# Create weighted graph
99
edges = [
100
    [1, 2, 10], [1, 3, 15], [2, 3, 12], 
101
    [2, 4, 15], [3, 4, 10]
102
]
103
graph = Graph(edges=edges, bi_directional=True)
104

105
# Find shortest path
106
finder = DijkstraFinder()
107
path, runs = finder.find_path(graph.node(1), graph.node(4), graph)
108

109
# Extract path
110
node_path = [node.node_id for node in path]
111
print(f"Shortest path: {node_path}")
112
```
113

114
### Best-First Search
115

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

118
```python { .api }
119
class BestFirst:
120
    def __init__(self, heuristic=None, weight=1, diagonal_movement=DiagonalMovement.never,
121
                 time_limit=TIME_LIMIT, max_runs=MAX_RUNS):
122
        """
123
        Create Best-First pathfinder.
124
        
125
        Parameters:
126
        - heuristic (function): Heuristic function (defaults to manhattan/octile)
127
        - weight (int): Edge weight multiplier
128
        - diagonal_movement (int): Diagonal movement policy
129
        - time_limit (float): Maximum execution time in seconds
130
        - max_runs (int): Maximum algorithm iterations
131
        """
132
    
133
    def find_path(self, start, end, grid):
134
        """
135
        Find path using Best-First search.
136
        
137
        Parameters:
138
        - start (Node): Starting node
139
        - end (Node): Target node
140
        - grid (Grid|Graph): Search space
141
        
142
        Returns:  
143
        Tuple[List[Node], int]: (path_nodes, runs_count)
144
        """
145
```
146

147
### Bi-directional A*
148

149
Bi-directional A* searching simultaneously from start and end until paths meet. More efficient for long paths but doesn't support weighted nodes.
150

151
```python { .api }
152
class BiAStarFinder:
153
    def __init__(self, heuristic=None, weight=1, diagonal_movement=DiagonalMovement.never,
154
                 time_limit=TIME_LIMIT, max_runs=MAX_RUNS):
155
        """
156
        Create Bi-directional A* pathfinder.
157
        
158
        Parameters:
159
        - heuristic (function): Heuristic function (defaults to manhattan/octile)
160
        - weight (int): Edge weight multiplier  
161
        - diagonal_movement (int): Diagonal movement policy
162
        - time_limit (float): Maximum execution time in seconds
163
        - max_runs (int): Maximum algorithm iterations
164
        """
165
    
166
    def find_path(self, start, end, grid):
167
        """
168
        Find path using bi-directional A*.
169
        
170
        Parameters:
171
        - start (Node): Starting node
172
        - end (Node): Target node
173
        - grid (Grid|Graph): Search space
174
        
175
        Returns:
176
        Tuple[List[Node], int]: (path_nodes, runs_count)
177
        """
178
```
179

180
### Breadth-First Search
181

182
Breadth-first search exploring nodes level by level from the start. Guarantees shortest path in unweighted graphs but can be slow for large spaces.
183

184
```python { .api }
185
class BreadthFirstFinder:
186
    def __init__(self, heuristic=None, weight=1, diagonal_movement=DiagonalMovement.never,
187
                 time_limit=TIME_LIMIT, max_runs=MAX_RUNS):
188
        """
189
        Create Breadth-First pathfinder.
190
        
191
        Parameters:
192
        - heuristic (function): Ignored (BFS doesn't use heuristics)
193
        - weight (int): Edge weight multiplier
194
        - diagonal_movement (int): Diagonal movement policy
195
        - time_limit (float): Maximum execution time in seconds
196
        - max_runs (int): Maximum algorithm iterations
197
        """
198
    
199
    def find_path(self, start, end, grid):
200
        """
201
        Find path using Breadth-First search.
202
        
203
        Parameters:
204
        - start (Node): Starting node
205
        - end (Node): Target node
206
        - grid (Grid|Graph): Search space
207
        
208
        Returns:
209
        Tuple[List[Node], int]: (path_nodes, runs_count)
210
        """
211
```
212

213
### IDA* (Iterative Deepening A*)
214

215
Memory-efficient iterative deepening A* using successive depth limits. Provides optimal paths with minimal memory usage but can be slower than regular A*.
216

217
```python { .api }
218
class IDAStarFinder:
219
    def __init__(self, heuristic=None, weight=1, diagonal_movement=DiagonalMovement.never,
220
                 time_limit=TIME_LIMIT, max_runs=MAX_RUNS, track_recursion=True):
221
        """
222
        Create IDA* pathfinder.
223
        
224
        Parameters:
225
        - heuristic (function): Heuristic function (defaults to manhattan/octile)
226
        - weight (int): Edge weight multiplier
227
        - diagonal_movement (int): Diagonal movement policy
228
        - time_limit (float): Maximum execution time in seconds
229
        - max_runs (int): Maximum algorithm iterations
230
        - track_recursion (bool): Track recursion for visualization
231
        """
232
    
233
    @property
234
    def nodes_visited(self) -> int:
235
        """Statistics counter for nodes visited during search."""
236
    
237
    def find_path(self, start, end, grid):
238
        """
239
        Find path using IDA* algorithm.
240
        
241
        Parameters:
242
        - start (Node): Starting node
243
        - end (Node): Target node
244
        - grid (Grid|Graph): Search space
245
        
246
        Returns:
247
        Tuple[List[Node], int]: (path_nodes, runs_count)
248
        """
249
```
250

251
#### Usage Example
252

253
```python
254
from pathfinding.finder.ida_star import IDAStarFinder
255

256
# Memory-efficient pathfinding for large grids
257
finder = IDAStarFinder(track_recursion=False)  # Disable tracking for performance
258
path, runs = finder.find_path(start, end, large_grid)
259
print(f"Nodes visited: {finder.nodes_visited}")
260
```
261

262
### Minimum Spanning Tree
263

264
Pathfinding via minimum spanning tree generation. Useful for finding paths in graphs where you need to connect all nodes with minimum total cost.
265

266
```python { .api }
267
class MinimumSpanningTree:
268
    def __init__(self, *args, **kwargs):
269
        """Create Minimum Spanning Tree pathfinder."""
270
    
271
    def find_path(self, start, end, grid):
272
        """
273
        Find path via minimum spanning tree.
274
        
275
        Parameters:
276
        - start (Node): Starting node
277
        - end (Node): Target node
278
        - grid (Grid|Graph): Search space
279
        
280
        Returns:
281
        Tuple[List[Node], int]: (path_nodes, runs_count)
282
        """
283
    
284
    def tree(self, grid, start):
285
        """
286
        Generate complete minimum spanning tree.
287
        
288
        Parameters:
289
        - grid (Grid|Graph): Search space
290
        - start (Node): Root node for tree
291
        
292
        Returns:
293
        List[Node]: All nodes in spanning tree order
294
        """
295
    
296
    def itertree(self, grid, start):
297
        """
298
        Generator for spanning tree nodes.
299
        
300
        Parameters:
301
        - grid (Grid|Graph): Search space
302
        - start (Node): Root node for tree
303
        
304
        Yields:
305
        Node: Next node in spanning tree
306
        """
307
```
308

309
## Base Finder Class
310

311
All pathfinding algorithms inherit from the base Finder class, providing common functionality and interface consistency.
312

313
```python { .api }
314
class Finder:
315
    def __init__(self, heuristic=None, weight=1, diagonal_movement=DiagonalMovement.never,
316
                 weighted=True, time_limit=TIME_LIMIT, max_runs=MAX_RUNS):
317
        """
318
        Base pathfinder class.
319
        
320
        Parameters:
321
        - heuristic (function): Heuristic function
322
        - weight (int): Edge weight multiplier
323
        - diagonal_movement (int): Diagonal movement policy
324
        - weighted (bool): Whether algorithm supports weighted nodes
325
        - time_limit (float): Maximum execution time in seconds
326
        - max_runs (int): Maximum algorithm iterations
327
        """
328
    
329
    def apply_heuristic(self, node_a, node_b, heuristic=None, graph=None):
330
        """
331
        Calculate heuristic distance between nodes.
332
        
333
        Parameters:
334
        - node_a (Node): Start node
335
        - node_b (Node): End node
336
        - heuristic (function): Heuristic function to use
337
        - graph (Grid|Graph): Search space context
338
        
339
        Returns:
340
        float: Heuristic distance
341
        """
342
    
343
    def find_neighbors(self, grid, node, diagonal_movement=None):
344
        """
345
        Find neighboring nodes.
346
        
347
        Parameters:
348
        - grid (Grid|Graph): Search space
349
        - node (Node): Center node
350
        - diagonal_movement (int): Diagonal movement policy
351
        
352
        Returns:
353
        List[Node]: Neighboring nodes
354
        """
355
    
356
    def keep_running(self):
357
        """
358
        Check if algorithm should continue running.
359
        
360
        Returns:
361
        bool: True if within time and iteration limits
362
        """
363
```
364

365
## Exceptions
366

367
```python { .api }
368
class ExecutionTimeException(Exception):
369
    """Raised when pathfinding exceeds time limit."""
370

371
class ExecutionRunsException(Exception):
372
    """Raised when pathfinding exceeds maximum runs."""
373
```
374

375
## Constants
376

377
```python { .api }
378
TIME_LIMIT = 10.0   # Default maximum execution time in seconds
379
MAX_RUNS = 100000   # Default maximum algorithm iterations
380
```
381

382
## Algorithm Selection Guide
383

384
### Choose A* when:
385
- You need optimal paths
386
- You have a good heuristic function
387
- Memory usage is acceptable
388
- Grid/graph has moderate size
389

390
### Choose Dijkstra when:
391
- You need guaranteed optimal paths
392
- No good heuristic is available
393
- Graph has weighted edges
394
- You need to find shortest paths to multiple targets
395

396
### Choose Best-First when:
397
- Speed is more important than optimality
398
- You have a good heuristic
399
- Approximate solutions are acceptable
400

401
### Choose Bi-directional A* when:
402
- Paths are typically long
403
- You need optimal paths
404
- Graph/grid is large
405
- Start and end are far apart
406

407
### Choose Breadth-First when:
408
- Graph is unweighted
409
- You need shortest path (by number of steps)
410
- Graph is relatively small
411

412
### Choose IDA* when:
413
- Memory is very limited
414
- You need optimal paths
415
- Grid/graph is large
416
- You can tolerate slower execution
417

418
### Choose MSP when:
419
- You need to connect all nodes
420
- Total connection cost matters more than individual paths
421
- Working with network design problems
422

423
## Usage Patterns
424

425
### Algorithm Comparison
426

427
```python
428
from pathfinding.core.grid import Grid
429
from pathfinding.finder.a_star import AStarFinder
430
from pathfinding.finder.dijkstra import DijkstraFinder
431
from pathfinding.finder.breadth_first import BreadthFirstFinder
432

433
grid = Grid(matrix=large_maze)
434
start = grid.node(0, 0)
435
end = grid.node(99, 99)
436

437
algorithms = [
438
    ("A*", AStarFinder()),
439
    ("Dijkstra", DijkstraFinder()),
440
    ("BFS", BreadthFirstFinder())
441
]
442

443
for name, finder in algorithms:
444
    grid.cleanup()  # Important: clean between runs
445
    path, runs = finder.find_path(start, end, grid)
446
    print(f"{name}: path length {len(path)}, runs {runs}")
447
```
448

449
### Performance Monitoring
450

451
```python
452
import time
453
from pathfinding.finder.a_star import AStarFinder
454

455
# Set time and iteration limits
456
finder = AStarFinder(time_limit=5.0, max_runs=10000)
457

458
start_time = time.time()
459
try:
460
    path, runs = finder.find_path(start, end, grid)
461
    elapsed = time.time() - start_time
462
    print(f"Found path in {elapsed:.2f}s with {runs} runs")
463
except ExecutionTimeException:
464
    print("Pathfinding timed out")
465
except ExecutionRunsException:
466
    print("Pathfinding exceeded maximum runs")
467
```