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）：为完美方案买单

CBS（Conflict-Based Search）是学术界目前最主流的“最优”MAPF求解器框架之一。它的思想很直观：先让所有智能体独立规划出最短路径（底层搜索，如A*）。然后检查这些路径之间是否有冲突（比如在同一时间走到同一格子）。如果发现冲突，就通过“增加约束”来化解——比如，要求智能体A在时间t不能位于格子G。这个约束会生成新的搜索节点，算法在这个高层搜索树上不断寻找一个无冲突的解决方案。

为什么选择CBS？因为它能保证找到最优解（在设定的成本函数下，如总时间）。这对于一些对公平性、绝对效率要求极高的场景，比如仓库机器人调度，是至关重要的。在游戏中，如果你需要为一段关键的剧情动画或电影运镜规划绝对精确、无任何穿帮的群体移动，CBS是可靠的选择。

它的代价是什么？速度。智能体数量稍多（比如超过20个），地图稍复杂，求解时间就可能从毫秒级跳到秒级甚至分钟级，完全无法满足游戏实时性的要求（通常要求每帧在几毫秒内完成）。因此，在快节奏的RTS游戏中，直接使用标准CBS通常是不现实的。

注意：不要被“最优”二字迷惑。游戏中的“最优”往往是主观的、符合玩家预期的“好看”和“流畅”，而非数学上的绝对最短时间。为后者付出的计算成本，在游戏中常常是不值得的。

2.2 基于优先级的规划（PBS）：快节奏游戏的实用之选

PBS（Priority-Based Search）代表了另一大类思路：降低最优性要求，换取速度的大幅提升。它的核心是为智能体分配一个固定的移动优先级。规划时，从优先级最高的智能体开始，为它规划一条避开所有障碍物的路径。然后，优先级次高的智能体在规划时，必须把高优先级智能体的路径视为“临时移动障碍物”来避开。以此类推，直到所有智能体完成规划。

为什么在游戏中PBS更常见？因为它的速度极快。规划过程几乎是线性的，智能体数量增加，计算时间也基本线性增加。对于需要每帧或每几帧就重新规划一次路径的RTS游戏来说，这种效率是救命稻草。虽然它放弃了全局最优解（低优先级单位可能会绕远路），但结果在视觉上通常是可接受的——就像现实中，领导先走，员工让路，虽然整体不是最快，但秩序井然。

实战中的变种：单纯的PBS结果可能不够好。因此，实战中常引入“窗口式”规划（Windowed PBS）或“动态优先级”。例如，只规划未来几秒内的路径，然后滚动执行；或者根据单位类型（骑兵优先于步兵）、状态（受伤单位优先撤退）动态调整优先级。这都是在PBS框架内，用可控的复杂度换取更好的效果。

2.3 联合状态A*（Joint-State A*）：小规模精确控制的利器

这是最“暴力”也最直观的方法：把N个智能体的状态组合成一个“超级状态”（比如，每个智能体的位置合起来作为一个元组），在这个维度极高的状态空间里进行A*搜索。搜索的目标是让这个“超级状态”从所有智能体的起点组合，移动到终点组合。

什么时候会用？当智能体数量非常少（通常2-4个），且它们之间的协作要求极度精确时。一个经典例子就是《吃豆人》的四个幽灵。虽然看起来是四个独立单位，但高级的AI会让它们表现出协作行为：一个正面追击，一个侧翼包抄，两个在远处预判拦截。这种带有策略性的包围，可以通过为幽灵们设计一个联合目标（如“形成包围圈”），然后用简化的联合状态搜索来规划初期的走位来实现。当然，全程使用联合搜索计算量太大，但用于关键决策点是可行的。

它的局限性：状态空间随智能体数量指数级膨胀。2个智能体在10x10地图上，联合状态空间是100*100=10000；3个智能体就是100万。这决定了它只能用于极小规模的“精英小队”AI。

2.4 基于规则与势场的混合方法：工业界的黑魔法

在大量商业RTS游戏中，你很少会看到纯粹的学术MAPF算法。更多是一种高度特化、基于规则的混合系统。其中，“势场法”（Potential Fields）是重要的组成部分。

每个单位同时受多种“势场”影响：目标点的“引力场”、障碍物和其他单位的“斥力场”、维持队形的“对齐场”。单位每帧的移动方向，就是这些力场的向量叠加结果。这天然避免了碰撞（因为靠太近时斥力会剧增），并能涌现出流畅的群体运动，像鸟群或鱼群。

