简介这是一份由 Andrei 与 Marius 合作的 Java 版 Pacman 游戏项目源码适合正在学习 Java 游戏开发、GUI 设计与基础人工智能的开发者参考。项目围绕经典吃豆人玩法覆盖游戏循环、碰撞检测、键盘事件处理、多线程动画等关键实现可帮助读者理解面向对象编程在真实小游戏中的应用。压缩包体积约 12KB包含 12 个文件其中 5 个 Java 源文件、3 个 class 编译产物、1 个 Markdown 说明文档以及 .classpath、.project、.prefs 等工程配置文件整体结构紧凑可直接导入 IDE 查看运行便于对照源码排查问题。目前已有 152 人学习下载。通过这份代码可快速了解 Pacman 核心机制的最小实现包括角色移动、迷宫地图布局和鬼魂追击逻辑同时可借此练习读代码、改参数、扩展 AI 策略是难得的轻量级 Java 练手项目。1. pacman-andreimarius 是什么能吃豆也会跑路的 AI 课程项目搜索「pacman」会得到两拨完全不同的结果一拨是 Arch Linux 包管理器满屏都是 pacman 设置源的教程另一拨就是以 pacman-andreimarius 为代表的吃豆人课程项目。Andrei 和 Marius 完成的这个 pacman 项目本质上不是让你通关的小游戏而是把「搜索算法」「对抗博弈」「评估函数」这些 AI 课上的抽象概念全部塞进一个能跑、能看、能统计分数的场景里。适合三种人正在选课程设计题目、想复现别人 PAC-MAN 实验、或者需要在一个现成代码上做扩展的。别急着找下载地址先把项目拆开。2. 先拆解 pacman 项目的运行逻辑地图、状态和决策链提示如果你是被「pacman 设置源」带进来的这个项目跟 Arch Linux 没有任何关系。下面要讲的是吃豆人游戏不是包管理器。拿到这类项目我一般不会先看渲染代码而是先找游戏主循环。不管 Andrei 和 Marius 把入口文件命名成pacman.py还是game.py它的核心就是三件事循环处理输入、更新游戏状态、把结果画到屏幕上。理解了这个循环后面塞搜索算法、调评估函数才有下手点。2.1 游戏循环的最小框架渲染、输入、更新三件事读代码时先定位那个while循环。绝大多数课程项目用 pygame 写少数用纯命令行字符画。两者的循环结构一致只是渲染函数不同。我见过不少同学一上来就研究绘图函数结果卡在坐标系换算上——这是最不值得花时间的地方。def run_game(agent, maze, fps30): state init_state(maze) clock pygame.time.Clock() while not state.is_terminal(): action agent.choose_action(state) # 决策入口 state state.apply_action(action) # 移动、吃豆、撞鬼 render(state) # 画到窗口 clock.tick(fps) return state.scoreagent.choose_action(state)就是你要替换的决策层。键盘手动玩时这个 agent 读取上下左右按键换成 AI 时这里放 A* 搜索或者 Minimax 搜索。apply_action负责把动作应用到状态上包括位置更新、豆子扣除、鬼的移动和碰撞判定。clock.tick控制帧率一般定在 30太高的帧率会把 CPU 烧满对决策质量没有任何帮助。is_terminal()的终局判定通常是两个条件豆子全部吃完或者生命值扣到 0。如果你改搜索算法后游戏迟迟不结束优先检查这两个条件是否还成立而不是去查搜索逻辑。2.2 把吃豆问题改写成搜索问题State 里装了什么Pacman 项目区别于普通小游戏的关键点在于它把游戏过程抽象成了一个搜索问题。你不需要知道屏幕上的像素只需要知道一个状态State和一个动作集合Actions。对 Pacman 来说动作集合永远是四个方向状态则复杂一些字段类型含义变化频率pacman_pos(x, y)吃豆人当前格子坐标每步都变ghost_positionslist[(x, y)]每个鬼的坐标每步都变food_mapbool[][]地图上剩余豆子的分布吃到时变scared_timerint能量豆剩余的生效帧数逐帧递减livesint剩余生命数撞鬼时减写搜索算法时所有函数签名都以这个 State 为输入。A* 搜索里的「状态」往往是吃豆人的坐标加上豆子集合Minimax 里的「状态」则必须带上鬼坐标。如果State里没有带你要的信息比如缺了scared_timer那决策一定会出问题。2.3 判分、命数与鬼的巡逻参数先定规则再调算法PAC-MAN 原始规则在几乎所有课程项目里被保留普通豆 10 分能量豆 50 分吃掉虚弱状态的鬼 200 分。命数一般是 3 条被鬼碰到扣一条并重置位置。这些参数放在项目的常量区调整它们会直接影响评估函数的设计。鬼的行为也有一套固定模式平时在固定路径上巡逻看到吃豆人后切换成追击吃到能量豆后变成虚弱状态四处逃窜。实现里通常用一个状态机表示鬼的三种模式——scatter、chase、frightened。你在跑实验时如果发现鬼不追人先看它是不是停在scatter模式忘了切换这是最常见的「鬼不动」原因。3. 用 A* 搜索让 Pacman 自己找路代码与三个关键参数这章是 pacman-andreimarius 这类项目的主菜。让吃豆人动起来并不难难的是让它用最短路径吃到豆子。A* 在中等规模地图上能在几十毫秒内算出一条最优路线是课程项目里最常用的搜索器。3.1 地图建模把迷宫变成一张带权图课程项目的地图通常用字符画表示#是墙壁.是豆子P是吃豆人出生点G是鬼的出生点。加载地图时把这些字符读进内存转成坐标集合。这一步做错了后面所有搜索都白搭。def load_maze(lines): walls set() food set() ghost_start [] pacman_start None for row, line in enumerate(lines): for col, ch in enumerate(line.strip()): if ch #: walls.add((col, row)) elif ch .: food.add((col, row)) elif ch P: pacman_start (col, row) elif ch G: ghost_start.append((col, row)) return { walls: walls, food: food, pacman: pacman_start, ghosts: ghost_start, }坐标用(col, row)而不是(x, y)是为了跟二维数组的索引习惯对齐。walls用集合而不是列表因为后面判碰撞时只需要in操作集合平均 O(1) 的查询速度在反复寻路时优势明显。ghost_start用列表是因为一张地图可能有多只鬼。加载完可以打印一下墙壁数量如果跟原图对不上多半是readline()把换行符带进来了。3.2 A* 主循环open list、close list 与启发式函数A* 的核心是一个带优先级的开放列表。每次取出 f 值最小的节点展开直到找到目标。这里的 f 值等于 g 值已经走的步数加 h 值到目标的估计距离。优先级队列用 Python 的heapq实现比每次排序快得多。import heapq def astar(start, goal, neighbors, heuristic): open_heap [(heuristic(start, goal), 0, start)] came_from {start: None} cost_so_far {start: 0} while open_heap: _, _, current heapq.heappop(open_heap) if current goal: break for nxt in neighbors(current): new_cost cost_so_far[current] 1 if nxt not in cost_so_far or new_cost cost_so_far[nxt]: cost_so_far[nxt] new_cost priority new_cost heuristic(nxt, goal) heapq.heappush(open_heap, (priority, new_cost, nxt)) came_from[nxt] current return came_from堆里存的是三元组(priority, new_cost, node)new_cost放在中间是为了打破同优先级时的排序歧义。如果只存(priority, node)两个节点优先级相同时会去比较坐标元组结果可能让搜索路径出现莫名其妙的抖动。cost_so_far就是 g 值表每次发现更短路径就覆盖这才是 A* 能保证最优解的关键。启发函数用曼哈顿距离因为地图是四连通网格只能上下左右走。用欧氏距离会低估真实代价导致搜索范围扩大在中等地图上可能多扩展几百个节点在大地图上直接卡顿。启发函数必须保证不大于真实代价否则 A* 退化成贪心搜索路径会明显绕路。3.3 让 A* 可直接跑的最小命令与三个参数课程项目一般会提供一个命令行入口常见格式是python pacman.py -l mediumMaze -p SearchAgent -a fnastar,heuristicmanhattan跑通之后请重点调三个参数。第一个是heuristic的选择除了曼哈顿距离有些项目还会提供euclidean但效果通常更差。第二个是tie-breaker同一 f 值下优先往目标方向走的格子可以让路径更直、看起来更「聪明」。第三是权重系数有些实现支持给启发函数乘一个小系数比如heuristicWeight1.0001能让路径偏向目标方向。这种「加极小权重」的手法属于调参界的玄学它不影响路径长度但能让视觉路径更直。注意系数别超过 1.01否则会破坏 A* 的最优性保证。跑出来后看两个指标扩展节点数和最终路径长度。如果扩展节点数远大于地图格子数基本可以确定启发函数写得有问题。4. 遇到鬼以后Minimax 评估函数与对抗决策让吃豆人学会走最短路径只是第一步。真实对局里鬼会移动静态的 A* 路径每走一步就可能失效。这时候需要把决策模型从「单向搜索」升级成「对抗搜索」。4.1 从寻路到博弈为什么单靠 A* 打不过鬼A* 的假设是环境静止目标点固定。但鬼在动你算出的最短路径下一秒可能正好撞上鬼。Minimax 的思路是把吃豆人和鬼看成对抗双方吃豆人每走一步鬼会走一步来响应。吃豆人做决策时要把鬼的可能反应也考虑进去。4.2 评估函数的三维度与一套默认参数Minimax 需要一个评估函数来给局面打分。经典的维度有三个剩余豆子数、最近豆子的距离、最近鬼的距离。把它们加权组合起来就得到一个局面分。def evaluation(state): pacman state.pacman_pos ghost_dists [manhattan(pacman, g) for g in state.ghost_positions] nearest_ghost min(ghost_dists) food_dists [manhattan(pacman, f) for f in state.food_list()] nearest_food min(food_dists) if food_dists else 0 food_left len(state.food_list()) if nearest_ghost 2: danger 4 * (3 - nearest_ghost) # 鬼越近惩罚越重 else: danger 0 return -food_left * 10 - nearest_food danger这套权重设计的逻辑是剩余豆子越少越好最近豆子越近越好鬼离得越近越危险。nearest_ghost 2时的惩罚是阶梯式的鬼在一格以内时惩罚巨大让 Pacman 宁可不吃豆也要跑路。注意scared_timer 0时要翻转鬼距离的符号虚弱鬼离得越近越应该冲上去吃。忘记处理这个状态吃豆人会在鬼虚弱时四处逃窜白白浪费反杀机会。4.3 递归深度、Alpha-Beta 剪枝与多鬼逐层决策Minimax 的递归深度一般设 2 到 4。深度太浅看不到危险深度太深则每步决策耗时长这类项目的地图规模不需要超过 4 层。多个鬼的处理方式是把每只鬼当成独立的一层吃豆人层取最大值每只鬼的层取最小值逐层交替。如果项目里只做了暴力递归装上三只鬼后决策会明显变慢。Alpha-Beta 剪枝是标配优化原理是当前层已经找到足够好的选择时后面的兄弟节点就没必要再算。剪枝后同样深度下耗时可能降到原来的三分之一。评估函数是黑匣子别指望从公式上推最优权重跑对局看分数才是正经调法。5. pacman 项目避坑鬼打墙、穿墙与栈溢出排查这章写我在跑别人写的 Pacman 项目时踩过、也帮人排过的坑。每一条都是现象先说清楚再给原因和解决方案。5.1 鬼在原地打转邻居顺序与去重逻辑现象鬼始终沿着同一段路径往复走即便吃豆人就在旁边也不追。首先排除scatter模式没切换的问题这个看状态机就行。真正隐蔽的原因是鬼的路径规划里目标点被设成了自己当前所在格子。原因分析很多实现里鬼的移动策略是「每次都往离吃豆人最近的相邻格子走」。如果鬼当前已经站在一个局部最优点下一步会退回上一步的位置再下一步走回来就形成了往复。解决方式有两个给邻居列表引入随机扰动或者当鬼的位置和目标点重合时强制选择随机方向走两步。课程项目里对这个坑的标准解法是加入「禁止掉头」规则——记录上一个位置在候选邻居里排除掉它。5.2 吃豆人穿墙碰撞检测的边界值现象吃豆人沿着墙移动时会嵌进墙里半个格子或者卡在墙里出不来。这类问题在图形渲染模式下尤其明显。原因几乎都是移动和碰撞检测的先后顺序搞反了。常见错误写法是先更新坐标再判断是不是撞墙撞墙后把坐标往回推一格。回推逻辑在同时按两个方向键时会出现负数或者半个格子偏差。正确顺序是先计算新坐标用新坐标去查墙壁集合撞墙就放弃本次移动没撞墙才更新坐标。墙壁集合用set后判定就一行if new_pos not in walls。注意四个方向的边界都要判定有些实现只检查前方两个方向侧向撞墙时虽然看着没穿但角色会被墙「吸」住。5.3 决策卡顿和栈溢出递归深度与状态拷贝现象Minimax 深度调到 4 之后每走一步明显卡顿深度到 5 直接栈溢出。原因是每个递归节点都在复制整个State对象。如果State里包含一个几百格的地图矩阵深度 4 时会复制几千次内存和 CPU 全被拖垮。解决思路把地图、墙壁这些只读数据放进一个共享对象递归时只传引用每个节点只需要拷贝变化的部分比如吃豆人坐标、鬼坐标、豆子集合。豆子集合的拷贝可以用frozenset做快照或者用「全局豆子计数 修改列表」做增量回滚。我做这类项目时习惯给State的__init__加一个shared_maze参数复制构造函数时只拷贝动态数据。5.4 调参玄学同一套权重今天赢明天输现象评估函数的权重调好后一局表现良好换一局开局就翻车。如果你仔细看对局会发现鬼的初始方向和随机扰动种子每次不同局与局之间的方差很大。评估函数的调参不能只看一两局。解决方式命令行入口加--seed参数固定随机种子。评估时固定三张地图、固定种子跑 10 局用平均分和死亡率来比较权重变化。Andrei 和 Marius 这类双人协作项目里如果两个作者各自调了一套权重合并代码时一定要用同一组种子复测否则很容易出现「我的分支赢你的分支输」的僵局。6. 验证一个 pacman 项目是否真的合格三条检查路径项目跑起来只是开始验证方向对不对才是关键。我一般用三步来验收每一步都能暴露不同的问题。6.1 固定地图反复跑确认「每局都能走完」选mediumMaze和bigMaze各跑 10 局要求全部走完不卡死。如果有一局卡在死胡同里说明路径搜索缺少「无解回退」处理。这时候检查搜索器有没有维护 close list没有的话就会反复访问同一个格子。6.2 相同条件下对比 A* 和 BFS 的扩展节点数算法mediumMaze 扩展节点数大迷宫扩展节点数BFS约 600明显增多可能爆表A* 曼哈顿约 400稳定增长A* 错误启发与 BFS 接近与 BFS 接近A* 用曼哈顿距离时扩展节点数应该显著低于 BFS如果你发现两者几乎一样说明启发函数返回的始终是 0等价于没有启发。检查heuristic函数有没有把坐标参数正确传进去这是最常见的「A* 虚设」问题。6.3 看对局统计不只盯胜负多跑几局后统计平均得分、平均死亡次数、平均吃豆数。评估函数调好的表现应该是豆子优先度高时得分稳步上升靠近鬼时果断绕路。如果平均死亡次数下降但得分也下降说明权重把「保命」放得太重了吃豆人全程在躲不吃东西。我做这类项目最深的教训是拿到源码先跑通最小地图再动算法。Andrei 和 Marius 这个项目属于典型的双人课程代码两个作者对State的理解可能不一致合并时容易出接口不匹配。看代码时先确认每个函数的入参出参是什么比追渲染效果重要得多。希望这篇拆解能让你少走几步弯路。本文还有配套的精品资源点击获取