【Python】壁伸ばし法で迷路を生成する

迷路の幅と高さをそれぞれ 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(width)] for y in range(height)]
    random.seed(seed)

  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_kabenobashi(self):
    self.set_outer_wall()
    stack = deque()
    for y in range(2, self.height-1, 2):
      for x in range(2, self.width-1, 2):
        stack.append([x,y])
    while True:
      if len(stack) == 0:
        break
      random.shuffle(stack)
      point = stack.pop()
      if self.maze[point[1]][point[0]] == self.WALL:
        continue
      self.maze[point[1]][point[0]] = self.WALL
      extend_wall = []
      extend_wall.append([point[0],point[1]])
      while True:
        directions = []
        if self.maze[point[1]-1][point[0]] == self.PATH and [point[0],point[1]-2] not in extend_wall:
          directions.append(0)
        if self.maze[point[1]][point[0]+1] == self.PATH and [point[0]+2,point[1]] not in extend_wall:
          directions.append(1)
        if self.maze[point[1]+1][point[0]] == self.PATH and [point[0],point[1]+2] not in extend_wall:
          directions.append(2)
        if self.maze[point[1]][point[0]-1] == self.PATH and [point[0]-2,point[1]] not in extend_wall:
          directions.append(3)
        if len(directions) == 0:
          break
        direction = random.choice(directions)
        if direction == 0:
          if self.maze[point[1]-2][point[0]] == self.WALL:
            self.maze[point[1]-1][point[0]] = self.WALL
            break
          else:
            self.maze[point[1]-1][point[0]] = self.WALL
            self.maze[point[1]-2][point[0]] = self.WALL
            extend_wall.append([point[0],point[1]-2])
            point = [point[0],point[1]-2]
        elif direction == 1:
          if self.maze[point[1]][point[0]+2] == self.WALL:
            self.maze[point[1]][point[0]+1] = self.WALL
            break
          else:
            self.maze[point[1]][point[0]+1] = self.WALL
            self.maze[point[1]][point[0]+2] = self.WALL
            extend_wall.append([point[0]+2,point[1]])
            point = [point[0]+2,point[1]]
        elif direction == 2:
          if self.maze[point[1]+2][point[0]] == self.WALL:
            self.maze[point[1]+1][point[0]] = self.WALL
            break
          else:
            self.maze[point[1]+1][point[0]] = self.WALL
            self.maze[point[1]+2][point[0]] = self.WALL
            extend_wall.append([point[0],point[1]+2])
            point = [point[0],point[1]+2]
        elif direction == 3:
          if self.maze[point[1]][point[0]-2] == self.WALL:
            self.maze[point[1]][point[0]-1] = self.WALL
            break
          else:
            self.maze[point[1]][point[0]-1] = self.WALL
            self.maze[point[1]][point[0]-2] = self.WALL
            extend_wall.append([point[0]-2,point[1]])
            point = [point[0]-2,point[1]]
    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_kabenobashi()
maze1.print_maze()

今回は、以下のように出力される。

###############
#             #
##### # ### ###
#   # # #     #
# # ##### # ###
# #       # # #
# ### # # ### #
#   # # # #   #
####### # ### #
#   # # #   # #
### # # # ### #
#   # # # #   #
# # # # ### ###
# #           #
###############

参考

迷路生成(壁伸ばし法) - Algoful
壁伸ばし法は迷路生成アルゴリズムの一種で...
[Python] 壁伸ばし法による迷路生成
迷路生成のアルゴリズム 迷路生成のアルゴリズムは数多くあります。 Maze Classification -M…
自動生成迷路

コメント

タイトルとURLをコピーしました