为什么它有效？因为它本质上是分布式的、无中心的计算。每个单位只根据自己局部感知的信息（周围的单位和障碍）独立决定移动，计算开销小，且非常适合并行。当一群单位移动时，看起来就像有智能的流体。

它的坑在哪里？势场法很容易陷入局部最优，导致单位在复杂地形中“抖动”或卡住。比如，两个单位在狭窄门洞前互相排斥，谁都进不去。因此，工业级实现一定会混入其他技术：用A*或流场（Flow Field）规划一条宏观的“建议路径”作为主导引力；当检测到卡顿时，临时启用一个轻量级的、基于规则的解耦逻辑（例如，让其中一个单位短暂“停下”或“后退一步”）；对于队形，则可能采用“锚点”法，先为整个队伍规划一个队长路径，其他单位相对队长保持偏移位置。

下表对比了这几种核心思路的典型特征，方便你根据项目需求快速筛选：

选型的关键，在于问自己几个问题：你的游戏是实时还是回合制？同时移动的单位通常有多少（几个、几十个、几百个）？玩家对路径“最优”的容忍度有多高（是否允许少量绕路）？你的性能预算是每帧多少毫秒？回答完这些，合适的技术象限就清晰了。

3. 实战拆解一：为《吃豆人》幽灵注入协作灵魂

让我们从一个相对简单的例子开始。吃豆人的四个幽灵（Blinky, Pinky, Inky, Clyde）是游戏史上最经典的AI角色之一。它们的原始行为模式其实规则简单：每个幽灵有一个固定的主导策略（追击、预判、巡逻、随机），并会在“追击”和“散布”模式间切换。但这已经蕴含了MAPF的雏形：避免四个幽灵完全重叠在一起，那样对玩家没有威胁。

第一步：基础移动与碰撞避免首先，每个幽灵都需要一个最基础的寻路能力。这里使用A完全足够，地图不大，目标明确（玩家位置或某个散点目标）。但直接让四个幽灵独立A，必然撞车。所以我们需要一个最简单的协调机制：每帧为幽灵分配唯一的移动优先级。例如，按照Blinky, Pinky, Inky, Clyde的顺序。在当前帧，Blinky先根据A结果移动到一个相邻格子。然后Pinky规划时，如果它的A首选格子被Blinky这帧占用了，它就选择次优格子。以此类推。这本质上是一个每帧执行的、极简版的PBS。

第二步：引入策略性行为（联合目标）原始游戏的幽灵AI不仅仅是避碰。Inky（蓝色幽灵）的行为是“镜像预判”，它需要参考Blinky（红色幽灵）和玩家的位置。这就可以看作一个微型的联合规划问题。我们可以这样实现：

1. 计算Blinky到玩家的向量。
2. 将这个向量从玩家位置反向延长一倍，得到Inky的“预判目标点”。
3. 为Inky规划通往该目标点的路径。 这里的关键是，Inky的目标是动态的、依赖于另一个智能体（Blinky）的状态。在规划Inky的路径时，我们需要把Blinky未来几帧的预测路径也作为临时障碍物考虑进去，避免Inky和Blinky跑成一条线。这就引入了基于时间窗口的轻量级联合思考。

第三步：模式切换与全局协调当吃豆人吃掉能量豆，幽灵会进入“恐惧”模式，四散逃回巢穴。此时，它们的目标从“追击玩家”突然变为“逃回地图中央的复活点”。这是一个所有智能体目标同时发生剧烈变化的MAPF场景，极易在巢穴入口造成死锁。 一个实用的解决方法是：在切换模式的瞬间，为所有幽灵重新计算一次路径，并强制赋予它们返回巢穴的路径一个“高优先级通道”。具体来说，可以临时修改地图的代价，让通往巢穴的路径代价显著降低，或者更粗暴地，在极短时间内（比如0.5秒）允许幽灵之间发生“穿透”（忽略碰撞），让它们能快速通过瓶颈区域。虽然不真实，但保证了游戏流程的顺畅，玩家也几乎不会察觉。

实操心得：在吃豆人这类游戏中，幽灵的“智能”不在于找到数学上的最优包围路径，而在于通过简单规则组合出令玩家感到有压力、有变化的行为。MAPF在这里的作用，更多的是确保这些行为规则能流畅执行，不因碰撞而显得愚蠢。因此，采用非常轻量级的、基于规则和优先级的协调就足够了，切忌过度设计。

4. 实战拆解二：RTS大规模单位调度的工程实现

RTS的单位调度是MAPF问题的重灾区。玩家框选50个步兵，点击地图另一端，他们期望看到的是部队保持大致队形、高效地通过复杂地形，而不是一团乱麻。下面是一个可落地的分层实现方案。

