Python+Pygame+AI算法：从迷宫生成到自动寻路实战

简介：基于 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 和 1，0 是空地，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, c+1)的左墙，两个格子就连通。这样表示的好处是方便两种算法共用同一套数据：生成算法负责把墙从 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_size=32): 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_size，y = 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_interval=0.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 = True

dt是上一帧到这一帧的时间，单位是秒。不管电脑帧率是 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不直接写算法细节，只负责串流程：读配置、生成迷宫、初始化玩家、进入游戏循环。这样别人拿到源码后看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 = 7

ROWS和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 里要做长耗时逻辑，第一反应就是拆步、生成器、让出主循环，这三个词能挡掉大多数翻车。希望帮到你。

本文还有配套的精品资源，点击获取