简介基于 Python 与 Pygame 的迷宫小游戏项目是一套面向初学者的完整源码包适合作为课程设计、期末大作业或毕业设计参考。项目融入人工智能寻路算法涵盖迷宫随机生成与非随机地图设计、角色移动、步数统计、障碍反馈和 AI 自动走迷宫等核心功能代码附有详细注释即使刚接触 Python 也能较快理解并部署运行。压缩包共 19 个文件包含 5 个 Python 源文件主程序、迷宫生成、AI 寻路及辅助模块、10 张运行效果截图、README、使用说明文本和 docx 手册截图直观呈现常规界面、AI 寻路、障碍反馈、走出迷宫以及程序调试等场景便于对照学习。整个资源仅 1.1MB轻量简洁部署门槛低目前已有 271 人学习/下载。项目曾获 98 分课设评价导师认可度高借助源码注释、使用说明和配套截图读者可以理解迷宫生成与 AI 寻路算法的实现思路快速搭建可交互的迷宫游戏也能在此基础上二次开发是毕业设计与期末大作业的高性价比参考。1. 为什么迷宫小游戏要同时用到 Python、Pygame 和 AI 算法迷宫小游戏在 Python 练手项目里出现频率很高但很多所谓“源码”只是画了一个格子地图加上方向键移动AI 算法几乎没参与。真正值得动手的版本应该是把迷宫生成、Pygame 交互渲染、AI 自动求解三条线合成一个可运行的小系统地图由算法生成而不是手摆角色既能手动走也能让 AI 算法自己找到出口。对正在学数据结构和算法的开发者来说这比“纯鼠标移动小方块的 demo”更有价值。这套方案解决的其实是三个问题怎么用代码表示迷宫墙体、怎么保证生成的迷宫一定有解、怎么让 AI 算法在毫秒级找到一条可行路径。Python 负责逻辑Pygame 负责把逻辑画出来AI 算法负责生成和求解两条链路。适合有一定 Python 基础、想独立上手一个完整项目的开发者也适合准备面试时补一个“从数据结构到可视化”案例的人。思路比代码本身更重要下面从我实际整理源码时的顺序展开。2. 迷宫小游戏的地图数据从二维数组到生成算法2.1 为什么用“格点 墙体位掩码”而不是传统二维障碍数组常见做法是用二维数组存 0 和 10 是空地1 是墙。这个模型做贪吃蛇、推箱子很简单但做迷宫会很难受一个格子四面墙你无法表达“左边有墙、右边没墙”只能额外画四条边或者靠单元格相对位置去推算。迷宫这类问题更适合把每个格子当成一个节点只记录这个节点四面的墙是否存在。我一般用一个叫Cell的类来表达迷宫格子四个布尔值分别表示上右下左四面墙再加一个visited标记给生成算法用。class Cell: 一个迷宫格子只记录四面墙是否存在。 def __init__(self, row, col): self.row row self.col col self.walls {top: True, right: True, bottom: True, left: True} self.visited False开 始时四面墙全部为 True也就是一个封闭格子后面生成算法会成对地打通两个相邻格子之间的墙。比如打通(r, c)的右墙和(r, c1)的左墙两个格子就连通。这样表示的好处是方便两种算法共用同一套数据生成算法负责把墙从 True 改成 False寻路算法只走墙为 False 的边。如果你担心dict访问比元组慢在小游戏规模下完全不用在意。60×60 也就 3600 个格子walls[top]这种写法换来的是可读性。真要优化再改成位运算比如 1 表示上墙、2 表示右墙、4 表示下墙、8 表示左墙但调试时远不如字典直观。新手阶段先保证正确再谈优化。2.2 递归回溯生成核心算法与参数迷宫生成的算法很多最常见的是递归回溯也叫随机化深度优先搜索。思路很朴素从起点开始随机挑一个没访问过的邻居打掉中间的墙走过去走不下去就原路返回。这个过程最终会访问所有格子而且因为每一步都只打掉“两个已访问区域之间”的墙结果一定是一棵生成树迷宫任意两点之间只有一条路径。递归写法代码最短但有个隐患迷宫一大就容易爆栈。所以我在源码里用显式栈来实现逻辑等价但更可控也不依赖 Python 的递归深度上限。import random DIRS [ (-1, 0, top, bottom), (0, 1, right, left), (1, 0, bottom, top), (0, -1, left, right), ] def generate_maze(rows, cols): grid [[Cell(r, c) for c in range(cols)] for r in range(rows)] stack [(0, 0)] grid[0][0].visited True while stack: r, c stack[-1] candidates [] for dr, dc, wall, opp in DIRS: nr, nc r dr, c dc if 0 nr rows and 0 nc cols and not grid[nr][nc].visited: candidates.append((nr, nc, wall, opp)) if not candidates: stack.pop() continue nr, nc, wall, opp random.choice(candidates) grid[r][c].walls[wall] False grid[nr][nc].walls[opp] False grid[nr][nc].visited True stack.append((nr, nc)) return grid这段代码值得注意的就两个点。第一个是DIRS里四个方向的排列(dr, dc, wall, opp)表示从当前格子往哪个方向走、要打掉当前格子的哪面墙、目标格子的哪面墙。顺序不影响随机性但写错了会造成“墙打通了但格子之间有偏移”。第二个是stack[-1]的使用只有当前格子没有可访问邻居时才出栈保证了深度优先的“一条路走到底”。参数上最影响效果的是random.seed()。调迷宫生成的随机种子前先把种子固定后面生成的结果才能复现。迷宫尺寸rows、cols建议取值奇数比如 21×15这样起点和终点都能落在格子中心渲染也整齐。行列数太大时递归回溯生成的迷宫会有很长的走廊这是它的特性不算 bug。2.3 迷宫渲染把墙体位掩码画成 Pygame 画布生成完的迷宫只是一堆布尔值要用 Pygame 画出来。渲染的核心只有一件事遍历每个格子根据四面墙的状态逐条画线。每格边长用CELL_SIZE控制墙体用 2 像素白线背景用深色对比度足够后才看得清路径。import pygame def draw_maze(surface, grid, cell_size32): surface.fill((20, 20, 30)) rows, cols len(grid), len(grid[0]) for r in range(rows): for c in range(cols): x, y c * cell_size, r * cell_size cell grid[r][c] if cell.walls[top]: pygame.draw.line(surface, (230, 230, 230), (x, y), (x cell_size, y), 2) if cell.walls[right]: pygame.draw.line(surface, (230, 230, 230), (x cell_size, y), (x cell_size, y cell_size), 2) if cell.walls[bottom]: pygame.draw.line(surface, (230, 230, 230), (x, y cell_size), (x cell_size, y cell_size), 2) if cell.walls[left]: pygame.draw.line(surface, (230, 230, 230), (x, y), (x, y cell_size), 2)坐标换算规则是x col * cell_sizey row * cell_size一个格子覆盖从(x, y)到(x cell_size, y cell_size)的矩形区域。画线时上墙是矩形顶边右墙是矩形右边底墙是矩形底边左墙是矩形左边。一个容易忽略的点外边界不要额外画一圈否则会和最外一层格子的四面墙重叠出现双线。我的习惯是让起点在左上角(0, 0)终点在右下角(rows - 1, cols - 1)然后生成时把这两个格子的外墙打开一格这样入口和出口视觉上才明显。渲染效果确认后再进入寻路算法部分就不容易混淆逻辑和像素坐标。3. AI 算法介入BFS 最短路径与 A* 启发搜索3.1 用双端队列实现 BFS最短路径与父节点记录迷宫生成结束紧接着就是重头戏AI 算法自动找人。最容易讲清楚的是广度优先搜索 BFS。因为迷宫任意两点之间只有一条路径BFS 一定能找到解而且首次到达终点时用的步数就是最短路径长度。BFS 的代价也很低只需要维护一个队列和一个记录父节点的字典。from collections import deque def rebuild_path(parent, start, goal): path [] cur goal while cur is not None: path.append(cur) cur parent.get(cur) return path[::-1] def bfs_solve(grid, start, goal): rows, cols len(grid), len(grid[0]) parent {start: None} queue deque([start]) visited {start} while queue: r, c queue.popleft() if (r, c) goal: return rebuild_path(parent, start, goal) for dr, dc, wall, opp in DIRS: if grid[r][c].walls[wall]: continue nr, nc r dr, c dc if (nr, nc) not in visited: visited.add((nr, nc)) parent[(nr, nc)] (r, c) queue.append((nr, nc)) return None这里有个细节判断某个方向能不能走用的是“从当前格子出发要穿过的墙”wall而不是目标格子的墙。原因是从(r, c)走到(r-1, c)需要确认的是当前格子的上墙是开的。如果误判成目标格子的下墙出口边界处就会出问题。BFS 在 60×60 的迷宫上扩展的节点数通常远小于全部格子数因为迷宫树结构让很多分支很快就到底了所以性能上完全够用。它最大的价值是“步数最少”在完全连通的迷宫里几乎等价于最优路线。3.2 A* 寻路的启发函数选择曼哈顿距离与优先级队列BFS 虽然稳但漫无目的朝四个方向扩散在接近目标时才慢慢收窄。A* 加入了启发函数优先扩展“当前代价 估计剩余代价”最小的节点。迷宫是四连通网格最常用的启发函数就是曼哈顿距离因为它算的是两个格子之间不考虑墙时还需要移动的最少步数不会高估剩余距离所以 A* 能找到最优路径。import heapq def manhattan(a, b): return abs(a[0] - b[0]) abs(a[1] - b[1]) def get_open_neighbors(grid, pos): r, c pos neighbors [] for dr, dc, wall, _ in DIRS: if grid[r][c].walls[wall]: continue nr, nc r dr, c dc neighbors.append((nr, nc)) return neighbors def astar_solve(grid, start, goal): g_score {start: 0} parent {start: None} heap [(manhattan(start, goal), 0, start)] while heap: _, _, current heapq.heappop(heap) if current goal: return rebuild_path(parent, start, goal) for nbr in get_open_neighbors(grid, current): tentative_g g_score[current] 1 if tentative_g g_score.get(nbr, float(inf)): parent[nbr] current g_score[nbr] tentative_g f tentative_g manhattan(nbr, goal) heapq.heappush(heap, (f, tentative_g, nbr)) return None用heapq的时候要注意堆里存的是三元组(f_score, g_score, pos)。之所以把g_score放第二位是为了当 f 值相同的时候让更接近起点的节点先出堆这只是个排序细节不影响正确性。parent字典存的是“我是从哪个格子来的”重建路径时从终点一路回溯到起点再反转。A* 和 BFS 在这个场景下最大的差别是扩展节点数。迷宫通达路径单一A* 的启发函数会明显把搜索方向“拉”向终点在长走廊里尤其省事。代价是代码复杂度略高还要维护g_score。如果你的目标是讲解算法两个都写上用同一个迷宫对比扩展节点数效果比口头讲十遍都直观。3.3 把 AI 路径变成 Pygame 动画算法返回的路径是(row, col)坐标列表直接拿去画线就能看到完整路径。但一次性画完会少掉“过程感”也看不出 AI 是怎么一步步走的。更好玩的做法是写一个AIPlayer类每一帧只前进一格用累计时间控制移动速度。class AIPlayer: def __init__(self, path, start_pos, step_interval0.08): self.path path self.index 0 self.step_interval step_interval self.timer 0 self.pos start_pos self.finished False def update(self, dt): if self.finished or not self.path: return self.timer dt if self.timer self.step_interval: self.timer 0 if self.index len(self.path) - 1: self.index 1 self.pos self.path[self.index] else: self.finished Truedt是上一帧到这一帧的时间单位是秒。不管电脑帧率是 30 还是 120只要dt累计到0.08秒角色就走一格这就是为什么移动速度和帧率解耦。如果你直接在游戏循环里for pos in path: move()会让动画瞬间播放完画面完全卡死。路径动画我一般分两步渲染先把已走过的路径用半透明色块画出来再把角色当前位置画成高亮圆点。这样既能看清 AI 的决策路线又不至于被整条路径把地图盖住。4. 避坑Pygame 和寻路结合时的 4 个高频翻车点4.1 画面假死算法一次跑完Pygame 没有机会刷新现象程序启动后窗口定格等几秒后突然跳出最终结果中间完全看不到生成或寻路动画。原因把迷宫生成循环或者寻路循环直接写在 Pygame 的事件循环里并且没有在循环中调用pygame.event.pump()或者更新画面。Pygame 不是异步渲染库你在一段代码里跑 3600 次操作期间窗口消息全部堆积在系统队列里画面自然像死了一样。解决把“一步操作”抽象成生成器或迭代器。每执行一次next(gen)就让出一帧让主循环有机会刷新画面和响应退出事件。迷宫生成改成生成器后代码逻辑不变只是从“一口气跑完”变成“一帧跑一步”。def generate_maze_step_by_step(rows, cols): grid [[Cell(r, c) for c in range(cols)] for r in range(rows)] stack [(0, 0)] grid[0][0].visited True while stack: r, c stack[-1] candidates [...] if candidates: nr, nc, wall, opp random.choice(candidates) grid[r][c].walls[wall] False grid[nr][nc].walls[opp] False grid[nr][nc].visited True stack.append((nr, nc)) else: stack.pop() yield grid然后在主循环里写gen generate_maze_step_by_step(...)每帧调一次next(gen, None)再pygame.display.flip()。这个套路同样适合 BFS / A*只要把搜索循环改成手动栈或手动队列然后在外层yield当前状态。4.2 递归深度超限迷宫大点就 RecursionError现象rows和cols从 10 改成 50程序直接报RecursionError: maximum recursion depth exceeded。原因递归回溯生成算法如果写成函数递归每走一格就会多一层调用。Python 默认递归上限通常是 1000而迷宫路径轻松超过几百层。解决我在第 2 章给出的版本就是显式栈不依赖递归深度所以不会触发这个错误。如果你非要用递归写法也可以sys.setrecursionlimit(10000)临时解除限制但这只是把爆炸点往后推不如换栈来得干净。遇到这个报错时先自查是不是生成算法用了递归再决定改栈还是改递归上限。4.3 A* 堆里塞了太多重复节点内存和耗时一起涨现象30×30 的迷宫 A* 秒出换到 80×80 之后明显卡顿任务管理器里内存占用也涨得离谱。原因写 A* 时只往堆里 push没有判断该节点是否已经有一个更优的g_score。同一个格子可能被多个方向找到每次都 push 一遍堆里堆了重复坐标越到后面越浪费。解决在入堆前先判断tentative_g g_score.get(nbr, inf)只有找到更短路径时才更新并 push。即使这样堆里仍可能残留旧记录但 Python 堆不支持“改优先级”操作这种丢弃旧记录的懒惰删除是常见做法。出堆时用g_score[current]和堆里存的g对比如果发现堆里的 g 大于当前已知最优值直接忽略这一次出堆。while heap: _, old_g, current heapq.heappop(heap) if old_g ! g_score[current]: continue ...4.4 角色穿墙渲染坐标和逻辑坐标没有统一现象AI 走的路径在算法结果里明明是一条横线画到屏幕上却歪了一格甚至角色从“墙缝”里走过去。原因逻辑坐标(row, col)和像素坐标(x, y)换算出错。最常见的是把row当 X 轴、col当 Y 轴或者画墙时用cell_size但画角色时用了cell_size wall_thickness。解决定死一套换算函数所有涉及坐标的代码都走这一个入口。def grid_to_pixel(pos, cell_size): r, c pos return c * cell_size, r * cell_size def pixel_to_grid(px, py, cell_size): return py // cell_size, px // cell_size规则是行号永远对应 Y列号永远对应 X。角色位置、路径点、鼠标点击检测都用这两个函数转换不要把像素坐标直接存进逻辑层。5. 使用说明源码目录、依赖安装和运行参数5.1 环境与依赖Python 3.10 以上加 pygame 即可这份源码不依赖任何第三方复杂库核心只有两个包pygame做窗口和事件其余全是 Python 标准库。创建虚拟环境后直接装 pygame不要用pip install pygame装到全局虚拟环境隔离能省掉不少环境冲突的麻烦。python -m venv .venv source .venv/bin/activate # Windows 用 .venv\Scripts\activate pip install pygame python main.py如果你用的是 Python 3.12 或 3.13建议装 pygame 的最新 2.x 版本老版本在某些平台上对新版 Python 的兼容性不好。装完后先跑一句python -c import pygame; print(pygame.version)能打印版本号就说明环境没问题。不要用 Anaconda 里默认带的老 pygame 版本遇到窗口不显示先往这查。5.2 源码目录结构与入口文件我整理源码时习惯把不同职责放不同文件迷宫游戏这种项目没必要追求一个文件几百行。下面是我推荐的目录结构你也可以按自己的习惯调整但入口文件和配置文件的区分值得保留。文件/目录作用main.py程序入口初始化 Pygame管理主循环和游戏状态cell.py定义Cell类描述单个迷宫格子maze_gen.py迷宫生成算法递归回溯的两种版本pathfind.pyBFS 与 A* 寻路算法ai_player.pyAIPlayer类控制 AI 角色沿路径移动settings.py全局参数包括尺寸、速度、颜色README.md使用说明运行命令和按键操作入口文件main.py不直接写算法细节只负责串流程读配置、生成迷宫、初始化玩家、进入游戏循环。这样别人拿到源码后看main.py就能知道程序怎么跑想改算法时去对应文件找比全堆在入口文件里友好得多。5.3 修改迷宫尺寸、步长和随机种子所有和运行效果相关的参数统一放settings.py方便调试。ROWS 15 COLS 21 CELL_SIZE 32 WALL_THICKNESS 2 AI_SPEED 0.08 MANUAL_SPEED 0.05 RANDOM_SEED 7ROWS和COLS控制迷宫大小。调大时注意窗口尺寸COLS * CELL_SIZE就是画布宽度屏幕不够大会截断。AI_SPEED的单位是“秒/格”0.08 表示每 0.08 秒走一格数值越小越快。MANUAL_SPEED是手动模式下的移动冷却时间避免按一下方向键连跳两格。RANDOM_SEED是个很容易被忽略但很重要的参数。固定随机种子后同一个迷宫每次运行都长一样这对复现 bug、对比不同寻路算法特别有用。不固定种子每次重启程序迷宫都不同你可能白天调试好的路径到晚上就复现不出来了。6. 把迷宫小游戏源码加一个 AI 自动演示模式6.1 自动演示模式按一个键从生成到求解默认代码里玩家是手动控制但很多场景下观众更想看到“AI 自己走”。我加了一个模式开关启动时若传入--demo则程序自动执行“生成迷宫 → 高亮路径 → AI 沿线走到终点”的完整流程中间不接收键盘输入。import sys DEMO_MODE --demo in sys.argv if DEMO_MODE: state generating else: state playing主循环里按状态机切分逻辑generating状态每帧推进一次迷宫生成生成器solving状态让 A* 在后台搜完并缓存路径playing状态由AIPlayer沿路径移动。每个状态都不阻塞主循环这样动画才连贯。这个演示模式对讲课很有用。开讲前先跑一遍完整流程观众能看到迷宫像画出来一样逐格生成然后路径像水一样慢慢流向出口。比截两张静态图有说服力得多。6.2 用路径长度和扩展节点数评估 AI 算法做完自动演示后别急着收工。我给两个寻路算法各加一个计数器统计“总共弹出多少个节点”然后打印出来对比就很直观BFS 扩展节点数明显高于 A*尤其在地图比较大的时候。这个指标比单纯的运行时间更稳定因为运行时间受机器影响扩展节点数是纯算法行为。class SearchStats: def __init__(self): self.expanded 0 def count(self): self.expanded 1 stats SearchStats() # 在 bfs_solve / astar_solve 的循环开头调用 stats.count()手动模式也别删掉这是排查算法问题的关键工具。我最初做完 A* 后总觉得路径“不够聪明”后来才发现是我的墙判断写反了导致 AI 只会在部分通道里绕路。手动走一遍同一张迷宫对比步数很快就能定位是算法问题还是渲染问题。这套迷宫小游戏源码做完后最大的收获不是学会了 Pygame 画线而是理解了“同一种数据结构怎么被两个方向相反的逻辑复用”生成算法往死里打通墙寻路算法在打通的墙上找最短路。你把这个思路迁移到任何网格类游戏里从塔防的路径点到战棋的移动范围都是同一套底子。我第一次给模拟项目X加自动寻路时也掉进过画面假死的坑后来养成习惯只要 Pygame 里要做长耗时逻辑第一反应就是拆步、生成器、让出主循环这三个词能挡掉大多数翻车。希望帮到你。本文还有配套的精品资源点击获取
简介基于 Python 与 Pygame 的迷宫小游戏项目是一套面向初学者的完整源码包适合作为课程设计、期末大作业或毕业设计参考。项目融入人工智能寻路算法涵盖迷宫随机生成与非随机地图设计、角色移动、步数统计、障碍反馈和 AI 自动走迷宫等核心功能代码附有详细注释即使刚接触 Python 也能较快理解并部署运行。压缩包共 19 个文件包含 5 个 Python 源文件主程序、迷宫生成、AI 寻路及辅助模块、10 张运行效果截图、README、使用说明文本和 docx 手册截图直观呈现常规界面、AI 寻路、障碍反馈、走出迷宫以及程序调试等场景便于对照学习。整个资源仅 1.1MB轻量简洁部署门槛低目前已有 271 人学习/下载。项目曾获 98 分课设评价导师认可度高借助源码注释、使用说明和配套截图读者可以理解迷宫生成与 AI 寻路算法的实现思路快速搭建可交互的迷宫游戏也能在此基础上二次开发是毕业设计与期末大作业的高性价比参考。1. 为什么迷宫小游戏要同时用到 Python、Pygame 和 AI 算法迷宫小游戏在 Python 练手项目里出现频率很高但很多所谓“源码”只是画了一个格子地图加上方向键移动AI 算法几乎没参与。真正值得动手的版本应该是把迷宫生成、Pygame 交互渲染、AI 自动求解三条线合成一个可运行的小系统地图由算法生成而不是手摆角色既能手动走也能让 AI 算法自己找到出口。对正在学数据结构和算法的开发者来说这比“纯鼠标移动小方块的 demo”更有价值。这套方案解决的其实是三个问题怎么用代码表示迷宫墙体、怎么保证生成的迷宫一定有解、怎么让 AI 算法在毫秒级找到一条可行路径。Python 负责逻辑Pygame 负责把逻辑画出来AI 算法负责生成和求解两条链路。适合有一定 Python 基础、想独立上手一个完整项目的开发者也适合准备面试时补一个“从数据结构到可视化”案例的人。思路比代码本身更重要下面从我实际整理源码时的顺序展开。2. 迷宫小游戏的地图数据从二维数组到生成算法2.1 为什么用“格点 墙体位掩码”而不是传统二维障碍数组常见做法是用二维数组存 0 和 10 是空地1 是墙。这个模型做贪吃蛇、推箱子很简单但做迷宫会很难受一个格子四面墙你无法表达“左边有墙、右边没墙”只能额外画四条边或者靠单元格相对位置去推算。迷宫这类问题更适合把每个格子当成一个节点只记录这个节点四面的墙是否存在。我一般用一个叫Cell的类来表达迷宫格子四个布尔值分别表示上右下左四面墙再加一个visited标记给生成算法用。class Cell: 一个迷宫格子只记录四面墙是否存在。 def __init__(self, row, col): self.row row self.col col self.walls {top: True, right: True, bottom: True, left: True} self.visited False开 始时四面墙全部为 True也就是一个封闭格子后面生成算法会成对地打通两个相邻格子之间的墙。比如打通(r, c)的右墙和(r, c1)的左墙两个格子就连通。这样表示的好处是方便两种算法共用同一套数据生成算法负责把墙从 True 改成 False寻路算法只走墙为 False 的边。如果你担心dict访问比元组慢在小游戏规模下完全不用在意。60×60 也就 3600 个格子walls[top]这种写法换来的是可读性。真要优化再改成位运算比如 1 表示上墙、2 表示右墙、4 表示下墙、8 表示左墙但调试时远不如字典直观。新手阶段先保证正确再谈优化。2.2 递归回溯生成核心算法与参数迷宫生成的算法很多最常见的是递归回溯也叫随机化深度优先搜索。思路很朴素从起点开始随机挑一个没访问过的邻居打掉中间的墙走过去走不下去就原路返回。这个过程最终会访问所有格子而且因为每一步都只打掉“两个已访问区域之间”的墙结果一定是一棵生成树迷宫任意两点之间只有一条路径。递归写法代码最短但有个隐患迷宫一大就容易爆栈。所以我在源码里用显式栈来实现逻辑等价但更可控也不依赖 Python 的递归深度上限。import random DIRS [ (-1, 0, top, bottom), (0, 1, right, left), (1, 0, bottom, top), (0, -1, left, right), ] def generate_maze(rows, cols): grid [[Cell(r, c) for c in range(cols)] for r in range(rows)] stack [(0, 0)] grid[0][0].visited True while stack: r, c stack[-1] candidates [] for dr, dc, wall, opp in DIRS: nr, nc r dr, c dc if 0 nr rows and 0 nc cols and not grid[nr][nc].visited: candidates.append((nr, nc, wall, opp)) if not candidates: stack.pop() continue nr, nc, wall, opp random.choice(candidates) grid[r][c].walls[wall] False grid[nr][nc].walls[opp] False grid[nr][nc].visited True stack.append((nr, nc)) return grid这段代码值得注意的就两个点。第一个是DIRS里四个方向的排列(dr, dc, wall, opp)表示从当前格子往哪个方向走、要打掉当前格子的哪面墙、目标格子的哪面墙。顺序不影响随机性但写错了会造成“墙打通了但格子之间有偏移”。第二个是stack[-1]的使用只有当前格子没有可访问邻居时才出栈保证了深度优先的“一条路走到底”。参数上最影响效果的是random.seed()。调迷宫生成的随机种子前先把种子固定后面生成的结果才能复现。迷宫尺寸rows、cols建议取值奇数比如 21×15这样起点和终点都能落在格子中心渲染也整齐。行列数太大时递归回溯生成的迷宫会有很长的走廊这是它的特性不算 bug。2.3 迷宫渲染把墙体位掩码画成 Pygame 画布生成完的迷宫只是一堆布尔值要用 Pygame 画出来。渲染的核心只有一件事遍历每个格子根据四面墙的状态逐条画线。每格边长用CELL_SIZE控制墙体用 2 像素白线背景用深色对比度足够后才看得清路径。import pygame def draw_maze(surface, grid, cell_size32): surface.fill((20, 20, 30)) rows, cols len(grid), len(grid[0]) for r in range(rows): for c in range(cols): x, y c * cell_size, r * cell_size cell grid[r][c] if cell.walls[top]: pygame.draw.line(surface, (230, 230, 230), (x, y), (x cell_size, y), 2) if cell.walls[right]: pygame.draw.line(surface, (230, 230, 230), (x cell_size, y), (x cell_size, y cell_size), 2) if cell.walls[bottom]: pygame.draw.line(surface, (230, 230, 230), (x, y cell_size), (x cell_size, y cell_size), 2) if cell.walls[left]: pygame.draw.line(surface, (230, 230, 230), (x, y), (x, y cell_size), 2)坐标换算规则是x col * cell_sizey row * cell_size一个格子覆盖从(x, y)到(x cell_size, y cell_size)的矩形区域。画线时上墙是矩形顶边右墙是矩形右边底墙是矩形底边左墙是矩形左边。一个容易忽略的点外边界不要额外画一圈否则会和最外一层格子的四面墙重叠出现双线。我的习惯是让起点在左上角(0, 0)终点在右下角(rows - 1, cols - 1)然后生成时把这两个格子的外墙打开一格这样入口和出口视觉上才明显。渲染效果确认后再进入寻路算法部分就不容易混淆逻辑和像素坐标。3. AI 算法介入BFS 最短路径与 A* 启发搜索3.1 用双端队列实现 BFS最短路径与父节点记录迷宫生成结束紧接着就是重头戏AI 算法自动找人。最容易讲清楚的是广度优先搜索 BFS。因为迷宫任意两点之间只有一条路径BFS 一定能找到解而且首次到达终点时用的步数就是最短路径长度。BFS 的代价也很低只需要维护一个队列和一个记录父节点的字典。from collections import deque def rebuild_path(parent, start, goal): path [] cur goal while cur is not None: path.append(cur) cur parent.get(cur) return path[::-1] def bfs_solve(grid, start, goal): rows, cols len(grid), len(grid[0]) parent {start: None} queue deque([start]) visited {start} while queue: r, c queue.popleft() if (r, c) goal: return rebuild_path(parent, start, goal) for dr, dc, wall, opp in DIRS: if grid[r][c].walls[wall]: continue nr, nc r dr, c dc if (nr, nc) not in visited: visited.add((nr, nc)) parent[(nr, nc)] (r, c) queue.append((nr, nc)) return None这里有个细节判断某个方向能不能走用的是“从当前格子出发要穿过的墙”wall而不是目标格子的墙。原因是从(r, c)走到(r-1, c)需要确认的是当前格子的上墙是开的。如果误判成目标格子的下墙出口边界处就会出问题。BFS 在 60×60 的迷宫上扩展的节点数通常远小于全部格子数因为迷宫树结构让很多分支很快就到底了所以性能上完全够用。它最大的价值是“步数最少”在完全连通的迷宫里几乎等价于最优路线。3.2 A* 寻路的启发函数选择曼哈顿距离与优先级队列BFS 虽然稳但漫无目的朝四个方向扩散在接近目标时才慢慢收窄。A* 加入了启发函数优先扩展“当前代价 估计剩余代价”最小的节点。迷宫是四连通网格最常用的启发函数就是曼哈顿距离因为它算的是两个格子之间不考虑墙时还需要移动的最少步数不会高估剩余距离所以 A* 能找到最优路径。import heapq def manhattan(a, b): return abs(a[0] - b[0]) abs(a[1] - b[1]) def get_open_neighbors(grid, pos): r, c pos neighbors [] for dr, dc, wall, _ in DIRS: if grid[r][c].walls[wall]: continue nr, nc r dr, c dc neighbors.append((nr, nc)) return neighbors def astar_solve(grid, start, goal): g_score {start: 0} parent {start: None} heap [(manhattan(start, goal), 0, start)] while heap: _, _, current heapq.heappop(heap) if current goal: return rebuild_path(parent, start, goal) for nbr in get_open_neighbors(grid, current): tentative_g g_score[current] 1 if tentative_g g_score.get(nbr, float(inf)): parent[nbr] current g_score[nbr] tentative_g f tentative_g manhattan(nbr, goal) heapq.heappush(heap, (f, tentative_g, nbr)) return None用heapq的时候要注意堆里存的是三元组(f_score, g_score, pos)。之所以把g_score放第二位是为了当 f 值相同的时候让更接近起点的节点先出堆这只是个排序细节不影响正确性。parent字典存的是“我是从哪个格子来的”重建路径时从终点一路回溯到起点再反转。A* 和 BFS 在这个场景下最大的差别是扩展节点数。迷宫通达路径单一A* 的启发函数会明显把搜索方向“拉”向终点在长走廊里尤其省事。代价是代码复杂度略高还要维护g_score。如果你的目标是讲解算法两个都写上用同一个迷宫对比扩展节点数效果比口头讲十遍都直观。3.3 把 AI 路径变成 Pygame 动画算法返回的路径是(row, col)坐标列表直接拿去画线就能看到完整路径。但一次性画完会少掉“过程感”也看不出 AI 是怎么一步步走的。更好玩的做法是写一个AIPlayer类每一帧只前进一格用累计时间控制移动速度。class AIPlayer: def __init__(self, path, start_pos, step_interval0.08): self.path path self.index 0 self.step_interval step_interval self.timer 0 self.pos start_pos self.finished False def update(self, dt): if self.finished or not self.path: return self.timer dt if self.timer self.step_interval: self.timer 0 if self.index len(self.path) - 1: self.index 1 self.pos self.path[self.index] else: self.finished Truedt是上一帧到这一帧的时间单位是秒。不管电脑帧率是 30 还是 120只要dt累计到0.08秒角色就走一格这就是为什么移动速度和帧率解耦。如果你直接在游戏循环里for pos in path: move()会让动画瞬间播放完画面完全卡死。路径动画我一般分两步渲染先把已走过的路径用半透明色块画出来再把角色当前位置画成高亮圆点。这样既能看清 AI 的决策路线又不至于被整条路径把地图盖住。4. 避坑Pygame 和寻路结合时的 4 个高频翻车点4.1 画面假死算法一次跑完Pygame 没有机会刷新现象程序启动后窗口定格等几秒后突然跳出最终结果中间完全看不到生成或寻路动画。原因把迷宫生成循环或者寻路循环直接写在 Pygame 的事件循环里并且没有在循环中调用pygame.event.pump()或者更新画面。Pygame 不是异步渲染库你在一段代码里跑 3600 次操作期间窗口消息全部堆积在系统队列里画面自然像死了一样。解决把“一步操作”抽象成生成器或迭代器。每执行一次next(gen)就让出一帧让主循环有机会刷新画面和响应退出事件。迷宫生成改成生成器后代码逻辑不变只是从“一口气跑完”变成“一帧跑一步”。def generate_maze_step_by_step(rows, cols): grid [[Cell(r, c) for c in range(cols)] for r in range(rows)] stack [(0, 0)] grid[0][0].visited True while stack: r, c stack[-1] candidates [...] if candidates: nr, nc, wall, opp random.choice(candidates) grid[r][c].walls[wall] False grid[nr][nc].walls[opp] False grid[nr][nc].visited True stack.append((nr, nc)) else: stack.pop() yield grid然后在主循环里写gen generate_maze_step_by_step(...)每帧调一次next(gen, None)再pygame.display.flip()。这个套路同样适合 BFS / A*只要把搜索循环改成手动栈或手动队列然后在外层yield当前状态。4.2 递归深度超限迷宫大点就 RecursionError现象rows和cols从 10 改成 50程序直接报RecursionError: maximum recursion depth exceeded。原因递归回溯生成算法如果写成函数递归每走一格就会多一层调用。Python 默认递归上限通常是 1000而迷宫路径轻松超过几百层。解决我在第 2 章给出的版本就是显式栈不依赖递归深度所以不会触发这个错误。如果你非要用递归写法也可以sys.setrecursionlimit(10000)临时解除限制但这只是把爆炸点往后推不如换栈来得干净。遇到这个报错时先自查是不是生成算法用了递归再决定改栈还是改递归上限。4.3 A* 堆里塞了太多重复节点内存和耗时一起涨现象30×30 的迷宫 A* 秒出换到 80×80 之后明显卡顿任务管理器里内存占用也涨得离谱。原因写 A* 时只往堆里 push没有判断该节点是否已经有一个更优的g_score。同一个格子可能被多个方向找到每次都 push 一遍堆里堆了重复坐标越到后面越浪费。解决在入堆前先判断tentative_g g_score.get(nbr, inf)只有找到更短路径时才更新并 push。即使这样堆里仍可能残留旧记录但 Python 堆不支持“改优先级”操作这种丢弃旧记录的懒惰删除是常见做法。出堆时用g_score[current]和堆里存的g对比如果发现堆里的 g 大于当前已知最优值直接忽略这一次出堆。while heap: _, old_g, current heapq.heappop(heap) if old_g ! g_score[current]: continue ...4.4 角色穿墙渲染坐标和逻辑坐标没有统一现象AI 走的路径在算法结果里明明是一条横线画到屏幕上却歪了一格甚至角色从“墙缝”里走过去。原因逻辑坐标(row, col)和像素坐标(x, y)换算出错。最常见的是把row当 X 轴、col当 Y 轴或者画墙时用cell_size但画角色时用了cell_size wall_thickness。解决定死一套换算函数所有涉及坐标的代码都走这一个入口。def grid_to_pixel(pos, cell_size): r, c pos return c * cell_size, r * cell_size def pixel_to_grid(px, py, cell_size): return py // cell_size, px // cell_size规则是行号永远对应 Y列号永远对应 X。角色位置、路径点、鼠标点击检测都用这两个函数转换不要把像素坐标直接存进逻辑层。5. 使用说明源码目录、依赖安装和运行参数5.1 环境与依赖Python 3.10 以上加 pygame 即可这份源码不依赖任何第三方复杂库核心只有两个包pygame做窗口和事件其余全是 Python 标准库。创建虚拟环境后直接装 pygame不要用pip install pygame装到全局虚拟环境隔离能省掉不少环境冲突的麻烦。python -m venv .venv source .venv/bin/activate # Windows 用 .venv\Scripts\activate pip install pygame python main.py如果你用的是 Python 3.12 或 3.13建议装 pygame 的最新 2.x 版本老版本在某些平台上对新版 Python 的兼容性不好。装完后先跑一句python -c import pygame; print(pygame.version)能打印版本号就说明环境没问题。不要用 Anaconda 里默认带的老 pygame 版本遇到窗口不显示先往这查。5.2 源码目录结构与入口文件我整理源码时习惯把不同职责放不同文件迷宫游戏这种项目没必要追求一个文件几百行。下面是我推荐的目录结构你也可以按自己的习惯调整但入口文件和配置文件的区分值得保留。文件/目录作用main.py程序入口初始化 Pygame管理主循环和游戏状态cell.py定义Cell类描述单个迷宫格子maze_gen.py迷宫生成算法递归回溯的两种版本pathfind.pyBFS 与 A* 寻路算法ai_player.pyAIPlayer类控制 AI 角色沿路径移动settings.py全局参数包括尺寸、速度、颜色README.md使用说明运行命令和按键操作入口文件main.py不直接写算法细节只负责串流程读配置、生成迷宫、初始化玩家、进入游戏循环。这样别人拿到源码后看main.py就能知道程序怎么跑想改算法时去对应文件找比全堆在入口文件里友好得多。5.3 修改迷宫尺寸、步长和随机种子所有和运行效果相关的参数统一放settings.py方便调试。ROWS 15 COLS 21 CELL_SIZE 32 WALL_THICKNESS 2 AI_SPEED 0.08 MANUAL_SPEED 0.05 RANDOM_SEED 7ROWS和COLS控制迷宫大小。调大时注意窗口尺寸COLS * CELL_SIZE就是画布宽度屏幕不够大会截断。AI_SPEED的单位是“秒/格”0.08 表示每 0.08 秒走一格数值越小越快。MANUAL_SPEED是手动模式下的移动冷却时间避免按一下方向键连跳两格。RANDOM_SEED是个很容易被忽略但很重要的参数。固定随机种子后同一个迷宫每次运行都长一样这对复现 bug、对比不同寻路算法特别有用。不固定种子每次重启程序迷宫都不同你可能白天调试好的路径到晚上就复现不出来了。6. 把迷宫小游戏源码加一个 AI 自动演示模式6.1 自动演示模式按一个键从生成到求解默认代码里玩家是手动控制但很多场景下观众更想看到“AI 自己走”。我加了一个模式开关启动时若传入--demo则程序自动执行“生成迷宫 → 高亮路径 → AI 沿线走到终点”的完整流程中间不接收键盘输入。import sys DEMO_MODE --demo in sys.argv if DEMO_MODE: state generating else: state playing主循环里按状态机切分逻辑generating状态每帧推进一次迷宫生成生成器solving状态让 A* 在后台搜完并缓存路径playing状态由AIPlayer沿路径移动。每个状态都不阻塞主循环这样动画才连贯。这个演示模式对讲课很有用。开讲前先跑一遍完整流程观众能看到迷宫像画出来一样逐格生成然后路径像水一样慢慢流向出口。比截两张静态图有说服力得多。6.2 用路径长度和扩展节点数评估 AI 算法做完自动演示后别急着收工。我给两个寻路算法各加一个计数器统计“总共弹出多少个节点”然后打印出来对比就很直观BFS 扩展节点数明显高于 A*尤其在地图比较大的时候。这个指标比单纯的运行时间更稳定因为运行时间受机器影响扩展节点数是纯算法行为。class SearchStats: def __init__(self): self.expanded 0 def count(self): self.expanded 1 stats SearchStats() # 在 bfs_solve / astar_solve 的循环开头调用 stats.count()手动模式也别删掉这是排查算法问题的关键工具。我最初做完 A* 后总觉得路径“不够聪明”后来才发现是我的墙判断写反了导致 AI 只会在部分通道里绕路。手动走一遍同一张迷宫对比步数很快就能定位是算法问题还是渲染问题。这套迷宫小游戏源码做完后最大的收获不是学会了 Pygame 画线而是理解了“同一种数据结构怎么被两个方向相反的逻辑复用”生成算法往死里打通墙寻路算法在打通的墙上找最短路。你把这个思路迁移到任何网格类游戏里从塔防的路径点到战棋的移动范围都是同一套底子。我第一次给模拟项目X加自动寻路时也掉进过画面假死的坑后来养成习惯只要 Pygame 里要做长耗时逻辑第一反应就是拆步、生成器、让出主循环这三个词能挡掉大多数翻车。希望帮到你。本文还有配套的精品资源点击获取
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
