迷路を自動で作って、自動で解く、そんなプログラムを作りたいと前々から思っていました。
試行錯誤しながら作ってみると、なんと、作るのも解くのも同じアルゴリズムでできることが分かりました。
youtube 動画にもupしました。こちらは迷路のサイズを変えながら、迷路を作って、それを解く、を繰り返します。
プログラムは、こちら
https://github.com/itoshin-tech/maze
迷路を生成する方法
それでは迷路を作る方法を説明します。まず、fieldという2次元の配列変数を考え、ここに道を作っていくとします。
fieldの要素は初めは全て0です。0をブランクと呼ぶことにします。ここに、道のid（2, 3, 4…）で書き換えることで道を作っていきます。idが2からなのは、迷路を解く方法と整合性を得るためで深い意味はありません。
まず、スタート地点をランダムに決め、その要素を2にします。そして、上下左右方向に一つ飛ばした先のセルを調べます。セルがブランク(0)であれば、そちらに道を伸ばすことができます。進める方向が複数ある場合には、ランダムで1つの方向を選びます。
選んだ方向に進みます。伸ばした道にはidである2を代入します。ここからまた同様に、4方向を調べ、ブランクの方向に道を伸ばします。
これを繰り返しながら道を伸ばしていきますが、いずれ進めなくなります。
進めなくなったら、作ってきた道で、分岐方向を選んできた座標を確認します（オレンジの枠）。そして、矢印で示した(x=1, y=5)の位置から分岐を伸ばそうと考えます。
ここで少しプログラムのことを考えます。
作る関数は、以下のようなfill_with_road()という関数です。この関数は、(x, y)の地点から道を伸ばし、0の領域を道で満たす、という働きを想定しています。
はじめから考えて、x=3, y=3 のスタート地点をセットして、fill_with_road(x=3, y=3, id)を実行したと想定します。そして、はじめの一本道を伸ばし終えて、(x=1, y=5)から分岐を伸ばすフェーズになっているとします。まだ、fill_with_road(x=3, y=3, id)の中です。
(x=1, y=5)から分岐を作るために、この箇所をスタート地点としたfill_with_road(x=1, y=5, id=id+1)を実行します。idは今のidから一つ増やすします（id を変えるのは単にアルゴリズムの動きを知るためです）。しつこいようですが、これはfill_with_road(x=3, y=3, id)の中で実行します。
同様に、fill_with_road(x=3, y=3, id)の中で、全ての分岐ができる可能性のあるオレンジの箇所から、fill_with_roadを実行します。
これでアルゴリズムの概要は終わりです。
このようにすることで、分岐の先でも、さらなる分岐が起き、その先でも分岐を起こすことができるのです。理論上は、何段階でも分岐を起こすことができるのです。
ややこしいのですが面白いですよね。このように、関数の中で自分自身の関数を呼ぶ方法を再帰と呼びます。
今の例の続きを考えると、3の道が作られ、更に下のオレンジの枠で分岐が起こり、4の道が伸びていきます。ここで新しい道を作るスペースがなくなるので迷路が完成します。
あとは、field の要素で1以上の部分を全て1に直して迷路が完成です。
1を迷路の道、0を壁と解釈します。スタート地点とゴール地点はどこにおいても成り立ちます。
実は、迷路を解くときにもfill_with_road()が使えます。1の部分をbrankと解釈し、そこに道を充填していけばよいのです。
迷路を解く方法
迷路を解く方法です。左上がスタート、右下がゴールだとします。今度は、1をブランクとします。1の上にid=2, 3, 4, … の道を作っていくことを考えます。
迷路生成時ではブランクの空間は広い長方形でしたが、今回のブランクは迷路のくねくねした廊下の形状です。しかし、fill_with_roadは、単に隙間があったらそこに道を伸ばしていくアルゴリズムなので、ブランクの形状には関係なく動作します。
よって、ここでも、迷路生成時とほとんど同じアルゴリズムで道を伸ばしていけば、いつかゴールにまで道（？）が到達します。
ただし、前回使ったfill_with_roadの以下の部分だけ、変更します。
隣り合った4方向でbrank=1の方向に道を進めます。行ける方向が分かったら、2マス進めます。この要領で道を長くしていきます。
結果、以下のような行き止まりにたどり着きました。ここからは、方向を決定した箇所全てにおいて分岐を試します。
分岐をするときにはidに1を加えるとすれば、以下のような道が生成され、ゴールにたどり着くことができます。
以上で迷路の作り方・解き方の説明は終わりです。読んでいただきありがとうございました。
プログラムは github にもupload しています。
https://github.com/itoshin-tech/maze
ファイルは1つなので以下にも出しておきます。
|
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 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 |
""" 迷路生成、迷路解きプログラム """ import numpy as np import random import cv2 import matplotlib.pyplot as plt import seaborn as sns import sys class MazeCreater(): """ 迷路を作るクラス """ def __init__(self, size_w=10, size_h=5): """ Parameters ---------- size_w: int 迷路の横サイズ（分岐できる点の数） size_h: int 迷路の縦サイズ """ self.size_w = size_w self.size_h = size_h # 道生成クラスのインスタンス生成 # 引数 max_col は画像出力時の色の数 self.roadfiller =RoadFiller( max_col=size_w, ) def generate_maze(self, is_show=True, unit=10, delay=100): """ 迷路を生成する 内部で使用するRoadFillerクラスが、実際に迷路を生成している Parameters ---------- unit: int 画像生成時のセルサイズ delay: int アニメーション時の遅延(ms) Returns ------- field_out: 2d numpuy.array 生成した迷路 0が壁 1が通路 """ # field のサイズ n_w = 2 * self.size_w + 1 n_h = 2 * self.size_h + 1 # field をブランク0で満たす field = np.zeros((n_h, n_w), dtype=np.uint8) # 道の開始時のid (画面表示の都合上2から開始) road_id = 2 # スタート地点をランダムで決める x = 2* np.random.randint(0, self.size_w) + 1 y = 2* np.random.randint(0, self.size_h) + 1 # 道の生成 field = self.roadfiller.fill_with_road( field, x, y, id=road_id, mode='create', is_show=is_show, delay=delay, unit=unit, ) # 道のid を全て1に変換して出力 field_out = field.copy() field_out[field > 0] = 1 return field_out class MazeSolver: """ 迷路を解くクラス """ def __init__(self, field, start, goal): self.field = field.copy() self.start_xy = start self.goal_xy = goal self.xy = self.start_xy max_col = int(self.field.shape[1] / 2) self.roadfiller =RoadFiller( max_col=max_col, goal_xy=goal, start_xy=start, ) def solve_maze(self, is_show=True, unit=10, delay=100): """ 通路を0、壁を1とする 通路に沿って進む、分岐点に来たらゴールが近くなる方を選ぶ 迷路生成クラスと同じ、RoadFillerクラスを内部で使用 Parameters ---------- unit: int 画像生成時のセルサイズ delay: int アニメーション時の遅延(ms) Returns ------- field_out: 2d numpuy.array 解いた迷路 0が壁 1が通路 2以上が通った軌跡 """ field = self.field.copy() x, y = self.start_xy # 道のidは2から開始 road_id = 2 field[y, x] = road_id # 道の生成ds field_out = self.roadfiller.fill_with_road( field, x, y, id=road_id, mode='solve', is_show=is_show, delay=delay, unit=unit, ) return field_out class RoadFiller: """ 指定したidの領域を、道を分岐させながら道で満たすクラス """ def __init__(self, max_col=10, mode='create', goal_xy=None, start_xy=None): self.render = Render( max_col=max_col, mode=mode, goal_xy=goal_xy, start_xy=start_xy, ) self.reach_goal = False self.goal_xy = goal_xy self.start_xy = start_xy def fill_with_road( self, field, x, y, id=1, mode='create', is_show=True, delay=100, unit=10, ): """ 0の領域を道で満たす 迷路を生成する本体 迷路を解くときにも使用 Parameters ---------- field: 2d numpy.array 迷路のフィールド 0の領域に道が作られる x, y: int スタート地点 id: int 作る道のid mode: str 'create': 迷路を作る 'solve': 迷路を解く is_show: bool True: アニメーションを出す Returens -------- field: 2d numpy.array 道が生成されたフィールド """ # ゴールに到達したら終了 if self.reach_goal is True: return field self.field = field.copy() self.delay = delay self.unit = unit # 開始地点が0なら id とする if self.field[y, x] == 0: self.field[y, x] = id # xy の履歴 (B)で使用 xy_history = [(x, y)] # (A) while True: # x, y の周囲を調べて、道が伸ばせるならば伸ばす res, x, y, fields = self.extend_road( self.field, x, y, id, mode=mode, ) self.field = fields[-1] if res == 'stretched': # 道を伸ばした場合は、xy を記録して繰り返す xy_history.append((x, y)) # 描画 if is_show is True: if self.delay > 50: for ff in fields: self.render.draw( ff, delay=self.delay, unit=self.unit, ) else: self.render.draw( fields[-1], delay=self.delay, unit=self.unit, ) # ゴール判定 if mode == 'solve': if x == self.goal_xy[0] and y == self.goal_xy[1]: # ゴールに辿り着いたら終了 self.reach_goal = True return self.field continue # 行き止まりに来たら # ループから抜けて(B)へ if res == 'deadend': break # (B) # 履歴を一つずつもどった地点から、行き止まりまで道を伸ばす xy_history.pop(-1) xy_history.reverse() for xy in xy_history: x = xy[0] y = xy[1] self.fill_with_road( self.field, x, y, id=id + 1, mode=mode, is_show=is_show, delay=self.delay, unit=self.unit, ) return self.field def extend_road( self, field, x, y, id, mode='create', ): """ fieldの(x,y)を中心として、 上下左右の4方向を調べ、 id_brank があったら道を伸ばす 'create'のときid_brank = 0 'solve'のときid_brank = 1 Parameters ---------- field: 2d numpy.array フィールド x, y: int 開始地点 id: int 道のid mode: str 'create': 迷路を作る 'solve': 迷路を解く Returens -------- res: str 'stretched': 道を伸ばした 'deaded': 行き止まりだった next_x, next_y: int 'streatched' で伸ばした先の座標 fields: list of 2d numpy.array 段階的に道を伸ばしたときのfieldのリスト （アニメーション用） """ if mode == 'create': id_brank = 0 elif mode == 'solve': id_brank = 1 else: raise ValueError('modeが違います') # 4方向のx, y の増加分 dd = [ (1, 0), (-1, 0), (0, 1), (0, -1), ] # 変数準備 n_h, n_w = field.shape[:2] next_field = field.copy() pre_field = field.copy() # 4方向の状態を調べる dd_res = [''] * 4 # 結果の格納変数 for id_dir in range(4): x1 = x + dd[id_dir][0] * 2 y1 = y + dd[id_dir][1] * 2 x0 = x + dd[id_dir][0] y0 = y + dd[id_dir][1] if x1 < 0 or n_w <= x1: # 横方向のはみ出し dd_res[id_dir] = 'out' continue if y1 < 0 or n_h <= y1: # 縦方向のはみ出し dd_res[id_dir] = 'out' continue if (mode == 'create' and field[y1, x1] == id_brank) or \ (mode == 'solve' and field[y0, x0] == id_brank): # ブランク(道を伸ばせる) dd_res[id_dir] = 'brank' continue # 道を伸ばせない dd_res[id_dir] = 'no' # ブランクあったらそこに道を伸ばす ids_dir = [i for i, x in enumerate(dd_res) if x == 'brank'] if len(ids_dir) > 0: res = 'stretched' if mode == 'create': # ランダムで選ぶ id_dir = random.sample(ids_dir, 1)[0] elif mode == 'solve': # ゴールに近くなる方を選ぶ dist = [] for i, id_dir in enumerate(ids_dir): x0 = x + dd[id_dir][0] y0 = y + dd[id_dir][1] dist.append((x0 - self.goal_xy[0])**2 + (y0 - self.goal_xy[1]) ** 2) iid = dist.index(min(dist)) # 最小の要素のindex を返す id_dir = ids_dir[iid] else: raise ValueError('modeが違います') x1 = x + dd[id_dir][0] * 2 y1 = y + dd[id_dir][1] * 2 x0 = x + dd[id_dir][0] y0 = y + dd[id_dir][1] pre_field[y0, x0] = id # アニメーション用の途中状態 next_field[y1, x1] = id next_field[y0, x0] = id # 最終的な状態 next_x = x1 next_y = y1 fields = [pre_field, next_field] return res, next_x, next_y, fields # 行き止まり res = 'deadend' next_x = None next_y = None fields = [pre_field, next_field] return res, next_x, next_y, fields class Render(): """ 画像生成、表示 """ def __init__( self, max_col=10, goal_xy=None, start_xy=None, mode='create', ): self.max_col = max_col # 色の種類の上限 self.goal_xy=goal_xy self.start_xy=start_xy self.mode=mode self.colorpalette = sns.color_palette( "hls", n_colors = self.max_col, ) def draw( self, field, unit=10, is_show=True, delay=0, unicol=None, start_xy=None, goal_xy=None, ): """ 迷路の画像生成 """ if start_xy is not None: self.start_xy = start_xy if goal_xy is not None: self.goal_xy = goal_xy # field をunit分拡大 val = field max_val = np.max(val) val = val.astype(dtype=np.uint8) val = cv2.resize( val, dsize=(0, 0), fx=unit, fy=unit, interpolation=cv2.INTER_NEAREST, ) #--- for video fix size """ val_bak = np.ones((440, 840), dtype=np.uint8) * 80 h, w = val.shape[:2] val_bak[:h, :w] = val val = val_bak """ # ---- img_r = val.copy() img_g = val.copy() img_b = val.copy() # 道をid毎に色を付けて描画 for v in range(max_val + 1): if self.mode == 'create': if v == 0: # ブランク（道を伸ばす） col = (80, 80, 80) elif v == 1: # 壁（道を伸ばす） col = (255, 255, 255) else: ic = v % self.max_col col = np.array(self.colorpalette[ic]) * 255 elif self.mode == 'solve': if v == 0: # 壁 col = (80, 80, 80) elif v == 1: # ブランク col = (255, 255, 255) else: ic = v % self.max_col col = np.array(self.colorpalette[ic]) * 255 else: raise ValueError('mode が違います') img_r[val == v] = col[0] img_g[val == v] = col[1] img_b[val == v] = col[2] h, w = val.shape img = np.zeros((h, w, 3), dtype=np.uint8) img[:, :, 0] = img_b img[:, :, 1] = img_g img[:, :, 2] = img_r # スタート地点の目印 if self.start_xy is not None: x = int(self.start_xy[0] * unit + unit / 2) y = int(self.start_xy[1] * unit + unit / 2) r = int(0.45 * unit) col = (100, 100, 200) img = cv2.circle(img, (x, y), r, col, -1) # ゴール地点の目印 if self.goal_xy is not None: x = int(self.goal_xy[0] * unit + unit / 2) y = int(self.goal_xy[1] * unit + unit / 2) r = int(0.45 * unit) col = (100, 200, 100) img = cv2.circle(img, (x, y), r, col, -1) # アニメーション表示 if is_show: cv2.imshow('img', img) INPUT = cv2.waitKey(delay) & 0xFF if INPUT == ord('q'): sys.exit() return img if __name__ == '__main__': prms = { 0: (10, 5, 40, 100), 1: (20, 10, 20, 50), 2: (40, 20, 10, 1), } # for video """ cv2.imshow('img', np.ones((440, 840, 3), dtype=np.uint8) * 80) cv2.waitKey(0) """ for i in range(100): # パラメータの取得 w, h, u, d = prms[i % len(prms)] # 迷路生成クラスのインスタンス生成 maze = MazeCreater(size_w=w, size_h=h) # 迷路をアニメーションさせながら生成 field = maze.generate_maze(is_show=True, unit=u, delay=d) # スタートとゴール地点を作成 f_h, f_w = field.shape[:2] start_xy = (1, 1) goal_xy = (f_w - 2, f_h - 2) # 完成した迷路を表示 img = maze.roadfiller.render.draw( field, unit=u, delay=1000, unicol=(255, 255, 255), start_xy=start_xy, goal_xy=goal_xy, ) # 迷路解きのインスタンス生成 solver = MazeSolver( field, start=start_xy, goal=goal_xy) # 迷路をアニメーションさせながら解く map = solver.solve_maze(is_show=True, unit=u, delay=d) # 解いた迷路を表示 solver.roadfiller.render.draw(map, unit=u, delay=1000) |
コメントを残す