迷路の幅と高さをそれぞれ width, height として設定し、
その数値にしたがって穴掘り法で迷路を生成する。
※迷路の幅と高さは5以上の奇数とする。
import sys
import random
from collections import deque
class Maze:
PATH = 0
WALL = 1
def __init__(self, width, height, seed=0):
self.width = width
self.height = height
if self.width < 5 or self.height < 5:
sys.exit()
if self.width % 2 == 0:
self.width += 1
if self.height % 2 == 0:
self.height += 1
self.maze = [[self.PATH for x in range(self.width)] for y in range(self.height)]
self.start = [1, 1]
random.seed(seed)
def set_all_wall(self):
for y in range(0, self.height):
for x in range(0, self.width):
self.maze[y][x] = self.WALL
return self.maze
def set_outer_path(self):
for y in range(0, self.height):
for x in range(0, self.width):
if x == 0 or y == 0 or x == self.width-1 or y == self.height-1:
self.maze[y][x] = self.PATH
return self.maze
def set_outer_wall(self):
for y in range(0, self.height):
for x in range(0, self.width):
if x == 0 or y == 0 or x == self.width-1 or y == self.height-1:
self.maze[y][x] = self.WALL
return self.maze
def set_maze_anahori(self):
self.set_all_wall()
self.set_outer_path()
stack = deque()
point = self.start
stack.append(point)
self.maze[point[1]][point[0]] = self.PATH
while True:
if len(stack) == 0:
break
random.shuffle(stack)
point = stack.pop()
while True:
directions = []
if self.maze[point[1]-1][point[0]] == self.WALL and self.maze[point[1]-2][point[0]] == self.WALL:
directions.append(0)
if self.maze[point[1]][point[0]+1] == self.WALL and self.maze[point[1]][point[0]+2] == self.WALL:
directions.append(1)
if self.maze[point[1]+1][point[0]] == self.WALL and self.maze[point[1]+2][point[0]] == self.WALL:
directions.append(2)
if self.maze[point[1]][point[0]-1] == self.WALL and self.maze[point[1]][point[0]-2] == self.WALL:
directions.append(3)
if len(directions) == 0:
break
direction = random.choice(directions)
if direction == 0:
self.maze[point[1]-1][point[0]] = self.PATH
self.maze[point[1]-2][point[0]] = self.PATH
stack.append([point[0],point[1]])
point = [point[0],point[1]-2]
elif direction == 1:
self.maze[point[1]][point[0]+1] = self.PATH
self.maze[point[1]][point[0]+2] = self.PATH
stack.append([point[0],point[1]])
point = [point[0]+2,point[1]]
elif direction == 2:
self.maze[point[1]+1][point[0]] = self.PATH
self.maze[point[1]+2][point[0]] = self.PATH
stack.append([point[0],point[1]])
point = [point[0],point[1]+2]
elif direction == 3:
self.maze[point[1]][point[0]-1] = self.PATH
self.maze[point[1]][point[0]-2] = self.PATH
stack.append([point[0],point[1]])
point = [point[0]-2,point[1]]
self.set_outer_wall()
return self.maze
def print_maze(self):
for col in self.maze:
for cell in col:
if cell == self.WALL:
print('#', end='')
elif cell == self.PATH:
print(' ', end='')
print()
maze1 = Maze(15, 15)
maze1.set_maze_anahori()
maze1.print_maze()
今回は、以下のように出力される。
###############
# # # #
# # ### # #####
# # # # # #
# # ### # # # #
# # # # #
##### ### # ###
# # # # #
### # # # ### #
# # # # # #
# ### # ### # #
# # # # # #
# # # ### ### #
# # # #
###############
参考
迷路生成(穴掘り法) - Algoful
穴掘り法は迷路生成アルゴリズムの一種です。全面壁の状態から穴を掘り進めながら迷路を作ります。シミュレーション機能で生成される過程を確認できます。複雑な迷路が生成できるためおすすめです。C#の実装サンプルを用意しているのでUnityでのゲーム...
[Python] 穴掘り法による迷路生成
迷路生成のアルゴリズム 迷路生成のアルゴリズムは数多くあります。 Maze Classification -M…
自動生成迷路