アルゴリズムの「穴掘り法」を使い、迷路を自動生成するモジュールを作成しました。
迷路を構成するのは配列と文字列で、壁を「'#'」、通路を「' '（半角スペース）」としました。
迷路の例
['#', '#', '#', '#', '#', '#', '#'] ['#', ' ', ' ', ' ', ' ', ' ', '#'] ['#', '#', '#', '#', '#', ' ', '#'] ['#', ' ', ' ', ' ', '#', ' ', '#'] ['#', ' ', '#', ' ', '#', ' ', '#'] ['#', ' ', '#', ' ', ' ', ' ', '#'] ['#', '#', '#', '#', '#', '#', '#']
スクリプトとして実行すると、ターミナルで出力されます。
$ python3 generate.py Width = 9 Height = 9 # # # # # # # # # # # G # # # # # # # # # # # # # # # # # # # # # # # # # # S # # # # # # # # # # #
コード全文は「完成」にあります。
参考にしたページ
迷路生成アルゴリズム(穴掘り法) - Algoful
参考したYoutube
迷路を簡単に自動生成するアルゴリズムが面白い【穴掘り法】
スポンサーリンク
穴掘り法
穴掘り法は、まず迷路のすべてを壁に設定し、穴を掘り進めていく方法です。
手順は次のようになっています。
- 迷路の縦幅・横幅ともに5以上の奇数に設定する。
- 迷路のすべてを壁に設定。
- 迷路の壁を1マス掘る。掘る場所は、y軸、x軸がともに1以上の奇数。
- 掘った場所から上下左右の2マス先を見て、そこがインデックスの範囲内であり、かつ壁ならそこまで掘り進めることができる。ランダムに行き先を選んで掘る。
- 行けるところまで進め、掘れるところがなくなったら、2マス前に戻り、そこからまたランダムに行けるところを選んで掘り進める。
- 完全に行けるところがなくなったら完成。
3番は任意の場所でも良いし、ランダムに選んでもいいですが、これもインデックスの範囲内です。
4番は3で最初に掘った穴の座標がともに奇数であるため、一番外側に面する壁を掘る心配がなくなり、インデックス内の壁かどうかで判定します。
5番は、再帰を使っても出来そうですが、今回はスタックを使います。
掘り進めた座標をスタックに格納していき、掘り進めなくなったらスタックから取り除くことで2マス前に戻ることを実現します。
アルゴリズムの実装
import random
class GenerateMaze():
# widthとheightは共に奇数かつ5以上の整数
def __init__(self, width, height):
self.width = width
self.height = height
self.maze = [list('#'*width) for _ in range(height)]
self._dig_walls()
def _search_directions(self, y , x):
directions = []
if x - 2 > 0 and self.maze[y][x-2] == '#':
directions.append('L')
if x + 2 < self.width and self.maze[y][x+2] == '#':
directions.append('R')
if y - 2 > 0 and self.maze[y-2][x] == '#':
directions.append('U')
if y + 2 < self.height and self.maze[y+2][x] == '#':
directions.append('D')
return directions
def _dig_walls(self):
start_y = random.choice([i for i in range(1, self.height, 2)])
start_x = random.choice([i for i in range(1, self.width, 2)])
self.maze[start_y][start_x] = ' '
stack = [(start_y, start_x)]
while stack:
y, x = stack[-1]
directions = self._search_directions(y, x)
if directions == []:
stack.pop()
continue
choiced = random.choice(directions)
if choiced == 'L':
for i in range(1, 3):
self.maze[y][x-i] = ' '
x -= i
elif choiced == 'R':
for i in range(1, 3):
self.maze[y][x+i] = ' '
x += i
elif choiced == 'U':
for i in range(1, 3):
self.maze[y-i][x] = ' '
y -= i
elif choiced == 'D':
for i in range(1, 3):
self.maze[y+i][x] = ' '
y += i
stack.append((y, x))
「GenerateMaze」クラスを作成しました。
迷路の横幅「self.width」、縦幅「self.height」を持ち、「self.maze」が迷路を配列として収めた属性です。
「_dig_walls」メソッドで「穴掘り法」を実装しています。
まずランダムな奇数を取得し、それをy軸、x軸の座標としてスタック（変数stack）に収めます。その座標地点の壁を穴に変えます。
スタックを基準としてループを回し、スタック最後尾のタプルの座標をyとxに代入、「_search_directions」メソッドでその2マス先が行けるか判断します。
メソッドの戻り値が空のリストでないなら行き先をランダムで選び、2マス掘り進めます。進めたらスタックに現在の地点を追加します。
どんどん進めていきます。
2マス先へどこへも進めなくなった時点でスタックからポップ、2マス前にいた場所がスタック最後尾に来るので、そこからまた行ける場所を掘り進めます。
進めるところがなくなり、スタックが空になった時点でループが終了し、迷路が完成です。
完成
いくつかメソッドを追加します。
- 「print_maze」で迷路の出力。
- 「preset_start_goal」でスタート「S」とゴール「G」の追加。（とりあえず座標は（self.height-2, 0）と（1, self.width-1）の固定にしています）
- 「regenerate」で迷路の再生成。
そしてスクリプトとしての処理を書いて完成です。
import random
class GenerateMaze():
# widthとheightは共に奇数かつ5以上の整数
def __init__(self, width, height):
self.width = width
self.height = height
self.maze = [list('#'*width) for _ in range(height)]
self._dig_walls()
def _search_directions(self, y , x):
directions = []
if x - 2 > 0 and self.maze[y][x-2] == '#':
directions.append('L')
if x + 2 < self.width and self.maze[y][x+2] == '#':
directions.append('R')
if y - 2 > 0 and self.maze[y-2][x] == '#':
directions.append('U')
if y + 2 < self.height and self.maze[y+2][x] == '#':
directions.append('D')
return directions
def _dig_walls(self):
start_y = random.choice([i for i in range(1, self.height, 2)])
start_x = random.choice([i for i in range(1, self.width, 2)])
self.maze[start_y][start_x] = ' '
stack = [(start_y, start_x)]
while stack:
y, x = stack[-1]
directions = self._search_directions(y, x)
if directions == []:
stack.pop()
continue
choiced = random.choice(directions)
if choiced == 'L':
for i in range(1, 3):
self.maze[y][x-i] = ' '
x -= i
elif choiced == 'R':
for i in range(1, 3):
self.maze[y][x+i] = ' '
x += i
elif choiced == 'U':
for i in range(1, 3):
self.maze[y-i][x] = ' '
y -= i
elif choiced == 'D':
for i in range(1, 3):
self.maze[y+i][x] = ' '
y += i
stack.append((y, x))
def print_maze(self, print_width=2):
for line in self.maze:
for char in line:
print(char.center(print_width), end='')
print()
# SとGをself.mazeに書き込み
def preset_start_goal(self):
self.start = (self.height-2, 0)
self.maze[self.height-2][0] = 'S'
self.goal = (1, self.width-1)
self.maze[1][self.width-1] = 'G'
def regenerate(self):
self.maze = [list('#'*self.width) for _ in range(self.height)]
self._dig_walls()
if __name__ == '__main__':
def check_value(user):
if user < 5 or user % 2 == 0:
return False
else:
return True
while True:
print('迷路を出力します')
print('幅と高さが5以上の奇数を入力')
try:
width = int(input('Width = '))
height = int(input('Height = '))
except ValueError:
print('有効な数字を入力して下さい\n')
continue
if all([check_value(width), check_value(height)]):
break
maze = GenerateMaze(width, height)
maze.preset_start_goal()
maze.print_maze()
モジュールとして読み込んでみます。
$ python3 Python 3.10.0 (default, Oct 12 2021, 16:02:08) [GCC 9.3.0] on linux Type "help", "copyright", "credits" or "license" for more information. >>> import generate >>> maze = generate.GenerateMaze(13, 9) >>> maze <generate.GenerateMaze object at 0x7fa4769ba200> >>> for line in maze.maze: ... print(line) ... ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'] ['#', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', '#'] ['#', '#', '#', ' ', '#', ' ', '#', ' ', '#', '#', '#', ' ', '#'] ['#', ' ', ' ', ' ', '#', ' ', '#', ' ', ' ', ' ', '#', ' ', '#'] ['#', ' ', '#', '#', '#', '#', '#', '#', '#', '#', '#', ' ', '#'] ['#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', '#'] ['#', ' ', '#', '#', '#', '#', '#', ' ', '#', ' ', '#', '#', '#'] ['#', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', '#'] ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'] >>> maze.print_maze() # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # >>> maze.preset_start_goal() >>> maze.print_maze() # # # # # # # # # # # # # # # G # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # S # # # # # # # # # # # # # # # >>> maze.regenerate() >>> maze.print_maze() # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
つぎはスクリプトとして実行します。
$ python3 generate.py 迷路を出力します 幅と高さが5以上の奇数を入力 Width = 21 Height = 21 # # # # # # # # # # # # # # # # # # # # # # # # # G # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # S # # # # # # # # # # # # # # # # # # # # # # #
完成です。
迷路を解いてみました↓
迷路を作成するWebページ↓
内部処理はRustですが、アルゴリズムはこのページのものと同じです。