1. 项目概述当游戏AI不止一个“人”在走路做游戏AI尤其是涉及到单位移动的新手和老手之间最大的分水岭往往不是会不会写A*算法而是当屏幕上同时有几十、上百个单位需要移动并且它们之间不能“穿模”、不能卡死、还得看起来有点智能的时候你该怎么办。这个问题在《吃豆人》里是四个颜色各异的幽灵如何围追堵截玩家在《星际争霸》或《帝国时代》里是一队士兵如何保持阵型穿过狭窄的峡谷在《文明》里是你的大军如何有条不紊地开赴前线。这就是多智能体路径规划Multi-Agent Path Finding, MAPF要解决的核心问题。它不再是给单个角色找一条从A到B的最短路径那么简单而是要为一群有各自起点和终点的智能体在共享的、有障碍物的地图上规划出一组无碰撞、且整体上“最优”的路径。这个“最优”可以是总移动步数最少、总完成时间最短或者像在RTS游戏里更看重队形的保持和调度的流畅性。我最初接触这个问题是在尝试复刻一个简化版的《吃豆人》时。给单个幽灵写个A追着玩家跑很简单但四个幽灵一放进去问题就来了它们经常在转角处挤成一团或者为了追玩家而互相堵死路口看起来蠢得不行。后来做RTS类的原型问题更严重框选一队单位点一个目标点它们要么挤成一坨“叠罗汉”过去要么在狭窄路口发生“交通瘫痪”半天动弹不得。这些体验让我意识到单体的A只是“能走”多体的MAPF才是“会走”。网络上常说的“贪吃蛇寻路”其实也是一个非常形象的MAPF问题——蛇身每一个节都是一位智能体它们的路径必须首尾相连且不能自交。而“ai翻译.json怎么装进游戏里”这种热词虽然看似不相关但它背后反映的是开发者希望将外部AI模型可能就定义在json配置里集成到游戏逻辑中的普遍需求MAPF算法作为游戏AI的核心模块之一其选型和集成正是这种需求的典型场景。至于“串口rts是什么意思”那是硬件通信里的流控制信号和我们说的即时战略游戏RTS纯属同名巧合但也提醒我们在技术领域明确语境和定义是多么重要。所以这篇内容我想抛开那些复杂的数学证明和论文术语就从一个游戏开发者的实战视角聊聊当我们从“一个单位寻路”进阶到“一群单位调度”时手头有哪些MAPF算法可以选它们各自适合什么场景以及在实际项目中怎么把它们“装进”游戏里并调出能用的效果。2. MAPF核心思路与方案选型没有银弹只有权衡面对MAPF问题第一反应可能是“我给每个单位独立跑一遍A*不就行了” 这确实是基线方案我们称之为“独立规划”Independent Planning。但这样做的后果就是碰撞满天飞。于是所有MAPF算法本质上都在做一件事在独立规划的基础上引入不同形式和程度的“协调”Coordination以避免碰撞。协调的代价通常是计算复杂度的飙升。MAPF已被证明是NP-Hard问题意味着随着智能体数量增加找到最优解的计算时间会爆炸式增长。因此所有实战算法都是在解的质量最优性和计算速度之间寻找平衡。根据协调的时机和方式主流算法可以分成几大类。2.1 基于冲突的搜索CBS为完美方案买单CBSConflict-Based Search是学术界目前最主流的“最优”MAPF求解器框架之一。它的思想很直观先让所有智能体独立规划出最短路径底层搜索如A*。然后检查这些路径之间是否有冲突比如在同一时间走到同一格子。如果发现冲突就通过“增加约束”来化解——比如要求智能体A在时间t不能位于格子G。这个约束会生成新的搜索节点算法在这个高层搜索树上不断寻找一个无冲突的解决方案。为什么选择CBS因为它能保证找到最优解在设定的成本函数下如总时间。这对于一些对公平性、绝对效率要求极高的场景比如仓库机器人调度是至关重要的。在游戏中如果你需要为一段关键的剧情动画或电影运镜规划绝对精确、无任何穿帮的群体移动CBS是可靠的选择。它的代价是什么速度。智能体数量稍多比如超过20个地图稍复杂求解时间就可能从毫秒级跳到秒级甚至分钟级完全无法满足游戏实时性的要求通常要求每帧在几毫秒内完成。因此在快节奏的RTS游戏中直接使用标准CBS通常是不现实的。注意不要被“最优”二字迷惑。游戏中的“最优”往往是主观的、符合玩家预期的“好看”和“流畅”而非数学上的绝对最短时间。为后者付出的计算成本在游戏中常常是不值得的。2.2 基于优先级的规划PBS快节奏游戏的实用之选PBSPriority-Based Search代表了另一大类思路降低最优性要求换取速度的大幅提升。它的核心是为智能体分配一个固定的移动优先级。规划时从优先级最高的智能体开始为它规划一条避开所有障碍物的路径。然后优先级次高的智能体在规划时必须把高优先级智能体的路径视为“临时移动障碍物”来避开。以此类推直到所有智能体完成规划。为什么在游戏中PBS更常见因为它的速度极快。规划过程几乎是线性的智能体数量增加计算时间也基本线性增加。对于需要每帧或每几帧就重新规划一次路径的RTS游戏来说这种效率是救命稻草。虽然它放弃了全局最优解低优先级单位可能会绕远路但结果在视觉上通常是可接受的——就像现实中领导先走员工让路虽然整体不是最快但秩序井然。实战中的变种单纯的PBS结果可能不够好。因此实战中常引入“窗口式”规划Windowed PBS或“动态优先级”。例如只规划未来几秒内的路径然后滚动执行或者根据单位类型骑兵优先于步兵、状态受伤单位优先撤退动态调整优先级。这都是在PBS框架内用可控的复杂度换取更好的效果。2.3 联合状态A*Joint-State A*小规模精确控制的利器这是最“暴力”也最直观的方法把N个智能体的状态组合成一个“超级状态”比如每个智能体的位置合起来作为一个元组在这个维度极高的状态空间里进行A*搜索。搜索的目标是让这个“超级状态”从所有智能体的起点组合移动到终点组合。什么时候会用当智能体数量非常少通常2-4个且它们之间的协作要求极度精确时。一个经典例子就是《吃豆人》的四个幽灵。虽然看起来是四个独立单位但高级的AI会让它们表现出协作行为一个正面追击一个侧翼包抄两个在远处预判拦截。这种带有策略性的包围可以通过为幽灵们设计一个联合目标如“形成包围圈”然后用简化的联合状态搜索来规划初期的走位来实现。当然全程使用联合搜索计算量太大但用于关键决策点是可行的。它的局限性状态空间随智能体数量指数级膨胀。2个智能体在10x10地图上联合状态空间是100*100100003个智能体就是100万。这决定了它只能用于极小规模的“精英小队”AI。2.4 基于规则与势场的混合方法工业界的黑魔法在大量商业RTS游戏中你很少会看到纯粹的学术MAPF算法。更多是一种高度特化、基于规则的混合系统。其中“势场法”Potential Fields是重要的组成部分。每个单位同时受多种“势场”影响目标点的“引力场”、障碍物和其他单位的“斥力场”、维持队形的“对齐场”。单位每帧的移动方向就是这些力场的向量叠加结果。这天然避免了碰撞因为靠太近时斥力会剧增并能涌现出流畅的群体运动像鸟群或鱼群。为什么它有效因为它本质上是分布式的、无中心的计算。每个单位只根据自己局部感知的信息周围的单位和障碍独立决定移动计算开销小且非常适合并行。当一群单位移动时看起来就像有智能的流体。它的坑在哪里势场法很容易陷入局部最优导致单位在复杂地形中“抖动”或卡住。比如两个单位在狭窄门洞前互相排斥谁都进不去。因此工业级实现一定会混入其他技术用A*或流场Flow Field规划一条宏观的“建议路径”作为主导引力当检测到卡顿时临时启用一个轻量级的、基于规则的解耦逻辑例如让其中一个单位短暂“停下”或“后退一步”对于队形则可能采用“锚点”法先为整个队伍规划一个队长路径其他单位相对队长保持偏移位置。下表对比了这几种核心思路的典型特征方便你根据项目需求快速筛选算法思路典型代表解的质量计算速度适用场景游戏中的常见形态全局最优搜索CBS, Joint-State A*最优(理论保证)慢(指数/高阶增长)小规模精确调度、离线计算、回合制策略剧情动画路径预计算、回合制游戏单位移动优先级协调PBS, Windowed PBS次优(依赖优先级)快(近线性增长)实时战略游戏RTS单位集群移动RTS中框选部队的移动、MOBA中小兵推进局部反应式势场法, 流场避障涌现性(无全局保证)极快(每帧本地计算)大规模群体移动、群体模拟人群、鸟群RTS中极大规模混战、模拟经营游戏中的市民流动混合架构A*宏观路径 势场局部避障实用性好快(分层处理)绝大多数商业RTS、MMO游戏《星际争霸2》、《全面战争》系列的单位移动系统选型的关键在于问自己几个问题你的游戏是实时还是回合制同时移动的单位通常有多少几个、几十个、几百个玩家对路径“最优”的容忍度有多高是否允许少量绕路你的性能预算是每帧多少毫秒回答完这些合适的技术象限就清晰了。3. 实战拆解一为《吃豆人》幽灵注入协作灵魂让我们从一个相对简单的例子开始。吃豆人的四个幽灵Blinky, Pinky, Inky, Clyde是游戏史上最经典的AI角色之一。它们的原始行为模式其实规则简单每个幽灵有一个固定的主导策略追击、预判、巡逻、随机并会在“追击”和“散布”模式间切换。但这已经蕴含了MAPF的雏形避免四个幽灵完全重叠在一起那样对玩家没有威胁。第一步基础移动与碰撞避免首先每个幽灵都需要一个最基础的寻路能力。这里使用A完全足够地图不大目标明确玩家位置或某个散点目标。但直接让四个幽灵独立A必然撞车。所以我们需要一个最简单的协调机制每帧为幽灵分配唯一的移动优先级。例如按照Blinky, Pinky, Inky, Clyde的顺序。在当前帧Blinky先根据A结果移动到一个相邻格子。然后Pinky规划时如果它的A首选格子被Blinky这帧占用了它就选择次优格子。以此类推。这本质上是一个每帧执行的、极简版的PBS。第二步引入策略性行为联合目标原始游戏的幽灵AI不仅仅是避碰。Inky蓝色幽灵的行为是“镜像预判”它需要参考Blinky红色幽灵和玩家的位置。这就可以看作一个微型的联合规划问题。我们可以这样实现计算Blinky到玩家的向量。将这个向量从玩家位置反向延长一倍得到Inky的“预判目标点”。为Inky规划通往该目标点的路径。 这里的关键是Inky的目标是动态的、依赖于另一个智能体Blinky的状态。在规划Inky的路径时我们需要把Blinky未来几帧的预测路径也作为临时障碍物考虑进去避免Inky和Blinky跑成一条线。这就引入了基于时间窗口的轻量级联合思考。第三步模式切换与全局协调当吃豆人吃掉能量豆幽灵会进入“恐惧”模式四散逃回巢穴。此时它们的目标从“追击玩家”突然变为“逃回地图中央的复活点”。这是一个所有智能体目标同时发生剧烈变化的MAPF场景极易在巢穴入口造成死锁。 一个实用的解决方法是在切换模式的瞬间为所有幽灵重新计算一次路径并强制赋予它们返回巢穴的路径一个“高优先级通道”。具体来说可以临时修改地图的代价让通往巢穴的路径代价显著降低或者更粗暴地在极短时间内比如0.5秒允许幽灵之间发生“穿透”忽略碰撞让它们能快速通过瓶颈区域。虽然不真实但保证了游戏流程的顺畅玩家也几乎不会察觉。实操心得在吃豆人这类游戏中幽灵的“智能”不在于找到数学上的最优包围路径而在于通过简单规则组合出令玩家感到有压力、有变化的行为。MAPF在这里的作用更多的是确保这些行为规则能流畅执行不因碰撞而显得愚蠢。因此采用非常轻量级的、基于规则和优先级的协调就足够了切忌过度设计。4. 实战拆解二RTS大规模单位调度的工程实现RTS的单位调度是MAPF问题的重灾区。玩家框选50个步兵点击地图另一端他们期望看到的是部队保持大致队形、高效地通过复杂地形而不是一团乱麻。下面是一个可落地的分层实现方案。4.1 层级一群体宏观路径规划Flow Field当玩家下达移动指令时首先不为每个单位单独计算A路径。想象一下50个单位同时计算A的CPU开销。取而代之的是计算一次流场。以目标点或目标区域中心为源头使用类似Dijkstra的算法计算地图上每个格子到达目标点的代价。对于每个格子其移动方向就是指向周围8个邻居中代价最小的那个方向。最终生成一个覆盖全地图的方向向量场。 这个计算过程可能比单个A*慢但只做一次所有前往该目标区域的单位都可以共享这个流场。单位只需每帧查询自己所在格子的方向向量就能知道该往哪走。这解决了宏观路径导向问题效率极高。4.2 层级二局部碰撞避免与队形保持局部势场规则单位按照流场方向移动时碰撞避免和队形保持由本地每帧计算处理。斥力场每个单位都会向周围一定半径内的其他友军单位和障碍物施加一个斥力。斥力大小与距离成反比。单位最终受到的合力 流场方向引力 所有斥力的向量和。这能自然让单位散开避免堆积。队形锚点对于需要保持队形的移动如步兵方阵我们不在每个单位身上计算复杂的相对位置。而是为整个群体虚拟一个“队长”或“锚点”。这个锚点严格按照流场移动。其他单位的目标位置是相对于这个锚点的一个固定偏移比如在3x3网格中自己的位置。每个单位使用一个轻量的A*或转向行为如Seek朝自己的目标位置移动同时叠加上述的局部斥力场来避免与队友碰撞。这样队形在开阔地能保持在狭窄处能自然变形通过再通过时又能恢复。4.3 层级三死锁检测与解决轻量级PBS/规则仲裁即使有了势场在极端地形如狭窄桥梁、门口仍可能发生死锁几个单位互相卡住斥力让它们都无法前进。这时需要第三层“仲裁器”。死锁检测非常简单如果一个单位的速度连续若干帧接近零且其目标方向上有其他友军单位则判定为可能死锁。死锁解决触发一个轻量级的协调逻辑。例如临时优先级让卡住的单位中随机一个获得高优先级在接下来几帧内其他单位对它“主动避让”即临时增强它对其他单位的斥力或减弱其他单位的斥力。短暂停滞让其中一个单位完全停止1-2秒放其他单位通过。局部重新规划为卡住的这个小群体在一个很小的范围内比如5x5运行一个极简的、2-3个智能体的PBS快速规划出一个解耦顺序。 这个仲裁器不需要经常运行只在检测到问题时激活因此开销可控。4.4 性能优化关键点空间划分计算斥力时不要遍历所有友军单位。使用空间划分结构如网格Spatial Grid或四叉树只查询相邻单元格内的单位。更新频率流场不需要每帧计算只有在目标点改变或地形发生重大变化如建筑被摧毁时才重新计算。局部势场和队形调整每帧进行。死锁检测可以每5-10帧进行一次。分级细节LOD对于远离屏幕中心或数量极大的单位群可以降低其避障和队形计算的精度甚至关闭避障采用更简单的“粘附”移动直到它们进入关键视野区域。踩坑记录早期实现时我曾尝试为每个RTS单位都做完整的A*寻路加CBS协调结果在单位数量超过20时帧率就暴跌。后来转向流场局部势场的混合模型同一台机器上能流畅支持超过200个单位的混合移动。最大的教训是在游戏里“看起来正确”远比“数学上最优”重要而效率是“看起来正确”的前提。5. 算法集成与参数调优把“AI”装进游戏里理解了算法下一步就是如何将它集成到游戏引擎中并调出好效果。这个过程就像调试游戏手感需要反复微调。5.1 数据结构与接口设计首先你需要一个管理所有移动单位的MovementSystem。每个单位有一个MovementAgent组件包含位置、速度、目标等状态。MovementSystem每帧更新其工作流程如下收集指令接收来自玩家或AI的移动命令更新群体的目标流场。分层更新更新流场低频。为每个活跃单位计算局部合力流场引力 友军/障碍斥力 队形偏移力。执行死锁检测与解决低频。应用移动根据合力计算新的速度和位置并处理与地图碰撞体的物理交互如果有的化。关键是如何将算法模块化。例如将流场生成器、势场计算器、队形管理器、仲裁器都设计成可插拔的模块。这样你可以为不同的单位类型配置不同的移动“套餐”。比如农民单位可能只需要流场基础斥力而精锐步兵则需要全套的流场势场队形仲裁。5.2 核心参数调优指南MAPF在游戏中的效果很大程度上取决于一堆“魔法数字”参数。以下是一些关键的调试点参数影响调优建议斥力半径单位开始互相排斥的距离。太小会碰撞太大会让队伍过于松散。通常设为单位碰撞半径的2-3倍。对于大型单位如坦克需要更大。斥力强度排斥力的力度。与单位质量或权重相关。需要与流场引力和最大速度平衡。强度太大会导致单位抖动太小无法避免碰撞。从1.0开始调试观察单位通过狭窄通道的行为。流场引力系数单位朝向目标方向的意愿强度。通常设为1.0。在复杂地形中可以临时调高以帮助单位“冲过”拥挤区域。最大速度 / 力单位每帧能改变的速度上限。限制合力的大小使移动更平滑避免单位像弹珠一样被弹飞。死锁检测阈值速度低于此值多少帧触发死锁检测。例如速度 0.1持续15帧。需要根据单位正常移动速度来设定。太敏感会频繁触发仲裁增加开销太迟钝会让卡住现象持续过久。队形保持刚度单位试图回归队形指定位置的力度。刚度高队形整齐但通过狭窄地形时变形困难刚度低队形松散但通过性强。通常需要一个较高的基础值并在检测到拥挤时动态降低。调试方法不要凭感觉瞎调。在游戏中创建可视化调试工具绘制流场用箭头显示每个格子的移动方向。绘制势场用不同颜色显示单位周围的斥力场强度。显示单位受力在单位头上画线显示其受到的合力向量引力、斥力分开展示。记录死锁事件当死锁发生时在屏幕上高亮显示相关单位并打印日志。 通过这些可视化工具你能直观地看到为什么单位会卡住、为什么队形会散开从而有针对性地调整参数。5.3 应对动态障碍与突发情况游戏世界是动态的。建筑会被建造或摧毁桥梁会断裂敌人会突然出现挡住去路。动态流场更新当地形发生永久性变化建筑建成/摧毁需要标记相关区域为“脏”区域并在下一帧或空闲时重新计算流场。对于临时性障碍如一个停留的友军单位则通过局部斥力场来处理而不是更新全局流场后者开销太大。移动中更改目标玩家频繁下达新命令是常态。当新目标下达时最简单的方式是立即重新计算新目标的流场所有单位平滑转向新的方向。更复杂的实现可以比较新旧目标如果距离很近可以沿用部分旧流场或进行局部调整。处理单位死亡当单位死亡时需要立即将其从所有相关数据结构空间划分、队形锚点列表中移除否则会成为“幽灵障碍物”影响其他单位的移动。6. 常见问题与排查实录在实际开发中你会遇到各种各样诡异的问题。下面是一些我踩过的坑和解决方法。问题1单位在开阔地移动时队伍像“爆炸”一样四散开来无法保持紧凑。排查检查斥力场的参数。很可能“斥力半径”设置得过大或者“斥力强度”过强。同时检查“队形保持刚度”是否过低或未生效。解决减小斥力半径使其略大于单位碰撞半径之和。降低斥力强度并确保队形偏移力将单位拉向队形位置的强度足以对抗斥力。可以尝试让队形力在单位间距正常时较弱当间距过大时增强形成一个“软约束”。问题2单位在狭窄路口如一格宽的通道发生严重堵塞完全无法通过。排查这是典型的死锁问题。局部斥力场让所有单位在入口处互相排斥谁也无法率先进入通道。解决这是引入“仲裁器”层级的典型场景。除了前面提到的临时优先级或短暂停滞还有一个巧妙的“排队”规则当检测到多个单位试图进入同一狭窄通道时可以临时将它们的目标点稍微错开例如在通道入口外形成一个虚拟的排队线让它们依次通过。这比复杂的全局规划要简单高效。问题3单位移动时出现高频抖动尤其在地形边缘或墙角。排查首先检查是否是物理引擎的碰撞体与寻路网格NavMesh或流场网格不对齐导致的。其次检查合力计算是否每帧波动过大。可能是流场在格子边缘方向突变或者斥力计算不稳定。解决确保物理碰撞体与寻路数据的一致性。对于流场方向突变可以在查询流场方向时不只取当前格子的方向而是与周围格子方向做平滑插值。对于合力波动可以引入“平滑移动”或“转向速率限制”让单位每帧的转向角度有上限使移动更平滑。问题4大量单位100移动时帧率显著下降。排查使用性能分析工具如Unity的Profiler, Unreal的Insights定位热点。瓶颈通常出现在1) 每帧遍历所有单位计算斥力O(N²)复杂度2) 频繁的流场重计算3) 复杂的队形计算。解决必须使用空间划分将单位存入网格或四叉树计算斥力时只查询相邻格子内的单位将复杂度降至接近O(N)。流场缓存与异步计算流场计算放到子线程或分帧进行计算完成前单位沿用旧流场或朝目标点直线移动。分级细节LOD对于屏幕外或远处的单位群使用简化的移动模拟例如只移动群体包围盒的中心点内部单位做相对简单的跟随。降低更新频率不是所有单位都需要每帧进行高精度避障。可以每2-3帧更新一次非核心单位的移动。问题5单位在移动中特别是转向时会“滑步”或移动轨迹不自然。排查这通常是移动动画与底层逻辑位置更新不同步或者转向速度过快导致的。如果直接每帧将单位位置设置为计算出的新位置就会缺乏过渡感。解决引入“转向”和“移动”的插值。计算出一个理想的移动方向向量后不要立即将单位朝向设为该方向而是每帧以一定的最大角速度如180度/秒旋转朝向。位置更新也类似根据当前朝向和速度进行平滑移动而不是瞬间“传送”。这虽然增加了一点延迟但视觉体验大幅提升更符合人们对有惯性物体的认知。最后记住调试MAPF相关AI是一个迭代和需要耐心的过程。从一个最简单的、会碰撞的版本开始逐步加入流场、避障、队形等一层层功能每加一层都充分测试和调试参数。建立一个丰富的测试场景包含开阔地、狭窄通道、死胡同、动态开启的门等确保你的移动系统在各种极端情况下都能有可接受的表现。毕竟在游戏中一个偶尔会卡一下但大部分时间流畅的移动系统远比一个绝对完美但导致游戏卡成幻灯片的系统要好得多。
1. 项目概述当游戏AI不止一个“人”在走路做游戏AI尤其是涉及到单位移动的新手和老手之间最大的分水岭往往不是会不会写A*算法而是当屏幕上同时有几十、上百个单位需要移动并且它们之间不能“穿模”、不能卡死、还得看起来有点智能的时候你该怎么办。这个问题在《吃豆人》里是四个颜色各异的幽灵如何围追堵截玩家在《星际争霸》或《帝国时代》里是一队士兵如何保持阵型穿过狭窄的峡谷在《文明》里是你的大军如何有条不紊地开赴前线。这就是多智能体路径规划Multi-Agent Path Finding, MAPF要解决的核心问题。它不再是给单个角色找一条从A到B的最短路径那么简单而是要为一群有各自起点和终点的智能体在共享的、有障碍物的地图上规划出一组无碰撞、且整体上“最优”的路径。这个“最优”可以是总移动步数最少、总完成时间最短或者像在RTS游戏里更看重队形的保持和调度的流畅性。我最初接触这个问题是在尝试复刻一个简化版的《吃豆人》时。给单个幽灵写个A追着玩家跑很简单但四个幽灵一放进去问题就来了它们经常在转角处挤成一团或者为了追玩家而互相堵死路口看起来蠢得不行。后来做RTS类的原型问题更严重框选一队单位点一个目标点它们要么挤成一坨“叠罗汉”过去要么在狭窄路口发生“交通瘫痪”半天动弹不得。这些体验让我意识到单体的A只是“能走”多体的MAPF才是“会走”。网络上常说的“贪吃蛇寻路”其实也是一个非常形象的MAPF问题——蛇身每一个节都是一位智能体它们的路径必须首尾相连且不能自交。而“ai翻译.json怎么装进游戏里”这种热词虽然看似不相关但它背后反映的是开发者希望将外部AI模型可能就定义在json配置里集成到游戏逻辑中的普遍需求MAPF算法作为游戏AI的核心模块之一其选型和集成正是这种需求的典型场景。至于“串口rts是什么意思”那是硬件通信里的流控制信号和我们说的即时战略游戏RTS纯属同名巧合但也提醒我们在技术领域明确语境和定义是多么重要。所以这篇内容我想抛开那些复杂的数学证明和论文术语就从一个游戏开发者的实战视角聊聊当我们从“一个单位寻路”进阶到“一群单位调度”时手头有哪些MAPF算法可以选它们各自适合什么场景以及在实际项目中怎么把它们“装进”游戏里并调出能用的效果。2. MAPF核心思路与方案选型没有银弹只有权衡面对MAPF问题第一反应可能是“我给每个单位独立跑一遍A*不就行了” 这确实是基线方案我们称之为“独立规划”Independent Planning。但这样做的后果就是碰撞满天飞。于是所有MAPF算法本质上都在做一件事在独立规划的基础上引入不同形式和程度的“协调”Coordination以避免碰撞。协调的代价通常是计算复杂度的飙升。MAPF已被证明是NP-Hard问题意味着随着智能体数量增加找到最优解的计算时间会爆炸式增长。因此所有实战算法都是在解的质量最优性和计算速度之间寻找平衡。根据协调的时机和方式主流算法可以分成几大类。2.1 基于冲突的搜索CBS为完美方案买单CBSConflict-Based Search是学术界目前最主流的“最优”MAPF求解器框架之一。它的思想很直观先让所有智能体独立规划出最短路径底层搜索如A*。然后检查这些路径之间是否有冲突比如在同一时间走到同一格子。如果发现冲突就通过“增加约束”来化解——比如要求智能体A在时间t不能位于格子G。这个约束会生成新的搜索节点算法在这个高层搜索树上不断寻找一个无冲突的解决方案。为什么选择CBS因为它能保证找到最优解在设定的成本函数下如总时间。这对于一些对公平性、绝对效率要求极高的场景比如仓库机器人调度是至关重要的。在游戏中如果你需要为一段关键的剧情动画或电影运镜规划绝对精确、无任何穿帮的群体移动CBS是可靠的选择。它的代价是什么速度。智能体数量稍多比如超过20个地图稍复杂求解时间就可能从毫秒级跳到秒级甚至分钟级完全无法满足游戏实时性的要求通常要求每帧在几毫秒内完成。因此在快节奏的RTS游戏中直接使用标准CBS通常是不现实的。注意不要被“最优”二字迷惑。游戏中的“最优”往往是主观的、符合玩家预期的“好看”和“流畅”而非数学上的绝对最短时间。为后者付出的计算成本在游戏中常常是不值得的。2.2 基于优先级的规划PBS快节奏游戏的实用之选PBSPriority-Based Search代表了另一大类思路降低最优性要求换取速度的大幅提升。它的核心是为智能体分配一个固定的移动优先级。规划时从优先级最高的智能体开始为它规划一条避开所有障碍物的路径。然后优先级次高的智能体在规划时必须把高优先级智能体的路径视为“临时移动障碍物”来避开。以此类推直到所有智能体完成规划。为什么在游戏中PBS更常见因为它的速度极快。规划过程几乎是线性的智能体数量增加计算时间也基本线性增加。对于需要每帧或每几帧就重新规划一次路径的RTS游戏来说这种效率是救命稻草。虽然它放弃了全局最优解低优先级单位可能会绕远路但结果在视觉上通常是可接受的——就像现实中领导先走员工让路虽然整体不是最快但秩序井然。实战中的变种单纯的PBS结果可能不够好。因此实战中常引入“窗口式”规划Windowed PBS或“动态优先级”。例如只规划未来几秒内的路径然后滚动执行或者根据单位类型骑兵优先于步兵、状态受伤单位优先撤退动态调整优先级。这都是在PBS框架内用可控的复杂度换取更好的效果。2.3 联合状态A*Joint-State A*小规模精确控制的利器这是最“暴力”也最直观的方法把N个智能体的状态组合成一个“超级状态”比如每个智能体的位置合起来作为一个元组在这个维度极高的状态空间里进行A*搜索。搜索的目标是让这个“超级状态”从所有智能体的起点组合移动到终点组合。什么时候会用当智能体数量非常少通常2-4个且它们之间的协作要求极度精确时。一个经典例子就是《吃豆人》的四个幽灵。虽然看起来是四个独立单位但高级的AI会让它们表现出协作行为一个正面追击一个侧翼包抄两个在远处预判拦截。这种带有策略性的包围可以通过为幽灵们设计一个联合目标如“形成包围圈”然后用简化的联合状态搜索来规划初期的走位来实现。当然全程使用联合搜索计算量太大但用于关键决策点是可行的。它的局限性状态空间随智能体数量指数级膨胀。2个智能体在10x10地图上联合状态空间是100*100100003个智能体就是100万。这决定了它只能用于极小规模的“精英小队”AI。2.4 基于规则与势场的混合方法工业界的黑魔法在大量商业RTS游戏中你很少会看到纯粹的学术MAPF算法。更多是一种高度特化、基于规则的混合系统。其中“势场法”Potential Fields是重要的组成部分。每个单位同时受多种“势场”影响目标点的“引力场”、障碍物和其他单位的“斥力场”、维持队形的“对齐场”。单位每帧的移动方向就是这些力场的向量叠加结果。这天然避免了碰撞因为靠太近时斥力会剧增并能涌现出流畅的群体运动像鸟群或鱼群。为什么它有效因为它本质上是分布式的、无中心的计算。每个单位只根据自己局部感知的信息周围的单位和障碍独立决定移动计算开销小且非常适合并行。当一群单位移动时看起来就像有智能的流体。它的坑在哪里势场法很容易陷入局部最优导致单位在复杂地形中“抖动”或卡住。比如两个单位在狭窄门洞前互相排斥谁都进不去。因此工业级实现一定会混入其他技术用A*或流场Flow Field规划一条宏观的“建议路径”作为主导引力当检测到卡顿时临时启用一个轻量级的、基于规则的解耦逻辑例如让其中一个单位短暂“停下”或“后退一步”对于队形则可能采用“锚点”法先为整个队伍规划一个队长路径其他单位相对队长保持偏移位置。下表对比了这几种核心思路的典型特征方便你根据项目需求快速筛选算法思路典型代表解的质量计算速度适用场景游戏中的常见形态全局最优搜索CBS, Joint-State A*最优(理论保证)慢(指数/高阶增长)小规模精确调度、离线计算、回合制策略剧情动画路径预计算、回合制游戏单位移动优先级协调PBS, Windowed PBS次优(依赖优先级)快(近线性增长)实时战略游戏RTS单位集群移动RTS中框选部队的移动、MOBA中小兵推进局部反应式势场法, 流场避障涌现性(无全局保证)极快(每帧本地计算)大规模群体移动、群体模拟人群、鸟群RTS中极大规模混战、模拟经营游戏中的市民流动混合架构A*宏观路径 势场局部避障实用性好快(分层处理)绝大多数商业RTS、MMO游戏《星际争霸2》、《全面战争》系列的单位移动系统选型的关键在于问自己几个问题你的游戏是实时还是回合制同时移动的单位通常有多少几个、几十个、几百个玩家对路径“最优”的容忍度有多高是否允许少量绕路你的性能预算是每帧多少毫秒回答完这些合适的技术象限就清晰了。3. 实战拆解一为《吃豆人》幽灵注入协作灵魂让我们从一个相对简单的例子开始。吃豆人的四个幽灵Blinky, Pinky, Inky, Clyde是游戏史上最经典的AI角色之一。它们的原始行为模式其实规则简单每个幽灵有一个固定的主导策略追击、预判、巡逻、随机并会在“追击”和“散布”模式间切换。但这已经蕴含了MAPF的雏形避免四个幽灵完全重叠在一起那样对玩家没有威胁。第一步基础移动与碰撞避免首先每个幽灵都需要一个最基础的寻路能力。这里使用A完全足够地图不大目标明确玩家位置或某个散点目标。但直接让四个幽灵独立A必然撞车。所以我们需要一个最简单的协调机制每帧为幽灵分配唯一的移动优先级。例如按照Blinky, Pinky, Inky, Clyde的顺序。在当前帧Blinky先根据A结果移动到一个相邻格子。然后Pinky规划时如果它的A首选格子被Blinky这帧占用了它就选择次优格子。以此类推。这本质上是一个每帧执行的、极简版的PBS。第二步引入策略性行为联合目标原始游戏的幽灵AI不仅仅是避碰。Inky蓝色幽灵的行为是“镜像预判”它需要参考Blinky红色幽灵和玩家的位置。这就可以看作一个微型的联合规划问题。我们可以这样实现计算Blinky到玩家的向量。将这个向量从玩家位置反向延长一倍得到Inky的“预判目标点”。为Inky规划通往该目标点的路径。 这里的关键是Inky的目标是动态的、依赖于另一个智能体Blinky的状态。在规划Inky的路径时我们需要把Blinky未来几帧的预测路径也作为临时障碍物考虑进去避免Inky和Blinky跑成一条线。这就引入了基于时间窗口的轻量级联合思考。第三步模式切换与全局协调当吃豆人吃掉能量豆幽灵会进入“恐惧”模式四散逃回巢穴。此时它们的目标从“追击玩家”突然变为“逃回地图中央的复活点”。这是一个所有智能体目标同时发生剧烈变化的MAPF场景极易在巢穴入口造成死锁。 一个实用的解决方法是在切换模式的瞬间为所有幽灵重新计算一次路径并强制赋予它们返回巢穴的路径一个“高优先级通道”。具体来说可以临时修改地图的代价让通往巢穴的路径代价显著降低或者更粗暴地在极短时间内比如0.5秒允许幽灵之间发生“穿透”忽略碰撞让它们能快速通过瓶颈区域。虽然不真实但保证了游戏流程的顺畅玩家也几乎不会察觉。实操心得在吃豆人这类游戏中幽灵的“智能”不在于找到数学上的最优包围路径而在于通过简单规则组合出令玩家感到有压力、有变化的行为。MAPF在这里的作用更多的是确保这些行为规则能流畅执行不因碰撞而显得愚蠢。因此采用非常轻量级的、基于规则和优先级的协调就足够了切忌过度设计。4. 实战拆解二RTS大规模单位调度的工程实现RTS的单位调度是MAPF问题的重灾区。玩家框选50个步兵点击地图另一端他们期望看到的是部队保持大致队形、高效地通过复杂地形而不是一团乱麻。下面是一个可落地的分层实现方案。4.1 层级一群体宏观路径规划Flow Field当玩家下达移动指令时首先不为每个单位单独计算A路径。想象一下50个单位同时计算A的CPU开销。取而代之的是计算一次流场。以目标点或目标区域中心为源头使用类似Dijkstra的算法计算地图上每个格子到达目标点的代价。对于每个格子其移动方向就是指向周围8个邻居中代价最小的那个方向。最终生成一个覆盖全地图的方向向量场。 这个计算过程可能比单个A*慢但只做一次所有前往该目标区域的单位都可以共享这个流场。单位只需每帧查询自己所在格子的方向向量就能知道该往哪走。这解决了宏观路径导向问题效率极高。4.2 层级二局部碰撞避免与队形保持局部势场规则单位按照流场方向移动时碰撞避免和队形保持由本地每帧计算处理。斥力场每个单位都会向周围一定半径内的其他友军单位和障碍物施加一个斥力。斥力大小与距离成反比。单位最终受到的合力 流场方向引力 所有斥力的向量和。这能自然让单位散开避免堆积。队形锚点对于需要保持队形的移动如步兵方阵我们不在每个单位身上计算复杂的相对位置。而是为整个群体虚拟一个“队长”或“锚点”。这个锚点严格按照流场移动。其他单位的目标位置是相对于这个锚点的一个固定偏移比如在3x3网格中自己的位置。每个单位使用一个轻量的A*或转向行为如Seek朝自己的目标位置移动同时叠加上述的局部斥力场来避免与队友碰撞。这样队形在开阔地能保持在狭窄处能自然变形通过再通过时又能恢复。4.3 层级三死锁检测与解决轻量级PBS/规则仲裁即使有了势场在极端地形如狭窄桥梁、门口仍可能发生死锁几个单位互相卡住斥力让它们都无法前进。这时需要第三层“仲裁器”。死锁检测非常简单如果一个单位的速度连续若干帧接近零且其目标方向上有其他友军单位则判定为可能死锁。死锁解决触发一个轻量级的协调逻辑。例如临时优先级让卡住的单位中随机一个获得高优先级在接下来几帧内其他单位对它“主动避让”即临时增强它对其他单位的斥力或减弱其他单位的斥力。短暂停滞让其中一个单位完全停止1-2秒放其他单位通过。局部重新规划为卡住的这个小群体在一个很小的范围内比如5x5运行一个极简的、2-3个智能体的PBS快速规划出一个解耦顺序。 这个仲裁器不需要经常运行只在检测到问题时激活因此开销可控。4.4 性能优化关键点空间划分计算斥力时不要遍历所有友军单位。使用空间划分结构如网格Spatial Grid或四叉树只查询相邻单元格内的单位。更新频率流场不需要每帧计算只有在目标点改变或地形发生重大变化如建筑被摧毁时才重新计算。局部势场和队形调整每帧进行。死锁检测可以每5-10帧进行一次。分级细节LOD对于远离屏幕中心或数量极大的单位群可以降低其避障和队形计算的精度甚至关闭避障采用更简单的“粘附”移动直到它们进入关键视野区域。踩坑记录早期实现时我曾尝试为每个RTS单位都做完整的A*寻路加CBS协调结果在单位数量超过20时帧率就暴跌。后来转向流场局部势场的混合模型同一台机器上能流畅支持超过200个单位的混合移动。最大的教训是在游戏里“看起来正确”远比“数学上最优”重要而效率是“看起来正确”的前提。5. 算法集成与参数调优把“AI”装进游戏里理解了算法下一步就是如何将它集成到游戏引擎中并调出好效果。这个过程就像调试游戏手感需要反复微调。5.1 数据结构与接口设计首先你需要一个管理所有移动单位的MovementSystem。每个单位有一个MovementAgent组件包含位置、速度、目标等状态。MovementSystem每帧更新其工作流程如下收集指令接收来自玩家或AI的移动命令更新群体的目标流场。分层更新更新流场低频。为每个活跃单位计算局部合力流场引力 友军/障碍斥力 队形偏移力。执行死锁检测与解决低频。应用移动根据合力计算新的速度和位置并处理与地图碰撞体的物理交互如果有的化。关键是如何将算法模块化。例如将流场生成器、势场计算器、队形管理器、仲裁器都设计成可插拔的模块。这样你可以为不同的单位类型配置不同的移动“套餐”。比如农民单位可能只需要流场基础斥力而精锐步兵则需要全套的流场势场队形仲裁。5.2 核心参数调优指南MAPF在游戏中的效果很大程度上取决于一堆“魔法数字”参数。以下是一些关键的调试点参数影响调优建议斥力半径单位开始互相排斥的距离。太小会碰撞太大会让队伍过于松散。通常设为单位碰撞半径的2-3倍。对于大型单位如坦克需要更大。斥力强度排斥力的力度。与单位质量或权重相关。需要与流场引力和最大速度平衡。强度太大会导致单位抖动太小无法避免碰撞。从1.0开始调试观察单位通过狭窄通道的行为。流场引力系数单位朝向目标方向的意愿强度。通常设为1.0。在复杂地形中可以临时调高以帮助单位“冲过”拥挤区域。最大速度 / 力单位每帧能改变的速度上限。限制合力的大小使移动更平滑避免单位像弹珠一样被弹飞。死锁检测阈值速度低于此值多少帧触发死锁检测。例如速度 0.1持续15帧。需要根据单位正常移动速度来设定。太敏感会频繁触发仲裁增加开销太迟钝会让卡住现象持续过久。队形保持刚度单位试图回归队形指定位置的力度。刚度高队形整齐但通过狭窄地形时变形困难刚度低队形松散但通过性强。通常需要一个较高的基础值并在检测到拥挤时动态降低。调试方法不要凭感觉瞎调。在游戏中创建可视化调试工具绘制流场用箭头显示每个格子的移动方向。绘制势场用不同颜色显示单位周围的斥力场强度。显示单位受力在单位头上画线显示其受到的合力向量引力、斥力分开展示。记录死锁事件当死锁发生时在屏幕上高亮显示相关单位并打印日志。 通过这些可视化工具你能直观地看到为什么单位会卡住、为什么队形会散开从而有针对性地调整参数。5.3 应对动态障碍与突发情况游戏世界是动态的。建筑会被建造或摧毁桥梁会断裂敌人会突然出现挡住去路。动态流场更新当地形发生永久性变化建筑建成/摧毁需要标记相关区域为“脏”区域并在下一帧或空闲时重新计算流场。对于临时性障碍如一个停留的友军单位则通过局部斥力场来处理而不是更新全局流场后者开销太大。移动中更改目标玩家频繁下达新命令是常态。当新目标下达时最简单的方式是立即重新计算新目标的流场所有单位平滑转向新的方向。更复杂的实现可以比较新旧目标如果距离很近可以沿用部分旧流场或进行局部调整。处理单位死亡当单位死亡时需要立即将其从所有相关数据结构空间划分、队形锚点列表中移除否则会成为“幽灵障碍物”影响其他单位的移动。6. 常见问题与排查实录在实际开发中你会遇到各种各样诡异的问题。下面是一些我踩过的坑和解决方法。问题1单位在开阔地移动时队伍像“爆炸”一样四散开来无法保持紧凑。排查检查斥力场的参数。很可能“斥力半径”设置得过大或者“斥力强度”过强。同时检查“队形保持刚度”是否过低或未生效。解决减小斥力半径使其略大于单位碰撞半径之和。降低斥力强度并确保队形偏移力将单位拉向队形位置的强度足以对抗斥力。可以尝试让队形力在单位间距正常时较弱当间距过大时增强形成一个“软约束”。问题2单位在狭窄路口如一格宽的通道发生严重堵塞完全无法通过。排查这是典型的死锁问题。局部斥力场让所有单位在入口处互相排斥谁也无法率先进入通道。解决这是引入“仲裁器”层级的典型场景。除了前面提到的临时优先级或短暂停滞还有一个巧妙的“排队”规则当检测到多个单位试图进入同一狭窄通道时可以临时将它们的目标点稍微错开例如在通道入口外形成一个虚拟的排队线让它们依次通过。这比复杂的全局规划要简单高效。问题3单位移动时出现高频抖动尤其在地形边缘或墙角。排查首先检查是否是物理引擎的碰撞体与寻路网格NavMesh或流场网格不对齐导致的。其次检查合力计算是否每帧波动过大。可能是流场在格子边缘方向突变或者斥力计算不稳定。解决确保物理碰撞体与寻路数据的一致性。对于流场方向突变可以在查询流场方向时不只取当前格子的方向而是与周围格子方向做平滑插值。对于合力波动可以引入“平滑移动”或“转向速率限制”让单位每帧的转向角度有上限使移动更平滑。问题4大量单位100移动时帧率显著下降。排查使用性能分析工具如Unity的Profiler, Unreal的Insights定位热点。瓶颈通常出现在1) 每帧遍历所有单位计算斥力O(N²)复杂度2) 频繁的流场重计算3) 复杂的队形计算。解决必须使用空间划分将单位存入网格或四叉树计算斥力时只查询相邻格子内的单位将复杂度降至接近O(N)。流场缓存与异步计算流场计算放到子线程或分帧进行计算完成前单位沿用旧流场或朝目标点直线移动。分级细节LOD对于屏幕外或远处的单位群使用简化的移动模拟例如只移动群体包围盒的中心点内部单位做相对简单的跟随。降低更新频率不是所有单位都需要每帧进行高精度避障。可以每2-3帧更新一次非核心单位的移动。问题5单位在移动中特别是转向时会“滑步”或移动轨迹不自然。排查这通常是移动动画与底层逻辑位置更新不同步或者转向速度过快导致的。如果直接每帧将单位位置设置为计算出的新位置就会缺乏过渡感。解决引入“转向”和“移动”的插值。计算出一个理想的移动方向向量后不要立即将单位朝向设为该方向而是每帧以一定的最大角速度如180度/秒旋转朝向。位置更新也类似根据当前朝向和速度进行平滑移动而不是瞬间“传送”。这虽然增加了一点延迟但视觉体验大幅提升更符合人们对有惯性物体的认知。最后记住调试MAPF相关AI是一个迭代和需要耐心的过程。从一个最简单的、会碰撞的版本开始逐步加入流场、避障、队形等一层层功能每加一层都充分测试和调试参数。建立一个丰富的测试场景包含开阔地、狭窄通道、死胡同、动态开启的门等确保你的移动系统在各种极端情况下都能有可接受的表现。毕竟在游戏中一个偶尔会卡一下但大部分时间流畅的移动系统远比一个绝对完美但导致游戏卡成幻灯片的系统要好得多。
