迷路を自動で作って、自動で解く、そんなプログラムを作りたいと前々から思っていました。
試行錯誤しながら作ってみると、なんと、作るのも解くのも同じアルゴリズムでできることが分かりました。
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つなので以下にも出しておきます。
"""
迷路生成、迷路解きプログラム
"""
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)
コメントを残す