代码收藏家 Python迷宫生成算法详解及可视化实现（使用pygame扩展功能，附带详细注释）
目录
前言：
实现：
研究思路
思路：
算法：
应用：
扩展（可玩性角度）：
总结
题外话：
前言：
该领域确实没什么新东西，我那天突发奇想学了迷宫生成算法，看的那些效果，哇塞哇塞，copy下来代码后一跑一个报错，然后自己实现了一遍，我觉得本文除了记录以外，当属迷宫绘制类最有意义了。（高端的东西写不来，低端的东西节省一下大家时间还是蛮不错的）
效果是下面的样子，自娱自乐了。
实现：
复制下述代码即可，注意todo，代码含义见注释。
补充解释：MazeMap用于处理迷宫数据，其中迷宫的生成有两种生成方式，分别为深搜的solved_map和prim算法的solved_map1，在初始化里面更新就行，自己改改也行。
然后是两种迷宫可视化方式，MazeShow和MazeGazeShow，对应上面的左右两种效果。
我只是给个可能行的应用，自己用最好修修，还有就是我的代码（一言难尽），有点小毒
import pygame
import sys
import random as r
from typing import List
# todo:
# 1. maze_size处修改迷宫尺寸
# 2. 迷宫可视化类与迷宫计算类
# 3. main函数思路
# 设定全局界面参数
SCREEN_WIDTH = 800
SCREEN_HIGHT = 600
maze_size = (10, 10) # 迷宫的宽和高
class MazeMap(object):
"""处理地图相关数据"""
def __init__(self, size=(5, 5)):
"""初始化"""
self.width, self.high = (0, 0) # 地图有效格子
self.map = [[]] # 地图数据
self.point = [] # 地图有效格子的坐标
self.set_map(size) # 生成初始化地图
self.solve_map1() # 地图迷宫化
def set_map(self, size=(5, 5)):
"""生成路径与围墙地图"""
self.width, self.high = size # 读取地图尺寸
# 将有效格子周围的墙壁特化为格子，因此地图尺寸变为（x * 2 + 1, y * 2 + 1）
self.map = [[1 for _ in range(self.width * 2 + 1)] for _ in range(self.high * 2 + 1)]
self.point = []
for i in range(self.high): # 处理有效格子
for j in range(self.width):
self.map[i * 2 + 1][j * 2 + 1] = 0
self.point.append((i * 2 + 1, j * 2 + 1))
def solve_map(self):
"""所有点遍历一次 dfs算法"""
"""
数据结构：
遍历节点列表：储存已经遍历过的节点
遍历栈：储存遍历节点的循序
周围节点列表：储存当前节点周围的节点（符合一定条件）
思路：
初始化：将起点设为当前点
当有节点没有被遍历时：
对于当前点
更新周围节点列表为空
查询当前点周围所有点（四个方向），若有不在遍历节点列表的，将其加入周围节点列表
若周围节点列表不为空
将当前点压入遍历栈
从中随机选取一点，将其与当前点之间的墙壁打通，并将其设定为当前点
若周围节点列表为空
从遍历栈弹出顶点，将其设为当前点
"""
length = len(self.point)
pass_point = []
path_list = []
swap_point = [] # 本来不该在这写的，方便理解吧
current_point = self.point[0] # 初始化起点为当前点
while length != len(pass_point): # 有节点未遍历
if current_point not in pass_point: # 更新当前点的遍历状态
pass_point.append(current_point)
# 寻找当前点周围的所有点，并筛选合法的且没有遍历过的那些
possible_point = self.possible_point(current_point)
swap_point = []
for _point in possible_point:
if _point in self.point and _point not in pass_point: # 点有效且未经过
swap_point.append(_point)
if swap_point: # 周围节点列表 有点
path_list.append(current_point) # 入栈
swap_point = self.choose_point(swap_point) # 随机选取一点
self.break_wall(current_point, swap_point) # 打破墙壁
current_point = swap_point # 更新当前点
else: # 周围节点列表 无点
current_point = path_list[-1] # 等效出栈，更新当前点
path_list.remove(current_point)
def solve_map1(self):
"""prim算法实现"""
start = self.point[0] # 迷宫起点
visited = [start] # 已访问节点
frontier = [] # 边界节点（待处理的未访问节点）
# 初始化边界列表：添加起点的所有有效邻居
for neighbor in self.possible_point(start):
if neighbor in self.point and neighbor not in visited:
frontier.append(neighbor)
while frontier:
# 从边界列表中随机选择当前节点
current = self.choose_point(frontier)
# 获取当前节点的所有邻居
neighbors = self.possible_point(current)
# 找出已访问的邻居（用于打通墙壁）
linked = [n for n in neighbors if n in visited]
if linked:
# 随机选择一个已访问邻居，打通墙壁
target = self.choose_point(linked)
wx = (current[0] + target[0]) // 2
wy = (current[1] + target[1]) // 2
self.map[wx][wy] = 0 # 移除墙壁
# 标记当前节点为已访问
visited.append(current)
frontier.remove(current)
# 将当前节点的新邻居加入边界列表
for neighbor in neighbors:
if neighbor in self.point and neighbor not in visited and neighbor not in frontier:
frontier.append(neighbor)
def possible_point(self, current_point):
"""找一个节点周围的节点"""
x, y = current_point
path = [[0, 2], [2, 0], [-2, 0], [0, -2]] # 四个方向，后续可扩展
possible = []
for enum in path:
_x, _y = enum
possible.append((x + _x, y + _y))
return possible
def choose_point(self, next_point):
"""在一个点的列表中随机抽取一点"""
return next_point[r.randint(0, len(next_point) - 1)]
def break_wall(self, pos1, pos2):
"""打通两个格子之间的墙壁"""
self.map[int((pos1[0] + pos2[0]) / 2)][int((pos1[1] + pos2[1]) / 2)] = 0
def get_map(self):
"""获得地图数据"""
return self.map
def get_point(self):
"""获得有效点信息"""
return self.point
# 用于可视化迷宫
# 要求二维列表,例如下
# [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
# [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1]
# [1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1]
# [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1]
# [1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1]
# [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1]
# [1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1]
# [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1]
# [1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1]
# [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1]
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]
class MazeShow(object):
"""迷宫可视化工具1"""
def __init__(self, size=(SCREEN_WIDTH, SCREEN_HIGHT)):
"""初始化"""
self.high = size[1] - 100 # 最大显示范围
self.wide = size[0] - 100
self.high_size = 0 # 单个格子的显示参数
self.width_size = 0
self.high_num = 0 # 格子的数目
self.width_num = 0
self.data = [[]] # 数据
def set_data(self, inf: List[List[int]]) -> None:
"""设定地图数据"""
self.data = inf
self.high_num = len(inf)
self.width_num = len(inf[0])
self.high_size = int(self.high / self.high_num)
self.width_size = int(self.wide / self.width_num)
self.high_size, self.width_size = min(self.high_size, self.width_size), min(self.high_size, self.width_size)
def display(self, screen, pos=(50, 50)):
"""绘制图像"""
x, y = pos # 绘制的左上角
for i in range(self.high_num):
for j in range(self.width_num):
# 对于每个点，根据地图中的不同数值，绘制不同效果，留作后续接口
# 此处应当还有一个函数的，不写了
if self.data[i][j] == 1: # 绘制一个填充的方块
pygame.draw.rect(screen, (155, 155, 155),
(x + j * self.width_size, y + i * self.high_size, self.width_size, self.high_size),
0)
if self.data[i][j] == 0: # 通过两次绘制，实现方框与填充不同颜色的效果
pygame.draw.rect(screen, "red",
(x + j * self.width_size, y + i * self.high_size, self.width_size, self.high_size),
0)
pygame.draw.rect(screen, (155, 155, 155),
(x + j * self.width_size, y + i * self.high_size, self.width_size, self.high_size),
1)
class MazeGazeShow(object):
def __init__(self, size=(SCREEN_WIDTH, SCREEN_HIGHT)):
self.high = size[1] - 100
self.wide = size[0] - 100
self.high_size = 0
self.width_size = 0
self.high_num = 0
self.width_num = 0
self.player = (0, 0)
self.player_path = []
self.data = [[]]
def set_data(self, inf: List[List[int]]) -> None:
self.data = inf
self.high_num = int(len(inf) / 2) # 有效网格数
self.width_num = int(len(inf[0]) / 2)
self.high_size = int(self.high / self.high_num)
self.width_size = int(self.wide / self.width_num)
self.high_size, self.width_size = min(self.high_size, self.width_size), min(self.high_size, self.width_size)
def display(self, screen, pos=(50, 50)):
x, y = pos
# 为整个界面铺设背景，方便后续添加功能
for i in range(self.high_num):
for j in range(self.width_num):
# if self.data[i * 2 + 1][j * 2 + 1] == 1:
pygame.draw.rect(screen, (155, 155, 155),
(x + j * self.width_size, y + i * self.high_size, self.width_size, self.high_size),
0)
# 水平
for i in range(self.high_num + 1):
for j in range(self.width_num):
if self.data[i * 2][j * 2 + 1] == 1:
pygame.draw.line(screen, (255, 0, 0), (x + j * self.width_size, y + i * self.high_size),
(x + (j + 1) * self.width_size, y + i * self.high_size), 2)
# 竖直
for i in range(self.high_num):
for j in range(self.width_num+1):
if self.data[i * 2 + 1][j * 2] == 1:
pygame.draw.line(screen, (255, 0, 0), (x + j * self.width_size, y + i * self.high_size),
(x + j * self.width_size, y + (i + 1) * self.high_size), 2)
def main():
# 初始化
pygame.init()
screen = pygame.display.set_mode((SCREEN_WIDTH * 2, SCREEN_HIGHT))
pygame.display.set_caption("迷宫可视化")
running = True
clock = pygame.time.Clock()
# 准备数据
maze = MazeShow()
maze1 = MazeGazeShow()
map1 = MazeMap((10, 10))
for line in map1.get_map():
print(line)
maze.set_data(map1.get_map())
maze1.set_data(map1.get_map())
# 绘制一次界面
screen.fill("white")
maze.display(screen)
maze1.display(screen, (SCREEN_WIDTH, 50))
# 刷新，目前不刷新也行
pygame.display.flip()
# 死循环
while running:
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
sys.exit()
# 需刷新请在此更新
clock.tick(10)
if __name__ == "__main__":
main()
————————————分割线——————————————————
代码解释：
我代码可读性还可以吧。。。（细节后面我再补）(已补)
理论部分放在后面了，文章不想重构了。
首先进入main函数，在此我创建了三个对象maze,maze1,map，分别对应我自定义的MazeShow类、MazeGazeShow类和MazeMap类。其中map初始化传入（10,10），该类在初始化时会自动生成有效格子为10*10的迷宫数据。
maze = MazeShow()
maze1 = MazeGazeShow()
map1 = MazeMap((10, 10))接下来查看生成的迷宫数据，并将数据传入maze,maze1。
for line in map1.get_map():
print(line)
maze.set_data(map1.get_map())
maze1.set_data(map1.get_map())然后将maze,maze1的数据展示在屏幕上。
# 绘制一次界面
screen.fill("white")
maze.display(screen)
maze1.display(screen, (SCREEN_WIDTH, 50))
# 刷新，目前不刷新也行
pygame.display.flip()其他部分为标准的pygame中main函数结构，请自学。
然后来看类是怎么实现的（代码不重复贴了）。
MazeMap类，初始化创建数据成员，调用set_map和solve_map方法。前者生成一个二维列表，表中的数据按照prim迷宫的数据结构来，构成一个初始化的迷宫。后者采用生成树的方法将迷宫的墙壁打通，变成一个可以使用的迷宫。其他函数均为辅助。
MazeShow类，初始化创建空数据成员，调用set_data方法接受二维列表构成的迷宫，根据全局变量屏幕大小自适应单个格子的宽度，取整后将长宽取小。display方法在传入的屏幕句柄上绘制图像，已传入的pos作为左上方的坐标，绘制整个地图，根据地图数据中的值不同，绘制不同的效果。绘制方框和方块组合城整个迷宫。在此类中空格与墙壁等价。
MazeGazeShow类，基本同MazeShow类，区别在于set_data方法自适应时，参照的是（m,n）而不是(2m+1, 2n+1)，display方法分三个部分实现：绘制背景，绘制横着的墙壁、竖着的墙壁。
于是整段代码可以概括为：使用pygame创建一个界面，实例化一个MazeMap对象，生成迷宫数据，生成方式为树算法，然后实例化两个MazeShow对象和MazeGazeShow对象，将生成的数据传入，设定自适应的地图数据，然后在界面上绘制，然后界面保持不变直到退出。
研究思路
首先普及一下迷宫生成问题中的数据结构，看这篇文章pygame迷宫生成-CSDN博客，比较难评的是他要收费，没有关系，看看预览部分就懂了（细节后面我再补）(已补)，毕竟我不收费是吧哈哈。
为什么要有这样的数据结构？首先我们知道，迷宫中的元素有两个，或者说可以通过和不可通过两种状态的元素，在此称为格子和墙壁。单独生成格子和墙壁构成一个迷宫是很困难的
（可以看我之前写的A*算法，就是解这类迷宫），但是提前将格子和 墙壁规规矩矩的设定好，然后将多余的墙壁打破，生成迷宫就变容易了。可以将迷宫抽象成许多个小部分，小部分的四周有墙壁，类似于一个九宫格，中间的部分代表格子，四周代表墙壁，许多个小部分组合成整体，格子与格子之间就会有两个墙壁，为了优化数据结构，直接合并，最终的初始化数据应当是下面的样子。
思路：
在上述数据结构的基础上，迷宫生成表面上看，是找个复杂的网络，把所有格子连接起来。于是大家将其抽象成树，为了确保起点和终点之间有且仅有一条路径，要求树中没有环，于是进一步抽象成最小生成树，所以啊，所有可以实现最小生成树的算法都有对应的迷宫生成算法。我学了prim算法，手搓的时候给搓成了dfs，然后用了ai辅助一下，写出来了prim。
算法：
prim算法，理论部分看看其他文章吧（细节后面我再补）(已补)
准备一个已访问列表，一个候选列表。
1. 初始化一个起始单元格（随机），将其加入已访问列表，并将它的所有相邻单元格加入候选列表。
2. 当候选列表不为空时：
a. 随机选择一个候选单元格，将其从候选列表移除，加入已访问列表。
b. 如果当前候选单元格周围有已访问单元格，随机选取一个，打通两者间的墙壁。
c. 将当前候选单元格周围所有未访问单元格加入候选列表（去重）。
思想：将所有格子分成三部分，已经访问、等待访问、未知。已经访问的部分，所有格子都是想通的，等待访问的部分，所有格子都可以加入已经访问，未知部分，无意义。
因为每个格子至少和两个其他格子相邻，所以按照上面的流程可以将所有格子遍历一遍。
这篇文章理论好prim算法（普里姆算法）详解，图文并茂 – C语言中文网
这篇文章讲了怎么在迷宫问题中应用Python编程：自制迷宫生成器-CSDN博客
(手机端预览可以最后看到思路)
dfs，额，应该都会。
应用：
假设生成迷宫为m行n列（后面写（m, n）了），按照上面的数据结构，初始化（2m+1, 2n+1）的二维列表全为1，然后把格子变成0，然后想办法把格子之间的墙壁打通（改为0）就成功了。最后类返回一个二维列表（数据结构真的很重要，某个文章代码崩了我一脸）。（细节后面我再补）（我的窘迫还是算了吧，不补了）
这样的数据，方便你我他是吧。
[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]绘制：
第一种没什么好说的，就是所有格子，依次按照格子的状态去绘制嘛。
重点是第二种，我实现的方式是，把上面的（2m+1, 2n+1）的二维列表，拆分出有效格子（m, n）和竖着的障碍（m+1, n）、横着的障碍（m, n+1），分三部分绘制。（细节后面我再补）（上方已补）
就是用了pygame库去实现的，也挺简单的，随便搜个入门教程看看图形怎么画就行。
扩展（可玩性角度）：
1. 在所有格子共同构成了一个最小生成树的情况下，随便指定两个点作为起始点就可以作为一个迷宫使用。所以真的迷宫你们自己扩展吧。
特别的，入口和出口在相对的墙壁上就是传统的迷宫了。 
2. 不使用最小生成树的算法，使用一般的树的算法，有时候会出来很多好玩的图形，而不使用树的算法，瞎写一些算法（不是我菜）也能有神奇的效果，毕竟有时候莫名其妙的就好玩了。 
3. 其实一个格子周围有八个墙壁，我们只利用了四个，这也挺可惜的是吧，做个八向的迷宫如何？有大佬实现了，我就不献丑了（大佬是真的强）。
生成随机迷宫：算法与应用场景详解-CSDN博客
4. 所有其他的游戏，但凡有地图的，比如推箱子、吃豆豆、坦克大战、元气的手游……
简简单单写了个吃豆豆，（后面单开讲吧）
5. 不仅是游戏嘛，现实问题也可以进行抽象，变成这个问题，比如城市路径规划。
总结
1. 学习东西要看本质，此问题就是个树的算法和prim的数据结构，加上编程思想。
2. 学会东西多扩展扩展，要不平时知识和游戏白学白玩了。
3. 强大的AI确实好用，但是花时间去做一件事情做好还是不错的。（AI是真会骗人）
4. 像这种无聊的东西写多了，不知不觉间就提升自我了。
题外话：
浪费我两天将近20个小时。
其他该说的但是没说的。
所有代码评论要吧，或者等等我给贴上，或者github开个源是吧，哈哈。
看到这里不点个赞？
作者：还是想睡觉zzz
