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_densities(mazes, policies):
 114     start = (mazes == v_start).nonzero(as_tuple=True)
 115     probas = mazes.new_zeros(mazes.size())
 116     pred_probas = probas.clone()
 117     probas[start] = 1.0
 118
 119     while not pred_probas.equal(probas):
 120         pred_probas.copy_(probas)
 121         probas.zero_()
 122         probas[:, 1:, :] = pred_probas[:, :-1, :] * policies[:, 0, :-1, :]
 123         probas[:, :-1, :] = pred_probas[:, 1:, :] * policies[:, 1, 1:, :]
 124         probas[:, :, 1:] = pred_probas[:, :, :-1] * policies[:, 2, :, :-1]
 125         probas[:, :, :-1] = pred_probas[:, :, 1:] * policies[:, 3, :, 1:]
 126         probas[start] = 1.0
 127
 128     return probas
 129
 130
 131 ######################################################################
 132
 133
 134 def mark_path(walls, i, j, goal_i, goal_j, policy):
 135     action = torch.distributions.categorical.Categorical(
 136         policy.permute(1, 2, 0)
 137     ).sample()
 138     n, nmax = 0, walls.numel()
 139     while i != goal_i or j != goal_j:
 140         di, dj = [(0, -1), (0, 1), (-1, 0), (1, 0)][action[i, j]]
 141         i, j = i + di, j + dj
 142         assert walls[i, j] == 0
 143         walls[i, j] = v_path
 144         n += 1
 145         assert n < nmax
 146
 147
 148 def path_correctness(mazes, paths):
 149     still_ok = (mazes - (paths * (paths < 4))).view(mazes.size(0), -1).abs().sum(1) == 0
 150     reached = still_ok.new_zeros(still_ok.size())
 151     current, pred_current = paths.clone(), paths.new_zeros(paths.size())
 152     goal = (mazes == v_goal).long()
 153     while not pred_current.equal(current):
 154         pred_current.copy_(current)
 155         u = (current == v_start).long()
 156         possible_next = (
 157             u[:, 2:, 1:-1] + u[:, 0:-2, 1:-1] + u[:, 1:-1, 2:] + u[:, 1:-1, 0:-2] > 0
 158         ).long()
 159         u = u[:, 1:-1, 1:-1]
 160         reached += ((goal[:, 1:-1, 1:-1] * possible_next).sum((1, 2)) == 1) * (
 161             (current == v_path).sum((1, 2)) == 0
 162         )
 163         current[:, 1:-1, 1:-1] = (1 - u) * current[:, 1:-1, 1:-1] + (
 164             v_start - v_path
 165         ) * (possible_next * (current[:, 1:-1, 1:-1] == v_path))
 166         still_ok *= (current == v_start).sum((1, 2)) <= 1
 167
 168     return still_ok * reached
 169
 170
 171 ######################################################################
 172
 173
 174 def create_maze_data(
 175     nb, height=11, width=17, nb_walls=8, dist_min=10, progress_bar=lambda x: x
 176 ):
 177     mazes = torch.empty(nb, height, width, dtype=torch.int64)
 178     paths = torch.empty(nb, height, width, dtype=torch.int64)
 179     policies = torch.empty(nb, 4, height, width)
 180
 181     for n in progress_bar(range(nb)):
 182         maze = create_maze(height, width, nb_walls)
 183         i = (maze == v_empty).nonzero()
 184         while True:
 185             start, goal = i[torch.randperm(i.size(0))[:2]]
 186             if (start - goal).abs().sum() >= dist_min:
 187                 break
 188         start_i, start_j, goal_i, goal_j = start[0], start[1], goal[0], goal[1]
 189
 190         policy = compute_policy(maze, goal_i, goal_j)
 191         path = maze.clone()
 192         mark_path(path, start_i, start_j, goal_i, goal_j, policy)
 193         maze[start_i, start_j] = v_start
 194         maze[goal_i, goal_j] = v_goal
 195         path[start_i, start_j] = v_start
 196         path[goal_i, goal_j] = v_goal
 197
 198         mazes[n] = maze
 199         paths[n] = path
 200         policies[n] = policy
 201
 202     return mazes, paths, policies
 203
 204
 205 ######################################################################
 206
 207
 208 def save_image(
 209     name,
 210     mazes,
 211     target_paths=None,
 212     predicted_paths=None,
 213     score_paths=None,
 214     path_correct=None,
 215 ):
 216     colors = torch.tensor(
 217         [
 218             [255, 255, 255],  # empty
 219             [0, 0, 0],  # wall
 220             [0, 255, 0],  # start
 221             [127, 127, 255],  # goal
 222             [255, 0, 0],  # path
 223         ]
 224     )
 225
 226     mazes = mazes.cpu()
 227
 228     c_mazes = (
 229         colors[mazes.reshape(-1)].reshape(mazes.size() + (-1,)).permute(0, 3, 1, 2)
 230     )
 231
 232     imgs = c_mazes.unsqueeze(1)
 233
 234     if target_paths is not None:
 235         target_paths = target_paths.cpu()
 236
 237         c_target_paths = (
 238             colors[target_paths.reshape(-1)]
 239             .reshape(target_paths.size() + (-1,))
 240             .permute(0, 3, 1, 2)
 241         )
 242
 243         imgs = torch.cat((imgs, c_target_paths.unsqueeze(1)), 1)
 244
 245     if predicted_paths is not None:
 246         predicted_paths = predicted_paths.cpu()
 247         c_predicted_paths = (
 248             colors[predicted_paths.reshape(-1)]
 249             .reshape(predicted_paths.size() + (-1,))
 250             .permute(0, 3, 1, 2)
 251         )
 252         imgs = torch.cat((imgs, c_predicted_paths.unsqueeze(1)), 1)
 253
 254     if score_paths is not None:
 255         score_paths = score_paths.cpu()
 256         c_score_paths = score_paths.unsqueeze(1).expand(-1, 3, -1, -1)
 257         c_score_paths = (
 258             c_score_paths * colors[4].reshape(1, 3, 1, 1)
 259             + (1 - c_score_paths) * colors[0].reshape(1, 3, 1, 1)
 260         ).long()
 261         c_score_paths = c_score_paths * (mazes.unsqueeze(1) == v_empty) + c_mazes * (
 262             mazes.unsqueeze(1) != v_empty
 263         )
 264         imgs = torch.cat((imgs, c_score_paths.unsqueeze(1)), 1)
 265
 266     # NxKxCxHxW
 267     if path_correct is None:
 268         path_correct = torch.zeros(imgs.size(0)) <= 1
 269     path_correct = path_correct.cpu().long().view(-1, 1, 1, 1)
 270     img = torch.tensor([224, 224, 224]).view(1, -1, 1, 1) * path_correct + torch.tensor(
 271         [255, 0, 0]
 272     ).view(1, -1, 1, 1) * (1 - path_correct)
 273     img = img.expand(
 274         -1, -1, imgs.size(3) + 2, 1 + imgs.size(1) * (1 + imgs.size(4))
 275     ).clone()
 276     for k in range(imgs.size(1)):
 277         img[
 278             :,
 279             :,
 280             1 : 1 + imgs.size(3),
 281             1 + k * (1 + imgs.size(4)) : 1 + k * (1 + imgs.size(4)) + imgs.size(4),
 282         ] = imgs[:, k]
 283
 284     img = img.float() / 255.0
 285
 286     torchvision.utils.save_image(img, name, nrow=4, padding=1, pad_value=224.0 / 256)
 287
 288
 289 ######################################################################
 290
 291 if __name__ == "__main__":
 292     device = torch.device("cuda" if torch.cuda.is_available() else "cpu")
 293     mazes, paths = create_maze_data(8)
 294     mazes, paths = mazes.to(device), paths.to(device)
 295     save_image("test.png", mazes, paths, paths)
 296     print(path_correctness(mazes, paths))
 297
 298 ######################################################################