python随机迷宫生成算法

以下是一种基于深度优先搜索算法的python随机迷宫生成算法：

1.初始化一个二维矩阵，表示迷宫的格子，每个格子都是墙
2.从任意一个格子开始，将其标记为已访问，并将其周围四个格子中未访问的格子加入一个栈中
3.从栈中取出一个格子，将其与栈顶格子之间的墙打通，标记为已访问，并将其周围未访问的格子加入栈中
4.重复步骤3，直到栈为空

以下是实现代码：

import random

def generate_maze(width, height):
    # 初始化迷宫
    maze = [[1] * width + [0] for _ in range(height)] + [[1] * (width + 1)]
    # 从随机位置开始
    start_row = random.randint(0, height - 1)
    start_col = random.randint(0, width - 1)
    maze[start_row][start_col] = 0
    stack = [(start_row, start_col)]

    while stack:
        row, col = stack.pop()
        directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
        random.shuffle(directions)
        for d_row, d_col in directions:
            new_row, new_col = row + d_row, col + d_col
            if not (0 <= new_row < height and 0 <= new_col < width):
                continue
            if maze[new_row][new_col] == 0:
                continue
            # 打通墙
            if d_row == -1:
                maze[row][col] &= 0b0010
                maze[new_row][new_col] &= 0b1000
            elif d_row == 1:
                maze[row][col] &= 0b1000
                maze[new_row][new_col] &= 0b0010
            elif d_col == -1:
                maze[row][col] &= 0b0100
                maze[new_row][new_col] &= 0b0001
            elif d_col == 1:
                maze[row][col] &= 0b0001
                maze[new_row][new_col] &= 0b0100
            # 标记已访问
            maze[new_row][new_col] = 0
            stack.append((new_row, new_col))

    return maze

其中，二维矩阵中的数字表示当前格子的四面墙是否存在，从低位到高位分别表示东南西北四面墙，0表示不存在，1表示存在。例如，0b1010表示当前格子存在东墙和西墙，不存在南墙和北墙。