推箱子自动寻路说白了就是写个程序替你玩游戏——你什么都不用按它能自己算出从当前局面走到通关的操作序列每一步是往哪走、哪一步推了箱子全部列得清清楚楚。做这个东西的人一般有两类一类是刚学算法拿它练广度优先搜索BFS和A*另一类是想把某个经典Sokoban关卡做成自动演示、回放或者游戏内置提示需要一个能“解谜”的后端引擎。标题里挂着“未完”我就顺着这个思路来把已经落地的部分、正在做的优化和踩过的坑一起整理出来。推箱子自动寻路的核心难点不在“寻路”而在“状态空间”。普通迷宫寻路只要管一个人坐标推箱子要同时管玩家的位置和所有箱子的位置这组合爆炸的规模比你想象中大得多。这篇内容会从地图建模、状态定义、BFS和A*选型、死锁剪枝到完整代码骨架一次讲完适合有一定编程基础但还没碰过状态空间搜索的读者看完可以直接照着写一个能解的求解器。1. 从寻路到推箱子问题定义先搞清楚1.1 为什么不能只用BFS算玩家路径很多人第一反应是“这跟迷宫寻路差不多啊让玩家走到箱子旁边再往目标方向推不就行了”。实际做下去就发现不对。你确实可以让玩家走到某个箱子旁边但推到一半可能路就堵死了要么箱子被推进死角要么另一个箱子挡在必经之路上要么玩家自己把自己卡在墙角动弹不得。推箱子真正的难点是“全局协调”不是单步移动。每一步都要同时考虑玩家能走到哪、箱子能不能推、推完以后整个局面还有没有解。所以搜索的对象必须升级成状态而不是“玩家的位置”。一个状态这样定义状态 玩家坐标, 所有箱子坐标的集合假设地图有10×10个格子去掉墙壁算90个可站立点只有一个箱子时状态数量上限就是 90玩家位置 × 90箱子位置 ≈ 8100看起来很少。但如果箱子数量变成4个状态数大约是C(90,4) × 90 ≈ 2555190 × 90 ≈ 2.3亿这还是不考虑死锁、不考虑墙壁分割地形。2.3亿个状态每个状态还要记录父指针、步数、算子操作内存爆炸是分分钟的事。所以推箱子自动寻路的本质是在一个巨大的状态空间里做搜索靠的是“状态压缩 剪枝 启发式”而不是单纯写个搜索框架。1.2 推箱子状态搜索求解的本质目标状态是什么所有箱子都落在目标点上玩家可以在任意位置。搜索的起点是给定的初始局面我们要找的是一条从“初始状态”到“目标状态”的合法动作序列。动作有两种类型移动玩家向四个方向走一个格子不改变任何箱子的位置。推箱玩家走向一个箱子所在格箱子被往前顶一格。注意“拉箱子”这种操作在标准推箱子规则里是不允许的。这意味着状态转移是有方向性的玩家可以自由绕到箱子后面去推但不能从对面把箱子拽回来。这一条直接决定了反向搜索不好做——反向动作是“拉”规则不一致后面会细说。每次从当前状态出发合法动作的数量有限方向只有四个所以分支因子不大。但因为状态总数巨大搜索必须配合去重visited集合来避免无限循环。同一局面反复出现如果没有去重BFS会越跑越长DFS更是直接卡死在死循环里。2. 地图建模先把地图“读”进程序里2.1 ASCII地图格式与解析在做算法前第一步是把关卡文本转成程序能处理的数据结构。大多数推箱子关卡文件都用ASCII字符表示这已经是社区通用格式字符含义#墙壁空格地板玩家当前位置不在目标上玩家当前位置在目标上$箱子不在目标上*箱子在目标上.目标点没有箱子或玩家比如下面这个经典小关卡##### # # # $ # # # #####这是最简的一幕没有目标点只是示意。正常关卡会有.像这样###### # # # $. # # # # # ######地图解析的常规做法是按行读取然后逐字符判断填充一个二维数组。每个格子记录以下信息是否为墙是否为目标点当前是否有箱子当前是否有玩家比较稳的数据结构是定义一个Cell类或直接用字典比如{“wall”: False, “goal”: False, “box”: False, “player”: False}。如果用二维数组建议同时维护玩家坐标和箱子坐标集合后面搜索状态直接用坐标集合来表示避免每次从地图格子反推。这里有个小坑文本行长度可能不一致。有的关卡文件里缩进对齐后部分行末尾的空格会被编辑器自动删除读进来每行长度不一样。如果不做处理数组会越界。我习惯在读入后做一次行补全把所有行补齐到同一长度不足部分填成墙壁字符#。别小看这个处理真实关卡文件里几乎必遇到。2.2 移动与推动的边界检测一道核心逻辑是给定玩家的当前坐标和移动方向判断这一步是“走过去”还是“推箱子”以及是否合法。伪代码如下计算玩家下一个位置next_player。如果next_player是墙则非法不能移动。如果next_player不是箱子则玩家移动到该位置箱子不动。如果next_player是箱子计算箱子被推之后的位置next_box。如果next_box是墙或者被另一个箱子占据则非法。否则箱子移动到next_box玩家移动到next_player。第4步是最容易写错的地方。很多初学者漏了“箱子前方还有箱子”这种情况只判断了墙。实际棋盘上一个玩家推动一个箱子撞向另一个箱子这两个都动不了整个推动行为非法。还有边界问题地图外一律视为墙别让坐标飘出数组范围。推箱子功能实现完后状态转换也就有了输入一个“旧状态”和一个方向输出一个“新状态”或者“非法”。这就是搜索算法的地基。3. 搜索算法选型BFS、A*还是别的3.1 BFS能保证最优解但状态膨胀快广度优先搜索是推箱子求解器最基础、也最不容易出错的方案。按“层”向外扩展先尝试所有一步能到达的状态再两步再三步……第一次搜索到目标状态时路径步数一定是最短。因为BFS天然能保证“最少总步数”注意是玩家移动步数不是推箱次数玩家每走一步算一步推箱也算一步。实现上用queue.Queue或者collections.deque配合一个visited集合去重。但BFS的问题也很明显它是一个纯无信息搜索没有任何方向感。所有状态一律平等一层一层扩出去状态量稍大就卡死。BFS更适合那种“只有一两个箱子”的初级关卡一旦箱子数量到4个以上搜索空间动辄亿级排队列和visited集合都会把内存吃穿。我在实际测试中遇到过这样的情况用一个4箱子的中等难度关卡跑BFS内存从几百MB一路涨到近2GB还没搜完进程直接被系统杀掉。BFS不是不能用是必须配合强剪枝再用。3.2 A*启发式让搜索方向更聪明A*是目前更实用的方案。它不按层扩展而是维护一个优先队列每个状态用“已走步数 预估剩余代价”作为优先级f(n) g(n) h(n)g(n)从初始状态到当前状态已经花费的步数。h(n)从当前状态到目标状态的启发式预估值要求不能高估实际代价。每次从优先队列弹出f最小的状态继续扩展。启发函数的设计是关键推箱子比较常用的是所有箱子到目标点的曼哈顿距离之和。曼哈顿距离不用多解释distance(box, goal) |box.x - goal.x| |box.y - goal.y|每个箱子找最近的可用目标点算距离加起来就是h。这个启发是“乐观”的它忽略了箱子互相阻挡、需要绕路、玩家需要走回头路这些额外代价所以不会高估真实步数保证A*找到最优解。但实际搜索效率取决于h的质量。一个两箱子关卡纯曼哈顿距离已经够用了箱子一多启发函数信息量不够搜索空间还是会膨胀得很厉害。我见过不少实现在这时候会做一点改进比如对每个目标点做“最小匹配”让每个箱子不重复地匹配不同的目标点再算距离和这样启发更强不会出现“两个箱子同时瞄着同一个目标点”这种重复计算。3.3 为什么DFS和双向BFS在推箱子里不常用深搜在推箱子里表现很差。推箱子有大量循环动作——把箱子推一圈又回到类似状态如果不做状态去重DFS会陷入无限绕圈即使做了去重DFS找到的第一个解往往步数巨长没有任何实际价值。双向BFS看起来很美从起点和终点同时扩展状态量可以减少一个数量级。但推箱子有一个致命问题反向搜索的规则不匹配。正向操作是推反向操作变成“拉箱子”这在标准规则里是不允许的。除非另外定义一套允许拉箱子的反向规则并做状态映射否则双向BFS实现复杂、正确性难保。我的建议是除非你只想做“可行性判断”这局有没有解否则别在推箱子上用双向BFS。4. 死锁检测剪枝的关键有没有解的一把尺4.1 什么是死锁状态死锁就是“箱子再也无法被推到其他位置”的状态。最常见的例子是把箱子推进了墙角### #$ #.$在角落里两条边都被墙挡住玩家无论从哪里推都只会把它压得更死永远不可能出来。但如果$正好落在目标点上比如### #* #箱子虽然在角落但它已经到位了这不算死锁反而可能是一个成功子集。判断时必须先把“箱子上有目标”这种情况排除。死锁检测做得好能剪掉大量无效分支。我在做测试时发现同一关不开启死锁检测BFS扩展状态数是几十万开启基础的墙角死锁检测后直接降到一两万搜索性能能提升一个数量级以上。4.2 三类常见的死锁规则完整的死锁判定在学术界可以归结为“freeze状态分析”做起来很复杂。实际工程中先实现下面几条启发式规则就够了墙角死锁箱子在当前格与其水平方向相邻的一个方向是墙垂直方向相邻的另一个方向也是墙且该格不是目标点则死锁。贴墙死锁箱子贴着墙墙的方向上箱子前后两个方向都是墙且这整段贴墙的位置里没有任何目标点则死锁。这种情况箱子被卡在一段墙缝里根本没法再离开墙面。双箱互锁两个箱子在狭窄通道里横着堵死彼此把对方的路堵住了。这种比较复杂我平时先不做全局检测而是用“状态访问去重 大步数限制”来兜底。实现最基础的地角死锁代码如下def is_corner_deadlock(state, box_pos, goals, walls): x, y box_pos if box_pos in goals: return False left walls[(x - 1, y)] right walls[(x 1, y)] up walls[(x, y - 1)] down walls[(x, y 1)] return (left and up) or (left and down) or (right and up) or (right and down)在每个状态转移生成后对每一个箱子位置都做一次判断只要任意一个箱子死锁就将这个新状态丢弃。这里有个容易踩的坑不能只在入队前判断还需要对初始状态和中间状态同样生效。很多实现漏了“刚生成的新状态还没判断就直接入队”结果死锁分支还是被扩展了剪枝效果大打折扣。4.3 死锁检测与目标格的关系推箱子关卡的目标点常常不在开阔地带有的目标点本身就是墙角。比如### #*这个箱子已经挂在目标上虽然墙角死锁规则会命中但因为我们先判断了box_pos in goals直接返回False不会误杀。还有种情况是“箱子当前在目标上但未来需要把它推走让给另一个箱子”这时候规则也不能判死锁。实际项目里我会这样处理如果箱子在目标上一律先不当死锁只有连续几步内状态没有改善再加惩罚或者靠A*的代价函数去权衡。死锁规则写得太激进会漏掉真正有解的关卡写得太保守剪枝效果不明显。先做最朴素的墙角死锁稳扎稳打跑通之后再往更精细的方向扩展。5. 完整实现流程从地图到解题序列5.1 状态数据结构的选型状态里的箱子和玩家坐标用一个不可变tuple表示直接作为visited集合的键。比如class State: def __init__(self, player_pos, boxes): self.player_pos player_pos self.boxes tuple(sorted(boxes)) self.key (self.player_pos, self.boxes)boxes一定要排序后存成tuple不然两个箱子完全对称但顺序不同会被当成两个不同状态导致搜索空间翻倍。这一点非常影响性能真实调试时我因为这个没注意状态数多了一倍。每个搜索节点还要记录父状态和产生它的方向用于最后回溯路径。标准做法class Node: def __init__(self, state, parent, direction, push_count): self.state state self.parent parent self.direction direction # u, d, l, r self.push_count push_count回溯路径时从目标状态一直往parent方向走回起点然后把direction列表反转就是完整的操作序列。5.2 完整A*求解器骨架Python下面的代码是实际跑过一遍的核心骨架不依赖任何第三方库可以直接复制去改地图import heapq from collections import deque def solve_sokoban(level): walls, goals, player_start, boxes_start parse_level(level) def heuristic(boxes): total 0 remaining_goals list(goals) for box in boxes: best min(abs(box[0] - gx) abs(box[1] - gy) for gx, gy in remaining_goals) total best return total def gen_states(state): px, py state.player_pos for dx, dy, direction in [(-1, 0, u), (1, 0, d), (0, -1, l), (0, 1, r)]: nx, ny px dx, py dy if (nx, ny) in walls: continue new_boxes state.boxes if (nx, ny) in state.boxes: tx, ty nx dx, ny dy if (tx, ty) in walls or (tx, ty) in state.boxes: continue new_boxes set(state.boxes) new_boxes.remove((nx, ny)) new_boxes.add((tx, ty)) new_boxes tuple(sorted(new_boxes)) yield State((nx, ny), new_boxes), direction start_state State(player_start, tuple(sorted(boxes_start))) heap [] g_score {start_state.key: 0} heapq.heappush(heap, (heuristic(start_state.boxes), 0, start_state, None, None)) visited set() while heap: f, g, state, parent, move heapq.heappop(heap) if state.key in visited: continue visited.add(state.key) if all(box in goals for box in state.boxes): path [] node (state, move) while node[1] is not None: path.append(node[1]) node node[2] # parent return list(reversed(path)) for next_state, direction in gen_states(state): if next_state.key in visited: continue new_g g 1 if next_state.key not in g_score or new_g g_score[next_state.key]: g_score[next_state.key] new_g h heuristic(next_state.boxes) heapq.heappush(heap, (new_g h, new_g, next_state, state, direction)) return None这个实现有几点我特意做了简化没有做死锁检测、没有做复杂匹配、也没有对推箱动作加权。它适合理解A*在推箱子上的基本结构。真正要解大关卡需要在gen_states里加上“生成状态后立即死锁剪枝”的判断同时把heuristic从“每个箱子找最近目标”改成“最小匹配”效果会立竿见影。5.3 步数序列与推箱动作区分路径回溯拿到的是一串方向字符比如u u l d r。如果要输出“第几步推了哪个箱子”这种带语义的序列需要在回溯时同时记录动作类型。我常用的输出格式是普通移动用小写字母推箱动作用大写字母比如u(d) r u u(L) d d d或者更直观一点用带方向词的指令列表Move Up Push Left Move Right ...这个信息之后有两个用处一是游戏内置提示直接告诉玩家下一步该做什么二是回放系统一步步驱动精灵移动。若要让UI显示不同的玩家朝向或推行动画这一步就必须把推箱和非推行动作分开。实现时在gen_states里标记is_push然后元组里带上该标记即可。6. 常见问题与排查思路实录6.1 状态爆内存程序卡死状态量一大visited集合和优先队列同时爆内存。我自己遇到过最典型的一次8×8的地图4个箱子纯BFS跑了30分钟没出解内存占用一路涨到3GB最后直接OOM。排查思路先看visited集合的规模比如打印出集合长度。如果是几百万级别基本就是死锁剪枝没做或启发函数太弱。换成A*后状态量明显下降再开启墙角死锁检测通常能再降一个数量级。如果还想进一步压缩可以用位编码把“玩家坐标箱子坐标”压成一个整数做哈希键省内存也省比较时间。6.2 路径回溯断链或方向乱路径回溯出问题几乎都是因为父指针没存对或者visited去重直接跳过了正确路径的记录。一个隐蔽的问题是A*中同一个状态可能以不同g值被多次压入优先队列。第一次弹出来的是最优g但如果此时没有在visited里做记录后面第二次弹出来的时候会被判重复而跳过路径回溯会走到一个错误的前驱。解决办法是优先队列弹出时进行“延时去重”只在弹出时判断是否在visited里入队时不做这种判断。上面框架代码已经这么处理了但改代码时容易搞反。6.3 启发函数太弱会让A*退化成BFS如果启发函数全是0A*就退化成BFS。纯曼哈顿距离虽然不全是0但在推箱子较大的地图上信息量依然很低h(n)值平均偏小搜索方向感不足。实测中把启发函数升级成“最小匹配曼哈顿距离和”之后求解时间能缩短30%到60%。最小匹配本身是二分图最小权匹配问题箱子数量不超过5个时直接用全排列取最小值就够不必引入复杂算法。箱子到目标的分配是对应关系目标是几个就必须匹配几个对应箱子。6.4 回放时动作不合法求解器给出的序列在回放时经常碰到“推空箱子”或“穿墙”的错误。排查这一类问题的通用方法是用一个独立的解释器重新按照序列逐帧执行每步都验证格子类型。我的经验是问题往往不在搜索算法而在gen_states里的箱子更新逻辑——比如推了箱子但忘了更新玩家坐标或者把(nx, ny) in state.boxes判断时忘了旧箱子集合的排序导致去重和回放不一致。写一个简单的命令台关卡##### # # # $ # # # #####用求解器跑一遍然后在调试器里逐帧回放如果每一步都验证通过算法基本就稳了。6.5 常见问题速查表现象可能原因处理方式内存占用爆炸缺少死锁剪枝 / BFS无启发加墙角死锁检测改用A*无解返回None但关卡明明有解死锁规则误判目标格box in goals时跳过判死锁解序列很长且绕圈启发太弱 / visited漏了关键状态改最小匹配启发延时去重回放时动作非法状态更新逻辑不一致用独立解释器逐步验证每步动作程序一直跑不出结果搜索空间过大加大死锁检测范围、限制最大推箱次数7. 从“能解”到“解得好”后续还可以做的优化标题里写了“未完”因为这套求解器目前算是“能跑但不够猛”。我自己在后续计划里已经列好了几个值得投入的方向。第一个是IDA*搜索。它比A省内存每轮只维护一条路径配合一个阈值不断迭代加深。对小关卡IDA可能比A还快对大关卡它跑得慢但内存占用非常稳定。推箱子求解圈里很多经典求解器用的是IDA加强力启发。第二个是宏操作Macro Actions。把“玩家从A点走到箱子旁边再把箱子推一格”这种复合动作定义为一步搜索状态数会大幅减少代价是步数统计方式变了不一定再是传统意义的“最少步数”。第三个是模式数据库Pattern Database。先离线算出一部分目标区域的完美解作为启发函数的一部分。这个技术是真·推箱子求解器的标配但实现复杂度高适合拿来当长期项目做。第四个是可视化调试器。多做一个图形界面把每个状态的玩家位置、箱子位置渲染出来可以随时暂停、单步、看A*的优先队列里正在扩展哪些状态。这东西做出来排错效率能翻几倍对学习状态空间搜索也有很大帮助。我个人在实际操作中的体会是推箱子自动寻路最好的入门路径是先写一个BFS版本跑通所有逻辑再逐步替换成A*启发函数死锁剪枝。千万不要一上来就追求跑通最难的大关卡那样大概率会被状态爆炸劝退。每一步优化都配一个基准关卡做对比记录状态扩展数和耗时比什么都靠谱。后面我还会把这个项目继续往下做等模式数据库版本跑通后再回来填坑。
