0
# Utilities and Configuration
1
2
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.
3
4
## Capabilities
5
6
### Heuristic Functions
7
8
Distance calculation functions used by pathfinding algorithms to estimate costs between nodes. Different heuristics work better for different movement patterns and grid types.
9
10
```python
11
from pathfinding.core import heuristic
12
```
13
14
```python { .api }
15
def null(dx, dy):
16
"""
17
Null heuristic that always returns 0.
18
Used by Dijkstra's algorithm.
19
20
Parameters:
21
- dx (float): X distance
22
- dy (float): Y distance
23
24
Returns:
25
float: Always 0
26
"""
27
28
def manhattan(dx, dy):
29
"""
30
Manhattan distance heuristic.
31
Good for 4-directional movement (no diagonals).
32
33
Parameters:
34
- dx (float): X distance
35
- dy (float): Y distance
36
37
Returns:
38
float: |dx| + |dy|
39
"""
40
41
def euclidean(dx, dy):
42
"""
43
Euclidean distance heuristic.
44
Good for free movement in any direction.
45
46
Parameters:
47
- dx (float): X distance
48
- dy (float): Y distance
49
50
Returns:
51
float: sqrt(dx² + dy²)
52
"""
53
54
def chebyshev(dx, dy):
55
"""
56
Chebyshev distance heuristic.
57
Good for 8-directional movement with equal diagonal cost.
58
59
Parameters:
60
- dx (float): X distance
61
- dy (float): Y distance
62
63
Returns:
64
float: max(|dx|, |dy|)
65
"""
66
67
def octile(dx, dy):
68
"""
69
Octile distance heuristic.
70
Good for 8-directional movement with realistic diagonal costs.
71
72
Parameters:
73
- dx (float): X distance
74
- dy (float): Y distance
75
76
Returns:
77
float: Octile distance accounting for diagonal movement cost
78
"""
79
```
80
81
#### Usage Example
82
83
```python
84
from pathfinding.core.heuristic import euclidean, manhattan, octile
85
from pathfinding.finder.a_star import AStarFinder
86
from pathfinding.core.diagonal_movement import DiagonalMovement
87
88
# Choose heuristic based on movement type
89
grid_4way = AStarFinder(heuristic=manhattan, diagonal_movement=DiagonalMovement.never)
90
grid_8way = AStarFinder(heuristic=octile, diagonal_movement=DiagonalMovement.always)
91
free_movement = AStarFinder(heuristic=euclidean, diagonal_movement=DiagonalMovement.always)
92
93
# Compare heuristic estimates
94
dx, dy = 3, 4
95
print(f"Manhattan: {manhattan(dx, dy)}") # 7
96
print(f"Euclidean: {euclidean(dx, dy)}") # 5.0
97
print(f"Chebyshev: {chebyshev(dx, dy)}") # 4
98
print(f"Octile: {octile(dx, dy)}") # ~6.24
99
```
100
101
### Path Processing Functions
102
103
Functions for reconstructing and manipulating paths returned by pathfinding algorithms. These enable path optimization and format conversion.
104
105
```python
106
from pathfinding.core.util import backtrace, bi_backtrace
107
```
108
109
```python { .api }
110
def backtrace(node):
111
"""
112
Reconstruct path by following parent links from end node.
113
114
Parameters:
115
- node (Node): End node with parent chain
116
117
Returns:
118
List[Node]: Path from start to end node
119
"""
120
121
def bi_backtrace(node_a, node_b):
122
"""
123
Reconstruct path for bi-directional search.
124
Combines paths from both search directions.
125
126
Parameters:
127
- node_a (Node): Meeting point from start search
128
- node_b (Node): Meeting point from end search
129
130
Returns:
131
List[Node]: Complete path from original start to end
132
"""
133
```
134
135
### Path Optimization Functions
136
137
Advanced path manipulation for creating smoother, more natural-looking paths by removing unnecessary waypoints and applying line-of-sight optimizations.
138
139
```python
140
from pathfinding.core.util import smoothen_path, expand_path
141
```
142
143
```python { .api }
144
def smoothen_path(grid, path, use_raytrace=False):
145
"""
146
Smooth path by removing unnecessary waypoints.
147
Uses line-of-sight checks to create more direct paths.
148
149
Parameters:
150
- grid (Grid): Grid for line-of-sight checking
151
- path (List[Coords]): Path as coordinate list
152
- use_raytrace (bool): Use raytrace vs bresenham for line-of-sight
153
154
Returns:
155
List[Coords]: Smoothed path with fewer waypoints
156
"""
157
158
def expand_path(path):
159
"""
160
Interpolate compressed path to include all intermediate points.
161
162
Parameters:
163
- path (List[Coords]): Compressed path coordinates
164
165
Returns:
166
List[Coords]: Expanded path with all intermediate points
167
"""
168
```
169
170
### Line Algorithm Functions
171
172
Geometric algorithms for line-of-sight calculations and path interpolation between points.
173
174
```python
175
from pathfinding.core.util import raytrace, bresenham
176
```
177
178
```python { .api }
179
def raytrace(coords_a, coords_b):
180
"""
181
Ray-casting line algorithm for line-of-sight calculations.
182
183
Parameters:
184
- coords_a (Coords): Start coordinates
185
- coords_b (Coords): End coordinates
186
187
Returns:
188
List[Coords]: Points along line from A to B
189
"""
190
191
def bresenham(coords_a, coords_b):
192
"""
193
Bresenham line algorithm for integer grid line drawing.
194
195
Parameters:
196
- coords_a (Coords): Start coordinates
197
- coords_b (Coords): End coordinates
198
199
Returns:
200
List[Coords]: Grid points along line from A to B
201
"""
202
```
203
204
#### Usage Example
205
206
```python
207
from pathfinding.core.util import smoothen_path, expand_path, raytrace
208
from pathfinding.core.grid import Grid
209
from pathfinding.finder.a_star import AStarFinder
210
211
# Find initial path
212
grid = Grid(matrix=maze_matrix)
213
finder = AStarFinder()
214
path, runs = finder.find_path(grid.node(0,0), grid.node(10,10), grid)
215
216
# Convert to coordinates
217
coords = [(node.x, node.y) for node in path]
218
219
# Smooth the path
220
smooth_coords = smoothen_path(grid, coords, use_raytrace=True)
221
print(f"Original path: {len(coords)} points")
222
print(f"Smoothed path: {len(smooth_coords)} points")
223
224
# Check line of sight between two points
225
line_points = raytrace((0, 0), (5, 3))
226
print(f"Line passes through: {line_points}")
227
```
228
229
### Module Exports and Import Patterns
230
231
The pathfinding library exposes its API through structured module exports:
232
233
```python { .api }
234
# Main package exports
235
pathfinding.__all__ = ['core', 'finder']
236
237
# Core module exports
238
pathfinding.core.__all__ = ['diagonal_movement', 'graph', 'grid', 'heuristic', 'node', 'util']
239
240
# Finder module exports
241
pathfinding.finder.__all__ = ['a_star', 'best_first', 'bi_a_star', 'breadth_first', 'dijkstra', 'finder', 'ida_star']
242
```
243
244
Note: The `world`, `heap`, and `msp` modules are available but not included in `__all__` exports.
245
246
### Constants and Types
247
248
Common constants and type definitions used throughout the library.
249
250
```python { .api }
251
# Mathematical constants
252
SQRT2 = 1.4142135623730951 # Square root of 2 for diagonal distances
253
254
# Type definitions
255
Coords = Tuple[float, float] # Coordinate pair type
256
PathResult = Tuple[List[Node], int] # Return type for find_path methods
257
258
# Algorithm limits
259
TIME_LIMIT = 10.0 # Default maximum execution time in seconds
260
MAX_RUNS = 100000 # Default maximum algorithm iterations
261
```
262
263
### Heap Implementation
264
265
Internal priority queue implementation optimized for pathfinding with efficient node removal and ordering.
266
267
```python { .api }
268
class SimpleHeap:
269
def __init__(self, node, grid):
270
"""
271
Create priority queue for pathfinding nodes.
272
273
Parameters:
274
- node (Node): Example node for type inference
275
- grid (Grid|Graph): Grid or graph reference for compatibility checking
276
"""
277
278
def push_node(self, node):
279
"""
280
Add node to priority queue.
281
282
Parameters:
283
- node (Node): Node to add with f-value for priority
284
"""
285
286
def pop_node(self):
287
"""
288
Remove and return node with lowest f-value.
289
290
Returns:
291
Node: Node with minimum f-value
292
"""
293
294
def remove_node(self, node, f):
295
"""
296
Mark node as removed without restructuring heap.
297
298
Parameters:
299
- node (Node): Node to remove
300
- f (float): F-value when node was added
301
"""
302
303
def __len__(self):
304
"""
305
Get number of active nodes in heap.
306
307
Returns:
308
int: Count of non-removed nodes
309
"""
310
```
311
312
## Configuration and Best Practices
313
314
### Diagonal Movement Selection
315
316
```python
317
from pathfinding.core.diagonal_movement import DiagonalMovement
318
319
# Choose based on your needs:
320
movement_configs = {
321
"grid_based_games": DiagonalMovement.always,
322
"realistic_movement": DiagonalMovement.only_when_no_obstacle,
323
"turn_based_strategy": DiagonalMovement.if_at_most_one_obstacle,
324
"simple_pathfinding": DiagonalMovement.never
325
}
326
```
327
328
### Heuristic Selection Guide
329
330
```python
331
# Match heuristic to movement pattern
332
heuristic_guide = {
333
DiagonalMovement.never: manhattan, # 4-directional
334
DiagonalMovement.always: octile, # 8-directional realistic
335
DiagonalMovement.only_when_no_obstacle: octile, # 8-directional constrained
336
DiagonalMovement.if_at_most_one_obstacle: octile # 8-directional relaxed
337
}
338
```
339
340
### Path Post-Processing Workflow
341
342
```python
343
from pathfinding.core.util import smoothen_path, expand_path
344
345
def optimize_path(grid, raw_path, smooth=True, expand=False):
346
"""Complete path optimization workflow."""
347
# Convert nodes to coordinates
348
coords = [(node.x, node.y) for node in raw_path]
349
350
# Smooth path if requested
351
if smooth:
352
coords = smoothen_path(grid, coords, use_raytrace=True)
353
354
# Expand path if requested
355
if expand:
356
coords = expand_path(coords)
357
358
return coords
359
360
# Usage
361
optimized_coords = optimize_path(grid, path, smooth=True, expand=False)
362
```
363
364
### Performance Optimization
365
366
```python
367
from pathfinding.core.grid import Grid
368
369
def setup_efficient_pathfinding(matrix):
370
"""Setup grid for optimal pathfinding performance."""
371
# Create grid once, reuse multiple times
372
grid = Grid(matrix=matrix)
373
374
# Pre-compute expensive operations if possible
375
# (This library handles most optimizations internally)
376
377
return grid
378
379
def pathfind_efficiently(grid, start_pos, end_pos, finder):
380
"""Efficient pathfinding with proper cleanup."""
381
# Always cleanup between runs on same grid
382
grid.cleanup()
383
384
# Get nodes
385
start = grid.node(*start_pos)
386
end = grid.node(*end_pos)
387
388
# Find path
389
path, runs = finder.find_path(start, end, grid)
390
391
return path, runs
392
```
393
394
### Memory Management
395
396
```python
397
# For repeated pathfinding on same grid
398
grid = Grid(matrix=large_matrix)
399
finder = AStarFinder()
400
401
for start_pos, end_pos in path_requests:
402
# Critical: cleanup between runs
403
grid.cleanup()
404
405
path, runs = finder.find_path(
406
grid.node(*start_pos),
407
grid.node(*end_pos),
408
grid
409
)
410
411
# Process path immediately to avoid memory buildup
412
process_path(path)
413
```
414
415
### Error Handling
416
417
```python
418
from pathfinding.finder.finder import ExecutionTimeException, ExecutionRunsException
419
420
def robust_pathfinding(finder, start, end, grid):
421
"""Pathfinding with proper error handling."""
422
try:
423
grid.cleanup()
424
path, runs = finder.find_path(start, end, grid)
425
426
if not path:
427
return None, "No path found"
428
429
return path, f"Success: {runs} runs"
430
431
except ExecutionTimeException:
432
return None, "Pathfinding timed out"
433
434
except ExecutionRunsException:
435
return None, "Too many iterations"
436
437
except Exception as e:
438
return None, f"Unexpected error: {e}"
439
```