★ FEATURED ARTICLE 推箱子这玩意儿看着简单十六个格子加几个箱子谁小时候没在文曲星上搓过两把。但真让你写个程序自动解出来再回头设计新关卡那完全是两码事。我花了两周业余时间在这玩意儿上踩了不少坑也摸出点门道从BFS暴力搜索到死锁检测再到反向生成关卡一条龙全打通了。这篇文章就把我的完整思路和能直接跑的代码逻辑捋一遍给想入坑算法游戏或者搞AI寻路的朋友做个参考。1. 先把问题拆开看自动求解到底在求什么1.1 别急着写代码先搞懂推箱子的状态空间很多人一提自动求解上来就想用A*问就是“启发式搜索更高效”。但真动手之前你得先想明白一件事推箱子的“状态”到底是什么。一个棋盘上有玩家位置、若干箱子的位置、若干目标点位置。所谓状态就是这些信息的快照。箱子位置集合 玩家位置集合合起来才是一个完整状态。为什么玩家位置也要算进去因为箱子能不能推取决于玩家站在哪里。举个例子一个4x4的棋盘两个箱子两个目标。箱子位置的组合有C(16,2)120种每个组合下玩家理论上可以在剩下14个格子中的任意一个粗算状态数就是1680。听着不大但如果换成10x10棋盘、5个箱子箱子组合飙到C(100,5)约7520万种再乘以玩家位置几十亿量级就上来了。这就是推箱子求解的第一个核心难点状态爆炸。不是算法不行是问题本身的分支因子和状态空间就摆在那。所以第一步不是选算法而是先搞清楚你面对的题目规模。3个箱子的小关卡BFS都能秒解8个箱子以上的复杂关卡裸BFS直接内存爆炸给你看。1.2 求解算法的选型逻辑BFS、DFS还是A*这块我直接给结论再说为什么。BFS广度优先搜索适合小关卡优点是第一次找到的路径一定最短缺点是真·吃内存。状态存哈希表里几百万状态一进来内存就嗖嗖往上涨。DFS深度优先搜索内存友好但容易陷进死胡同出不来。推箱子这游戏你推错一步往往要退十几步才能回到正轨深搜的天性就是一条道走到黑效率和可用性都堪忧。A启发式搜索*目前自动求解的主流选择。关键在于启发函数的设计。常见的是“曼哈顿距离之和”也就是每个箱子到最近目标点的格子距离总和。这个启发函数永远不会高估实际步数满足A*的admissible条件不会因为高估而错过最优解。但A*也有自己的坑。一是优先队列里推入的状态多了内存照样吃紧二是启发函数太粗糙搜索效率上不去。实战里我还用了加权启发——把启发值乘个系数比如1.2到1.5牺牲“保证最优步数”换取“更快找到解”很多复杂关卡根本不在乎多走十几步解出来比解最短重要得多。1.3 准备工作地图数据结构和状态表示开工前先把地图数据结构定好。我用的方案是字符串数组墙是#空地是空格玩家是箱子是$目标点是.箱子在目标点上是*玩家在目标点上是。开局地图长这样###### # # # $ # # . # ######解析之后我把地图存成三个集合墙坐标集合、箱子坐标集合、目标坐标集合。玩家坐标单独存。状态就用不可变对象或字符串做key方便哈希。比如把状态序列化成(玩家x,玩家y):(箱子1x,箱子1y):(箱子2x,箱子2y)...这样直接用字典做去重逻辑简单又不慢。2. 核心细节拆解从状态表达到死锁检测2.1 状态压缩与移动逻辑的完整实现不搞花活直接上最稳的状态表示方案。我把坐标转成单整数x*widthy一个二维坐标就变成一个int。整个状态就可以用一个int玩家位置 一个int数组箱子位置表示。为什么要这么做因为Python里tuple是hashable的但每次比较开销比整数大得多。实测下来整数化之后哈希查询速度能提升30%往上在大规模搜索时差距非常明显。移动逻辑是推箱子的灵魂只有两条规则玩家移动到空地玩家位置更新箱子不动玩家移动到箱子所在格且箱子前方的格子是空地或目标点玩家位置更新箱子位置更新就这么简单但坑在细节。比如箱子前方越界或者撞墙这次移动直接不可用再比如箱子前方是另一个箱子也不能推。一个箱子被另一个箱子挡住的情况很多新手代码里没处理结果就是解出来一条穿模路径调试半天才发现。我写移动逻辑的时候直接返回新状态不修改原状态天然支持回溯搜索时省心很多。2.2 死锁检测让搜索剪枝效率翻倍这步才是自动求解真正拉开差距的地方。纯靠BFS/A*裸搜5个箱子的中等关卡可能要跑几分钟甚至跑不完。加了死锁检测之后秒出解是常事。死锁分两种静态死锁箱子卡在某个位置无论如何都不可能被推到目标点。最简单的例子就是墙角。箱子在角上两侧都是墙那它这辈子都出不来了。检测方法很直接如果箱子当前不在目标点上且它相邻的两个方向比如上和左都是墙那就是死锁直接剪掉。更复杂的静态死锁还包括边上的连续墙段。比如箱子在一条长墙边贴着推进去之后没有横向移动空间也算死锁。这需要提前预处理地图把“不可达区域”标记出来。动态死锁箱子互相卡死。比如两个箱子在墙边挤在一起互相堵死了对方的移动空间。这个检测复杂一些通用方法是“死锁表”——离线枚举小形状的箱子组合模式然后在线匹配。但工程上我用的简单方案是每当一个箱子即将被推到一个新位置检查该位置是否在“死锁区域”同时检查这个箱子是否被其他箱子墙完全包围。包围检测就是看以该箱子为中心的三个方向不算玩家方向是否都不可通行。2.3 A*的启发函数设计曼哈顿距离只是及格线启发函数这块我必须多说几句。全网都在教曼哈顿距离但推箱子光用曼哈顿距离效果真的一般。原因很简单箱子之间互相挡路。你算每个箱子到最近目标点的曼哈顿距离加起来当作整个状态的估值忽略了箱子之间的阻碍作用。启发值偏低搜索就会多展开很多状态。我在实践中稍微改良了一下每个箱子优先匹配到离自己最近的目标点然后加上“玩家到最近箱子附近推箱位置的曼哈顿距离”。为什么要加玩家距离因为有些状态箱子全在目标点附近但玩家离得远实际上还要走很多步才能推下一箱。不加这个A*会优先展开这些“表面接近完成”但实际还得绕远路的状态搜索效率直线下降。再加一个加权系数我常用1.3左右。加权A的代价是未必最优但在“解出来”这个目标面前多走几步完全无所谓。实际测试同样的迷宫加权A找解的速度比普通A*快50%到200%关卡越复杂差距越大。3. 求解器的完整实操一步步从输入到输出3.1 解析地图并建立内部模型我不想空谈直接给一个最小可运行的求解框架。先定义地图解析模块class Board: def __init__(self, lines): self.height len(lines) self.width max(len(l) for l in lines) self.walls set() self.goals set() self.boxes set() self.player_pos None for y, line in enumerate(lines): for x, ch in enumerate(line.strip(\n)): if ch #: self.walls.add((x, y)) elif ch .: self.goals.add((x, y)) elif ch $: self.boxes.add((x, y)) elif ch : self.player_pos (x, y) elif ch *: self.boxes.add((x, y)) self.goals.add((x, y)) elif ch : self.player_pos (x, y) self.goals.add((x, y))为什么用set而不是list因为查重和成员判断是O(1)搜索算法里面这个操作极其频繁必须用哈希结构。3.2 A*实现要点优先队列与状态去重核心搜索框架如下我把关键逻辑用注释标出来import heapq def solve(board): start State(board.player_pos, frozenset(board.boxes)) goal_check lambda s: s.boxes board.goals open_set [(heuristic(start), start)] came_from {} g_score {start: 0} closed_set set() while open_set: _, current heapq.heappop(open_set) if current in closed_set: continue closed_set.add(current) if goal_check(current): return reconstruct_path(came_from, current) for neighbor in get_neighbors(current, board): if is_deadlock(neighbor, board): continue tentative_g g_score[current] 1 if neighbor not in g_score or tentative_g g_score[neighbor]: came_from[neighbor] current g_score[neighbor] tentative_g f_score tentative_g heuristic(neighbor) heapq.heappush(open_set, (f_score, neighbor)) return None这里有几个容易踩的坑第一frozenset作为箱子的表示原因是可以哈希能直接丢进dict做key。字典查询是下一步能不能提速的关键。第二closed_set和g_score的去重逻辑要配合好。我上面是先判断是否在closed里再判g_score。注意一个问题A*要求同一个状态如果后续以更短g值再次出现要能更新。用closed_set之后第一次弹出的状态如果已经处理过就不再处理这个逻辑在一致性启发下是正确的但如果你用了加权启发严格来说可能丢掉更优路径。工程上我通常接受这点损失换取速度。3.3 邻居生成与移动合法性判断这一步是整个求解器最容易写错的地方。很多人图方便直接枚举玩家的四个方向然后判断能不能移动/推箱。但这里面有个隐藏问题玩家移动和推箱子其实是两种操作它们的成功条件完全不同。def get_neighbors(state, board): px, py state.player_pos for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]: nx, ny px dx, py dy if (nx, ny) in board.walls: continue if (nx, ny) in state.boxes: bx, by nx dx, ny dy if (bx, by) in board.walls or (bx, by) in state.boxes: continue new_boxes set(state.boxes) new_boxes.remove((nx, ny)) new_boxes.add((bx, by)) new_state State((nx, ny), frozenset(new_boxes)) else: new_state State((nx, ny), state.boxes) if (nx, ny) in board.walls: continue yield new_state这里特别要注意玩家走到箱子上等价于推箱但箱子往前推的位置如果撞墙或者撞另一个箱子整个操作就非法。我把这个逻辑放在箱子前面那格判断逻辑清晰也好调试。还有个小细节有些关卡定义里玩家不能穿箱但可以原地不动换方向这不影响状态生成。3.4 死锁检测的工程化落地死锁检测剪枝是搜索加速的核心我这里给一个精简实现。思路是预处理地图上所有“不安全区域”凡是箱子进入不安全区域且不在目标点直接判死。比如墙角检测我可以从简单场景开始写一个def is_deadlock(state, board): for (x, y) in state.boxes: if (x, y) in board.goals: continue # 角落死锁 left_wall (x-1, y) in board.walls right_wall (x1, y) in board.walls up_wall (x, y-1) in board.walls down_wall (x, y1) in board.walls if (left_wall and up_wall) or (left_wall and down_wall) or (right_wall and up_wall) or (right_wall and down_wall): return True return False这只是第一层比较粗糙但速度快。更精细的检测是把地图上所有“无法到达目标的死角区域”预先用BFS算出来然后只看箱子在不在这些区域。我的经验是先用粗检测拦掉80%的明显死锁如果关卡复杂到粗检测不够用再上精细检测。因为精细检测本身也耗CPU做过头反而拖慢搜索。4. 关卡生成的思路先解出来再“倒着设计”4.1 关卡生成的基本策略反向推箱法自动求解搞明白之后关卡生成就有基础了。关卡生成的难点不是“摆点障碍物”而是保证关卡可解。有些关卡你画出来看着挺好看结果自己解一晚上解不出来玩家拿到手更是直接弃坑。这种关卡只能自嗨不能发布。业界常用的生成思路叫“反向推箱子”。正向是你把箱子推到目标点反向则是从“所有箱子都在目标点且玩家在某个位置”的状态开始让玩家执行“反推”操作——把箱子从目标位置拖出来拖到一个新位置。关键在于反向操作一定是合法的。正向推箱子的逆操作就是反向拉箱子而反向拉的每一步在正向看来都天然可达这从原理上保证了生成关卡一定是可解的。4.2 生成流程从终态开始随机扩展具体流程我这么做的第一步初始化终态所有箱子都在目标点玩家随机放在一个空地上。第二步随机执行反向移动。所谓的反向移动就是把箱子从A拖到B箱子从B出来变成人在A、箱子在B。循环执行几百步得到一个“开局状态”。第三步把开局状态的箱子位置和玩家位置记录下来这个初始局面就是关卡的基础。但这里有个问题直接这样生成的关卡往往极其简单。因为你拖几步之后棋盘上基本没有障碍墙所有箱子都在一片开阔地里玩家随便一推就能归位。这就涉及难度控制。4.3 难度控制墙壁布置与步数阈值为了解决“太简单”的问题我调整了生成策略。先随机生成一些墙然后在有墙的地图上执行反向生成同时统计生成过程中“正向解算步数”的预估。更靠谱的办法是生成关卡后直接调用我们前面写的求解器去解一遍。解题步数就是衡量难度的一个指标。如果步数太少比如小于游戏预设的阈值就丢弃这个关卡重新生成。我设了几个档次解步数10步以内属于入门10到30步属于新手30到80步属于熟练80到150步属于专家150步以上属于地狱。然后根据想要的难度档位反向筛选。4.4 关卡去重与美学约束还有一个容易忽略的点关卡去重。随机生成很容易产出大量“本质相同”的关卡——镜像、旋转、平移后的同款。我做了个简单处理每生成一个新关卡就把它镜像翻转和翻转90度后的几个变体哈希存起来如果新关卡和已有关卡或其变体计算出的哈希值命中就说明重复了直接弃掉。美学约束也有讲究。有些算法生成的关卡墙和空地看起来完全随机像一个毛坯房玩起来没有任何美感。我加了几条规则不能有太长的连续死胡同利于互动的空间不能生成大面积孤立区域除非箱子确实在区域内并且目标点也在每个箱子至少要有两条移动路径的可能性保证操作感。这些规则落地无非是生成之后跑若干次自动求解同时做一些连通性检测。不过要说明白美学这东西主观性很强规则加多了反而生成速度会降平衡点需要你自己调。5. 实际项目中的性能优化与工具选型5.1 语言与框架选择Python调试C提速这个项目我最初用Python写了个原型主要目的是快速验证算法正确性。但Python跑复杂关卡是真的慢尤其搜索状态一多解释器的开销就非常明显。后来我把核心搜索逻辑用C重写了Python只做地图解析和关卡生成的“调度层”。同样的复杂关卡Python可能跑80多秒C版本4到5秒就能出解差距超过十倍。如果你是游戏开发者想把这个做成产品功能建议直接用C或Rust实现求解模块对外提供API。如果只是自己研究算法Python完全够用配合PyPy解释器也能比CPython快三到五倍。5.2 剪枝与缓存从状态空间压缩到位编码状态空间大还有一个工程化解法位编码。把每个格子用2bit表示空地、墙、箱子、目标点如果有玩家位置就单独再用一个int存。一个20x20的棋盘就是400个格子2bit一个总共800bit也就是25个int。所有状态都可以变成定长数组比Python的tuple紧凑得多内存占用直接降到原来的五分之一以下。再有就是前文说的闭包集合必须严防单个状态从不同路径反复入队。我的经验是达到如下水平才算优化到位100万状态以下内存占用不超过200MB解一个中等复杂关卡能控制在十秒以内。5.3 多线程与任务拆分批量生成的实战方案关卡生成需要的求解次数更多因为生成后要验证可解性生成过程中还要做步数预估。这块我用了多线程生成器线程负责产出候选关卡求解器线程负责验证这些关卡。Python多线程有GIL限制CPU密集任务效果不好我直接用了multiprocessing进程池最多12个worker去并发验证关卡可解性。这一步对批量生成特别有效生成1000个关卡如果单线程可能要两三个小时开12个进程之后十几分钟就搞定了。6. 常见问题与排查技巧实录6.1 搜索半天解不出来先查死锁检测和启发函数这是我遇到最多的求救场景。新手用A*搜小关卡没问题一上复杂关卡就卡死或者跑个不停。先查两件事第一死锁检测有没有加没加的话很多状态会反复围绕同一个死锁区域打转状态数爆炸。加上角落死锁检测状态数有时直接降到原来的五分之一。第二启发函数是不是一致性地低估了纯曼哈顿距离启发A*在复杂推箱子下效率不佳。我把加权系数调到1.3之后搜索时间能缩短一半左右。再不行就检查是不是有箱子在生成的时候放到了完全无法移动的位置。这种关卡从原理上就是无解的再怎么搜都没用你需要前置的可解性检查。6.2 内存爆了优先排查状态去重与数据结构内存爆炸几乎都是同一个原因closed_set里堆了太多状态没清理。换句话说你的剪枝太弱。这里有一个很容易犯的错误把状态存在一个list里没做哈希去重每次查询都是O(n)最后所有状态都塞进内存程序直接卡死。解决方法是两条腿走路保证去重用set或者dict保证死锁剪枝前置。如果状态数还是很大就换位编码把状态的内存占用压到最小。6.3 关卡生成出来不可解反向生成时拉了太多步反向生成法的坑就在这里。我最初调试的时候反向随机拖了几百步生成的关卡就位之后用求解器一解居然不可解。排查下来发现原因反向操作虽然是合法的但正向的求解路径可能被我自己后加的障碍物拦截了——我先随机生成了墙再从终态反向拖箱子拖的过程中有机会把墙“挤到”某些位置但这些墙可能堵住了箱子的返回路线。解决方案反向拖动的每一步都重新做一次可解性校验一旦发现不可解就回退一步重新拖。这样生成的关卡天然可解代价是会慢一些但可靠性高得多。6.4 生成关卡太简单步数阈值与美学约束的矛盾“步数少说明太简单步数多说明太难”这个判断在大方向上没错但并不总是准确。有些关卡步数很少但极其绕玩家要反复在很小的区域里腾挪有些关卡步数多但全是直推玩家闭着眼睛都能解。我最后的方案是用“最少推箱子次数”和“最少玩家移动次数”两个指标一起评估难度同时人工抽查几个样本做校准。虽然没有完美解决主观难度感受的问题但比单一步数靠谱得多。7. 工具链与扩展玩法别止步于“能解出来”7.1 可视化调试没有界面你会在DEBUG里崩溃搜索和生成是纯算法逻辑但纯文本输出状态的调试体验非常糟糕尤其是在复杂关卡上。我强烈建议花半小时做一个简单的可视化界面用颜色区分墙、箱子、目标、玩家支持单步播放。调试的时候你能直观看到A*每一轮在探索什么区域死锁剪枝把哪些状态砍掉了反向生成的随机性到底把箱子拖到了哪里。我用的是标准的SDL或者Python的pygame都能做。不做成产品级界面只做调试工具成本极低收益极高。7.2 扩展玩法难度动态调节与人机解析关卡生成的下一步是“动态难度调节”。比如玩家卡住超过两分钟就给他一个提示该推哪个箱子、下一步最优解的方向是什么。这个功能实质上就是实时调用求解器把玩家当前状态作为输入计算一个最短解并提示下一步动作。我在这块做了一点小实验在UI上显示“箱子距离目标的总步数”让玩家有个模糊的方向感。实测下来玩家体验好很多不至于因为困在一个中等关卡里直接卸载游戏。7.3 我把这个方案用在哪些场景自动求解和关卡生成组合起来最直接的应用就是游戏开发中的关卡设计。你可以一键生成1000个关卡人工抽检后放进游戏省掉设计师手动铺关卡的重复劳动。另一个很实用的场景是算法教学用推箱子当教学案例讲清楚状态空间、启发搜索、剪枝与优化比用八数码、十五数码那些干巴巴的题目有意思得多。最后我自己做成了一个小工具库输入任意关卡地图输出求解路径还能顺便评估这关的难度分数。给身边几个做游戏的朋友用反馈都还不错。8. 一个值得尝试的进阶方向两个箱子的小型关卡完全求解做了这么久我个人的体会是别一上来就想着搞定所有推箱子那是写论文的人才该干的事。我的心态是把“能用”和“好用”分开能用就是能解大多数中等以下关卡好用就是能在秒级出解并且能批量生成高质量关卡。最后的建议是你如果自己动手可以先从一个“极其小的关卡”做起比如3x3棋盘两个箱子一个目标。把这个小关卡彻底求解并输出最优路径。从这个规模出发你会自然遇到状态去重的必要性、死锁检测的出发点、启发函数的意义而这些才是推箱子自动求解真正的技术内核。
阅读完成 · 觉得有帮助？
