-
Notifications
You must be signed in to change notification settings - Fork 0
/
fov.py
159 lines (131 loc) · 3.88 KB
/
fov.py
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
_octants = (( 1, 0, 0, 1),
( 0, 1, 1, 0),
( 0, -1, 1, 0),
(-1, 0, 0, 1),
(-1, 0, 0, -1),
( 0, -1, -1, 0),
( 0, 1, -1, 0),
( 1, 0, 0, -1))
def get_fov(tile_map, cx, cy, r):
height = len(tile_map)
width = len(tile_map[0])
fov = [[False] * width for i in range(height)]
# Visit the center, ignoring whether it is a wall.
fov[cy][cx] = True
# Maintain a stack of pending beams. Store each beam as a tuple:
#
# (min_x, min_y, max_y, min_dy, min_dx, max_dy, max_dx)
#
# min_x - The first column to scan.
# min_y, max_y - The first and last rows to scan.
# min_dy, min_dx - The start slope of the beam.
# max_dy, max_dx - The end slope of the beam.
#
# We track min_y and max_y to avoid scanning all the way from top to bottom
# for each column. Another alternative is to calculate min_y and max_y from
# the slopes.
stack = []
# Scan all octants.
for xx, xy, yx, yy in _octants:
# Push the root beam for this octant onto the stack.
stack.append((1, 0, 1, 0, 1, 1, 1))
while stack:
# Pop the next beam from the stack.
min_x, min_y, max_y, min_dy, min_dx, max_dy, max_dx = stack.pop()
for x in range(min_x, r + 1):
min_cell_dx, max_cell_dx = 2 * x + 1, 2 * x - 1
# Skip any cells that are completely below or above the beam,
# or completely outside its radius.
while (2 * min_y + 1) * min_dx <= min_dy * max_cell_dx:
min_y += 1
while (2 * max_y - 1) * max_dx >= max_dy * min_cell_dx:
max_y -= 1
while (2 * x - 1) ** 2 + (2 * max_y - 1) ** 2 >= (2 * r) ** 2:
max_y -= 1
# Scan the column from base to top.
any_walls = False
all_walls = True
old_wall = False
for y in range(min_y, max_y + 1):
# Transform to global coordinates and visit the cell.
_x = cx + x * xx + y * xy
_y = cy + x * yx + y * yy
if (_x < 0 or width <= _x or
_y < 0 or height <= _y):
wall = True
else:
fov[_y][_x] = True
wall = tile_map[_y][_x].blocks_view
#wall = visit(cx + x * xx + y * xy, cy + x * yx + y * yy)
if wall:
if not any_walls:
# We have found the first wall in the column. Save
# the old beam.
any_walls = True
old_max_y = max_y
old_max_dy, old_max_dx = max_dy, max_dx
if not old_wall:
# Initially assume that the new wall spans the rest
# of the column.
old_wall = True
max_y = y
max_dy, max_dx = 2 * y - 1, min_cell_dx
# The second to last cell in the column may block the
# last cell.
if (y == old_max_y - 1 and (2 * y + 1) * old_max_dx
> old_max_dy * max_cell_dx):
break
else:
if old_wall:
# We have finished scanning a wall.
old_wall = False
if not all_walls and x < r:
# The wall divides the column into two gaps.
# Push a child beam for the lower gap onto the
# stack.
stack.append((x + 1, min_y, max_y, min_dy,
min_dx, max_dy, max_dx))
# Initially assume that the new gap spans the rest
# of the column.
min_y, max_y = y, old_max_y
min_dy, min_dx = 2 * (y - 1) + 1, max_cell_dx
max_dy, max_dx = old_max_dy, old_max_dx
all_walls = False
if all_walls:
break
# Increment max_y for the next column.
max_y += 1
return fov
def line(x1, y1, x2, y2):
points = []
issteep = abs(y2-y1) > abs(x2-x1)
if issteep:
x1, y1 = y1, x1
x2, y2 = y2, x2
rev = False
if x1 > x2:
x1, x2 = x2, x1
y1, y2 = y2, y1
rev = True
deltax = x2 - x1
deltay = abs(y2-y1)
error = int(deltax / 2)
y = y1
ystep = None
if y1 < y2:
ystep = 1
else:
ystep = -1
for x in range(x1, x2 + 1):
if issteep:
points.append((y, x))
else:
points.append((x, y))
error -= deltay
if error < 0:
y += ystep
error += deltax
# Reverse the list if the coordinates were reversed
if rev:
points.reverse()
return points