[Python] 穴掘り法による迷路生成

迷路生成のアルゴリズム

迷路生成のアルゴリズムは数多くあります。

Maze Classification -Maze Creation Algorithms

迷路生成の各種アルゴリズムのC++実装 (Win/Mac両対応)

前回は棒倒し法を用いて迷路を作成してみました。

今回は穴掘り法を使ってみます。

穴掘り法

穴掘り法は、四方を通路に、中を全て壁にした四角形の中で、2つ先が壁でない限り、どんどんと壁を壊して穴を掘り通路にすることで、最終的に迷路を作ります。

最初に四方を道にするのは、道を伸ばす際に、迷路が外に出ないようにするためです。

棒倒し法よりは、複雑な迷路を作ることができるそうです。

下のサイトはどれも説明が上手です。

迷路自動生成アルゴリズム

迷路生成アルゴリズム(穴掘り法)

【C#】穴掘り法で作る迷路

pythonで実装してみる

import random

class Maze():
    """ 迷路を作るクラス """
    PATH = 0
    WALL = 1
    def __init__(self, width, height):
        self.maze = []
        self.width = width
        self.height = height
        # 迷路は、幅高さ5以上の奇数で生成する。
        if(self.height < 5 or self.width < 5):
            print('at least 5')
            exit()
        if (self.width % 2) == 0:
            self.width += 1
        if (self.height % 2) == 0:
            self.height += 1


class MazeDig(Maze):
    """ 穴掘り法で迷路を作るクラス """
    # 既に堀った場所をスタックしておくための配列
    _stack_path = []

    def set_inner_wall_dig_point(self):
        """ 穴を掘る前の処理。"""
        # 四方を通路に中を壁にする。
        for _x in range(0, self.width):
            row = []
            for _y in range(0, self.height):
                if (_x == 0 or _y == 0 or _x == self.width-1 or _y == self.height -1):
                    cell = self.PATH
                else:
                    cell = self.WALL
                row.append(cell)
            self.maze.append(row)
        # 一番最初に穴を掘り始める座標をランダムに決める。
        # 座標は、xyとも奇数でなければならない。
        x_start_dig = random.randrange(1, self.width-1, 2)
        y_start_dig = random.randrange(1, self.height-1, 2)
        self.maze[x_start_dig][y_start_dig] = self.PATH
        self._stack_path.append([x_start_dig, y_start_dig])

    def dig_maze(self):
        """ 穴を掘る。 """
        while True:
            # もし既に掘った場所で戻れる場所が無い場合、ループを抜ける。
            if self._stack_path == []:
                break
            # 穴を掘り始めるxy座標をスタックからランダムにポップする。
            _x, _y = self._stack_path.pop(random.randrange(0, len(self._stack_path)))
            while True:
                # 一つ先、二つ先とも壁である場合は穴を掘ることが出来る。
                lst_direction_dig = []
                if self.maze[_x][_y-1] == self.WALL and self.maze[_x][_y-2] == self.WALL:
                    lst_direction_dig.append('up')
                if self.maze[_x+1][_y] == self.WALL and self.maze[_x+2][_y] == self.WALL:
                    lst_direction_dig.append('right')
                if self.maze[_x][_y+1] == self.WALL and self.maze[_x][_y+2] == self.WALL:
                    lst_direction_dig.append('down')
                if self.maze[_x-1][_y] == self.WALL and self.maze[_x-2][_y] == self.WALL:
                    lst_direction_dig.append('left')
                # 穴を掘ることが出来ない場合は、ループを抜ける。
                if lst_direction_dig == []:
                    break
                # 掘る方向をランダムに決める。
                else:
                    direction_dig = random.choice(lst_direction_dig)
                # 穴を掘り、xyとも奇数の座標をスタックに入れる。
                if direction_dig == 'up':
                    self.maze[_x][_y-1] = self.PATH
                    self.maze[_x][_y-2] = self.PATH
                    self._stack_path.append([_x, _y-2])
                elif direction_dig == 'right':
                    self.maze[_x+1][_y] = self.PATH
                    self.maze[_x+2][_y] = self.PATH
                    self._stack_path.append([_x+2, _y])
                elif direction_dig == 'down':
                    self.maze[_x][_y+1] = self.PATH
                    self.maze[_x][_y+2] = self.PATH
                    self._stack_path.append([_x, _y+2])
                elif direction_dig == 'left':
                    self.maze[_x-1][_y] = self.PATH
                    self.maze[_x-2][_y] = self.PATH
                    self._stack_path.append([_x-2, _y])

    def set_outer_wall_start_goal(self):
        """ 迷路に対して最後に行う処理。"""
        # 外周を壁にする
        for _x in range(0, self.width):
            for _y in range(0, self.height):
                if (_x == 0 or _y == 0 or _x == self.width-1 or _y == self.height -1):
                    self.maze[_x][_y] = self.WALL
        # スタートとゴールをセットする。
        self.maze[1][1] = 'S'
        self.maze[self.width-2][self.height-2] = 'G'

    def print_maze(self):
        """ 迷路を出力する。"""
        for row in self.maze:
            for cell in row:
                if cell == self.PATH:
                    print('   ', end='')
                elif cell == self.WALL:
                    print('###', end='')
                elif cell == 'S':
                    print('STR', end='')
                elif cell == 'G':
                    print('GOL', end='')
            print()


maze_dig = MazeDig(20, 20)
maze_dig.set_inner_wall_dig_point()
maze_dig.dig_maze()
maze_dig.set_outer_wall_start_goal()
maze_dig.print_maze()

次回は壁伸ばし法による迷路生成を行います。