-
Notifications
You must be signed in to change notification settings - Fork 74
Expand file tree
/
Copy pathgrid.py
More file actions
218 lines (195 loc) · 7.32 KB
/
grid.py
File metadata and controls
218 lines (195 loc) · 7.32 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
# -*- coding: utf-8 -*-
from .diagonal_movement import DiagonalMovement
from .node import Node
try:
import numpy as np
USE_NUMPY = True
except ImportError:
USE_NUMPY = False
def build_nodes(width, height, matrix=None, inverse=False):
"""
create nodes according to grid size. If a matrix is given it
will be used to determine what nodes are walkable.
:rtype : list
"""
nodes = []
use_matrix = (isinstance(matrix, (tuple, list))) or \
(USE_NUMPY and isinstance(matrix, np.ndarray) and matrix.size > 0)
for y in range(height):
nodes.append([])
for x in range(width):
# 0, '0', False will be obstacles
# all other values mark walkable cells.
# you can use values bigger then 1 to assign a weight.
# If inverse is False it changes
# (1 and up becomes obstacle and 0 or everything negative marks a
# free cells)
weight = int(matrix[y][x]) if use_matrix else 1
walkable = weight <= 0 if inverse else weight >= 1
nodes[y].append(Node(x=x, y=y, walkable=walkable, weight=weight))
return nodes
class Grid(object):
def __init__(self, width=0, height=0, matrix=None, inverse=False):
"""
a grid represents the map (as 2d-list of nodes).
"""
self.width = width
self.height = height
self.passable_left_right_border = False
self.passable_up_down_border = False
if isinstance(matrix, (tuple, list)) or (
USE_NUMPY and isinstance(matrix, np.ndarray) and
matrix.size > 0):
self.height = len(matrix)
self.width = self.width = len(matrix[0]) if self.height > 0 else 0
if self.width > 0 and self.height > 0:
self.nodes = build_nodes(self.width, self.height, matrix, inverse)
else:
self.nodes = [[]]
def set_passable_left_right_border(self):
self.passable_left_right_border = True
def set_passable_up_down_border(self):
self.passable_up_down_border = True
def node(self, x, y):
"""
get node at position
:param x: x pos
:param y: y pos
:return:
"""
return self.nodes[y][x]
def inside(self, x, y):
"""
check, if field position is inside map
:param x: x pos
:param y: y pos
:return:
"""
return 0 <= x < self.width and 0 <= y < self.height
def walkable(self, x, y):
"""
check, if the tile is inside grid and if it is set as walkable
"""
return self.inside(x, y) and self.nodes[y][x].walkable
def neighbors(self, node, diagonal_movement=DiagonalMovement.never):
"""
get all neighbors of one node
:param node: node
"""
x = node.x
y = node.y
neighbors = []
s0 = d0 = s1 = d1 = s2 = d2 = s3 = d3 = False
# ↑
if y == 0 and self.passable_up_down_border:
if self.walkable(x, self.height - 1):
neighbors.append(self.nodes[self.height - 1][x])
s0 = True
else:
if self.walkable(x, y - 1):
neighbors.append(self.nodes[y - 1][x])
s0 = True
# →
if x == self.width - 1 and self.passable_left_right_border:
if self.walkable(0, y):
neighbors.append(self.nodes[y][0])
s1 = True
else:
if self.walkable(x + 1, y):
neighbors.append(self.nodes[y][x + 1])
s1 = True
# ↓
if y == self.height - 1 and self.passable_up_down_border:
if self.walkable(x, 0):
neighbors.append(self.nodes[0][x])
s2 = True
else:
if self.walkable(x, y + 1):
neighbors.append(self.nodes[y + 1][x])
s2 = True
# ←
if x == 0 and self.passable_left_right_border:
if self.walkable(self.width - 1, y):
neighbors.append(self.nodes[y][self.width - 1])
s3 = True
else:
if self.walkable(x - 1, y):
neighbors.append(self.nodes[y][x - 1])
s3 = True
if diagonal_movement == DiagonalMovement.never:
return neighbors
if diagonal_movement == DiagonalMovement.only_when_no_obstacle:
d0 = s3 and s0
d1 = s0 and s1
d2 = s1 and s2
d3 = s2 and s3
elif diagonal_movement == DiagonalMovement.if_at_most_one_obstacle:
d0 = s3 or s0
d1 = s0 or s1
d2 = s1 or s2
d3 = s2 or s3
elif diagonal_movement == DiagonalMovement.always:
d0 = d1 = d2 = d3 = True
# ↖
if d0 and self.walkable(x - 1, y - 1):
neighbors.append(self.nodes[y - 1][x - 1])
# ↗
if d1 and self.walkable(x + 1, y - 1):
neighbors.append(self.nodes[y - 1][x + 1])
# ↘
if d2 and self.walkable(x + 1, y + 1):
neighbors.append(self.nodes[y + 1][x + 1])
# ↙
if d3 and self.walkable(x - 1, y + 1):
neighbors.append(self.nodes[y + 1][x - 1])
return neighbors
def cleanup(self):
for y_nodes in self.nodes:
for node in y_nodes:
node.cleanup()
def grid_str(self, path=None, start=None, end=None,
border=True, start_chr='s', end_chr='e',
path_chr='x', empty_chr=' ', block_chr='#',
show_weight=False):
"""
create a printable string from the grid using ASCII characters
:param path: list of nodes that show the path
:param start: start node
:param end: end node
:param border: create a border around the grid
:param start_chr: character for the start (default "s")
:param end_chr: character for the destination (default "e")
:param path_chr: character to show the path (default "x")
:param empty_chr: character for empty fields (default " ")
:param block_chr: character for blocking elements (default "#")
:param show_weight: instead of empty_chr show the cost of each empty
field (shows a + if the value of weight is > 10)
:return:
"""
data = ''
if border:
data = '+{}+'.format('-' * len(self.nodes[0]))
for y in range(len(self.nodes)):
line = ''
for x in range(len(self.nodes[y])):
node = self.nodes[y][x]
if node == start:
line += start_chr
elif node == end:
line += end_chr
elif path and ((node.x, node.y) in path or node in path):
line += path_chr
elif node.walkable:
# empty field
weight = str(node.weight) if node.weight < 10 else '+'
line += weight if show_weight else empty_chr
else:
line += block_chr # blocked field
if border:
line = '|' + line + '|'
if data:
data += '\n'
data += line
if border:
data += '\n+{}+'.format('-' * len(self.nodes[0]))
return data