游戏 AI：寻路、行为树与状态机
游戏 AI 设计入门：寻路、行为树与状态机
游戏人工智能（AI）的核心任务是赋予非玩家角色（NPC）智能行为，让它们能感知环境、做出决策并执行动作。本教程将聚焦三个最基础且广泛使用的技术模块：导航网格寻路、有限状态机和行为树，帮助你建立可落地的游戏 AI 设计知识体系。
1. 导航与寻路：让角色聪明地移动
角色移动是智能行为的基础。简单的直线移动无法处理障碍物和复杂地形，我们需要可靠的寻路系统。
1.1 图形表示：从网格到导航网格
寻路算法需要将游戏世界抽象为可遍历的图结构。常见表示方式有：
- 方格网格：将地图划分为均匀方格，每个格子标记为可行走或不可行走。实现简单，但内存消耗大，移动路径呈锯齿状。
- 路点图：手动放置关键位置点，并用连线表示可通行路径。适合固定路线，灵活性差。
- 导航网格：使用凸多边形覆盖可行走区域，多边形之间共享边表示可通行。路径质量高，内存效率好，是目前 3D 游戏的主流方案。引擎如 Unity 或 Unreal 都内置了自动生成导航网格的工具。
1.2 A* 寻路算法原理
A* 是游戏中最流行的启发式搜索算法，能在网格或导航网格上高效找到最短路径。它的核心思想是评估每个待探索节点的代价：
f(n) = g(n) + h(n)
- g(n)：从起点到节点 n 的实际路径成本（移动距离、消耗时间等）。
- h(n)：启发函数，估算从节点 n 到终点的剩余成本。它必须是被低估的（不大于实际成本），以保证算法找到最优解。常用欧几里得距离或曼哈顿距离。
- f(n)：节点 n 的综合优先级，算法每次扩展 f 值最小的节点。
算法步骤简述：
- 将起点加入开放列表（待探索节点）。
- 从开放列表取出 f 值最小的节点作为当前节点。
- 若当前节点是终点，回溯路径并结束。
- 遍历当前节点的相邻节点，计算它们的 g、h、f 值。若相邻节点未在开放列表或找到了更小的 g 值，则更新其父节点与成本，并加入开放列表。
- 将当前节点移入关闭列表，重复步骤 2 直到路径找到或开放列表为空（不可达）。
1.3 实践要点
- 动态障碍处理：当环境改变时，需要局部更新导航网格或使用分层路径规划（全局粗规划 + 局部动态避障）。
- 平滑路径：A* 输出的路径常含有折角，可通过弦截法（拉线法）或贝塞尔曲线进行平滑，使移动更自然。
- 群体移动：结合流场寻路或多智能体碰撞避免算法（如 RVO），避免多个单位堆叠。
2. 有限状态机：实现清晰的逻辑切换
有限状态机（FSM）是最简单直观的行为建模工具。它将 NPC 的行为分解为若干个独立状态，并定义了状态间的转换条件。
2.1 基本概念
- 状态：代表一种特定的行为模式，如“巡逻”、“追击”、“攻击”、“死亡”。每个状态通常包含
Enter()、Update()、Exit()三个生命周期函数，分别处理初始化、持续逻辑和清理工作。 - 转换：从一个状态指向另一个状态的有向连线，附带一个布尔条件。当条件满足时，状态机立即切换到目标状态。
- 状态机本身：负责存储所有状态、当前状态，并在每帧检查转换条件，执行状态生命周期。
2.2 设计实例：守卫 AI
一个简单的守卫 NPC 状态机可能包含：
- 巡逻状态：沿预设路径点循环移动，持续进行视野检测。
- 转换条件：发现敌人 → 切换到 追击状态。
- 追击状态：向最后发现敌人的位置移动，若到达该位置未发现敌人则进入搜索状态。
- 转换条件：敌人进入攻击范围 → 切换到 攻击状态；
- 转换条件：丢失视野超过 5 秒 → 切换到 搜索状态。
- 攻击状态：播放攻击动画，造成伤害。
- 转换条件：敌人死亡或脱离半径 → 切换到 巡逻状态。
- 搜索状态：在最后目击区域附近徘徊数秒。
- 转换条件：再次发现敌人 → 切换到 追击状态；
- 转换条件：超时 → 切换到 巡逻状态。
2.3 优缺点及应对
- 优点：简单直观、易于调试、性能优秀。状态数量少时维护性极佳。
- 缺点：状态增多后转换关系会爆炸式复杂，难以复用逻辑，不适合行为丰富、频繁组合的设计。
- 改进：可引入 层次状态机，将具有共享转换的状态组合成一个超级状态，减少重复连线；或使用下节的行为树。
3. 行为树：构建可扩展的决策逻辑
行为树是一种层次化、模块化的决策结构，尤其适合需要复杂逻辑和频繁迭代的行为设计。它由节点构成一棵树，自上而下逐帧执行。
3.1 核心节点类型
- 组合节点：控制子节点的执行顺序与逻辑。
- 序列：从左到右依次执行子节点。全部成功才返回成功；任一失败则停止并返回失败。
- 选择：从左到右依次执行子节点。任一成功则停止并返回成功；全部失败则失败。常用于实现备选行为。
- 并行：同时执行所有子节点，根据策略决定何时返回（如要求全部成功、任意一个成功等）。
- 装饰节点：只有一个子节点，用于修改子节点的行为或结果。如 逆变（成功变失败）、重复（循环执行）、限制（设定冷却时间）等。
- 叶节点：实际执行动作或判断条件。
- 条件：检查某个游戏世界状态（如“是否有敌人？”，“血量<30%？”），返回 Success 或 Failure。
- 动作：执行具体行为（如“移动到目标”，“播放动画”，“扣血”），返回 Success、Failure 或 Running（需多帧完成时）。
3.2 执行流程与状态
树从根节点开始向下遍历，每帧传递 tick 信号。节点执行后必须返回三种状态之一：成功、失败、运行中。节点逻辑示例：
- 序列节点：子节点 A → 成功 → 子节点 B → 运行中 → 序列返回运行中。下一帧会从 B 继续。
- 选择节点：子节点 A → 失败 → 子节点 B → 成功 → 选择返回成功，不再执行子节点 C。
3.3 设计实例：智能战斗 NPC
用行为树构建一个战士 AI 的决策子树：
根（选择）
├─ 序列（生存分支）
│ ├─ 条件：血量 < 20%？
│ └─ 动作：寻找掩体并恢复
├─ 序列（战斗分支）
│ ├─ 条件：有敌人在攻击范围内？
│ ├─ 动作：播放攻击动画
│ └─ 动作：造成伤害
├─ 序列（追击分支）
│ ├─ 条件：有敌人目标？
│ ├─ 动作：移动到目标附近
│ └─ 动作：嘲讽表情
└─ 动作：巡逻预设路径
通过这种树形结构，行为按优先级排列：生存 > 攻击 > 接近敌人 > 巡逻。后续若想加入“使用技能”，只需在战斗分支前插入新的序列选择分支，而不影响其他逻辑，完美体现模块化思想。
3.4 行为树 vs 状态机 选择建议
- 状态机：适合行为较少、状态切换逻辑清晰的小型 AI，如门、简单机关、剧情触发 NPC。
- 行为树：适合行为丰富、需要频繁调整、由大量条件组合驱动的角色 AI，如敌人战斗 AI、玩家协助 NPC。引擎如 Unreal 和 Unity（通过插件或自研）都提供了可视化行为树工具。
4. 三者的协同工作
在实际项目中，这三种技术不是孤立的，而是分层协作：
- 行为树或状态机作为顶层决策系统，负责决定“做什么”。例如“追击敌人”或“巡逻”。
- A* 寻路系统作为服务层，被动作节点调用。例如“移动到目标”动作内部会向寻路系统请求一条从当前位置到目标的路径。
- 导航网格为寻路提供可走区域数据，同时可用于位置有效性判断（如寻找最近的掩体位置）。
一个典型的执行流程：行为树的“移动到掩体”动作触发寻路系统，寻路系统基于导航网格计算出路径，然后由移动组件每帧沿路径移动，到位后动作返回成功，决策继续。
5. 实战注意事项与性能建议
- 分帧计算寻路：避免在同一帧内处理大量寻路请求，可将请求分散到多帧，或采用异步路径查找。
- 空间分割：使用四叉树、八叉树等空间结构加速最近节点查找和视野检测。
- LOD 系统：远处 NPC 可以降低 AI 更新频率，甚至使用更简单的决策模型。
- 可调试性：开发期间为行为树和状态机提供可视化运行时状态，将极大提高调试效率。记录节点执行历史与转换日志。
掌握寻路、状态机与行为树，你将能为大多数游戏类型设计出可信且可控的 AI 行为。从简单的敌人巡逻到复杂的 BOSS 战逻辑，这些基石技术都不可或缺。建议在引擎中动手实现一个完整的守卫 AI 示例，亲身体验从纸面设计到代码落地的全过程。