先日Youtubeでとある動画を見ていたら簡単なアルゴリズムで迷路が作れちゃうというので実装してみました。
穴掘り法って?
(1)開始地点から上・下・左・右の4方向の開いている地点(外に突き抜けないように)に2マスずつ進みながら通路を作っていく。
(2)4方向全て行き止まりになってしまったら前のマスへ戻りそこから掘れる場所を掘っていく
これを繰り返すだけです。試しに9x9のマスで作ってみましょう。なおこれ以降座標とかは0オリジンで表します、あらかじめご了承ください。(＞_＜)
全てのマスを壁で埋めます。
任意の奇数頂点を選びスタート地点とします。
進む方向を上下左右からランダムで選びます,、今回は下に行きましょう。
この操作を繰り返していくと例えばこんなものになると思います。
これ以上進める場所が無くなってしまいました、どうしよう。
しかしまだ掘れる場所はありますね、前に戻って掘れる場所を掘りましょう。
あとはこれをやっていくだけです。
できました、簡単！
作ってみる
前提として今回はPython 3.7.3を使っています(楽なので)。また壁となる部分を#、通路となる部分は空白(スペース)で表します。
まず縦横"奇数"のマスを用意します、奇数というところが重要なポイントです。
今回は縦横どちらも31、スタート地点は(1,1)と固定でやっていきます。
height, width = 31, 31
maze_base = [["#"]*width for _ in range(height)]
スタート地点進むベクトルをあらかじめ入れます。
maze_base[1][1] = " " #初期地点
dx = [(1,2), (-1,-2), (0,0), (0,0)] #x軸のベクトル
dy = [(0,0), (0,0), (1,2), (-1,-2)] #y軸のベクトル
次に迷路製作部分のコートですが
・ランダムに方向を決める
・再帰を用いて前の座標に戻る
を簡単に行うためsys,randomモジュールを入れておきます。特にsysモジュールのsetrecursionlimitを使わないと101x101くらいの迷路を作る際に再帰回数制限に余裕で引っ掛かります。今回は大丈夫ですが。
def make_maze(ny, nx):
array = list(range(4))
random.shuffle(array) #ランダムに行く方向を決める
for i in array:
if ny+dy[i][1]<1 or ny+dy[i][1]>=height: #周りの壁を越えていたらスルー
continue
if nx+dx[i][1]<1 or nx+dx[i][1]>=width: #周りの壁を越えていたらスルー
continue
if maze_base[ny+dy[i][1]][nx+dx[i][1]]==" ": #2つ先のマスがすでに開いていたらスルー
continue
for j in range(2): #通路を掘る
maze_base[ny+dy[i][j]][nx+dx[i][j]]=" "
make_maze(ny+dy[i][1], nx+dx[i][1]) #掘った先のところに移動
終わりです。大きさ、開始地点を奇数にしたのはここのためです。これをしないと外壁をぶっちぎり仕様上全ての外壁を食べてしまいます。
これを使い動くように纏めると以下のようになります。
import random
import sys
setrecursionlimit(10**6)
height, width = 31, 31
maze_base = [["#"]*width for _ in range(height)]
maze_base[1][1] = " " #初期地点
dx = [(1,2), (-1,-2), (0,0), (0,0)] #x軸のベクトル
dy = [(0,0), (0,0), (1,2), (-1,-2)] #y軸のベクトル
def make_maze(ny, nx):
array = list(range(4))
random.shuffle(array) #ランダムに行く方向を決める
for i in array:
if ny+dy[i][1]<1 or ny+dy[i][1]>=height: #周りの壁を越えていたらスルー
continue
if nx+dx[i][1]<1 or nx+dx[i][1]>=width: #周りの壁を越えていたらスルー
continue
if maze_base[ny+dy[i][1]][nx+dx[i][1]]==" ": #2つ先のマスがすでに開いていたらスルー
continue
for j in range(2): #通路を掘る
maze_base[ny+dy[i][j]][nx+dx[i][j]] = " "
make_maze(ny+dy[i][1], nx+dx[i][1]) #掘った先のところに移動
make_maze(1, 1)
maze_base[1][1] = "S"
for i in maze_base:
print(*i)
結果
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
# S # # # #
# # # # # # # # # # # # # # # # # # # # # # # #
# # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # #
# # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # # # #
# # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # # #
# # # # # # # #
# # # # # # # # # # # # # # # # # # # # # # # #
# # # # # # # #
# # # # # # # # # # # # # # # # # # # # # # #
# # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # # #
# # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # # # #
# # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # #
# # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # # # # #
# # # # # # #
# # # # # # # # # # # # # # # # # # # # # # # # #
# # # # # # # # #
# # # # # # # # # # # # # # # # # # # # # # #
# # # # # # # #
# # # # # # # # # # # # # # # # # # # # # # #
# # # # # # # # # #
# # # # # # # # # # # # # # # # # # # #
# # # # # # #
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
すごい、これだけで迷路が作れてしまいました。感激ですね。
問題点(?)
・迷路としての難易度は低めかも...?(分岐点から行き止まりのの距離が必ずしも長いとは言えないため)
・ゴールが決められていない(迷路ですらないですね)
一つ目の解決方法は良くわかりませんでした。何か解決できる案などありましたら教えていただけるとありがたいです。
ゴールを作ろう
右下をゴールにするのもいいんですがそれだと道の途中にゴールができるなんてこともありなんだかなーって感じなのでルールみたいなのを決めました。
スタート地点から一番遠いところをゴール地点とします。
これしか思いつかなかったんです...。こちらも意見募集ですよろしくお願いします。
この方法を実現するには幅優先探索を用います。幅優先探索については@drken氏の記事がとても分かりやすいので一度は見てみると良いと思います。
BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜
またグリッド上の幅優先探索についても同氏が記事にされています、そちらもどうぞ。
Pythonではこれらのデータ構造を高速に実現できるようcollectionsモジュールにdequeというライブラリが用意されているのでそれを使います。deque、他の組み込み関数の計算量はこちらに書かれています。
以下が最長距離の座標を求めるコードです。ただ距離を更新していくだけです。
q = deque([(sy, sx)])
max_dist = 0 # 最長距離
gy, gx=1, 1 # ゴール地点
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
dist = [[-1]*width for _ in range(height)] # それぞれのマスの距離を持つ配列
dist[sy][sx] = 0
while q: # キューに要素がなくなるまで回す
y,x = q.popleft() #先頭から要素を取り出す
for i in range(4):
ny = y+dy[i]
nx = x+dx[i]
if ny<=0 or nx<=0 or ny+1==height or nx+1==width: #次に行くマスが壁だったらスルー
continue
if maze_base[ny][nx]=="#": #次に行くマスが壁だったらスルー
continue
if dist[ny][nx]==-1: # まだ通っていなかったら距離を更新
q.append((ny,nx))
dist[ny][nx] = dist[y][x]+1
if max_dist<dist[ny][nx]: # 最長距離を更新
gy,gx = ny,nx
max_dist = dist[ny][nx]
maze_base[gy][gx] = "G"
これを全て纏めると
import random
import sys
from collections import deque
setrecursionlimit(10**6)
height, width = 31, 31
maze_base = [["#"]*width for _ in range(height)]
maze_base[1][1] = " " #初期地点
dx = [(1,2), (-1,-2), (0,0), (0,0)] #x軸のベクトル
dy = [(0,0), (0,0), (1,2), (-1,-2)] #y軸のベクトル
def make_maze(ny, nx):
array = list(range(4))
random.shuffle(array) #ランダムに行く方向を決める
for i in array:
if ny+dy[i][1]<1 or ny+dy[i][1]>=height: #周りの壁を越えていたらスルー
continue
if nx+dx[i][1]<1 or nx+dx[i][1]>=width: #周りの壁を越えていたらスルー
continue
if maze_base[ny+dy[i][1]][nx+dx[i][1]]==" ": #2つ先のマスがすでに開いていたらスルー
continue
for j in range(2): #通路を掘る
maze_base[ny+dy[i][j]][nx+dx[i][j]] = " "
make_maze(ny+dy[i][1], nx+dx[i][1]) #掘った先のところに移動
make_maze(1, 1)
maze_base[1][1] = "S"
q = deque([(sy, sx)])
max_dist = 0 # 最長距離
gy, gx=1, 1 # ゴール地点
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
dist = [[-1]*width for _ in range(height)] # それぞれのマスの距離を持つ配列
dist[sy][sx] = 0
while q: # キューに要素がなくなるまで回す
y,x = q.popleft() #先頭から要素を取り出す
for i in range(4):
ny = y+dy[i]
nx = x+dx[i]
if ny<=0 or nx<=0 or ny+1==height or nx+1==width: #次に行くマスが壁だったらスルー
continue
if maze_base[ny][nx]=="#": #次に行くマスが壁だったらスルー
continue
if dist[ny][nx]==-1: # まだ通っていなかったら距離を更新
q.append((ny,nx))
dist[ny][nx] = dist[y][x]+1
if max_dist<dist[ny][nx]: # 最長距離を更新
gy,gx = ny,nx
max_dist = dist[ny][nx]
maze_base[gy][gx] = "G"
for i in maze_base:
print(*i)
結果
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
# S # # # #
# # # # # # # # # # # # # # # # # # # # # # # #
# # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # #
# # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # # # #
# # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # # #
# # # # # # # #
# # # # # # # # # # # # # # # # # # # # # # # #
# # # # # # # #
# # # # # # # # # # # # # # # # # # # # # # #
# # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # # #
# # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # # # #
# # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # #
# # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # # # # #
# # # # # # #
# # # # # # # # # # # # # # # # # # # # # # # # #
# # # # G # # # # # ←←←
# # # # # # # # # # # # # # # # # # # # # # #
# # # # # # # #
# # # # # # # # # # # # # # # # # # # # # # #
# # # # # # # # # #
# # # # # # # # # # # # # # # # # # # #
# # # # # # #
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
分かりづらいのでゴールのある行に矢印を置いてます、やはり変な位置にゴールが置かれますね。
おわりに
全体の実装時間は40分くらいでした、かなり簡単に作れましたが難易度に疑問を感じる結果となりました。また穴掘り法だけでなく棒倒し法、壁のばし法などもあるそうなのでこれらも実装しそれぞれの迷路の特徴なども考えてみたいと思います。