迷路を生成する
大きな迷路を人が作成するには時間と根気が必要になります。
迷路に特別なこだわりがあるなら人の手によって作成すべきですが、そうでないならコンピュータに任せることもできます。
また、コンピュータや誰かが作った迷路を、自分好みに手を加えたら時間の節約になるかもしれません。
プログラムで迷路を生成するには様々なアルゴリズムがあり、ここでは「壁伸ばし法」を利用します。
「壁伸ばし法」の他に「棒倒し法」「穴掘り法」「クラスタ法」「深さ優先探索法」等があります。
(「プログラムで」と断っていますが、方眼紙とサイコロと鉛筆があれば、手作業で作成することもできます)
壁伸ばし法とは、どこか適当な場所から無作為に曲がりながら壁を伸ばし続け、
伸ばせなくなったら、また別の適当な場所から同じように壁を伸ばす方法です。
壁を伸ばす場所がすべてなくなったら迷路の完成です。このとき、右手法 (みぎてほう) で解ける迷路が出来上がります。
壁伸ばし法の開始位置の取り方は 2 種類あり、「A·周囲の壁から伸ばす方法」と「B·任意のゆかから伸ばす方法」です。
ここでは、実装がより簡単な「A·周囲の壁から伸ばす方法」を掲載します。
迷路を生成出来たら、前稿の探索プログラムで解いてみます。
0-1. この章では、pygame を使います。
インストールがまだなら、ここ (Windows10) か ここ (CentOS) を参考にしてインストールしておいてください。0-2. この章では、テキストエディタを使います。
pygame と書いて「パイゲーム」と読みます。
Python を使ってゲームを作るためのパッケージのことです。
Linux なら付属の「Vim」や「gedit」で十分です。0-3. 未経験者向けの情報を省いています。
(Vim の初心者向け使い方はここにあります)
Windows なら「メモ帳」でも構いませんが、本格的なテキストエディタをお勧めします。
(強力なアンドゥや、キーマクロが使えるようになります)
インストールがまだなら、ここ (秀丸エディタ) を参考にしてインストールしておいてください。
また、プログラムを起動するには拡張子が重要となるので、エクスプローラーで拡張子が表示されるようにしておいてください。
プログラミング未経験の方は、予めこちら (Python であそぼう 1) を、
アニメーションの仕組みをまだ考えたことがない方は、こちら (Python であそぼう 2) を
学習しておくことを推奨します。
1. 迷路生成プログラムの作成
<テキスト17> ファイル名「makemaze.py」
データのシャッフル (Xorshift128, DustShuffle) はこちらを使っています。
*1数えたビットから選択しているのでビットを発見できないケースは考えなくても大丈夫。
# 壁伸ばし法による迷路生成する関数。 # 迷路の大きさは 奇数×奇数 にすること。 def WallExtend(maze_w, maze_h): # 迷路の幅・高さを、指定された大きさを超えない奇数にそろえる。 w = maze_w - (1 - maze_w % 2) h = maze_h - (1 - maze_h % 2) # 幅・高さのどちらかが 3 以下だと迷路にできない。 if w <= 3 or h <= 3: return [] maze = [''] * h # 空文字列を縦の分だけ用意する。(横情報は文字列として作成する) # 部屋の上辺と下辺の壁を作成する。 maze[0] = '+' maze[h - 1] = '+' for x in range(1, w - 1): maze[0] += '-' maze[h - 1] += '-' maze[0] += '+' maze[h - 1] += '+' # 2 行目からの部屋を作成する。 for y in range(1, h - 1): maze[y] = '|' # 左端を壁にする。 for x in range(1, w - 1): # 左端と右端の間を空白で埋める。 maze[y] += ' ' maze[y] += '|' # 右端を壁にする。 kabePosTmp = [] # 予め分かっている壁の開始位置を格納するリストを用意する。 # Label-01 # 上辺の開始位置を記憶する。 for x in range(2, w - 2, 2): kabePosTmp.append([ x, 0 ]) # 下辺の開始位置を記憶する。 for x in range(2, w - 2, 2): kabePosTmp.append([ x, h - 1]) # 2 行目からの左端の開始位置を記憶する。 for y in range(2, h - 2, 2): kabePosTmp.append([ 0, y ]) # 2 行目からの右端の開始位置を記憶する。 for y in range(2, h - 2, 2): kabePosTmp.append([ w - 1, y ]) idx = DustShuffle(len(kabePosTmp)) # インデックスをかき混ぜる。 # 初期の検索リストを作成する。 kabePosQueue = [] for i in range(len(idx)): kabePosQueue.append(kabePosTmp[idx[i]]) # Label-02 # 検索リストが空になるまで壁の拡張を続ける。 while len(kabePosQueue) > 0: # Label-03 # 先頭の項目を取り出して削る。 x, y = kabePosQueue.pop(0) # Label-04 # 壁を伸ばせるか確認する。 d = Validate(maze, w, h, x, y) # Label-05 if d != 0: # ↓ 途中経過を見たい場合はこの行を有効にして実行してください。 #print(x,y,d) #PrintMaze(maze) # Label-06 # 探索済みの開始位置を検索リストの最後に追加する。 kabePosQueue.append([ x, y ]) # Label-07 bitCnt = BitCount(d) # 延ばせる方向の格納数を求める。 Xorshift128(xorshift_state) nextDirPos = xorshift_state[0] % bitCnt nextDir = BitSelect(d, nextDirPos) # 伸ばせる方向は 2 の指数*1 dx, dy = 0, 0 if nextDir == 0: dy = -1 # 上へ伸ばす。 if nextDir == 1: dx = +1 # 右へ伸ばす。 if nextDir == 2: dy = +1 # 下へ伸ばす。 if nextDir == 3: dx = -1 # 左へ伸ばす。 # 壁を 2 コマ伸ばす。 # 1 コマ先の分。 wx1 = x + dx * 1 wy1 = y + dy * 1 maze[wy1] = maze[wy1][:wx1] + '#' + maze[wy1][wx1 + 1:] # 2 コマ先の分。 wx2 = x + dx * 2 wy2 = y + dy * 2 maze[wy2] = maze[wy2][:wx2] + '#' + maze[wy2][wx2 + 1:] # Label-08 # 2 コマ伸ばした先が候補を持つなら検索リストの先頭に追加する。 nextD = Validate(maze, w, h, wx2, wy2) if nextD != 0: kabePosQueue.insert(0, [ wx2, wy2 ]) # Label-09 return maze
# 迷路を表示する関数。 def PrintMaze(maze): for s in maze: print('"' + s + '"')
# 乱数発生器 def Xorshift128(state): t = state[3] & 0xFFFFFFFF # fool proof s = state[0] & 0xFFFFFFFF # fool proof state[3] = state[2] state[2] = state[1] state[1] = s t = (t ^ t << 11) & 0xFFFFFFFF # t ^= t << 11 // unsigned 32bit t ^= t >> 8 state[0] = (t ^ s ^ (s >> 19)) & 0xFFFFFFFF # t ^ s ^ (s >> 19) // unsigned 32bit return state
# ダステンフェルドのシャッフル def DustShuffle(numLen): global xorshift_state idx = list(range(numLen)) for i in reversed(range(numLen)): xorshift_state = Xorshift128(xorshift_state) p = xorshift_state[0] % (i + 1) n = idx[p] idx[p] = idx[i] idx[i] = n return idx
# 有効な候補だけを選別する関数。 def Validate(maze, w, h, x, y): # 2 個先 (壁となるコマ) に空きが無ければ該当ビットを削る。 d = 0x0F if (y - 2) < 0: d &= ~2**0 # 上壁より上は外なので無効。 if (x + 2) >= w: d &= ~2**1 # 右壁より右は外なので無効。 if (y + 2) >= h: d &= ~2**2 # 下壁より下は外なので無効。 if (x - 2) < 0: d &= ~2**3 # 左壁より左は外なので無効。 # 壁の内側でもすでに先がゆか以外なら無効。 if d & 2**0 != 0 and maze[y-2][x:x+1] != ' ': d &= ~2**0 # 上側 if d & 2**1 != 0 and maze[y][x+2:x+3] != ' ': d &= ~2**1 # 右側 if d & 2**2 != 0 and maze[y+2][x:x+1] != ' ': d &= ~2**2 # 下側 if d & 2**3 != 0 and maze[y][x-2:x-1] != ' ': d &= ~2**3 # 左側 return d
# ビットを数える関数。 def BitCount(n): cnt = 0 while n > 0: # すべてのビットを調べるまで繰り返す。(負の数は扱わない) cnt += n & 1 # 最下位ビットの有無を加算する。 n >>= 1 return cnt
# ビットを選択する関数。 # p 番目に 1 となっているビット位置を返す。(p は 0 オリジン) # 該当のビットが無ければ -1 を返す。 def BitSelect(n, p): pos = -1 # 発見できなかった場合の値を保持しておく。 if p < 0: return -1 # 何番目かを指定するのは 0 以上であること。 times = 0 while n != 0: # すべてのビットを調べるまで繰り返す。 if (n & 2**times) != 0: p -= 1 if p < 0: break n &= ~2**times # 調べたビットを無効にする。 times += 1 # 指数をひとつ進める。 if p < 0: pos = times # 発見したビット (指数) を返す。 return pos
xorshift_state = [ # すべてが 0 にならないように初期化する。*2 123456789, 123456761, 123456757, 123456731, ] maze_w, maze_h = 37, 17 maze = WallExtend(maze_w, maze_h) PrintMaze(maze)
*2違う迷路を生成したいときは、ここの数字を 0 以外に書き換えてください。
このプログラムは、以下 Label-01 ～ Label-09 を順に実行しています。
Label-01 : 上下左右の四辺に壁の開始位置を設け、すべてを検索リストに追加する。*3壁を伸ばす方向には以下の意味を持たせています。
Label-02 : 検索リストに開始位置が残っていれば下記 Label-03 ～ Label-09 を繰り返す。
Label-03 : 検索リストの先頭から開始位置をひとつ取り出して削る。
Label-04 : 取り出した開始位置から、壁を伸ばせない方向を捨てる。
Label-05 : 壁を伸ばす選択肢が残っていないなら Label-09 へ。
Label-06 : Label-03 で取り出した開始位置を検索リストの最後に追加する。*4
Label-07 : 選択肢から伸長方向をひとつ選択して壁を 2 コマ伸ばす。
Label-08 : 2 コマ伸ばした先がさらに壁を伸ばせそうなら、そこを開始位置として検索リストの先頭に追加する。*5*6
Label-09 : Label-02 へ戻る。(ブロック文の終端を明記しない Python では存在しないブロック文の終端がここにあります)
*3偶数番目の縦・横はゆか (通路) なので、壁の開始位置の縦・横は必ず奇数番目となる。
*4Label-05 の結果により追加されなくなる。→ Label-03 により、検索リストが短くなっていく。
*5壁を伸ばせないなら開始位置を追加しない。→ Label-03 により、検索リストが短くなっていく。
*6Label-03 で先頭を削った後に先頭へ追加するので、この場合は検索リストの長さが変わらない。
00001111b (b は 2 進数の意味) |||+- 20: 上方向||+-- 21: 右方向
|+--- 22: 下方向
+---- 23: 左方向
各ビットが 2 の累乗を意味していることを利用して、 そのビットの有無によって壁を延伸できる情報を格納しています。 例えば、12 (1100b) は、下と左へ壁を伸ばせるという意味です。
迷路生成プログラムを実行すると、実行結果<テキスト18>が表示されます。
これはただの文字列なので「コピー＆ペースト」することにより、当 Python だけでなく他言語のプログラムに組み込むこともできます。
(他言語のプログラムに組み込むときは、その言語の文法に合わせてください)
<テキスト18> 実行結果
前章で作成した迷路探索プログラム<テキスト16>に、今回の迷路生成プログラムで生成した迷路<テキスト18>を組み込みます。
<テキスト19> ファイル名「program.py」
*7 lib.py は Python であそぼう 5 の<テキスト14>です。program.py と同じディレクトリに置いてください。
# 自動で歩かせる関数。 def HeadTurn(dir, fpv): mae = fpv[0] migi = fpv[1] hidari = fpv[2]ushiro = fpv[3]otherDir = -1 if migi == 0: if mae != 0: if hidari != 0: otherDir = (dir + 3) % 4 else: dir = (dir + 3) % 4 else: if mae != 0: otherDir = dir elif hidari != 0: otherDir = (dir + 3) % 4 dir = (dir + 1) % 4 return dir, otherDir
bunkiSpots = [] # 履歴格納用リストの用意 # 選択しなかった他通路をひとつ履歴用リストに追加する関数。 def BunkiAdd(dir, x, y): global bunkiSpots bunkiSpots.append([dir, x, y]) # 他通路の履歴をひとつ履歴用リストから削除する関数。 def BunkiDel(turnPoint): global bunkiSpots # 指定位置以外のデータで履歴用リストを再構築する。 bunkiSpots = bunkiSpots[:turnPoint] + bunkiSpots[turnPoint + 1:] # 履歴用リストに現在位置のデータがあるか検索する関数。 # データがあれば、その位置 (添え字) を返す。無ければ -1 を返す。 def BunkiSearch(x, y): turnPoint = -1 # 履歴の位置をデータが無い時の値で初期化しておく。 global bunkiSpots index = range(len(bunkiSpots)) # 履歴の添え字をすべて用意する。 # 履歴を最新から古いものへ検索する。 for i in reversed(index): if bunkiSpots[i][1:3] == [x, y]: turnPoint = i break return turnPoint
Controls = [ # X, Y, Mark コントロールの場所と記号 [ 1, 4, 'a' ], [ 9, 5, 'b' ], [ 15, 1, 'c' ], ] # コントロールを迷路に埋め込む。 for Mokuhyo in range(len(Controls)): mx, my, mm = Controls[Mokuhyo] heya[my] = heya[my][:mx] + mm + heya[my][mx+1:] # 自分の横位置、縦位置、方向 x, y, dir = 1, 1, 0 # 方向 0:↑ / 1:→ / 2:↓ / 3:← myChr = 'A>V<' lib.HeyaDisplay(screen, heya, x, y, myChr[dir]) Mokuhyo = 0 mx, my, mm = Controls[Mokuhyo] running = True while running: pgclock.tick(10) for event in pygame.event.get(): if event.type == pygame.QUIT: running = False idou = lib.Search(heya, x, y) # 過去の分岐点から現在位置と同じものを探す。 turnPoint = BunkiSearch(x, y) if turnPoint >= 0: # 過去の分岐点を回収して回頭する。 newDir = bunkiSpots[turnPoint][0] BunkiDel(turnPoint) if newDir == (dir + 2) % 4: pass else: dir = newDir else: # 普通に回頭する。 fpv = lib.GetFPV(dir, idou) dir, otherDir = HeadTurn(dir, fpv) # 向きを変える選択肢が他にもあったら履歴に追加する。 if otherDir != -1: BunkiAdd(otherDir, x, y) dx, dy = 0, 0 if dir == 1: dx = idou[0] elif dir == 3: dx = idou[1] elif dir == 2: dy = idou[2] elif dir == 0: dy = idou[3] x += dx y += dy lib.HeyaDisplay(screen, heya, x, y, myChr[dir]) if x == mx and y == my: if mm == 'c': running = False else: heya[my] = heya[my][:mx] + ' ' + heya[my][mx+1:] Mokuhyo += 1 mx, my, mm = Controls[Mokuhyo]
4. 生成された迷路を組み込んだプログラムの実行
この章は、ここで終了です。うまく解けました。
ところで、迷路データを変更する前の<テキスト16>は、右手法だけでは行けない通路も進行できるはずのプログラムでした。
そして「壁伸ばし法」では、右手法で解ける迷路が生成されています。
この<テキスト19>でも、プログラム部は変わっていないので、
壁がどこか途切れていても (右手法で行けない通路があったとしても) 解くことができるはずです。
各自、<テキスト19>の迷路部分を手作業で変更して、それが自動で解かれるかどうかを確認してください。
