1. 项目拆解自动求解与关卡生成到底在解决什么问题推箱子Sokoban这个游戏规则简单到一句话就能说清把箱子推到目标点上就算过关。但就是这么一个“简单”的游戏背后却藏着两道让开发者又爱又恨的难题——自动求解和关卡生成。我当年第一次接触这个项目时以为半天就能搞定结果硬生生折腾了两周。今天就把我的完整思路、踩过的坑、以及最终能跑通的方案一次性讲清楚。先说自动求解。推箱子本质上是状态空间搜索问题每一个“玩家位置 每个箱子的坐标”都构成一个状态玩家推一步状态就转移一次。理论上用广度优先搜索BFS就能找到最短解但实际跑起来你会发现状态数量爆炸得离谱。随便一个15x15的中等关卡状态数就能到百万甚至千万级别普通BFS根本扛不住。再说关卡生成。这玩意儿比求解更抽象。你要生成一个“有趣”的关卡意味着它必须是可解的、有挑战性的而且最好不是那种一眼望穿的直线推箱子。直接随机摆箱子很容易生成无解关卡所以主流的做法是逆向生成从一个简单的“已解决”状态出发反向推动作序列打乱箱子位置最后得到一个全新的初始布局。这个项目适合谁如果你是算法爱好者想练手搜索剪枝、状态压缩、判重优化自动求解部分能让你玩得很爽。如果你是游戏开发者想给自家游戏搞个无尽模式关卡生成部分就是你的刚需。哪怕你只是好奇“AI怎么玩推箱子”这篇文章也能让你理解其中的核心套路。2. 自动求解的设计思路从BFS到双向搜索再到启发式剪枝2.1 为什么普通BFS走不远一开始我天真地写了个标准BFS用字符串表示状态玩家坐标 所有箱子坐标拼接丢进队列里硬搜。很快发现两个致命问题状态膨胀中型关卡的状态数轻松破百万每个状态存一个字符串内存直接爆掉。无效搜索很多状态根本就是死胡同比如箱子被推到墙角但不在目标点上这种状态永远不可能解开但BFS不知道照样搜得乐此不疲。所以第一步优化是把状态编码压缩。我用整数数组代替字符串两个整数记录玩家位置行和列一串整数记录每个箱子位置。判重时用一个哈希集合存整数元组比字符串省好几倍内存。但光压缩不够你还需要剪枝。最简单的剪枝是“死局判定”如果某个箱子被推到了墙角两个相邻方向都是墙但该位置不是目标点直接丢弃这个状态。还有个更隐蔽的死局箱子贴墙滑动时如果滑动方向的下一格是墙且箱子不在目标点同样没救。这两个剪枝能砍掉大量无效分支实测搜索时间能缩短60%以上。2.2 双向BFS把搜索空间开根号当关卡规模上来后单向BFS依然力不从心。这时候我换成了双向BFS——从初始状态正向搜同时从目标状态所有箱子都在目标点反向搜两边轮流扩展直到中间相遇。为什么有效因为BFS的搜索空间随深度指数增长单向搜到深度d要遍历d层双向各搜d/2层总状态量大概是两倍的d/2层之和远小于单边的d层。用生活类比你从北京往上海走我从上海往北京走咱俩各走一半路比一个人从北京走完全程省力多了。实现双向BFS有个坑逆向搜索时“玩家推箱子”的逆操作不是“拉箱子”而是玩家从箱子周围走到一个合法空位并让箱子朝相反方向移动。具体说正向动作是“玩家在某方向推箱子”逆向动作就要判断当前箱子位置玩家站在它的反方向然后箱子移动到反方向的下一个位置玩家站到原来箱子的位置。逻辑容易绕晕建议画出状态转移图把正逆动作拆成独立的函数别混着写。双向BFS的相遇检查也很讲究。我是两个方向各维护一个visited集合每扩展一层就检查当前层的状态是否出现在对方的visited里。如果出现就说明找到了路径然后把两个方向的动作序列拼接起来。注意拼接时逆方向的序列要反过来因为那是从目标状态倒推回中间状态的。2.3 启发式搜索用A*把效率再拉一个档次双向BFS已经很能打了但遇到那种需要绕大远路的关卡它依然会搜出很多无意义的中间状态。我想既然都做了判重和剪枝不如直接上A*用启发函数引导搜索优先走“有希望”的方向。A的核心是估值函数 f(n) g(n) h(n)g是从起点到当前状态的实际步数h是当前状态到目标的估计代价。推箱子常用的启发函数是曼哈顿距离和每个箱子到最近目标点的曼哈顿距离之和。这玩意儿计算极快而且因为是松弛估计永远不会高估真实代价所以A一定能找到最优解。但我实测发现纯曼哈顿距离和太乐观了导致A搜索时还是撒开了跑。后来我加了一个改进考虑箱子之间的冲突。比如两个箱子挤在一起互相挡路实际代价会比各自距离相加高得多。这个改进做起来有点复杂简单点可以这样计算A的优先队列排序时在h里加一个惩罚项——如果有两个箱子的目标和曼哈顿路径重叠就在总和上加几份额外代价。别小看这个惩罚它能让A*在那种“箱子互相堵门”的关卡里少走很多弯路。还有个小技巧用“玩家到箱子的距离”修正h。因为推箱子之前玩家必须跑到箱子旁边。h里加上玩家到最近箱子的距离能加速前期搜索。修正方式h 箱子曼哈顿距离和 玩家到最近箱子距离。但注意这个修正只在特定实现下能保证admissible不超过真实代价如果你不想严格证明就把它当做一个“准A*”用也能接受。2.4 状态表示与去重的工程细节写到这里必须强调工程实现的重要性。算法再牛状态表示没做好照样卡死。我最终用的状态结构长这样# 状态表示示例 # 玩家位置: (pr, pc) # 箱子位置: 元组列表 [(r1, c1), (r2, c2), ...] # 为了判重将箱子坐标排序后拼接成元组 def state_key(player, boxes): sorted_boxes tuple(sorted(boxes)) return (player, sorted_boxes)排序是关键。因为同一组箱子坐标如果顺序不同判重时会被当成不同状态导致搜索空间虚增。我一开始没排序结果同一种局面至少被重复存了“箱子数量的阶乘”次。这种低级错误能让内存暴涨十几倍排查了半天才恍然大悟。另一个实用技巧是预计算“死锁区域”。在关卡加载时把那些格子标记为“如果箱子到达这里且不是目标点则必死”。这能进一步减少无效状态。死锁区域的判定方法对每个非目标点格子若它的上方和左方都是墙则标记为死角还有一种“贴墙死角”上方是墙且左方是墙或者上方是墙且右方是墙这种也很好判断。虽然这不能覆盖所有死局但实现简单收益很高。如果你用C写还能用bitset对关卡地板编码做位运算优化。用64位整数表示一行格子箱子位置用一个位标记这样状态可以压成几个64位整数哈希和比较都非常快。不过我是用Python写的原型图个省事后面的性能需求不极端的话也够用。3. 关卡生成的逆向思路先有解再添乱3.1 为什么不能直接随机摆放新手做关卡生成最容易掉进的坑就是随机放墙、随机放箱子、随机放目标点然后自己玩一下看看能不能解。结果99%的概率生成的是无解关卡或者过于简单、毫无趣味。因为随机摆放的箱子往往堵死了所有通路玩家根本没法把所有箱子推到目标点。更隐蔽的问题是“趣味性”难以量化。你可能随机到一个可解关但箱子全在起点附近几步就结束了这种关卡没有生成意义。所以我采用逆向生成法核心是从最终完成态开始反向走几步就得到一个可解的初始态。反向走的“步数”越大关卡越难因为箱子被推得越散、玩家需要绕的路越多。3.2 逆向生成的具体步骤初始化选定一个房间布局固定墙体和通道把所有箱子放在目标点上玩家安排在某个空地上。随机反向推箱子从当前状态出发随机选择一个箱子判断玩家能否走到它的“反向推动”位置。如果能就把箱子向某个合法方向挪动一格同时玩家的位置更新到原来箱子所在的位置。重复这个过程N次。清洗冗余记录下每一步的动作序列再把箱子位置“固定”为最终初始态。此时状态必然可解因为只要把动作序列正向执行一遍就能还原到目标态。添加挑战性为了让关卡不那么直白可以在已经生成的箱子位置附近增加一些装饰性墙体但要检查这些墙体是否破坏了可解性。这里有个参数特别关键反向移动的步数N。N太小时箱子几乎还在目标点附近太简单N太大箱子可能被推到一些极端角落导致解的空间极小甚至玩家第一步就没法动。我测试下来一个15x15的场地N在30-60之间比较稳。更大的场地可以把N调到80-120。反向移动还有一个限制箱子不能重叠不能推穿墙而且每次反向操作必须保证玩家原来的位置是合法的。这个合法性判断和正向求解完全一样只是方向反了。可以复用代码里的合法性检查函数注意正向和反向调用的语义差异。3.3 如何增加关卡“趣味性”光有可解还不够“好玩”才是目标。我的做法是设计一个难度评估函数维度包括箱子分散度统计各箱子位置到最近目标点的曼哈顿距离的方差。方差越大说明箱子分布越散玩家需要来回跑的次数越多难度越高。死锁风险度统计有多少箱子所在位置接近死锁区域但还没死锁。接近越多容错率越低关卡越刺激。干燥步数占比从初始态到目标态的最短解中“玩家推箱子的步数”与“玩家单纯走路的步数”之比。推箱子占比越低说明玩家花在绕路上的时间越多迷惑性越强。每次生成一批候选关卡按这些维度打分然后挑分数最符合你预期的那个作为最终产出。如果你想要一个“新手热身关”就把分散度和死锁风险调低想要“专家自虐关”就拉高。我自己的实践是先把N设为40生成100个候选跑一个求解器确定它们的最短解长度再筛选。如果最短解长度在80-150步之间通常是比较均衡的中等难度。3.4 墙体布局的生成策略逆向生成法其实对墙体布局要求不高你可以手动画一个模板也可以程序化生成。程序化生成我试过两种房间分割法类似“生成迷宫”的做法把场地分成若干小房间房间之间开连通门洞再把部分通道堵上形成回环。这种布局天然具备曲折感适合做中等以上难度关卡。随机障碍法在空地上随机放置一些实心块然后用遍历算法检查所有可达区域保证整个地图是连通且可达的。这个方法快但容易产生封闭小空间需要额外做可达性过滤。我推荐用房间分割法作为基底因为推箱子关卡本质上需要“行星际物流”般的感觉有多个子区域箱子需要在子区域之间搬运玩家在狭窄通道里反复转身操作。随机障碍法生成的开放空间太多推箱子缺少“卡位”乐趣。实现分割法时可以用一个二维数组表示地图0为空地1为墙。先用大块矩形划分再在矩形边界上开几个门洞门洞的位置尽量对称或错落有致。记得在门洞附近留足够空间否则玩家无法把箱子推过门洞。3.5 可解性验证不要盲目相信逆向法逆向生成法理论上保证可解但实际编码时经常出bug导致生成的关卡实际上不可解。比如反向推箱子时如果判断“玩家能否走到反向位置”的函数写错了可能把一个本来合法的状态转换成了非法状态最后生成一个伪可解的烂摊子。所以每次生成关卡后必须跑一遍自动求解器验证可解。如果不可解就丢弃重新生成。这里就体现自动求解器的另一重价值不是摆设是质量把关器。我甚至会把验证过的关卡连同它的最短解路径一起存起来。游戏里如果要加“提示”功能直接播放这个解路径就行一鱼两吃。验证效率也要注意。单关卡求解可能耗时所以生成一批后批量验证用多线程并发跑能省不少时间。我用Python的concurrent.futures开8个线程100个候选关卡几分钟内就能全部验证完。4. 实操记录从零搭一个可运行的求解器生成器4.1 项目结构和数据模型我建议把功能拆成这几个模块solver.py求解器、generator.py生成器、map.py地图数据模型、verify.py验证工具。如果以后要接入图形界面再加一个ui.py保持逻辑与渲染分离。地图数据模型用一个二维列表最直观。我用0表示空地,1表示墙,2表示目标点,3表示箱子,4表示玩家。不过如果你要频繁做状态转换直接维护两个集合更灵活一个boxes_set存箱子坐标一个player_pos存玩家坐标外加一个walls_set存墙坐标。地图大小用rows和cols记录。目标点可以从关卡配置里单独读出来存成goals_set。载入关卡时我会先做一次预处理把地图中有没有任何箱子一开始就压在目标点上如果有标记为“已完成箱子”再把所有目标点位置缓存到一个列表里方便后面算启发函数时快速取用。4.2 求解器的关键代码逻辑以下是我最终调通的自动求解器的简化核心代码Pythonfrom collections import deque import heapq def is_wall(maze, r, c): return maze[r][c] 1 def in_bounds(maze, r, c): return 0 r len(maze) and 0 c len(maze[0]) def is_box_at(boxes, r, c): return (r, c) in boxes def is_deadlock(maze, r, c, goals): if (r, c) in goals: return False # 简单死锁两个正交方向都是墙或者一个方向是墙且另一个方向是不可推的角落 up is_wall(maze, r-1, c) down is_wall(maze, r1, c) left is_wall(maze, r, c-1) right is_wall(maze, r, c1) if (up and left) or (up and right) or (down and left) or (down and right): return True return False def bfs_solve(maze, player_pos, boxes, goals): # 状态定义: (player_pos, tuple(sorted(boxes))) initial_boxes tuple(sorted(boxes)) start (player_pos, initial_boxes) if all(b in goals for b in boxes): return [] # 已经解决 q deque([start]) visited {start} parent {start: None} action {} while q: (p, b), path_len q.popleft(), 0 # 实际要记录长度可以用字典 # 为了简洁此处只写思路完整版需要记录步数 # 遍历四个方向 for dr, dc, act in [(-1,0,U),(1,0,D),(0,-1,L),(0,1,R)]: np (p[0]dr, p[1]dc) if not in_bounds(maze, *np) or is_wall(maze, *np): continue if (np[0], np[1]) in b: # 要推箱子 nb_pos (np[0]dr, np[1]dc) if not in_bounds(maze, *nb_pos) or is_wall(maze, *nb_pos): continue if is_box_at(b, *nb_pos): # 箱子的位置已经有箱子 continue # 新箱子集合 b_list list(b) b_list.remove((np[0], np[1])) b_list.append((nb_pos[0], nb_pos[1])) new_b tuple(sorted(b_list)) new_p (np[0], np[1]) # 玩家移到原来箱子位置 else: new_b b new_p np new_state (new_p, new_b) if new_state not in visited: visited.add(new_state) parent[new_state] (p, b) action[new_state] act if all(pos in goals for pos in new_b): # 反向回溯路径 seq [] cur new_state while parent[cur] is not None: seq.append(action[cur]) cur parent[cur] seq.reverse() return seq q.append(new_state) return None # 无解以上代码省略了父节点记录长度等细节真实运行需要把path_len也存起来否则BFS这里没问题但A就得用优先级队列了。A版本的核心是优先级(g h, g, state)def heuristic(boxes, goals): total 0 used_goals set() for box in boxes: best min(manhattan(box, g) for g in goals if g not in used_goals) # 简单处理允许重复用同一目标或者做匹配 total best # 如果要严格可以做二分图最小匹配开销大但更准 return total def astar_solve(maze, player_pos, boxes, goals): start (player_pos, tuple(sorted(boxes))) open_heap [(0, 0, start)] g_score {start: 0} parent {start: None} action {} while open_heap: f, g, state heapq.heappop(open_heap) p, b state if all(pos in goals for pos in b): # 回溯 ... for dr, dc, act in [(-1,0,U),(1,0,D),(0,-1,L),(0,1,R)]: # 逻辑与BFS相同只是将 g1 和 heuristic 计算出f ...实际工程中这里需要注意**heuristic的合法性**箱子到目标的曼哈顿距离之和前提是每个目标点都被一个箱子占用而曼哈顿距离允许箱子穿过别的箱子所以没问题因为穿过别的箱子在实际中可能需要额外代价故h只会低估不会高估。但如果你加入“箱子互相冲突”的惩罚就要额外小心不能完全保证h真实代价。如果只是求“任意路径而不一定最优”那倒是无所谓。另一个工程细节BFS时我用parent和action两个字典记录前驱状态和动作回溯时先走到None再反转列表。务必在push进队列时同步记录别等弹出时再找因为状态可能已经被更优路径更新了。4.3 生成器的核心代码逻辑生成器需要复用求解器里的合法性判断。我实现一个random_walk_back()函数import random def reverse_move(maze, player_pos, boxes, goals): # 随机选择一个箱子 box random.choice(list(boxes)) # 四个方向箱子反向移动即玩家站在箱子的反方向位置 dirs [(-1,0),(1,0),(0,-1),(0,1)] random.shuffle(dirs) for dr, dc in dirs: player_stand (box[0] - dr, box[1] - dc) # 玩家要站的位置 new_box_pos (box[0] dr, box[1] dc) # 箱子被推后的新位置 # 检查玩家站的位置合法且能到达不考虑箱子因为玩家是走过去的 if not in_bounds(maze, *player_stand) or is_wall(maze, *player_stand): continue if player_stand in boxes: continue # 检查新箱子位置合法且不与别的箱子重叠 if not in_bounds(maze, *new_box_pos) or is_wall(maze, *new_box_pos): continue if new_box_pos in boxes: continue # 检查玩家是否能从当前位置走到 player_stand 不能被箱子挡住 # 这里要跑一个BFS无障碍物但箱子算障碍 if can_player_reach(maze, player_pos, player_stand, set(boxes) - {box}): # 执行移动 new_boxes set(boxes) new_boxes.remove(box) new_boxes.add(new_box_pos) new_player (box[0], box[1]) # 原来箱子位置变成玩家位置因为反向推箱子等价于玩家从反方向把箱子推开 # 但注意玩家从 player_stand 推箱子到 new_box_pos所以操作后玩家站在 box 位置箱子在 new_box_pos # 嗯这里需要仔细想... return new_player, new_boxes return None等等上面这个函数我卡了一个逻辑问题反向推箱子应该理解为“正向推箱子的逆操作”。正向是玩家从P位置推动箱子从B到B玩家最终站在B处。逆操作就是玩家站在B处箱子在B处要将箱子从B推回到B然后玩家回到P处。所以逆操作的输入是当前玩家位置P、当前箱子集合包括B我们要找到原来的B和P。换个更清晰的写法随机选一个箱子它的当前位置记为B。然后我们想把箱子挪到它旁边的空位置BB需要满足B不是墙且B在B的某个方向上。同时玩家必须能够从当前位置走到B的反方向位置P即 从B朝着B的方向继续往前走一格的位置即P 2*B - B并且P不能是墙、不能是箱子。这里“玩家必须能走到P”但注意P可能被其他箱子挡路实际上反向推箱子时玩家是从P往B方向推箱子但在逆操作时刻玩家的当前位置是某个地方需要能走到P。我直接用BFS检测玩家从当前pos到P的可达性障碍是除当前箱外的所有箱子。例如当前箱子位置B(3,3)想把它挪回B(2,3)方向是“北”-1,0那么玩家要站在P(1,3)即B向B方向再前进一格即B再往北一格正向推箱子玩家在P(1,3)推箱子从B(2,3)到B(3,3)最后玩家站在B(2,3)逆操作玩家从P走到(1,3)把箱子从B推回B(2,3)最后玩家站在(2,3)如果B是目标点都没关系因为我们在生成时目标点只是地板标记。修正后的reverse_move逻辑def reverse_move(maze, player_pos, boxes, goals): box_list list(boxes) random.shuffle(box_list) for box in box_list: dirs [(-1,0),(1,0),(0,-1),(0,1)] random.shuffle(dirs) for dr, dc in dirs: # B box (dr,dc) 其实我们要推的“原位置B”应该在box的反方向 # 写清楚当前箱子在 B。我们希望箱子被推回去到 B box - (dr, dc) 还是 box ...? # 设想正向推箱子动作玩家在P推动箱子从B到B方向为(dr,dc)那么 B B (dr,dc)P B - (dr,dc)。 # 因此已知 B给定(dr,dc)则 B B - (dr,dc)P B - 2*(dr,dc)。 # 但要注意 dr,dc 是箱子移动方向即正向推的方向。 # 所以 B_prime box B (B_prime[0] - dr, B_prime[1] - dc) P (B_prime[0] - 2*dr, B_prime[1] - 2*dc) if not in_bounds(maze, *B) or is_wall(maze, *B): continue if B in boxes: continue if not in_bounds(maze, *P) or is_wall(maze, *P): continue if P in boxes: continue if can_player_reach(maze, player_pos, P, set(boxes) - {B_prime}): # 执行反向操作箱子从B移到B玩家从当前pos走到P然后推箱子到B最终玩家站到B # 简化直接返回新玩家位置为B因为操作后玩家确实站在原B处 new_boxes set(boxes) new_boxes.remove(B_prime) new_boxes.add(B) return B, frozenset(new_boxes) return None这里用frozenset做返回以便哈希。但注意can_player_reach中的障碍物要排除B_prime这个箱子因为玩家需要用身体贴着它路径上可能穿过它原来的位置不路径不能穿过箱子所以障碍物是boxes - {B_prime}加上墙。BFS时标记墙就是墙标记障碍物集合用于排除。如果你觉得反向生成写得绕推荐另一种更简单的实现正向随机推箱子。就是随机选一个箱子从当前状态初始箱子全在目标点随机执行合法正向推法推N步。推完后的状态就是初始关卡而合法动作序列就是解。这个思路更直观不容易出错。虽然生成的关卡难度分布可能不如逆向好调但可以先跑通再优化。正向随机推需要保证每步都能推得动箱子而且箱子不能推出边界或压墙另外别忘了检查玩家能否走到箱子推位。代码写起来更直接。我后来项目里就换成了正向版本更加省心。4.4 难度的量化与自动筛选生成一批候选后用求解器算出最短解的长度、箱子移动次数、玩家移动次数。我总结了一个可用的难度评分打个比方解的总步数在60-100之间简单100-160中等160-250困难250以上专家级但仅看步数不够还需要看“操作密度”。比如箱子移动次数占总步数的比例如果太低说明玩家大部分时间在走空路关卡显得绕且拖沓。一般这个比例在30%-50%比较合适。太高则说明关卡太直白就是个推箱子接力赛。我筛选时还设计了一个“回环度”检测统计最短路中玩家访问的格子坐标去重后的数量。如果数量小于总步数的60%说明玩家一直在重复走回头路这种关卡玩起来容易烦躁反之则说明路线丰富更耐玩。当然这个指标存在例外但作为自动筛选的“批量化指标”很有效。如果你不需要生成专家级折磨人关卡用简单规则筛选就够所有生成的关卡先验算得分分数在区间内就保留再多跑几个候选挑最好。4.5 与游戏前端的对接做完求解器和生成器之后我把它接到了一个简单的HTML5 Canvas前端里。基本思路是后端Python生成关卡后输出一个JSON对象包含地图网格、玩家初始位置、箱子位置、目标点位置。前端读取JSON渲染画面监听键盘事件玩家可以用方向键推箱子。求解器暴露一个API接口输入关卡JSON输出解序列前端拿到后按序列播放动画作为“提示”功能。这种前后端分离的好处是求解算法和渲染逻辑完全解耦。如果你只是做算法研究不接前端也无所谓但如果做游戏这个接口设计很实用。在实际对接中要注意坐标统一。我后端用的二维数组坐标row, col前端Canvas用的是像素坐标换算时务必写好转换函数。另外状态同步要小心前端每移动一步都要用后端同样的数据结构维护玩家位置和箱子列表不然“提示”回放就会错乱。5. 常见问题与排查技巧实录这一节是血泪总结希望你少踩我踩过的坑。5.1 求解器跑不出解还死循环最常见的原因是状态空间太大导致BFS超时。解决思路优先优化判重数据结构。用集合加上高效的哈希。开启剪枝死锁判定我实测能减少70%状态。换双向BFS或A*。如果依然跑不出来你就要检查地图里是否存在不可达区域。比如用填充算法Flood Fill检查玩家能否到达所有箱子。如果箱子在一个孤立区域而玩家根本进不去那这关本来就无解求解器再怎么优化都不可能得出路径。这种情况在测试地图前先用连通性验证过滤掉。5.2 生成器产出的关卡一眼就能看出“模板味”这个问题几乎必然出现。因为逆向生成的初始状态是从目标态随机反向推出来的而反向推移的路径往往带有某种“螺旋”特征。解决方法多做几次随机重排把玩家位置在最后再随机放置到一个非箱子非墙的空位。把初始的目标点集合也随机变换一下比如原来目标点在左侧生成后可以整体镜像、旋转增加多样性。加一些“噪音”在空闲区域随机加墙或空出空地但要保证连通性。如果你要生成大量关卡建议先跑一批人工看几关总结模式再调整随机种子策略。5.3 用BFS判可达性时忽略玩家碰撞这个坑很隐蔽。can_player_reach函数判断玩家能否从A点走到B点时我把所有箱子都当作障碍物这没问题。但有时候玩家要走到箱子旁边才能推箱此时路径不能穿过箱子而B点恰好在箱子旁BFS会认为合法。这没问题。问题在于当你要推某个箱子时玩家初始位置可能在箱子的另一侧路径需要绕到推位但如果绕不过去这一步就不该执行。现实中如果箱子挡住了唯一的通道玩家就无法从另一侧绕过去。我在can_player_reach里把正在推的箱子排除在障碍之外结果路径可能“穿过”该箱子。千万不能排除必须始终把箱子当障碍。我因为这个bug浪费了半天时间生成的关卡要么不可解要么解出来是歪的。5.4 死锁检测的误杀前面说的简单死锁判定是“任何箱子在墙角和另一方向也是墙且不在目标点”但有些看似死锁的位置其实可以通过“先推别的箱子”解锁。比如两个箱子紧挨着靠墙一个被判定死锁但另一个一旦推开这个箱子就能被推走了。我的简单判定只判断单箱紧贴双墙不会把这种情况误杀反而漏杀了“箱子贴墙但不是紧贴墙角”的真实死锁。更准确的做法是跑一个动态死锁检测从当前状态用BFS搜索看是否存在某个箱子能被推到目标点。但这成本太高不能每状态都调。所以我的妥协方案普通搜索只用简单死锁生成的关卡最终会用全量求解器验证。如果验证时无解说明死锁检测漏了但至少不会把可解关卡误判为无解。宁可多搜一些状态也不冒险剪枝剪掉正解。5.5 内存溢出与Python性能Python跑10x10的关卡没啥压力但20x20的大地图就可能吃紧。我用的优化状态集合用set存储元组并且元组里的箱子列表是排序后的tuple。用lru_cache缓存can_player_reach的局部可达性结果不行因为障碍物变化了不能直接缓存。将墙体、箱子分别用整数位掩码表示用frozenset存箱子集合哈希速度更快。如果追求极致性能还是建议用C重写核心求解器。Python适合做原型验证C适合在游戏里实际跑。我后来用C重写了一遍速度提升一个数量级以上。5.6 接口层坐标不一致这是个低级但高频的问题。前端用(x,y)表示横纵后端用(row,col)很容易搞混。我建议在项目最早期就在数据模型里统一坐标命名规则比如永远用(row, col)并在前端转换器中写清楚row对应ycol对应x。所有函数参数都按这个顺序传递千万别一时图方便调换。6. 一条龙试跑从生成到求解的完整演示为了让读到这里的朋友有一个直观的完整流程我贴一个整合脚本使用前文的函数省略重复实现完整跑通“生成一关 - 求解器验证 - 打印地图和解路径”。import random from collections import deque # 这里假设已经定义了 in_bounds, is_wall, is_deadlock, can_player_reach 等 # 省略以避免重复叙述 def generate_and_solve(rows10, cols10, holes10, max_steps40): # 初始化空地图 maze [[0 for _ in range(cols)] for _ in range(rows)] # 四周为墙 for r in range(rows): maze[r][0] 1 maze[r][cols-1] 1 for c in range(cols): maze[0][c] 1 maze[rows-1][c] 1 # 随机几个内部障碍不要堵死 for _ in range(holes): rr random.randint(1, rows-2) cc random.randint(1, cols-2) maze[rr][cc] 1 # 用洪水填充保证内部连通 # ... 略 ... # 随机放置目标点和箱子初始在同一点 goals set() while len(goals) 3: rr random.randint(1, rows-2) cc random.randint(1, cols-2) if maze[rr][cc] 0: goals.add((rr, cc)) boxes set(goals) # 初始箱子在目标上 player random.choice([(r,c) for r in range(1,rows-1) for c in range(1,cols-1) if (r,c) not in boxes and maze[r][c]0]) # 正向随机推箱子 max_steps 次 seq [] for _ in range(max_steps): res random_push(maze, player, boxes, goals) if res is None: break player, boxes, action res seq.append(action) # 此时 boxes 就是初始箱子位置seq 反向就是解 solution list(reversed(seq)) # 打印地图 display_maze(maze, player, boxes, goals) print(Solution:, .join(solution)) # 用BFS验证 sol2 bfs_solve(maze, player, boxes, goals) print(BFS solve length:, len(sol2) if sol2 else 无解)这里我把正向随机推箱子发下去了random_push的逻辑和前面逆向逻辑差不多区别是正向选择合法推法玩家先移动到箱子旁边再推。因为正向生成天然可解而且解法就是刚刚走过的动作序列所以在生成时其实不需要再跑求解器。但最终生成完还是推荐用求解器独立验证一次以防生成过程的随机动作序列里包含了“推完后玩家卡死无法进行下一步”的情况这种情况我们通过合法性检查已经避免但出现bug时验证能兜底。print解路径时U/D/L/R分别代表上下左右推箱步小写表示单纯移动。如果你有动画把这些动作喂给前端即可。7. 最后分享一个个人经验做这个项目最大的体会是推箱子这个游戏表面上是“搬运”本质上是“规划”。自动求解是经典的搜索问题关卡生成是“搜索的逆向使用”。两者相辅相成——求解器越高效生成器能验证和筛选的候选就越多最终得到的关卡质量也越高。如果你时间有限建议先做求解器因为它是整个项目的地基。等你熟悉了状态压缩、双向BFS、A*这些套路后再做生成器会顺很多。另外如果你打算把项目发布到社区或接成在线服务可以在网页上放一关“每日挑战”后端用生成器每日跑一批挑选一个满足分数区间的关卡然后用求解器算出最优解。这样玩家既能玩到新关还能看到“最少步数提示”互动感直接拉满。类似的扩展玩法比如“竞速模式”比谁步数少、“编辑模式”玩家自己摆关都是基于这个核心功能很自然的延伸。希望这篇分享能帮你把推箱子的两条主线打通。如果调试中遇到哪个环节始终跑不通试着把地图缩小到6x6先验证代码逻辑再慢慢放大规模。六格地图都跑不正确别急着上二十格。一步一步来比什么都重要。
1. 项目拆解自动求解与关卡生成到底在解决什么问题推箱子Sokoban这个游戏规则简单到一句话就能说清把箱子推到目标点上就算过关。但就是这么一个“简单”的游戏背后却藏着两道让开发者又爱又恨的难题——自动求解和关卡生成。我当年第一次接触这个项目时以为半天就能搞定结果硬生生折腾了两周。今天就把我的完整思路、踩过的坑、以及最终能跑通的方案一次性讲清楚。先说自动求解。推箱子本质上是状态空间搜索问题每一个“玩家位置 每个箱子的坐标”都构成一个状态玩家推一步状态就转移一次。理论上用广度优先搜索BFS就能找到最短解但实际跑起来你会发现状态数量爆炸得离谱。随便一个15x15的中等关卡状态数就能到百万甚至千万级别普通BFS根本扛不住。再说关卡生成。这玩意儿比求解更抽象。你要生成一个“有趣”的关卡意味着它必须是可解的、有挑战性的而且最好不是那种一眼望穿的直线推箱子。直接随机摆箱子很容易生成无解关卡所以主流的做法是逆向生成从一个简单的“已解决”状态出发反向推动作序列打乱箱子位置最后得到一个全新的初始布局。这个项目适合谁如果你是算法爱好者想练手搜索剪枝、状态压缩、判重优化自动求解部分能让你玩得很爽。如果你是游戏开发者想给自家游戏搞个无尽模式关卡生成部分就是你的刚需。哪怕你只是好奇“AI怎么玩推箱子”这篇文章也能让你理解其中的核心套路。2. 自动求解的设计思路从BFS到双向搜索再到启发式剪枝2.1 为什么普通BFS走不远一开始我天真地写了个标准BFS用字符串表示状态玩家坐标 所有箱子坐标拼接丢进队列里硬搜。很快发现两个致命问题状态膨胀中型关卡的状态数轻松破百万每个状态存一个字符串内存直接爆掉。无效搜索很多状态根本就是死胡同比如箱子被推到墙角但不在目标点上这种状态永远不可能解开但BFS不知道照样搜得乐此不疲。所以第一步优化是把状态编码压缩。我用整数数组代替字符串两个整数记录玩家位置行和列一串整数记录每个箱子位置。判重时用一个哈希集合存整数元组比字符串省好几倍内存。但光压缩不够你还需要剪枝。最简单的剪枝是“死局判定”如果某个箱子被推到了墙角两个相邻方向都是墙但该位置不是目标点直接丢弃这个状态。还有个更隐蔽的死局箱子贴墙滑动时如果滑动方向的下一格是墙且箱子不在目标点同样没救。这两个剪枝能砍掉大量无效分支实测搜索时间能缩短60%以上。2.2 双向BFS把搜索空间开根号当关卡规模上来后单向BFS依然力不从心。这时候我换成了双向BFS——从初始状态正向搜同时从目标状态所有箱子都在目标点反向搜两边轮流扩展直到中间相遇。为什么有效因为BFS的搜索空间随深度指数增长单向搜到深度d要遍历d层双向各搜d/2层总状态量大概是两倍的d/2层之和远小于单边的d层。用生活类比你从北京往上海走我从上海往北京走咱俩各走一半路比一个人从北京走完全程省力多了。实现双向BFS有个坑逆向搜索时“玩家推箱子”的逆操作不是“拉箱子”而是玩家从箱子周围走到一个合法空位并让箱子朝相反方向移动。具体说正向动作是“玩家在某方向推箱子”逆向动作就要判断当前箱子位置玩家站在它的反方向然后箱子移动到反方向的下一个位置玩家站到原来箱子的位置。逻辑容易绕晕建议画出状态转移图把正逆动作拆成独立的函数别混着写。双向BFS的相遇检查也很讲究。我是两个方向各维护一个visited集合每扩展一层就检查当前层的状态是否出现在对方的visited里。如果出现就说明找到了路径然后把两个方向的动作序列拼接起来。注意拼接时逆方向的序列要反过来因为那是从目标状态倒推回中间状态的。2.3 启发式搜索用A*把效率再拉一个档次双向BFS已经很能打了但遇到那种需要绕大远路的关卡它依然会搜出很多无意义的中间状态。我想既然都做了判重和剪枝不如直接上A*用启发函数引导搜索优先走“有希望”的方向。A的核心是估值函数 f(n) g(n) h(n)g是从起点到当前状态的实际步数h是当前状态到目标的估计代价。推箱子常用的启发函数是曼哈顿距离和每个箱子到最近目标点的曼哈顿距离之和。这玩意儿计算极快而且因为是松弛估计永远不会高估真实代价所以A一定能找到最优解。但我实测发现纯曼哈顿距离和太乐观了导致A搜索时还是撒开了跑。后来我加了一个改进考虑箱子之间的冲突。比如两个箱子挤在一起互相挡路实际代价会比各自距离相加高得多。这个改进做起来有点复杂简单点可以这样计算A的优先队列排序时在h里加一个惩罚项——如果有两个箱子的目标和曼哈顿路径重叠就在总和上加几份额外代价。别小看这个惩罚它能让A*在那种“箱子互相堵门”的关卡里少走很多弯路。还有个小技巧用“玩家到箱子的距离”修正h。因为推箱子之前玩家必须跑到箱子旁边。h里加上玩家到最近箱子的距离能加速前期搜索。修正方式h 箱子曼哈顿距离和 玩家到最近箱子距离。但注意这个修正只在特定实现下能保证admissible不超过真实代价如果你不想严格证明就把它当做一个“准A*”用也能接受。2.4 状态表示与去重的工程细节写到这里必须强调工程实现的重要性。算法再牛状态表示没做好照样卡死。我最终用的状态结构长这样# 状态表示示例 # 玩家位置: (pr, pc) # 箱子位置: 元组列表 [(r1, c1), (r2, c2), ...] # 为了判重将箱子坐标排序后拼接成元组 def state_key(player, boxes): sorted_boxes tuple(sorted(boxes)) return (player, sorted_boxes)排序是关键。因为同一组箱子坐标如果顺序不同判重时会被当成不同状态导致搜索空间虚增。我一开始没排序结果同一种局面至少被重复存了“箱子数量的阶乘”次。这种低级错误能让内存暴涨十几倍排查了半天才恍然大悟。另一个实用技巧是预计算“死锁区域”。在关卡加载时把那些格子标记为“如果箱子到达这里且不是目标点则必死”。这能进一步减少无效状态。死锁区域的判定方法对每个非目标点格子若它的上方和左方都是墙则标记为死角还有一种“贴墙死角”上方是墙且左方是墙或者上方是墙且右方是墙这种也很好判断。虽然这不能覆盖所有死局但实现简单收益很高。如果你用C写还能用bitset对关卡地板编码做位运算优化。用64位整数表示一行格子箱子位置用一个位标记这样状态可以压成几个64位整数哈希和比较都非常快。不过我是用Python写的原型图个省事后面的性能需求不极端的话也够用。3. 关卡生成的逆向思路先有解再添乱3.1 为什么不能直接随机摆放新手做关卡生成最容易掉进的坑就是随机放墙、随机放箱子、随机放目标点然后自己玩一下看看能不能解。结果99%的概率生成的是无解关卡或者过于简单、毫无趣味。因为随机摆放的箱子往往堵死了所有通路玩家根本没法把所有箱子推到目标点。更隐蔽的问题是“趣味性”难以量化。你可能随机到一个可解关但箱子全在起点附近几步就结束了这种关卡没有生成意义。所以我采用逆向生成法核心是从最终完成态开始反向走几步就得到一个可解的初始态。反向走的“步数”越大关卡越难因为箱子被推得越散、玩家需要绕的路越多。3.2 逆向生成的具体步骤初始化选定一个房间布局固定墙体和通道把所有箱子放在目标点上玩家安排在某个空地上。随机反向推箱子从当前状态出发随机选择一个箱子判断玩家能否走到它的“反向推动”位置。如果能就把箱子向某个合法方向挪动一格同时玩家的位置更新到原来箱子所在的位置。重复这个过程N次。清洗冗余记录下每一步的动作序列再把箱子位置“固定”为最终初始态。此时状态必然可解因为只要把动作序列正向执行一遍就能还原到目标态。添加挑战性为了让关卡不那么直白可以在已经生成的箱子位置附近增加一些装饰性墙体但要检查这些墙体是否破坏了可解性。这里有个参数特别关键反向移动的步数N。N太小时箱子几乎还在目标点附近太简单N太大箱子可能被推到一些极端角落导致解的空间极小甚至玩家第一步就没法动。我测试下来一个15x15的场地N在30-60之间比较稳。更大的场地可以把N调到80-120。反向移动还有一个限制箱子不能重叠不能推穿墙而且每次反向操作必须保证玩家原来的位置是合法的。这个合法性判断和正向求解完全一样只是方向反了。可以复用代码里的合法性检查函数注意正向和反向调用的语义差异。3.3 如何增加关卡“趣味性”光有可解还不够“好玩”才是目标。我的做法是设计一个难度评估函数维度包括箱子分散度统计各箱子位置到最近目标点的曼哈顿距离的方差。方差越大说明箱子分布越散玩家需要来回跑的次数越多难度越高。死锁风险度统计有多少箱子所在位置接近死锁区域但还没死锁。接近越多容错率越低关卡越刺激。干燥步数占比从初始态到目标态的最短解中“玩家推箱子的步数”与“玩家单纯走路的步数”之比。推箱子占比越低说明玩家花在绕路上的时间越多迷惑性越强。每次生成一批候选关卡按这些维度打分然后挑分数最符合你预期的那个作为最终产出。如果你想要一个“新手热身关”就把分散度和死锁风险调低想要“专家自虐关”就拉高。我自己的实践是先把N设为40生成100个候选跑一个求解器确定它们的最短解长度再筛选。如果最短解长度在80-150步之间通常是比较均衡的中等难度。3.4 墙体布局的生成策略逆向生成法其实对墙体布局要求不高你可以手动画一个模板也可以程序化生成。程序化生成我试过两种房间分割法类似“生成迷宫”的做法把场地分成若干小房间房间之间开连通门洞再把部分通道堵上形成回环。这种布局天然具备曲折感适合做中等以上难度关卡。随机障碍法在空地上随机放置一些实心块然后用遍历算法检查所有可达区域保证整个地图是连通且可达的。这个方法快但容易产生封闭小空间需要额外做可达性过滤。我推荐用房间分割法作为基底因为推箱子关卡本质上需要“行星际物流”般的感觉有多个子区域箱子需要在子区域之间搬运玩家在狭窄通道里反复转身操作。随机障碍法生成的开放空间太多推箱子缺少“卡位”乐趣。实现分割法时可以用一个二维数组表示地图0为空地1为墙。先用大块矩形划分再在矩形边界上开几个门洞门洞的位置尽量对称或错落有致。记得在门洞附近留足够空间否则玩家无法把箱子推过门洞。3.5 可解性验证不要盲目相信逆向法逆向生成法理论上保证可解但实际编码时经常出bug导致生成的关卡实际上不可解。比如反向推箱子时如果判断“玩家能否走到反向位置”的函数写错了可能把一个本来合法的状态转换成了非法状态最后生成一个伪可解的烂摊子。所以每次生成关卡后必须跑一遍自动求解器验证可解。如果不可解就丢弃重新生成。这里就体现自动求解器的另一重价值不是摆设是质量把关器。我甚至会把验证过的关卡连同它的最短解路径一起存起来。游戏里如果要加“提示”功能直接播放这个解路径就行一鱼两吃。验证效率也要注意。单关卡求解可能耗时所以生成一批后批量验证用多线程并发跑能省不少时间。我用Python的concurrent.futures开8个线程100个候选关卡几分钟内就能全部验证完。4. 实操记录从零搭一个可运行的求解器生成器4.1 项目结构和数据模型我建议把功能拆成这几个模块solver.py求解器、generator.py生成器、map.py地图数据模型、verify.py验证工具。如果以后要接入图形界面再加一个ui.py保持逻辑与渲染分离。地图数据模型用一个二维列表最直观。我用0表示空地,1表示墙,2表示目标点,3表示箱子,4表示玩家。不过如果你要频繁做状态转换直接维护两个集合更灵活一个boxes_set存箱子坐标一个player_pos存玩家坐标外加一个walls_set存墙坐标。地图大小用rows和cols记录。目标点可以从关卡配置里单独读出来存成goals_set。载入关卡时我会先做一次预处理把地图中有没有任何箱子一开始就压在目标点上如果有标记为“已完成箱子”再把所有目标点位置缓存到一个列表里方便后面算启发函数时快速取用。4.2 求解器的关键代码逻辑以下是我最终调通的自动求解器的简化核心代码Pythonfrom collections import deque import heapq def is_wall(maze, r, c): return maze[r][c] 1 def in_bounds(maze, r, c): return 0 r len(maze) and 0 c len(maze[0]) def is_box_at(boxes, r, c): return (r, c) in boxes def is_deadlock(maze, r, c, goals): if (r, c) in goals: return False # 简单死锁两个正交方向都是墙或者一个方向是墙且另一个方向是不可推的角落 up is_wall(maze, r-1, c) down is_wall(maze, r1, c) left is_wall(maze, r, c-1) right is_wall(maze, r, c1) if (up and left) or (up and right) or (down and left) or (down and right): return True return False def bfs_solve(maze, player_pos, boxes, goals): # 状态定义: (player_pos, tuple(sorted(boxes))) initial_boxes tuple(sorted(boxes)) start (player_pos, initial_boxes) if all(b in goals for b in boxes): return [] # 已经解决 q deque([start]) visited {start} parent {start: None} action {} while q: (p, b), path_len q.popleft(), 0 # 实际要记录长度可以用字典 # 为了简洁此处只写思路完整版需要记录步数 # 遍历四个方向 for dr, dc, act in [(-1,0,U),(1,0,D),(0,-1,L),(0,1,R)]: np (p[0]dr, p[1]dc) if not in_bounds(maze, *np) or is_wall(maze, *np): continue if (np[0], np[1]) in b: # 要推箱子 nb_pos (np[0]dr, np[1]dc) if not in_bounds(maze, *nb_pos) or is_wall(maze, *nb_pos): continue if is_box_at(b, *nb_pos): # 箱子的位置已经有箱子 continue # 新箱子集合 b_list list(b) b_list.remove((np[0], np[1])) b_list.append((nb_pos[0], nb_pos[1])) new_b tuple(sorted(b_list)) new_p (np[0], np[1]) # 玩家移到原来箱子位置 else: new_b b new_p np new_state (new_p, new_b) if new_state not in visited: visited.add(new_state) parent[new_state] (p, b) action[new_state] act if all(pos in goals for pos in new_b): # 反向回溯路径 seq [] cur new_state while parent[cur] is not None: seq.append(action[cur]) cur parent[cur] seq.reverse() return seq q.append(new_state) return None # 无解以上代码省略了父节点记录长度等细节真实运行需要把path_len也存起来否则BFS这里没问题但A就得用优先级队列了。A版本的核心是优先级(g h, g, state)def heuristic(boxes, goals): total 0 used_goals set() for box in boxes: best min(manhattan(box, g) for g in goals if g not in used_goals) # 简单处理允许重复用同一目标或者做匹配 total best # 如果要严格可以做二分图最小匹配开销大但更准 return total def astar_solve(maze, player_pos, boxes, goals): start (player_pos, tuple(sorted(boxes))) open_heap [(0, 0, start)] g_score {start: 0} parent {start: None} action {} while open_heap: f, g, state heapq.heappop(open_heap) p, b state if all(pos in goals for pos in b): # 回溯 ... for dr, dc, act in [(-1,0,U),(1,0,D),(0,-1,L),(0,1,R)]: # 逻辑与BFS相同只是将 g1 和 heuristic 计算出f ...实际工程中这里需要注意**heuristic的合法性**箱子到目标的曼哈顿距离之和前提是每个目标点都被一个箱子占用而曼哈顿距离允许箱子穿过别的箱子所以没问题因为穿过别的箱子在实际中可能需要额外代价故h只会低估不会高估。但如果你加入“箱子互相冲突”的惩罚就要额外小心不能完全保证h真实代价。如果只是求“任意路径而不一定最优”那倒是无所谓。另一个工程细节BFS时我用parent和action两个字典记录前驱状态和动作回溯时先走到None再反转列表。务必在push进队列时同步记录别等弹出时再找因为状态可能已经被更优路径更新了。4.3 生成器的核心代码逻辑生成器需要复用求解器里的合法性判断。我实现一个random_walk_back()函数import random def reverse_move(maze, player_pos, boxes, goals): # 随机选择一个箱子 box random.choice(list(boxes)) # 四个方向箱子反向移动即玩家站在箱子的反方向位置 dirs [(-1,0),(1,0),(0,-1),(0,1)] random.shuffle(dirs) for dr, dc in dirs: player_stand (box[0] - dr, box[1] - dc) # 玩家要站的位置 new_box_pos (box[0] dr, box[1] dc) # 箱子被推后的新位置 # 检查玩家站的位置合法且能到达不考虑箱子因为玩家是走过去的 if not in_bounds(maze, *player_stand) or is_wall(maze, *player_stand): continue if player_stand in boxes: continue # 检查新箱子位置合法且不与别的箱子重叠 if not in_bounds(maze, *new_box_pos) or is_wall(maze, *new_box_pos): continue if new_box_pos in boxes: continue # 检查玩家是否能从当前位置走到 player_stand 不能被箱子挡住 # 这里要跑一个BFS无障碍物但箱子算障碍 if can_player_reach(maze, player_pos, player_stand, set(boxes) - {box}): # 执行移动 new_boxes set(boxes) new_boxes.remove(box) new_boxes.add(new_box_pos) new_player (box[0], box[1]) # 原来箱子位置变成玩家位置因为反向推箱子等价于玩家从反方向把箱子推开 # 但注意玩家从 player_stand 推箱子到 new_box_pos所以操作后玩家站在 box 位置箱子在 new_box_pos # 嗯这里需要仔细想... return new_player, new_boxes return None等等上面这个函数我卡了一个逻辑问题反向推箱子应该理解为“正向推箱子的逆操作”。正向是玩家从P位置推动箱子从B到B玩家最终站在B处。逆操作就是玩家站在B处箱子在B处要将箱子从B推回到B然后玩家回到P处。所以逆操作的输入是当前玩家位置P、当前箱子集合包括B我们要找到原来的B和P。换个更清晰的写法随机选一个箱子它的当前位置记为B。然后我们想把箱子挪到它旁边的空位置BB需要满足B不是墙且B在B的某个方向上。同时玩家必须能够从当前位置走到B的反方向位置P即 从B朝着B的方向继续往前走一格的位置即P 2*B - B并且P不能是墙、不能是箱子。这里“玩家必须能走到P”但注意P可能被其他箱子挡路实际上反向推箱子时玩家是从P往B方向推箱子但在逆操作时刻玩家的当前位置是某个地方需要能走到P。我直接用BFS检测玩家从当前pos到P的可达性障碍是除当前箱外的所有箱子。例如当前箱子位置B(3,3)想把它挪回B(2,3)方向是“北”-1,0那么玩家要站在P(1,3)即B向B方向再前进一格即B再往北一格正向推箱子玩家在P(1,3)推箱子从B(2,3)到B(3,3)最后玩家站在B(2,3)逆操作玩家从P走到(1,3)把箱子从B推回B(2,3)最后玩家站在(2,3)如果B是目标点都没关系因为我们在生成时目标点只是地板标记。修正后的reverse_move逻辑def reverse_move(maze, player_pos, boxes, goals): box_list list(boxes) random.shuffle(box_list) for box in box_list: dirs [(-1,0),(1,0),(0,-1),(0,1)] random.shuffle(dirs) for dr, dc in dirs: # B box (dr,dc) 其实我们要推的“原位置B”应该在box的反方向 # 写清楚当前箱子在 B。我们希望箱子被推回去到 B box - (dr, dc) 还是 box ...? # 设想正向推箱子动作玩家在P推动箱子从B到B方向为(dr,dc)那么 B B (dr,dc)P B - (dr,dc)。 # 因此已知 B给定(dr,dc)则 B B - (dr,dc)P B - 2*(dr,dc)。 # 但要注意 dr,dc 是箱子移动方向即正向推的方向。 # 所以 B_prime box B (B_prime[0] - dr, B_prime[1] - dc) P (B_prime[0] - 2*dr, B_prime[1] - 2*dc) if not in_bounds(maze, *B) or is_wall(maze, *B): continue if B in boxes: continue if not in_bounds(maze, *P) or is_wall(maze, *P): continue if P in boxes: continue if can_player_reach(maze, player_pos, P, set(boxes) - {B_prime}): # 执行反向操作箱子从B移到B玩家从当前pos走到P然后推箱子到B最终玩家站到B # 简化直接返回新玩家位置为B因为操作后玩家确实站在原B处 new_boxes set(boxes) new_boxes.remove(B_prime) new_boxes.add(B) return B, frozenset(new_boxes) return None这里用frozenset做返回以便哈希。但注意can_player_reach中的障碍物要排除B_prime这个箱子因为玩家需要用身体贴着它路径上可能穿过它原来的位置不路径不能穿过箱子所以障碍物是boxes - {B_prime}加上墙。BFS时标记墙就是墙标记障碍物集合用于排除。如果你觉得反向生成写得绕推荐另一种更简单的实现正向随机推箱子。就是随机选一个箱子从当前状态初始箱子全在目标点随机执行合法正向推法推N步。推完后的状态就是初始关卡而合法动作序列就是解。这个思路更直观不容易出错。虽然生成的关卡难度分布可能不如逆向好调但可以先跑通再优化。正向随机推需要保证每步都能推得动箱子而且箱子不能推出边界或压墙另外别忘了检查玩家能否走到箱子推位。代码写起来更直接。我后来项目里就换成了正向版本更加省心。4.4 难度的量化与自动筛选生成一批候选后用求解器算出最短解的长度、箱子移动次数、玩家移动次数。我总结了一个可用的难度评分打个比方解的总步数在60-100之间简单100-160中等160-250困难250以上专家级但仅看步数不够还需要看“操作密度”。比如箱子移动次数占总步数的比例如果太低说明玩家大部分时间在走空路关卡显得绕且拖沓。一般这个比例在30%-50%比较合适。太高则说明关卡太直白就是个推箱子接力赛。我筛选时还设计了一个“回环度”检测统计最短路中玩家访问的格子坐标去重后的数量。如果数量小于总步数的60%说明玩家一直在重复走回头路这种关卡玩起来容易烦躁反之则说明路线丰富更耐玩。当然这个指标存在例外但作为自动筛选的“批量化指标”很有效。如果你不需要生成专家级折磨人关卡用简单规则筛选就够所有生成的关卡先验算得分分数在区间内就保留再多跑几个候选挑最好。4.5 与游戏前端的对接做完求解器和生成器之后我把它接到了一个简单的HTML5 Canvas前端里。基本思路是后端Python生成关卡后输出一个JSON对象包含地图网格、玩家初始位置、箱子位置、目标点位置。前端读取JSON渲染画面监听键盘事件玩家可以用方向键推箱子。求解器暴露一个API接口输入关卡JSON输出解序列前端拿到后按序列播放动画作为“提示”功能。这种前后端分离的好处是求解算法和渲染逻辑完全解耦。如果你只是做算法研究不接前端也无所谓但如果做游戏这个接口设计很实用。在实际对接中要注意坐标统一。我后端用的二维数组坐标row, col前端Canvas用的是像素坐标换算时务必写好转换函数。另外状态同步要小心前端每移动一步都要用后端同样的数据结构维护玩家位置和箱子列表不然“提示”回放就会错乱。5. 常见问题与排查技巧实录这一节是血泪总结希望你少踩我踩过的坑。5.1 求解器跑不出解还死循环最常见的原因是状态空间太大导致BFS超时。解决思路优先优化判重数据结构。用集合加上高效的哈希。开启剪枝死锁判定我实测能减少70%状态。换双向BFS或A*。如果依然跑不出来你就要检查地图里是否存在不可达区域。比如用填充算法Flood Fill检查玩家能否到达所有箱子。如果箱子在一个孤立区域而玩家根本进不去那这关本来就无解求解器再怎么优化都不可能得出路径。这种情况在测试地图前先用连通性验证过滤掉。5.2 生成器产出的关卡一眼就能看出“模板味”这个问题几乎必然出现。因为逆向生成的初始状态是从目标态随机反向推出来的而反向推移的路径往往带有某种“螺旋”特征。解决方法多做几次随机重排把玩家位置在最后再随机放置到一个非箱子非墙的空位。把初始的目标点集合也随机变换一下比如原来目标点在左侧生成后可以整体镜像、旋转增加多样性。加一些“噪音”在空闲区域随机加墙或空出空地但要保证连通性。如果你要生成大量关卡建议先跑一批人工看几关总结模式再调整随机种子策略。5.3 用BFS判可达性时忽略玩家碰撞这个坑很隐蔽。can_player_reach函数判断玩家能否从A点走到B点时我把所有箱子都当作障碍物这没问题。但有时候玩家要走到箱子旁边才能推箱此时路径不能穿过箱子而B点恰好在箱子旁BFS会认为合法。这没问题。问题在于当你要推某个箱子时玩家初始位置可能在箱子的另一侧路径需要绕到推位但如果绕不过去这一步就不该执行。现实中如果箱子挡住了唯一的通道玩家就无法从另一侧绕过去。我在can_player_reach里把正在推的箱子排除在障碍之外结果路径可能“穿过”该箱子。千万不能排除必须始终把箱子当障碍。我因为这个bug浪费了半天时间生成的关卡要么不可解要么解出来是歪的。5.4 死锁检测的误杀前面说的简单死锁判定是“任何箱子在墙角和另一方向也是墙且不在目标点”但有些看似死锁的位置其实可以通过“先推别的箱子”解锁。比如两个箱子紧挨着靠墙一个被判定死锁但另一个一旦推开这个箱子就能被推走了。我的简单判定只判断单箱紧贴双墙不会把这种情况误杀反而漏杀了“箱子贴墙但不是紧贴墙角”的真实死锁。更准确的做法是跑一个动态死锁检测从当前状态用BFS搜索看是否存在某个箱子能被推到目标点。但这成本太高不能每状态都调。所以我的妥协方案普通搜索只用简单死锁生成的关卡最终会用全量求解器验证。如果验证时无解说明死锁检测漏了但至少不会把可解关卡误判为无解。宁可多搜一些状态也不冒险剪枝剪掉正解。5.5 内存溢出与Python性能Python跑10x10的关卡没啥压力但20x20的大地图就可能吃紧。我用的优化状态集合用set存储元组并且元组里的箱子列表是排序后的tuple。用lru_cache缓存can_player_reach的局部可达性结果不行因为障碍物变化了不能直接缓存。将墙体、箱子分别用整数位掩码表示用frozenset存箱子集合哈希速度更快。如果追求极致性能还是建议用C重写核心求解器。Python适合做原型验证C适合在游戏里实际跑。我后来用C重写了一遍速度提升一个数量级以上。5.6 接口层坐标不一致这是个低级但高频的问题。前端用(x,y)表示横纵后端用(row,col)很容易搞混。我建议在项目最早期就在数据模型里统一坐标命名规则比如永远用(row, col)并在前端转换器中写清楚row对应ycol对应x。所有函数参数都按这个顺序传递千万别一时图方便调换。6. 一条龙试跑从生成到求解的完整演示为了让读到这里的朋友有一个直观的完整流程我贴一个整合脚本使用前文的函数省略重复实现完整跑通“生成一关 - 求解器验证 - 打印地图和解路径”。import random from collections import deque # 这里假设已经定义了 in_bounds, is_wall, is_deadlock, can_player_reach 等 # 省略以避免重复叙述 def generate_and_solve(rows10, cols10, holes10, max_steps40): # 初始化空地图 maze [[0 for _ in range(cols)] for _ in range(rows)] # 四周为墙 for r in range(rows): maze[r][0] 1 maze[r][cols-1] 1 for c in range(cols): maze[0][c] 1 maze[rows-1][c] 1 # 随机几个内部障碍不要堵死 for _ in range(holes): rr random.randint(1, rows-2) cc random.randint(1, cols-2) maze[rr][cc] 1 # 用洪水填充保证内部连通 # ... 略 ... # 随机放置目标点和箱子初始在同一点 goals set() while len(goals) 3: rr random.randint(1, rows-2) cc random.randint(1, cols-2) if maze[rr][cc] 0: goals.add((rr, cc)) boxes set(goals) # 初始箱子在目标上 player random.choice([(r,c) for r in range(1,rows-1) for c in range(1,cols-1) if (r,c) not in boxes and maze[r][c]0]) # 正向随机推箱子 max_steps 次 seq [] for _ in range(max_steps): res random_push(maze, player, boxes, goals) if res is None: break player, boxes, action res seq.append(action) # 此时 boxes 就是初始箱子位置seq 反向就是解 solution list(reversed(seq)) # 打印地图 display_maze(maze, player, boxes, goals) print(Solution:, .join(solution)) # 用BFS验证 sol2 bfs_solve(maze, player, boxes, goals) print(BFS solve length:, len(sol2) if sol2 else 无解)这里我把正向随机推箱子发下去了random_push的逻辑和前面逆向逻辑差不多区别是正向选择合法推法玩家先移动到箱子旁边再推。因为正向生成天然可解而且解法就是刚刚走过的动作序列所以在生成时其实不需要再跑求解器。但最终生成完还是推荐用求解器独立验证一次以防生成过程的随机动作序列里包含了“推完后玩家卡死无法进行下一步”的情况这种情况我们通过合法性检查已经避免但出现bug时验证能兜底。print解路径时U/D/L/R分别代表上下左右推箱步小写表示单纯移动。如果你有动画把这些动作喂给前端即可。7. 最后分享一个个人经验做这个项目最大的体会是推箱子这个游戏表面上是“搬运”本质上是“规划”。自动求解是经典的搜索问题关卡生成是“搜索的逆向使用”。两者相辅相成——求解器越高效生成器能验证和筛选的候选就越多最终得到的关卡质量也越高。如果你时间有限建议先做求解器因为它是整个项目的地基。等你熟悉了状态压缩、双向BFS、A*这些套路后再做生成器会顺很多。另外如果你打算把项目发布到社区或接成在线服务可以在网页上放一关“每日挑战”后端用生成器每日跑一批挑选一个满足分数区间的关卡然后用求解器算出最优解。这样玩家既能玩到新关还能看到“最少步数提示”互动感直接拉满。类似的扩展玩法比如“竞速模式”比谁步数少、“编辑模式”玩家自己摆关都是基于这个核心功能很自然的延伸。希望这篇分享能帮你把推箱子的两条主线打通。如果调试中遇到哪个环节始终跑不通试着把地图缩小到6x6先验证代码逻辑再慢慢放大规模。六格地图都跑不正确别急着上二十格。一步一步来比什么都重要。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
