Update
[beaver.git] / maze.py
1 #!/usr/bin/env python
2
3 # Any copyright is dedicated to the Public Domain.
4 # https://creativecommons.org/publicdomain/zero/1.0/
5
6 # Written by Francois Fleuret <francois@fleuret.org>
7
8 import torch, torchvision
9
10 ######################################################################
11
12 v_empty, v_wall, v_start, v_goal, v_path = 0, 1, 2, 3, 4
13
14
15 def create_maze(h=11, w=17, nb_walls=8):
16     a, k = 0, 0
17
18     while k < nb_walls:
19         while True:
20             if a == 0:
21                 m = torch.zeros(h, w, dtype=torch.int64)
22                 m[0, :] = 1
23                 m[-1, :] = 1
24                 m[:, 0] = 1
25                 m[:, -1] = 1
26
27             r = torch.rand(4)
28
29             if r[0] <= 0.5:
30                 i1, i2, j = (
31                     int((r[1] * h).item()),
32                     int((r[2] * h).item()),
33                     int((r[3] * w).item()),
34                 )
35                 i1, i2, j = i1 - i1 % 2, i2 - i2 % 2, j - j % 2
36                 i1, i2 = min(i1, i2), max(i1, i2)
37                 if i2 - i1 > 1 and i2 - i1 <= h / 2 and m[i1 : i2 + 1, j].sum() <= 1:
38                     m[i1 : i2 + 1, j] = 1
39                     break
40             else:
41                 i, j1, j2 = (
42                     int((r[1] * h).item()),
43                     int((r[2] * w).item()),
44                     int((r[3] * w).item()),
45                 )
46                 i, j1, j2 = i - i % 2, j1 - j1 % 2, j2 - j2 % 2
47                 j1, j2 = min(j1, j2), max(j1, j2)
48                 if j2 - j1 > 1 and j2 - j1 <= w / 2 and m[i, j1 : j2 + 1].sum() <= 1:
49                     m[i, j1 : j2 + 1] = 1
50                     break
51             a += 1
52
53             if a > 10 * nb_walls:
54                 a, k = 0, 0
55
56         k += 1
57
58     return m
59
60
61 ######################################################################
62
63
64 def compute_distance(walls, goal_i, goal_j):
65     max_length = walls.numel()
66     dist = torch.full_like(walls, max_length)
67
68     dist[goal_i, goal_j] = 0
69     pred_dist = torch.empty_like(dist)
70
71     while True:
72         pred_dist.copy_(dist)
73         d = (
74             torch.cat(
75                 (
76                     dist[None, 1:-1, 0:-2],
77                     dist[None, 2:, 1:-1],
78                     dist[None, 1:-1, 2:],
79                     dist[None, 0:-2, 1:-1],
80                 ),
81                 0,
82             ).min(dim=0)[0]
83             + 1
84         )
85
86         dist[1:-1, 1:-1] = torch.min(dist[1:-1, 1:-1], d)
87         dist = walls * max_length + (1 - walls) * dist
88
89         if dist.equal(pred_dist):
90             return dist * (1 - walls)
91
92
93 ######################################################################
94
95
96 def compute_policy(walls, goal_i, goal_j):
97     distance = compute_distance(walls, goal_i, goal_j)
98     distance = distance + walls.numel() * walls
99
100     value = distance.new_full((4,) + distance.size(), walls.numel())
101     value[0, :, 1:] = distance[:, :-1]
102     value[1, :, :-1] = distance[:, 1:]
103     value[2, 1:, :] = distance[:-1, :]
104     value[3, :-1, :] = distance[1:, :]
105
106     proba = (value.min(dim=0)[0][None] == value).float()
107     proba = proba / proba.sum(dim=0)[None]
108     proba = proba * (1 - walls) + walls.float() / 4
109
110     return proba
111
112
113 def stationary_density(policy, start_i, start_j):
114     probas = policy.new_zeros(policy.size()[:-1])
115     pred_probas = probas.clone()
116     probas[start_i, start_j] = 1.0
117
118     while not pred_probas.equal(probas):
119         pred_probas.copy_(probas)
120         probas.zero_()
121         probas[1:, :] = pred_probas[:-1, :] * policy[0, :-1, :]
122         probas[:-1, :] = pred_probas[1:, :] * policy[1, 1:, :]
123         probas[:, 1:] = pred_probas[:, :-1] * policy[2, :, :-1]
124         probas[:, :-1] = pred_probas[:, 1:] * policy[3, :, 1:]
125         probas[start_i, start_j] = 1.0
126
127
128 ######################################################################
129
130
131 def mark_path(walls, i, j, goal_i, goal_j, policy):
132     action = torch.distributions.categorical.Categorical(
133         policy.permute(1, 2, 0)
134     ).sample()
135     n, nmax = 0, walls.numel()
136     while i != goal_i or j != goal_j:
137         di, dj = [(0, -1), (0, 1), (-1, 0), (1, 0)][action[i, j]]
138         i, j = i + di, j + dj
139         assert walls[i, j] == 0
140         walls[i, j] = v_path
141         n += 1
142         assert n < nmax
143
144
145 def path_correctness(mazes, paths):
146     still_ok = (mazes - (paths * (paths < 4))).view(mazes.size(0), -1).abs().sum(1) == 0
147     reached = still_ok.new_zeros(still_ok.size())
148     current, pred_current = paths.clone(), paths.new_zeros(paths.size())
149     goal = (mazes == v_goal).long()
150     while not pred_current.equal(current):
151         pred_current.copy_(current)
152         u = (current == v_start).long()
153         possible_next = (
154             u[:, 2:, 1:-1] + u[:, 0:-2, 1:-1] + u[:, 1:-1, 2:] + u[:, 1:-1, 0:-2] > 0
155         ).long()
156         u = u[:, 1:-1, 1:-1]
157         reached += ((goal[:, 1:-1, 1:-1] * possible_next).sum((1, 2)) == 1) * (
158             (current == v_path).sum((1, 2)) == 0
159         )
160         current[:, 1:-1, 1:-1] = (1 - u) * current[:, 1:-1, 1:-1] + (
161             v_start - v_path
162         ) * (possible_next * (current[:, 1:-1, 1:-1] == v_path))
163         still_ok *= (current == v_start).sum((1, 2)) <= 1
164
165     return still_ok * reached
166
167
168 ######################################################################
169
170
171 def create_maze_data(
172     nb, height=11, width=17, nb_walls=8, dist_min=10, progress_bar=lambda x: x
173 ):
174     mazes = torch.empty(nb, height, width, dtype=torch.int64)
175     paths = torch.empty(nb, height, width, dtype=torch.int64)
176     policies = torch.empty(nb, 4, height, width)
177
178     for n in progress_bar(range(nb)):
179         maze = create_maze(height, width, nb_walls)
180         i = (maze == v_empty).nonzero()
181         while True:
182             start, goal = i[torch.randperm(i.size(0))[:2]]
183             if (start - goal).abs().sum() >= dist_min:
184                 break
185         start_i, start_j, goal_i, goal_j = start[0], start[1], goal[0], goal[1]
186
187         policy = compute_policy(maze, goal_i, goal_j)
188         path = maze.clone()
189         mark_path(path, start_i, start_j, goal_i, goal_j, policy)
190         maze[start_i, start_j] = v_start
191         maze[goal_i, goal_j] = v_goal
192         path[start_i, start_j] = v_start
193         path[goal_i, goal_j] = v_goal
194
195         mazes[n] = maze
196         paths[n] = path
197         policies[n] = policy
198
199     return mazes, paths, policies
200
201
202 ######################################################################
203
204
205 def save_image(
206     name,
207     mazes,
208     target_paths=None,
209     predicted_paths=None,
210     score_paths=None,
211     path_correct=None,
212 ):
213     colors = torch.tensor(
214         [
215             [255, 255, 255],  # empty
216             [0, 0, 0],  # wall
217             [0, 255, 0],  # start
218             [127, 127, 255],  # goal
219             [255, 0, 0],  # path
220         ]
221     )
222
223     mazes = mazes.cpu()
224
225     c_mazes = (
226         colors[mazes.reshape(-1)].reshape(mazes.size() + (-1,)).permute(0, 3, 1, 2)
227     )
228
229     imgs = c_mazes.unsqueeze(1)
230
231     if target_paths is not None:
232         target_paths = target_paths.cpu()
233
234         c_target_paths = (
235             colors[target_paths.reshape(-1)]
236             .reshape(target_paths.size() + (-1,))
237             .permute(0, 3, 1, 2)
238         )
239
240         imgs = torch.cat((imgs, c_target_paths.unsqueeze(1)), 1)
241
242     if predicted_paths is not None:
243         predicted_paths = predicted_paths.cpu()
244         c_predicted_paths = (
245             colors[predicted_paths.reshape(-1)]
246             .reshape(predicted_paths.size() + (-1,))
247             .permute(0, 3, 1, 2)
248         )
249         imgs = torch.cat((imgs, c_predicted_paths.unsqueeze(1)), 1)
250
251     if score_paths is not None:
252         score_paths = score_paths.cpu()
253         c_score_paths = score_paths.unsqueeze(1).expand(-1, 3, -1, -1)
254         c_score_paths = (
255             c_score_paths * colors[4].reshape(1, 3, 1, 1)
256             + (1 - c_score_paths) * colors[0].reshape(1, 3, 1, 1)
257         ).long()
258         c_score_paths = c_score_paths * (mazes.unsqueeze(1) == v_empty) + c_mazes * (
259             mazes.unsqueeze(1) != v_empty
260         )
261         imgs = torch.cat((imgs, c_score_paths.unsqueeze(1)), 1)
262
263     # NxKxCxHxW
264     if path_correct is None:
265         path_correct = torch.zeros(imgs.size(0)) <= 1
266     path_correct = path_correct.cpu().long().view(-1, 1, 1, 1)
267     img = torch.tensor([224, 224, 224]).view(1, -1, 1, 1) * path_correct + torch.tensor(
268         [255, 0, 0]
269     ).view(1, -1, 1, 1) * (1 - path_correct)
270     img = img.expand(
271         -1, -1, imgs.size(3) + 2, 1 + imgs.size(1) * (1 + imgs.size(4))
272     ).clone()
273     for k in range(imgs.size(1)):
274         img[
275             :,
276             :,
277             1 : 1 + imgs.size(3),
278             1 + k * (1 + imgs.size(4)) : 1 + k * (1 + imgs.size(4)) + imgs.size(4),
279         ] = imgs[:, k]
280
281     img = img.float() / 255.0
282
283     torchvision.utils.save_image(img, name, nrow=4, padding=1, pad_value=224.0 / 256)
284
285
286 ######################################################################
287
288 if __name__ == "__main__":
289     device = torch.device("cuda" if torch.cuda.is_available() else "cpu")
290     mazes, paths = create_maze_data(8)
291     mazes, paths = mazes.to(device), paths.to(device)
292     save_image("test.png", mazes, paths, paths)
293     print(path_correctness(mazes, paths))
294
295 ######################################################################