[Python] 基本的な迷路生成アルゴリズムまとめ(DFS/BFS/ブリム法/クラスカル法/ランダムウォーク法)

import random
def create_maze(width, height):
    # 迷路の初期化
    maze = [['#'] * (width * 2 + 1) for _ in range(height * 2 + 1)]
    visited = [[False] * (width * height) for _ in range(height)]
    
    def dfs(x, y):
        visited[y][x] = True
        maze[y * 2 + 1][x * 2 + 1] = ' '
        
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        random.shuffle(directions)
        
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < width and 0 <= ny < height and not visited[ny][nx]:
                maze[y * 2 + 1 + dy][x * 2 + 1 + dx] = ' '
                dfs(nx, ny)
    dfs(0, 0)
    return maze
# 迷路を生成して表示
maze = create_maze(5, 5)
for row in maze:
    print(''.join(row))

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

import random
from collections import deque

def create_maze(width, height):
    # 迷路の初期化
    maze = [['#'] * (width * 2 + 1) for _ in range(height * 2 + 1)]
    visited = [[False] * width for _ in range(height)]
    
    def bfs(start_x, start_y):
        queue = deque([(start_x, start_y)])
        visited[start_y][start_x] = True
        maze[start_y * 2 + 1][start_x * 2 + 1] = ' '
        
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        
        while queue:
            x, y = queue.popleft()
            
            random.shuffle(directions)  # ランダムに方向をシャッフル
            
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < width and 0 <= ny < height and not visited[ny][nx]:
                    # 間の壁を削除
                    maze[y * 2 + 1 + dy][x * 2 + 1 + dx] = ' '
                    # 次のセルを訪問済みにしてキューに追加
                    visited[ny][nx] = True
                    queue.append((nx, ny))
                    # 次のセルの位置を空白にする
                    maze[ny * 2 + 1][nx * 2 + 1] = ' '
    
    bfs(0, 0)
    return maze

# 迷路を生成して表示
maze = create_maze(5, 5)
for row in maze:
    print(''.join(row))

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

import random

def create_maze(width, height):
    # 迷路の初期化
    maze = [['#'] * (width * 2 + 1) for _ in range(height * 2 + 1)]
    edges = []
    
    # エッジの作成
    for y in range(height):
        for x in range(width):
            if x < width - 1:
                edges.append(((x, y), (x + 1, y)))  # 右のセル
            if y < height - 1:
                edges.append(((x, y), (x, y + 1)))  # 下のセル
    random.shuffle(edges)  # エッジをランダムにシャッフル

    # グループの初期化
    parent = {}
    for y in range(height):
        for x in range(width):
            parent[(x, y)] = (x, y)

    def find(node):
        if parent[node] != node:
            parent[node] = find(parent[node])
        return parent[node]

    def union(node1, node2):
        root1 = find(node1)
        root2 = find(node2)
        if root1 != root2:
            parent[root2] = root1

    # エッジを処理
    for edge in edges:
        cell1, cell2 = edge
        if find(cell1) != find(cell2):
            maze[cell1[1] * 2 + 1][cell1[0] * 2 + 1] = ' '
            maze[cell2[1] * 2 + 1][cell2[0] * 2 + 1] = ' '
            maze[(cell1[1] + cell2[1]) + 1][(cell1[0] + cell2[0]) + 1] = ' '
            union(cell1, cell2)

    return maze

# 迷路を生成して表示
maze = create_maze(5, 5)
for row in maze:
    print(''.join(row))

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

import random

def create_maze(width, height):
    # 迷路の初期化
    maze = [['#'] * (width * 2 + 1) for _ in range(height * 2 + 1)]
    edges = []
    
    # エッジの作成
    for y in range(height):
        for x in range(width):
            if x < width - 1:
                edges.append(((x, y), (x + 1, y)))  # 右のセル
            if y < height - 1:
                edges.append(((x, y), (x, y + 1)))  # 下のセル
    random.shuffle(edges)  # エッジをランダムにシャッフル
    
    # グループの初期化
    parent = {}
    for y in range(height):
        for x in range(width):
            parent[(x, y)] = (x, y)
    
    def find(node):
        if parent[node] != node:
            parent[node] = find(parent[node])
        return parent[node]
    
    def union(node1, node2):
        root1 = find(node1)
        root2 = find(node2)
        if root1 != root2:
            parent[root2] = root1
    
    # エッジを処理
    for edge in edges:
        cell1, cell2 = edge
        if find(cell1) != find(cell2):
            maze[cell1[1] * 2 + 1][cell1[0] * 2 + 1] = ' '
            maze[cell2[1] * 2 + 1][cell2[0] * 2 + 1] = ' '
            maze[(cell1[1] + cell2[1]) + 1][(cell1[0] + cell2[0]) + 1] = ' '
            union(cell1, cell2)
    
    return maze

# 迷路を生成して表示
maze = create_maze(5, 5)
for row in maze:
    print(''.join(row))

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

import random
def create_maze(width, height):
    # 迷路の初期化
    maze = [['#'] * (width * 2 + 1) for _ in range(height * 2 + 1)]
    x, y = 1, 1  # スタート地点
    maze[y][x] = ' '
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 右、下、左、上
    for _ in range(width * height * 10):  # 最大移動回数
        random.shuffle(directions)  # ランダムに方向をシャッフル
        for dx, dy in directions:
            nx, ny = x + dx * 2, y + dy * 2  # 2マス先のセルを計算
            if 1 <= nx < width * 2 and 1 <= ny < height * 2 and maze[ny][nx] == '#':
                maze[y + dy][x + dx] = ' '  # 道を作成
                maze[ny][nx] = ' '  # 新しいセルを訪問済みにする
                x, y = nx, ny  # 現在の位置を更新
                break  # 次の移動へ
    return maze
# 迷路を生成して表示
maze = create_maze(5, 5)
for row in maze:
    print(''.join(row))

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