python 迷宫地图可视化（迷宫生成算法、pygame 地图可视化 可扩展 详细注释）_pygame 画迷宫
目录
前言：
实现：
研究思路
思路：
算法：
应用：
扩展（可玩性角度）：
总结
题外话：
前言：
该领域确实没什么新东西，我那天突发奇想学了迷宫生成算法，看的那些效果，哇塞哇塞，copy下来代码后一跑一个报错，然后自己实现了一遍，我觉得本文除了记录以外，当属迷宫绘制类最有意义了。（高端的东西写不来，低端的东西节省一下大家时间还是蛮不错的）
效果是下面的样子，自娱自乐了。
实现：
复制下述代码即可，注意todo，代码含义见注释。
补充解释：MazeMap用于处理迷宫数据，其中迷宫的生成有两种生成方式，分别为深搜的solved_map和prim算法的solved_map1，在初始化里面更新就行，自己改改也行。
然后是两种迷宫可视化方式，MazeShow和MazeGazeShow，对应上面的左右两种效果。
我只是给个可能行的应用，自己用最好修修，还有就是我的代码（一言难尽），有点小毒
import pygameimport sysimport random as rfrom typing import List# todo:# 1. maze_size处修改迷宫尺寸# 2. 迷宫可视化类与迷宫计算类# 3. main函数思路# 设定全局界面参数SCREEN_WIDTH = 800SCREEN_HIGHT = 600maze_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开个源是吧，哈哈。
看到这里不点个赞？