4.1 层级一：群体宏观路径规划（Flow Field）

当玩家下达移动指令时，首先不为每个单位单独计算A路径。想象一下50个单位同时计算A的CPU开销。取而代之的是计算一次流场。

1. 以目标点（或目标区域中心）为源头，使用类似Dijkstra的算法，计算地图上每个格子到达目标点的代价。
2. 对于每个格子，其移动方向就是指向周围8个邻居中代价最小的那个方向。最终生成一个覆盖全地图的方向向量场。 这个计算过程可能比单个A*慢，但只做一次，所有前往该目标区域的单位都可以共享这个流场。单位只需每帧查询自己所在格子的方向向量，就能知道该往哪走。这解决了宏观路径导向问题，效率极高。

4.2 层级二：局部碰撞避免与队形保持（局部势场+规则）

单位按照流场方向移动时，碰撞避免和队形保持由本地每帧计算处理。

1. 斥力场：每个单位都会向周围一定半径内的其他友军单位和障碍物施加一个斥力。斥力大小与距离成反比。单位最终受到的合力 = 流场方向（引力） + 所有斥力的向量和。这能自然让单位散开，避免堆积。
2. 队形锚点：对于需要保持队形的移动（如步兵方阵），我们不在每个单位身上计算复杂的相对位置。而是为整个群体虚拟一个“队长”或“锚点”。这个锚点严格按照流场移动。其他单位的目标位置，是相对于这个锚点的一个固定偏移（比如，在3x3网格中自己的位置）。每个单位使用一个轻量的A*或转向行为（如Seek），朝自己的目标位置移动，同时叠加上述的局部斥力场来避免与队友碰撞。这样，队形在开阔地能保持，在狭窄处能自然变形通过，再通过时又能恢复。

4.3 层级三：死锁检测与解决（轻量级PBS/规则仲裁）

即使有了势场，在极端地形（如狭窄桥梁、门口）仍可能发生死锁：几个单位互相卡住，斥力让它们都无法前进。这时需要第三层“仲裁器”。

1. 死锁检测：非常简单，如果一个单位的速度连续若干帧接近零，且其目标方向上有其他友军单位，则判定为可能死锁。
2. 死锁解决：触发一个轻量级的协调逻辑。例如：
   • 临时优先级：让卡住的单位中，随机一个获得高优先级，在接下来几帧内，其他单位对它“主动避让”（即临时增强它对其他单位的斥力，或减弱其他单位的斥力）。
   • 短暂停滞：让其中一个单位完全停止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每帧更新，其工作流程如下：

1. 收集指令：接收来自玩家或AI的移动命令，更新群体的目标流场。
2. 分层更新：
   • 更新流场（低频）。
   • 为每个活跃单位计算局部合力（流场引力 + 友军/障碍斥力 + 队形偏移力）。
   • 执行死锁检测与解决（低频）。
3. 应用移动：根据合力计算新的速度和位置，并处理与地图碰撞体的物理交互（如果有的化）。

关键是如何将算法模块化。例如，将流场生成器、势场计算器、队形管理器、仲裁器都设计成可插拔的模块。这样，你可以为不同的单位类型配置不同的移动“套餐”。比如，农民单位可能只需要流场+基础斥力；而精锐步兵则需要全套的流场+势场+队形+仲裁。

5.2 核心参数调优指南

MAPF在游戏中的效果，很大程度上取决于一堆“魔法数字”参数。以下是一些关键的调试点：

调试方法：不要凭感觉瞎调。在游戏中创建可视化调试工具：

• 绘制流场：用箭头显示每个格子的移动方向。
• 绘制势场：用不同颜色显示单位周围的斥力场强度。
• 显示单位受力：在单位头上画线，显示其受到的合力向量（引力、斥力分开展示）。
• 记录死锁事件：当死锁发生时，在屏幕上高亮显示相关单位，并打印日志。 通过这些可视化工具，你能直观地看到为什么单位会卡住、为什么队形会散开，从而有针对性地调整参数。

5.3 应对动态障碍与突发情况

游戏世界是动态的。建筑会被建造或摧毁，桥梁会断裂，敌人会突然出现挡住去路。

