3 # Any copyright is dedicated to the Public Domain.
4 # https://creativecommons.org/publicdomain/zero/1.0/
6 # Written by Francois Fleuret <francois@fleuret.org>
8 import torch, torchvision
10 ######################################################################
12 v_empty, v_wall, v_start, v_goal, v_path = 0, 1, 2, 3, 4
15 def create_maze(h=11, w=17, nb_walls=8):
21 m = torch.zeros(h, w, dtype=torch.int64)
31 int((r[1] * h).item()),
32 int((r[2] * h).item()),
33 int((r[3] * w).item()),
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:
42 int((r[1] * h).item()),
43 int((r[2] * w).item()),
44 int((r[3] * w).item()),
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:
61 ######################################################################
64 def compute_distance(walls, i, j):
65 max_length = walls.numel()
66 dist = torch.full_like(walls, max_length)
69 pred_dist = torch.empty_like(dist)
76 dist[None, 1:-1, 0:-2],
79 dist[None, 0:-2, 1:-1],
86 dist[1:-1, 1:-1] = torch.min(dist[1:-1, 1:-1], d)
87 dist = walls * max_length + (1 - walls) * dist
89 if dist.equal(pred_dist):
90 return dist * (1 - walls)
93 ######################################################################
96 def compute_policy(walls, i, j):
97 distance = compute_distance(walls, i, j)
98 distance = distance + walls.numel() * walls
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:, :]
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
113 ######################################################################
116 def mark_path(walls, i, j, goal_i, goal_j, policy):
117 action = torch.distributions.categorical.Categorical(
118 policy.permute(1, 2, 0)
120 n, nmax = 0, walls.numel()
121 while i != goal_i or j != goal_j:
122 di, dj = [(0, -1), (0, 1), (-1, 0), (1, 0)][action[i, j]]
123 i, j = i + di, j + dj
124 assert walls[i, j] == 0
130 def path_correctness(mazes, paths):
131 still_ok = (mazes - (paths * (paths < 4))).view(mazes.size(0), -1).abs().sum(1) == 0
132 reached = still_ok.new_zeros(still_ok.size())
133 current, pred_current = paths.clone(), paths.new_zeros(paths.size())
134 goal = (mazes == v_goal).long()
135 while not pred_current.equal(current):
136 pred_current.copy_(current)
137 u = (current == v_start).long()
139 u[:, 2:, 1:-1] + u[:, 0:-2, 1:-1] + u[:, 1:-1, 2:] + u[:, 1:-1, 0:-2] > 0
142 reached += ((goal[:, 1:-1, 1:-1] * possible_next).sum((1, 2)) == 1) * (
143 (current == v_path).sum((1, 2)) == 0
145 current[:, 1:-1, 1:-1] = (1 - u) * current[:, 1:-1, 1:-1] + (
147 ) * (possible_next * (current[:, 1:-1, 1:-1] == v_path))
148 still_ok *= (current == v_start).sum((1, 2)) <= 1
150 return still_ok * reached
153 ######################################################################
156 def create_maze_data(
157 nb, height=11, width=17, nb_walls=8, dist_min=10, progress_bar=lambda x: x
159 mazes = torch.empty(nb, height, width, dtype=torch.int64)
160 paths = torch.empty(nb, height, width, dtype=torch.int64)
161 policies = torch.empty(nb, 4, height, width)
163 for n in progress_bar(range(nb)):
164 maze = create_maze(height, width, nb_walls)
165 i = (maze == v_empty).nonzero()
167 start, goal = i[torch.randperm(i.size(0))[:2]]
168 if (start - goal).abs().sum() >= dist_min:
170 start_i, start_j, goal_i, goal_j = start[0], start[1], goal[0], goal[1]
172 policy = compute_policy(maze, goal_i, goal_j)
174 mark_path(path, start_i, start_j, goal_i, goal_j, policy)
175 maze[start_i, start_j] = v_start
176 maze[goal_i, goal_j] = v_goal
177 path[start_i, start_j] = v_start
178 path[goal_i, goal_j] = v_goal
184 return mazes, paths, policies
187 ######################################################################
194 predicted_paths=None,
198 colors = torch.tensor(
200 [255, 255, 255], # empty
203 [127, 127, 255], # goal
211 colors[mazes.reshape(-1)].reshape(mazes.size() + (-1,)).permute(0, 3, 1, 2)
214 imgs = c_mazes.unsqueeze(1)
216 if target_paths is not None:
217 target_paths = target_paths.cpu()
220 colors[target_paths.reshape(-1)]
221 .reshape(target_paths.size() + (-1,))
225 imgs = torch.cat((imgs, c_target_paths.unsqueeze(1)), 1)
227 if predicted_paths is not None:
228 predicted_paths = predicted_paths.cpu()
229 c_predicted_paths = (
230 colors[predicted_paths.reshape(-1)]
231 .reshape(predicted_paths.size() + (-1,))
234 imgs = torch.cat((imgs, c_predicted_paths.unsqueeze(1)), 1)
236 if score_paths is not None:
237 score_paths = score_paths.cpu()
238 c_score_paths = score_paths.unsqueeze(1).expand(-1, 3, -1, -1)
240 c_score_paths * colors[4].reshape(1, 3, 1, 1)
241 + (1 - c_score_paths) * colors[0].reshape(1, 3, 1, 1)
243 c_score_paths = c_score_paths * (mazes.unsqueeze(1) == v_empty) + c_mazes * (
244 mazes.unsqueeze(1) != v_empty
246 imgs = torch.cat((imgs, c_score_paths.unsqueeze(1)), 1)
249 if path_correct is None:
250 path_correct = torch.zeros(imgs.size(0)) <= 1
251 path_correct = path_correct.cpu().long().view(-1, 1, 1, 1)
252 img = torch.tensor([224, 224, 224]).view(1, -1, 1, 1) * path_correct + torch.tensor(
254 ).view(1, -1, 1, 1) * (1 - path_correct)
256 -1, -1, imgs.size(3) + 2, 1 + imgs.size(1) * (1 + imgs.size(4))
258 for k in range(imgs.size(1)):
262 1 : 1 + imgs.size(3),
263 1 + k * (1 + imgs.size(4)) : 1 + k * (1 + imgs.size(4)) + imgs.size(4),
266 img = img.float() / 255.0
268 torchvision.utils.save_image(img, name, nrow=4, padding=1, pad_value=224.0 / 256)
271 ######################################################################
273 if __name__ == "__main__":
274 device = torch.device("cuda" if torch.cuda.is_available() else "cpu")
275 mazes, paths = create_maze_data(8)
276 mazes, paths = mazes.to(device), paths.to(device)
277 save_image("test.png", mazes, paths, paths)
278 print(path_correctness(mazes, paths))
280 ######################################################################