0
# Core Data Structures
1
2
Essential data structures that form the foundation of the pathfinding library. These include Grid for 2D pathfinding, Graph for network pathfinding, specialized Node classes, and World for managing multiple connected environments.
3
4
## Capabilities
5
6
### Grid Class
7
8
2D grid structure for pathfinding with support for obstacles, weighted nodes, and various movement policies. Grids can be created from matrices or dimensions and support wraparound borders.
9
10
```python { .api }
11
class Grid:
12
def __init__(self, width=0, height=0, matrix=None, grid_id=None, inverse=False):
13
"""
14
Create a new grid for pathfinding.
15
16
Parameters:
17
- width (int): Grid width in cells
18
- height (int): Grid height in cells
19
- matrix (List[List[int]]): Optional 2D matrix (>0=walkable, ≤0=obstacle by default)
20
- grid_id (int): Optional identifier for multi-grid worlds
21
- inverse (bool): When True, ≤0 values are walkable and >0 values are obstacles
22
"""
23
24
def node(self, x, y):
25
"""
26
Get node at coordinates.
27
28
Parameters:
29
- x (int): X coordinate
30
- y (int): Y coordinate
31
32
Returns:
33
GridNode: Node at specified position
34
"""
35
36
def inside(self, x, y):
37
"""
38
Check if coordinates are inside grid bounds.
39
40
Parameters:
41
- x (int): X coordinate
42
- y (int): Y coordinate
43
44
Returns:
45
bool: True if coordinates are inside grid
46
"""
47
48
def walkable(self, x, y):
49
"""
50
Check if position is walkable.
51
52
Parameters:
53
- x (int): X coordinate
54
- y (int): Y coordinate
55
56
Returns:
57
bool: True if position can be traversed
58
"""
59
60
def neighbors(self, node, diagonal_movement=DiagonalMovement.never):
61
"""
62
Get neighboring nodes.
63
64
Parameters:
65
- node (GridNode): Center node
66
- diagonal_movement (int): Diagonal movement policy
67
68
Returns:
69
List[GridNode]: List of accessible neighboring nodes
70
"""
71
72
def cleanup(self):
73
"""Reset all nodes for reuse in pathfinding."""
74
75
def update_node(self, x, y, *, weight=None, walkable=None):
76
"""
77
Update node properties.
78
79
Parameters:
80
- x (int): X coordinate
81
- y (int): Y coordinate
82
- weight (float): New weight value
83
- walkable (bool): New walkable state
84
"""
85
86
def calc_cost(self, node_a, node_b, weighted=False):
87
"""
88
Calculate movement cost between adjacent nodes.
89
90
Parameters:
91
- node_a (GridNode): Start node
92
- node_b (GridNode): End node
93
- weighted (bool): Whether to include node weights
94
95
Returns:
96
float: Movement cost
97
"""
98
99
def set_passable_left_right_border(self):
100
"""Enable horizontal wraparound borders."""
101
102
def set_passable_up_down_border(self):
103
"""Enable vertical wraparound borders."""
104
105
@property
106
def min_weight(self):
107
"""
108
Get minimum weight value in the grid.
109
110
Returns:
111
float: Minimum weight among all walkable nodes
112
"""
113
114
def grid_str(self, path=None, start=None, end=None, border=True,
115
start_chr='s', end_chr='e', path_chr='x', empty_chr=' ',
116
block_chr='#', show_weight=False):
117
"""
118
Generate ASCII representation of grid.
119
120
Parameters:
121
- path (List[GridNode]): Path to highlight
122
- start (GridNode): Start node to mark
123
- end (GridNode): End node to mark
124
- border (bool): Create border around grid
125
- empty_chr (str): Character for walkable cells
126
- block_chr (str): Character for obstacles
127
- start_chr (str): Character for start position
128
- end_chr (str): Character for end position
129
- path_chr (str): Character for path cells
130
- show_weight (bool): Show node weights instead of symbols
131
132
Returns:
133
str: ASCII grid representation
134
"""
135
```
136
137
### Graph Class
138
139
Graph structure for network-based pathfinding with support for weighted edges and bi-directional connections. Graphs are defined by edges and automatically generate nodes.
140
141
```python { .api }
142
class Graph:
143
def __init__(self, edges=None, nodes=None, bi_directional=False):
144
"""
145
Create a new graph for pathfinding.
146
147
Parameters:
148
- edges (List): Edge definitions [from_node, to_node, cost]
149
- nodes (Dict): Pre-existing nodes dictionary
150
- bi_directional (bool): Whether edges work in both directions
151
"""
152
153
def node(self, node_id):
154
"""
155
Get node by identifier.
156
157
Parameters:
158
- node_id: Node identifier (any hashable type)
159
160
Returns:
161
GraphNode: Node with specified identifier
162
"""
163
164
def neighbors(self, node, **kwargs):
165
"""
166
Get neighboring nodes connected by edges.
167
168
Parameters:
169
- node (GraphNode): Source node
170
171
Returns:
172
List[GraphNode]: List of connected neighboring nodes
173
"""
174
175
def calc_cost(self, node_a, node_b, _weighted=False):
176
"""
177
Calculate edge cost between connected nodes.
178
179
Parameters:
180
- node_a (GraphNode): Start node
181
- node_b (GraphNode): End node
182
- _weighted (bool): Ignored (for compatibility)
183
184
Returns:
185
float: Edge cost or infinity if not connected
186
"""
187
188
def cleanup(self):
189
"""Reset all nodes for reuse in pathfinding."""
190
191
def generate_nodes(self):
192
"""Generate nodes from edge definitions."""
193
```
194
195
### Node Classes
196
197
Specialized node classes that store pathfinding state and position information for different data structures.
198
199
```python { .api }
200
@dataclasses.dataclass
201
class Node:
202
"""Base node class with pathfinding attributes."""
203
h: float = 0.0 # Heuristic cost to goal
204
g: float = 0.0 # Cost from start
205
f: float = 0.0 # Total cost (g + h)
206
opened: int = 0 # Open list status
207
closed: bool = False # Closed list status
208
parent: 'Node' = None # Parent for backtracking
209
retain_count: int = 0 # Recursion tracking
210
tested: bool = False # Used by IDA* and JPS
211
212
def cleanup(self):
213
"""Reset all calculated values."""
214
215
@dataclasses.dataclass
216
class GridNode(Node):
217
def __init__(self, x=0, y=0):
218
"""
219
Create a grid node.
220
221
Parameters:
222
- x (int): X coordinate
223
- y (int): Y coordinate
224
"""
225
226
x: int = 0 # X coordinate
227
y: int = 0 # Y coordinate
228
walkable: bool = True # Whether node can be traversed
229
weight: float = 0.0 # Weight for weighted algorithms
230
grid_id: int = None # Grid identifier for multi-grid worlds
231
connections: list = None # Connections to other nodes
232
233
def connect(self, other_node):
234
"""
235
Connect to another node.
236
237
Parameters:
238
- other_node (GridNode): Node to connect to
239
"""
240
241
@dataclasses.dataclass
242
class GraphNode(Node):
243
def __init__(self, node_id):
244
"""
245
Create a graph node.
246
247
Parameters:
248
- node_id: Identifier for the node (any hashable type)
249
"""
250
251
node_id: any # Node identifier
252
```
253
254
### World Class
255
256
Multi-grid environment manager for pathfinding across connected grids with different properties. Enables complex scenarios like multi-level buildings or connected game areas.
257
258
```python { .api }
259
class World:
260
def __init__(self, grids):
261
"""
262
Create a world with multiple connected grids.
263
264
Parameters:
265
- grids (Dict[int, Grid]): Dictionary of grids by ID
266
"""
267
268
def cleanup(self):
269
"""Clean all grids in the world."""
270
271
def neighbors(self, node, diagonal_movement):
272
"""
273
Get neighbors across grids.
274
275
Parameters:
276
- node (Node): Source node
277
- diagonal_movement (int): Diagonal movement policy
278
279
Returns:
280
List[Node]: Neighbors including cross-grid connections
281
"""
282
283
def calc_cost(self, node_a, node_b, weighted=False):
284
"""
285
Calculate cost between nodes, including cross-grid costs.
286
287
Parameters:
288
- node_a (Node): Start node
289
- node_b (Node): End node
290
- weighted (bool): Whether to include node weights
291
292
Returns:
293
float: Movement cost
294
"""
295
```
296
297
### Diagonal Movement Policies
298
299
Configuration constants that control how pathfinding algorithms handle diagonal movement in grids.
300
301
```python { .api }
302
class DiagonalMovement:
303
"""Diagonal movement policy constants."""
304
always = 1 # Allow diagonal movement always
305
never = 2 # Never allow diagonal movement
306
if_at_most_one_obstacle = 3 # Allow diagonal if ≤1 obstacle
307
only_when_no_obstacle = 4 # Allow diagonal only when no obstacles
308
```
309
310
## Usage Examples
311
312
### Creating and Using a Grid
313
314
```python
315
from pathfinding.core.grid import Grid
316
from pathfinding.core.diagonal_movement import DiagonalMovement
317
318
# Create grid from matrix
319
matrix = [
320
[1, 1, 1, 0],
321
[1, 0, 1, 1],
322
[1, 1, 0, 1],
323
[0, 1, 1, 1]
324
]
325
grid = Grid(matrix=matrix)
326
327
# Access nodes
328
start = grid.node(0, 0)
329
end = grid.node(3, 3)
330
331
# Check properties
332
print(f"Start walkable: {start.walkable}")
333
print(f"Grid contains (2,2): {grid.inside(2, 2)}")
334
335
# Get neighbors with diagonal movement
336
neighbors = grid.neighbors(start, DiagonalMovement.always)
337
print(f"Start has {len(neighbors)} neighbors")
338
339
# Update node properties
340
grid.update_node(1, 1, walkable=True, weight=2.5)
341
```
342
343
### Creating and Using a Graph
344
345
```python
346
from pathfinding.core.graph import Graph
347
348
# Define weighted edges
349
edges = [
350
['A', 'B', 4],
351
['A', 'C', 2],
352
['B', 'C', 1],
353
['B', 'D', 5],
354
['C', 'D', 8],
355
['C', 'E', 10],
356
['D', 'E', 2]
357
]
358
359
# Create bi-directional graph
360
graph = Graph(edges=edges, bi_directional=True)
361
362
# Access nodes
363
node_a = graph.node('A')
364
node_e = graph.node('E')
365
366
# Get neighbors
367
neighbors = graph.neighbors(node_a)
368
neighbor_ids = [n.node_id for n in neighbors]
369
print(f"Node A connects to: {neighbor_ids}")
370
371
# Calculate edge costs
372
cost = graph.calc_cost(node_a, graph.node('B'))
373
print(f"Cost A->B: {cost}")
374
```
375
376
### Multi-Grid World
377
378
```python
379
from pathfinding.core.grid import Grid
380
from pathfinding.core.world import World
381
382
# Create multiple grids
383
ground_floor = Grid(width=10, height=10, grid_id=0)
384
second_floor = Grid(width=8, height=8, grid_id=1)
385
386
# Create world
387
world = World(grids={0: ground_floor, 1: second_floor})
388
389
# Nodes can connect between grids via their connections attribute
390
stair_bottom = ground_floor.node(5, 5)
391
stair_top = second_floor.node(1, 1)
392
stair_bottom.connect(stair_top)
393
394
# World can find neighbors across grids
395
neighbors = world.neighbors(stair_bottom, DiagonalMovement.never)
396
```