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