[Python] 壁伸ばし法による迷路生成

迷路生成のアルゴリズム

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

Maze Classification -Maze Creation Algorithms

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

棒倒し法、穴掘り法と迷路作成のアルゴリズムを試してきましたが、今回は壁伸ばし法で迷路を作成してみます。

棒倒し法

穴掘り法

壁伸ばし法

壁伸ばし法は、四方を壁に囲まれた四角形の中で、壁をどんどんと伸ばしていくことで、迷路を生成する方法です。壁伸ばし法は、①既存の壁から壁を伸ばしていく方法、②何もない点からランダムに点を選んで、既存の壁につながるまで壁を伸ばす方法、の2通りの方法があります。①は穴掘り法とほぼ同じなので、今回は②の方法で行ってみます。

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

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

迷路生成アルゴリズム(壁伸ばし法)

ネタがないので迷路を自動生成してみた

pythonで実装

import random

import colorama
import termcolor

class MazeByMakingWall():
    """ 壁伸ばし方で迷路を作る。"""

    def __init__(self, width, height):
        """ 迷路全体を構成する2次元配列、迷路の外周を壁とし、それ以外を通路とする。"""
        
        self.PATH = 0
        self.WALL = 1
        
        self.width = width
        self.height = height

        self.maze = []
        # 壁を作り始める開始ポイントを保持しておくリスト。
        self.lst_cell_start_make_wall = []

        # 迷路は、幅高さ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
        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.WALL
                else:
                    cell = self.PATH
                    # xyとも偶数の場合は、壁を作り始める開始ポイントとして保持。
                    if (x % 2 == 0 and y % 2 == 0):
                        self.lst_cell_start_make_wall.append([x, y])
                row.append(cell)
            self.maze.append(row)
            # スタートとゴールを入れる。
        self.maze[1][1] = 'S'
        self.maze[width-2][height-2] = 'G'

    def make_maze(self):
        """ 迷路の配列を作り戻す """
        # 壁の拡張を開始できるセルがなくなるまでループする。
        while self.lst_cell_start_make_wall != []:
            # 開始セルをランダムに取得してリストからは削除。
            x_start, y_start = self.lst_cell_start_make_wall.pop(random.randrange(0, len(self.lst_cell_start_make_wall)))
            # 選択候補が通路の場合は壁の拡張を開始する。
            if self.maze[x_start][y_start] == self.PATH:
                # 拡張中の壁情報を保存しておくリスト。
                self.lst_current_wall = []
                self.extend_wall(x_start, y_start)
        return self.maze

    def extend_wall(self, x, y):
        """ 開始位置から壁を2つずつ伸ばす """
        # 壁を伸ばすことのできる方向を決める。通路かつ、その2つ先が現在拡張中の壁ではない。
        lst_direction = []
        if self.maze[x][y-1] == self.PATH and [x, y-2] not in self.lst_current_wall:
            lst_direction.append('up')
        if self.maze[x+1][y] == self.PATH and [x+2, y] not in self.lst_current_wall:
            lst_direction.append('right')
        if self.maze[x][y+1] == self.PATH and [x, y+2] not in self.lst_current_wall:
            lst_direction.append('down')
        if self.maze[x-1][y] == self.PATH and [x-2, y] not in self.lst_current_wall:
            lst_direction.append('left')
        #壁を伸ばせる方向がある場合
        if lst_direction != []:
            #まずはこの地点を壁にして、拡張中の壁のリストに入れる。
            self.maze[x][y] = self.WALL
            self.lst_current_wall.append([x, y])
            # 伸ばす方向をランダムに決める
            direction = random.choice(lst_direction)
            # 伸ばす2つ先の方向が通路の場合は、既存の壁に到達できていないので、拡張を続ける判断のフラグ。
            contineu_make_wall = False
            # 伸ばした方向を壁にする
            if direction == 'up':
                contineu_make_wall = (self.maze[x][y-2] == self.PATH)
                self.maze[x][y-1] = self.WALL
                self.maze[x][y-2] = self.WALL
                self.lst_current_wall.append([x, y-2])
                if contineu_make_wall:
                    self.extend_wall(x, y-2)
            if direction == 'right':
                contineu_make_wall = (self.maze[x+2][y] == self.PATH)
                self.maze[x+1][y] = self.WALL
                self.maze[x+2][y] = self.WALL
                self.lst_current_wall.append([x+2, y])
                if contineu_make_wall:
                    self.extend_wall(x+2, y)
            if direction == 'down':
                contineu_make_wall = (self.maze[x][y+2] == self.PATH)
                self.maze[x][y+1] = self.WALL
                self.maze[x][y+2] = self.WALL
                self.lst_current_wall.append([x, y+2])
                if contineu_make_wall:
                    self.extend_wall(x, y+2)
            if direction == 'left':
                contineu_make_wall = (self.maze[x-2][y] == self.PATH)
                self.maze[x-1][y] = self.WALL
                self.maze[x-2][y] = self.WALL
                self.lst_current_wall.append([x-2, y])
                if contineu_make_wall:
                    self.extend_wall(x-2, y)
        else:
            previous_point_x, previous_point_y = self.lst_current_wall.pop()
            self.extend_wall(previous_point_x, previous_point_y)
    
    def print_maze(self):
        """ 壁が色付きの迷路を出力する。"""
        colorama.init()
        for row in self.maze:
            for cell in row:
                if cell == self.PATH:
                    print('   ', end='')
                elif cell == self.WALL:
                    print(termcolor.colored('   ', 'green', 'on_green'), end='')
                elif cell == 'S':
                    print(termcolor.colored('STA', 'red'), end='')
                elif cell == 'G':
                    print(termcolor.colored('GOA', 'red'), end='')
            print()


if __name__ == "__main__":
    maze = MazeByMakingWall(21, 21)
    maze.make_maze()
    maze.print_maze()