推箱子求解器与关卡生成：从BFS到A*的搜索优化实战

1. 一个看似简单的益智题为什么求解器会跑崩我第一次做推箱子游戏自动求解和关卡生成的时候差点被自己的天真坑死。当时想着这不就是一个宽搜问题吗让小人在棋盘上随便走碰见箱子就推一下推到目标点就算赢。结果跑起来才发现地图稍微大一点、箱子稍微多一点搜索程序就开始疯狂吃内存几分钟跑不出结果最后直接把开发机卡到风扇起飞。后来我才慢慢明白推箱子表面上是休闲游戏本质上是个状态空间搜索问题而且状态空间大得超乎想象。这篇文章就把我踩过的坑、最终跑通的方案、以及怎么用求解器反过来做关卡生成一条条讲清楚。适合正在写推箱子求解器、想做自动关卡生成或者想拿搜索算法练手的人参考。1.1 棋盘里的两种移动千万别混为一谈推箱子里其实有两种动作一种是玩家自己在空地上走来走去另一种是玩家推动箱子移动一格。新手最容易犯的错误就是把“玩家移动”也当成搜索状态的一部分。如果每次玩家挪一步都算一个新状态那一个状态里玩家可以在很多位置自由走动这些位置在搜索里会产生大量冗余节点。比如一块10乘以10的空地玩家从左上角走到右下角中间可能经过几十个格子这些全都会被放进搜索队列里但实际上它们并没有改变棋盘的格局只是玩家在“串门”。正确做法是只在“推动箱子”这个事件发生时切换状态玩家在某个状态里的所有可达位置只是在为下一次推动做铺垫。这样状态数量就从“玩家位置 × 箱子排列”的乘积里剥离了一大部分搜索节点数量能下降好几个量级。1.2 状态空间到底有多大算一笔账你就懂了我拿一个12列10行的地图举例共120个格子其中墙占掉32个剩下88个可站立格里面放了8个箱子。箱子之间不能重叠玩家自己占一格。粗略估算选择8个箱子位置的方式是组合数C(88,8)大概是4400亿的量级再乘上玩家可能的位置数量直接冲到万亿以上。就算用上哈希去重能访问到的状态也不会少到哪里去因为每一层推动都会衍生出大量合法分支。这就是为什么小地图也可能把求解器跑崩不是地图小就一定轻松箱子的组合爆炸才是真正的瓶颈。理解了这一点你就知道为什么推箱子自动求解的核心不是“写一个宽搜”而是“怎么在搜索过程中尽可能剪掉不可能的子树”。1.3 先定求解目标再决定用哪类算法做求解器之前先问自己一个问题你是要“任意一条解”还是要“最少推数”还是“最少步数”。这三个目标对应的算法选择完全不同。目标推荐算法说明任意一条解DFS、BFS只要能通就行速度优先最少推数BFS按“推数”分层、A*推数少更接近人类的操作习惯最少移动步数BFS按“移动步数”分层状态爆炸严重通常不推荐我做关卡生成时只关心“最少推数”因为推箱子难度和玩家推箱子的次数强相关和玩家瞎走多少步关系不大。所以求解器的搜索层数我直接定义为“推箱子的次数”玩家走位不参与计层。2. 用BFS打底先把状态表示和动作扩展想清楚别急着上A*先写一个朴素的BFS跑通整个流程再去优化也不迟。我自己的经验是先把基础版本跑对了后面加启发式、加死锁检测才有可对比的基准。2.1 状态怎么表示才能既好判断又省空间我推荐直接用不可变对象表示状态方便放进哈希集合里去重。状态包含两块玩家坐标以及所有箱子坐标的排序元组。箱子坐标必须排序不然同一组箱子只要摆放顺序不同就会被当成两个状态搜索量瞬间翻倍。from dataclasses import dataclass dataclass(frozenTrue) class GameState: player: tuple # (row, col) boxes: tuple # ((row, col), ...) 已排序玩家坐标单独存不参与排序。箱子坐标元组每次生成新状态时都要重新排序Python里对8个元素的元组排序开销很小可以忽略不计。2.2 动作扩展只生成“推动箱子”这一步实现核心转移函数时我建议分成两步走。第一步从当前玩家位置出发在不能穿过箱子和墙的前提下做一次连通性搜索得到玩家可达的所有格子。第二步遍历所有箱子对每个箱子检查四个方向箱子要推的方向前方必须是空地箱子“身后”那格必须是玩家可达的位置。推过去之后玩家站到箱子原来的位置箱子移到新位置形成下一个状态。def expand(state, walls, boxes_set): reachable compute_reachable_cells(state.player, walls, boxes_set) next_states [] for bx, by in state.boxes: for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)): px, py bx - dx, by - dy # 箱子“身后”的玩家站位 nx, ny bx dx, by dy # 箱子推过去的目标格 if (px, py) not in reachable: continue if (nx, ny) in walls or (nx, ny) in boxes_set: continue new_boxes list(state.boxes) new_boxes.remove((bx, by)) new_boxes.append((nx, ny)) new_boxes.sort() next_states.append(GameState((bx, by), tuple(new_boxes))) return next_states这个函数看起来简单但它是整个求解器的地基。模块化之后你给BFS、A*、IDA*用都不需要改逻辑只需要换外层搜索策略。2.3 玩家站立点的判定决定状态转移是否合法很多初学者会漏掉“箱子身后可达”这个条件。玩家推箱子必须是站在箱子后面推如果箱子贴墙玩家根本没有空间站到箱子后面那这个方向就是非法方向。可是如果只看“箱子前方的格子是否为空”很可能会生成一个看起来能推、实际上推不了的状态等回溯的时候才发现路径根本不可达。我在实际写代码过程中第一次就漏了“玩家可达区域”的更新导致生成了大量荒谬状态箱子被推到了一个玩家根本走不到的位置后续搜索全部无效。后来每次扩展状态之后我都把新玩家位置更新成“箱子移走之前的位置”再做下一轮可达性计算问题才彻底解决。2.4 A*优化启发函数可以夸大但别夸大过头BFS能跑通但面对稍大一点的关卡会力不从心。这时候我给A*加了启发函数。最基础的启发函数是所有箱子到最近目标点的曼哈顿距离之和。不过这个启发函数有一个问题它完全无视箱子之间的互相阻挡。比如两个箱子并排堵在走廊里曼哈顿距离可能算出来很近但实际上需要绕一大圈甚至根本推不动。于是搜索会被误导到一堆看起来分数很低、实际不可行的分支里。我后来做的改进是预计算每个箱子到每个目标点的最短路径长度路径上如果有墙或边界限制就加上绕路代价然后求所有箱子和目标点之间的“最小匹配和”。这个启发函数明显更紧搜索节点数比普通曼哈顿距离少了很多。代价是预计算时间变长但对于12乘10左右的地图完全值得。3. 死锁剪枝与状态去重搜索空间从指数级缩回可接受真正让求解器“跑得快”的功臣不是A的启发函数而是死锁剪枝。没有死锁检测A会在大量不可能的布局里来回试探直到把内存吃光。3.1 死锁的几类典型形态我把常见死锁分成三层来处理。第一层是单箱死锁比如箱子在墙角而墙角不是目标点这个箱子永远不可能再被推动了。第二层是贴墙死锁箱子沿着墙边被推到某个凹槽里前方没有出口后方被玩家站位限制也推不回来。第三层是组合死锁多个箱子围成一个封闭区域把其中一个箱子锁在中间。实现的时候最简单的检测就是对每个箱子做局部规则判断。箱子在角落且不在目标点可以直接判定死锁箱子贴着墙墙边没有出口且不在目标点也可以判定死锁。def is_simple_deadlock(state, goals): for bx, by in state.boxes: if (bx, by) in goals: continue # 上下都是墙 或 左右都是墙则为角落死锁 up_wall is_wall(bx - 1, by); down_wall is_wall(bx 1, by) left_wall is_wall(bx, by - 1); right_wall is_wall(bx, by 1) if (up_wall and left_wall) or (up_wall and right_wall): return True if (down_wall and left_wall) or (down_wall and right_wall): return True if (up_wall and down_wall) or (left_wall and right_wall): return True return False组合死锁检测要复杂得多我在项目里只做了“相邻箱子围出死角”的简化版覆盖率大概七八成剩下的交给搜索层数限制兜底。对一般关卡生成来说这个剪枝力度已经够用了。3.2 状态去重两个哈希细节决定成败状态去重看似简单实际上有两个细节很容易踩坑。第一个是箱子的排列顺序前面已经说过要排序第二个是玩家位置的去重策略。如果目标是“最少推数”那么两个状态即使玩家位置不同、箱子布局相同也应该合并成一个状态因为未来推箱子时的可达性只和玩家能走到哪些格子有关和玩家具体站在哪个格子上没有必然关系。我在哈希集合里存的是状态对象本身Python会自动处理元组哈希程序运行起来没有额外负担。如果你用C写建议把箱子坐标压缩成一个整数位掩码玩家可达区域预先计算成连通区域编号状态比较会更快。我自己在原型阶段用Python验证逻辑后来才翻译成C跑大规模测试。3.3 剪枝前后对比我实测的一组数据我拿一个10乘10、内含4个箱子的小地图做了对比。不做死锁检测时BFS扩展了几万个状态勉强能出解加上简单死锁检测后状态数降到几千再配合A*的最小匹配启发函数状态数只剩下几百。这个对比说明死锁剪枝才是性价比最高的优化。不要一上来就研究非常复杂的死锁检测算法先把角落死锁、贴墙死锁这种基础场景覆盖掉搜索性能就能提升一个量级。3.4 求解器的主流程骨架把上面的模块拼起来就是一个完整的A*求解器主循环。我用最小堆维护待扩展状态堆顶是“当前推数 启发值”最小的状态。import heapq def solve_puzzle(initial, goals, walls): heap [(heuristic(initial, goals), 0, initial)] g_score {initial: 0} parent {initial: None} while heap: _, push_count, state heapq.heappop(heap) if set(state.boxes) set(goals): return reconstruct_path(parent, state) for nxt in expand(state, walls, set(state.boxes)): new_g push_count 1 if new_g g_score.get(nxt, float(inf)): g_score[nxt] new_g parent[nxt] state heapq.heappush(heap, (new_g heuristic(nxt, goals), new_g, nxt)) return None注意启发函数必须在任何状态下都返回一个“不超过真实剩余推数”的估值否则A*就不保证最优。因为我最终生成的关卡需要知道“最少推数”所以我宁可启发函数偏保守也不要偶尔高估。4. 关卡生成的两种路线先保证可解再控制难度求解器跑通之后我把重点转向了关卡生成。推箱子关卡生成不是随便往地图里扔几个箱子就行核心目标是生成结果必须可解且难度尽量可控。4.1 逆向生成从目标状态倒着“拉箱子”逆向生成是我最终采用的主力方案。思路很简单先定好所有目标点的位置让箱子和目标点重合然后从“已完成”的状态出发执行合法的“反向推动”。正向是玩家把箱子从A推到B反向就是玩家站在B旁边把箱子从B拉回A。这里有个容易搞混的点反向操作时玩家必须站在“箱子要拉过去的目标格”相邻的位置并且这个位置在反向状态里是可达的。也就是说每次反向移动都要重新计算玩家可达区域不能让箱子被拉到一个玩家根本去不了的地方。def reverse_expand(state, walls, goals): reachable compute_reachable_cells(state.player, walls, state.boxes) new_states [] for bx, by in state.boxes: for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)): sx, sy bx dx, by dy # 反向操作时玩家所站的位置 tx, ty bx - dx, by - dy # 箱子被拉回去的位置 if (sx, sy) not in reachable: continue if (tx, ty) in walls or (tx, ty) in state.boxes: continue new_boxes list(state.boxes) new_boxes.remove((bx, by)) new_boxes.append((tx, ty)) new_boxes.sort() new_states.append(GameState((sx, sy), tuple(new_boxes))) return new_states每次反向推动箱子和玩家都会移动记录下这个动作。重复执行几十次之后箱子和目标点完全分离玩家被丢在一个随机可达位置一个可解的初始关卡就诞生了。4.2 洗牌与随机性控制别让地图看起来有规律一开始我以为只要随机执行反向操作就行结果生成的关卡一眼就能看出规律箱子总是一条直线散开玩家永远站在某个固定方位。后来我加了两个控制反向动作随机挑选并允许一定概率“反向撤销”掉某些箱子移动每执行完一轮就检查箱子和目标的重合数量控制重合度过高或过低的情况。难度控制方面我在逆向生成之后会调用求解器算出最少推数。如果推数落在目标区间就保留这关否则丢弃重新生成。对于10乘10的地图我大致按这个区间分档难度档位地图尺寸箱子数量最少推数区间入门8乘82到35到20普通10乘104到520到60进阶12乘125到760到120硬核12乘148以上120以上这个区间是基于我的测试地图给出的参考值不同地图布局下感受差异很大你需要用自己的求解器跑一批数据再调整。4.3 正向生成随机摆箱子再验证虽然笨但有用逆向生成的问题是难度不可控有时候反向走了20步正向求解器一算只要3推就解完了。为什么因为反向路径和正向解路径不一定对应反向生成只是保证“存在一条解”不保证“这条解就是最短的”。所以我也保留了一条正向生成路线随机在地图上放置若干箱子随机放置目标点然后用求解器验证可解性验证通过后统计最少推数。这种拒绝采样的方式命中率很低大概十次能出一两次可解关卡但好处是布局更自然不容易看出来人工雕刻的痕迹。我实际项目中是把两条路线都做了逆向生成保证速度正向生成保证多样性。生成完之后统一交给求解器做合法性验证再进入人工筛选。4.4 关卡合法性校验清单一条都不能少生成器写完以后我整理了一份校验清单每次都照着检查目标点数量必须和箱子数量一致且目标点分布在可行走区域。箱子初始位置不能和目标点重合否则开局就完成了一部分目标。所有目标点必须在箱子的可达推动范围内不能存在某个目标点被墙完全孤立的情况。玩家出生点必须和至少一个箱子处于同一个连通区域否则玩家第一步就动不了。正向求解器必须能在限定推数内找到解验证结果存档。如果目标是“近似无解唯一性”至少确认最短解不会短得离谱。清单看起来琐碎但每一条都对应真实翻车案例。我曾在生成结果里见过一个关卡玩家出生在左下角所有箱子都在右上角中间隔了两堵墙连碰都碰不到这关扔给谁都解不开。5. 实测调优中的七个坑与对应排查手法求解器和生成器拼装到一起之后测试阶段才是真正的噩梦。我把遇到的七个典型问题整理成了表格每一个都附带排查思路。问题现象根因排查方法解决方案内存暴涨程序卡死状态表示冗余箱子位置未排序打印状态数量增长曲线箱子坐标排序后入哈希集A*一直搜索不到解启发函数高估或死锁检测漏判先换成BFS验证逻辑是否正确改用最小匹配启发补基础死锁规则生成的关卡轻而易举只用随机布局没有求解器评估统计最少推数分布加入难度区间筛选逆向生成中途卡住箱子被拉进不可达区域打印每次反向操作的可达集合反向操作后重新计算可达区域箱子贴墙后再也推不动墙边死锁检测缺失单步回放移动序列补贴墙死锁规则求解器返回路径不可执行玩家移动混入搜索状态比对状态链上玩家位置只按推箱子动作记录路径连续生成几十关全是同一套路随机种子初始化方式单一检查每一次随机调用的种子来源用时间和关卡索引混合做种子5.1 内存暴涨先把状态号印出来遇到内存问题别急着优化算法先确认状态是否真的在减少。我会在搜索循环里每隔一万个节点打印一次当前状态集合大小如果增长曲线接近线性甚至超线性十有八九是状态去重失效。查一下箱子元组有没有排序查一下玩家位置有没有被错误地排除出状态比较逻辑。5.2 启发函数高估引发的“死循环”假象A长时间不返回不一定代表代码死循环也可能是启发函数返回了过大的值导致优先队列总去扩展一些看似接近终点、实则不可能的分支。排查方法很直接把启发函数临时改成恒等于0A就退化成BFS如果此时能出解问题就锁定在启发函数上。5.3 逆向生成卡住可达性是关键逆向操作里最隐蔽的坑是玩家位置更新。正向推完箱子后玩家站在箱子原来的位置反向操作则相反玩家站在箱子当前位置相邻的格子把箱子拉走。如果玩家站的那个格子本身不可达这次反向拉箱就是非法的。我最初没有重新计算可达集合结果生成的关卡里经常出现玩家站在墙里的非法状态。5.4 路径回放验证关卡合法性的终极手段我写了一个路径回放器把求解器返回的动作序列逐步执行每一步都校验玩家位置、箱子位置、墙碰撞状态。回放通过这关才算真正可玩。这一步看似笨重但它能一次性发现动作序列里所有的异常比肉眼审查棋盘高效太多。6. 两个进阶方向提示系统与难度评估求解器和生成器稳定之后我又往里加了两个“周边功能”一个是给玩家的提示系统一个是对关卡难度做自动评估。这两个功能都直接复用求解器产出的数据没有额外引入复杂模块。6.1 提示系统先算完整解再高亮当前动作提示系统的实现思路很简单求解器求出最短解路径之后把整个动作序列存下来。玩家每次点击提示按钮就从当前棋局状态里找到对应的下一步推箱子动作在界面上高亮显示即将被推动的箱子和推的方向。一个容易被忽略的细节是提示要给“推动动作”不是给“玩家步行路径”。有些游戏会画一条玩家走路的小箭头看起来像提示实际上完全没用因为玩家看提示是想知道“哪个箱子往哪边推”。我的实现是直接标记箱子的移动方向玩家照着推就行。6.2 轻量难度评估不看步数看决策压力最少推数是一个粗粒度指标两个推数相同的关卡体感难度可能天差地别。我后来加了一个评估函数综合三个因子推数、搜索过程中的平均分支因子、以及死锁风险区域的数量。平均分支因子越高说明玩家每一步能选的合理方向越多越容易迷路死锁风险区域多说明玩家稍有不慎就会把箱子推死。我给这三个因子分配了权重算出一个0到100之间的分数难度分 0.55 × 推数因子 0.30 × 分支因子 0.15 × 死锁区域因子推数因子是最少推数除以当前尺寸下的推数上限分支因子是求解器扩展节点时统计出的平均可选方向数死锁区域因子来自预计算的危险区域网格。这套评估不算严谨但用于生成器筛选关卡足够了。如果你有更好的特征指标完全可以替换掉其中某一项。6.3 一些可以继续扩展的想法如果你的目标是做完整游戏后续还可以做“悔棋功能”和“关卡编辑器”。悔棋功能只需要把求解器记录的状态栈反向回放关卡编辑器则可以直接把逆向生成器的反向动作序列暴露给玩家手动操作。如果让我重来一次我会在第一天就把死锁检测写进求解器而不是后期再加。死锁检测是推箱子求解器的分水岭有它和没有它的性能差距完全是两个世界。至于关卡生成我始终觉得“可解”只是及格线真正考验功夫的是难度控制和对重复套路的规避这部分只能靠大量生成、大量实测不断调整权重和参数没有一劳永逸的公式。希望这篇文章能让你少走一些我走过的弯路。