• 动态流场更新：当地形发生永久性变化（建筑建成/摧毁），需要标记相关区域为“脏”区域，并在下一帧或空闲时重新计算流场。对于临时性障碍（如一个停留的友军单位），则通过局部斥力场来处理，而不是更新全局流场，后者开销太大。
• 移动中更改目标：玩家频繁下达新命令是常态。当新目标下达时，最简单的方式是立即重新计算新目标的流场，所有单位平滑转向新的方向。更复杂的实现可以比较新旧目标，如果距离很近，可以沿用部分旧流场或进行局部调整。
• 处理单位死亡：当单位死亡时，需要立即将其从所有相关数据结构（空间划分、队形锚点列表）中移除，否则会成为“幽灵障碍物”影响其他单位的移动。

6. 常见问题与排查实录

在实际开发中，你会遇到各种各样诡异的问题。下面是一些我踩过的坑和解决方法。

问题1：单位在开阔地移动时，队伍像“爆炸”一样四散开来，无法保持紧凑。

• 排查：检查斥力场的参数。很可能“斥力半径”设置得过大，或者“斥力强度”过强。同时，检查“队形保持刚度”是否过低或未生效。
• 解决：减小斥力半径，使其略大于单位碰撞半径之和。降低斥力强度，并确保队形偏移力（将单位拉向队形位置）的强度足以对抗斥力。可以尝试让队形力在单位间距正常时较弱，当间距过大时增强，形成一个“软约束”。

问题2：单位在狭窄路口（如一格宽的通道）发生严重堵塞，完全无法通过。

• 排查：这是典型的死锁问题。局部斥力场让所有单位在入口处互相排斥，谁也无法率先进入通道。
• 解决：这是引入“仲裁器”层级的典型场景。除了前面提到的临时优先级或短暂停滞，还有一个巧妙的“排队”规则：当检测到多个单位试图进入同一狭窄通道时，可以临时将它们的目标点稍微错开（例如，在通道入口外形成一个虚拟的排队线），让它们依次通过。这比复杂的全局规划要简单高效。

问题3：单位移动时出现高频抖动，尤其在地形边缘或墙角。

• 排查：首先检查是否是物理引擎的碰撞体与寻路网格（NavMesh）或流场网格不对齐导致的。其次，检查合力计算是否每帧波动过大。可能是流场在格子边缘方向突变，或者斥力计算不稳定。
• 解决：确保物理碰撞体与寻路数据的一致性。对于流场方向突变，可以在查询流场方向时，不只取当前格子的方向，而是与周围格子方向做平滑插值。对于合力波动，可以引入“平滑移动”或“转向速率限制”，让单位每帧的转向角度有上限，使移动更平滑。

问题4：大量单位（>100）移动时，帧率显著下降。

• 排查：使用性能分析工具（如Unity的Profiler, Unreal的Insights）定位热点。瓶颈通常出现在：1) 每帧遍历所有单位计算斥力（O(N²)复杂度）；2) 频繁的流场重计算；3) 复杂的队形计算。
• 解决：
  1. 必须使用空间划分：将单位存入网格或四叉树，计算斥力时只查询相邻格子内的单位，将复杂度降至接近O(N)。
  2. 流场缓存与异步计算：流场计算放到子线程或分帧进行，计算完成前单位沿用旧流场或朝目标点直线移动。
  3. 分级细节（LOD）：对于屏幕外或远处的单位群，使用简化的移动模拟（例如，只移动群体包围盒的中心点，内部单位做相对简单的跟随）。
  4. 降低更新频率：不是所有单位都需要每帧进行高精度避障。可以每2-3帧更新一次非核心单位的移动。

问题5：单位在移动中，特别是转向时，会“滑步”或移动轨迹不自然。

• 排查：这通常是移动动画与底层逻辑位置更新不同步，或者转向速度过快导致的。如果直接每帧将单位位置设置为计算出的新位置，就会缺乏过渡感。
• 解决：引入“转向”和“移动”的插值。计算出一个理想的移动方向向量后，不要立即将单位朝向设为该方向，而是每帧以一定的最大角速度（如180度/秒）旋转朝向。位置更新也类似，根据当前朝向和速度进行平滑移动，而不是瞬间“传送”。这虽然增加了一点延迟，但视觉体验大幅提升，更符合人们对有惯性物体的认知。

最后，记住调试MAPF相关AI是一个迭代和需要耐心的过程。从一个最简单的、会碰撞的版本开始，逐步加入流场、避障、队形等一层层功能，每加一层都充分测试和调试参数。建立一个丰富的测试场景，包含开阔地、狭窄通道、死胡同、动态开启的门等，确保你的移动系统在各种极端情况下都能有可接受的表现。毕竟，在游戏中，一个偶尔会卡一下但大部分时间流畅的移动系统，远比一个绝对完美但导致游戏卡成幻灯片的系统要好得多。