GAMES104：游戏引擎 Gameplay 玩法系统：基础 AI（上）

课程：GAMES104《现代游戏引擎：从入门到实践》
第 16 讲（上）：游戏引擎 Gameplay 玩法系统：基础 AI
本地视频时长：约 1 小时 8 分钟

一、本讲的核心：让角色在世界中可靠移动

基础游戏 AI 的第一类问题是导航：给定起点、终点和环境约束，如何找到一条角色确实能够行走的路径，并让角色以自然、稳定的方式沿路移动。

寻路并不等价于在画面上画一条最短线。引擎需要先把连续、复杂、可能动态变化的三维世界转换为适合搜索的可通行表示，再在该表示上搜索、平滑路径，并处理角色尺寸、坡度、障碍、动作能力和运行时更新。

二、学习目标

• 了解游戏 AI 的基础领域与导航问题的定位。
• 比较路点网络、网格、导航网格和稀疏体素八叉树等空间表示。
• 理解 BFS、Dijkstra 与 A* 在路径搜索中的差异。
• 掌握路径平滑、NavMesh 构建、区域标记与动态更新的工程思路。

三、基础 AI 的问题范围

游戏 AI 不只包含寻路，还常涉及：

领域	要解决的问题
导航 Navigation	从当前位置到目标位置找到可行路径
转向 Steering	在局部环境中平滑避障、追逐或保持队形
群体模拟 Crowd Simulation	让多个角色互相避让且行为稳定
感知 Sensing	让角色获得视野、听觉、距离或威胁信息
决策 Decision Making	根据目标、状态和环境选择动作

本讲聚焦导航。导航系统提供“该往哪里走”的全局结果；转向和群体系统通常负责“眼前这一小段如何走得不撞人”。将两者区分，能避免把全局路径搜索错误地承担为局部运动控制。

四、先把世界变成可搜索的可通行空间

1. 为什么不能直接在原始场景模型上寻路

游戏世界由渲染网格、碰撞体、地形、动态物体和规则区域组成。直接对所有三角形或物理形状做搜索，数据量过大，也难以反映角色的真实运动能力。

可通行空间的表示需要考虑：

• 角色半径、高度和碰撞外形。
• 可攀爬高度、最大坡度、跳跃或飞行能力。
• 静态建筑、地形和禁入区域。
• 运行时出现或消失的动态障碍。

对玩家和 AI 使用同一套移动能力模型通常最容易保持一致，但成本可能很高；实际项目会根据 NPC 类型和玩法需要使用不同精度的可通行空间。

2. 四种常见地图表示

表示	基本单位	优点	局限
路点网络	预设节点和连边	实现简单，适合固定路线	覆盖不连续，需要人工布点
规则网格	二维或三维栅格单元	数据结构统一，易于搜索和动态修改	分辨率影响精度与内存，路径易呈锯齿
导航网格 NavMesh	连通的可通行凸多边形	空间利用率高，路径质量好	构建更复杂，三维重叠空间需额外处理
稀疏体素八叉树	按空间自适应细分的体素	适合稀疏三维空间和分层查询	实现、更新与存储管理复杂

选择表示时，首先问角色如何运动：地表行走、自由飞行、攀爬、跳跃或多层建筑，都会改变最合适的数据结构。

五、路点、网格与导航网格

1. 路点网络

路点网络将地图抽象为图：路点是节点，可直达关系是边。路径搜索只需要在节点图上进行，因此实现直观、计算成本低。

它适合巡逻路线、固定道路和小规模关卡；不足是路点布局决定了所有路径质量。若节点稀疏，角色会绕远；若节点太密，人工维护与搜索成本都会上升。

2. 规则网格

网格把空间离散成等大小单元，角色可从一个单元移动到相邻单元。它可以自然支持代价地图：泥地、道路、危险区和拥挤区域可拥有不同移动代价。

网格的关键取舍是分辨率：

• 网格过粗会丢失窄路、边缘和复杂地形细节。
• 网格过细会增大内存、搜索节点数和重建成本。
• 三维网格还能表达上下重叠空间，但复杂度明显提升。

3. 导航网格

导航网格由可通行区域的凸多边形组成。凸多边形的任意两点之间都可以直接连线而不离开区域，因此很适合连接、搜索和路径平滑。

相邻多边形通过共享边连接，共享边常被称为通道。角色从一个多边形跨过通道进入下一个多边形，最终形成一串区域路径。

导航网格的优势包括：

• 使用较少节点覆盖大面积可行走区域。
• 路径更贴合真实地形，而不是受网格方向限制。
• 可为不同区域附加类型和代价，例如道路、泥地、危险区。

它的局限是构建流程更复杂，对桥梁、楼层、洞穴等重叠空间也需要设计专门的连接关系。

4. 稀疏体素八叉树

稀疏体素八叉树以递归方式细分空间：空旷区域可用大节点表示，复杂边界附近才继续细分。它比均匀三维网格更节省空间，适合自由飞行、太空或高度立体的导航场景。

但这种表示的数据结构更复杂，邻域查询、路径连接和动态更新都需要更谨慎的实现。它并不是地表 NPC 寻路的默认选择，而是针对三维可通行空间的专门方案。

六、将寻路抽象为图搜索

无论地图如何表示，最终都可以形成图：

$$ G = (V, E) $$

其中 $V$ 是可达位置、区域或状态的集合，$E$ 是它们之间允许移动的连接。每条边可带有移动代价，寻路的目标是在满足约束的前提下寻找总代价较低的路径。

1. 广度优先搜索

广度优先搜索按离起点的层数扩展节点。若所有边代价相同，它能得到最少步数路径。

优点是简单、适合无权图；缺点是面对不同地形代价或较大搜索空间时，会扩展大量与目标无关的节点。

2. Dijkstra 算法

Dijkstra 算法总是优先扩展当前已知总代价最小的节点，因此适用于边代价非负且不相同的图。

它能得到最短路径，但不知道目标在哪个方向。对于大地图，算法会从起点向许多方向均匀扩张，可能做出大量不必要工作。

3. A* 算法

A* 在已走代价 $g(n)$ 的基础上加入到目标的估计代价 $h(n)$：

$$ f(n) = g(n) + h(n) $$

算法优先处理 $f(n)$ 较小的节点，因此既考虑已经付出的成本，也朝目标方向搜索。若启发函数不高估真实剩余代价，即：

$$ h(n) \leq h^*(n) $$

其中 $h^(n)$ 是从节点 $n$ 到目标的真实最小代价，A 可以在保持最优性的同时显著减少搜索范围。

启发函数设计是 A* 的关键：太弱时接近 Dijkstra，太激进时虽然更快，却可能失去最优路径保证。对地表移动，欧氏距离或曼哈顿距离常是自然起点；对 NavMesh，还需考虑多边形中心、顶点或通道中点等代表位置的误差。

七、从粗路径到可行走路径

1. 为什么搜索结果需要平滑

网格或区域图搜索得到的往往是一串离散节点。直接让角色依次经过这些节点，会产生明显折线、无意义绕点和生硬转向。

路径平滑的目标是：在不穿过障碍的前提下，移除冗余转折，让角色沿更短、更自然的轨迹前进。平滑应建立在可通行空间约束上，不能只做视觉插值，否则角色可能穿墙或越界。

2. Funnel 算法

在 NavMesh 中，粗路径是一串相邻多边形及其通道。Funnel 算法将通道两侧边界看作逐渐收缩的漏斗：

1. 从起点向后依次处理每个通道。
2. 维护当前漏斗的左右边界。
3. 当新的边界使漏斗交叉时，确定一个必要转折点。
4. 继续处理直到终点。

该方法能在多边形通道内得到较短且平滑的路径，避免把每个多边形中心都当作必经点。

3. 路径并非移动的全部

全局路径只提供方向。角色实际移动仍需处理速度、转身、碰撞、局部避障、动态物体、动画步态和重新规划。一个良好的导航系统需要在“路径不可行”时能检测原因，并选择等待、绕行、局部躲避或重新寻路。

八、NavMesh 的构建与运行时能力

1. 从场景到导航网格

NavMesh 构建通常包含以下概念步骤：

1. 从碰撞场景或可行走几何提取静态环境。
2. 将空间体素化或栅格化，判断障碍和可通行表面。
3. 按角色尺寸、坡度和高度差过滤不可通行区域。
4. 划分连通区域，并生成简化后的多边形网格。
5. 建立相邻多边形连接与查询数据。

构建过程本质上是在把复杂视觉几何转换为角色能力约束下的移动空间。因此更换角色尺寸、最大坡度或跳跃能力后，往往需要重新生成或选择不同的导航数据。

2. 区域、标记与代价

导航多边形可携带类型标记，例如道路、草地、水面、危险区或跳跃区域。查询时可以据此限制角色可走区域，或调整路径代价。

例如人类 NPC 可以避开深水，飞行单位可忽略地面障碍，警卫可优先走道路。相同的 NavMesh 结构通过不同过滤器与代价配置，可服务多个角色类别。

3. Tile 化与动态更新

大地图通常将导航数据划分为多个 Tile。局部建筑物移动、门开关或地形修改时，只重建受影响 Tile，而不是重算整个世界。

Tile 大小存在取舍：

Tile 较大	Tile 较小
管理简单，边界较少	局部更新更快，修改影响范围更小
单次重建成本高	Tile 数量、边界连接和管理成本更高

动态障碍不一定都要重建 NavMesh。短时变化可通过局部避障、阻挡体或路径代价修正处理；长期地形变化才更适合触发导航数据更新。

九、导航系统的工程原则

1. 先定义角色的移动能力，再选择空间表示和构建参数。
2. 让全局寻路、局部避障与角色运动各自承担明确职责。
3. 为路径搜索提供符合地图几何和玩法规则的代价与启发函数。
4. 使用平滑与通道算法改善路径，但始终保持在可通行空间内。
5. 用区域标记、Tile 化和增量更新支持多角色类型与动态世界。

十、要点回顾

1. 导航的第一步是把复杂场景抽象为与角色能力匹配的可通行空间。
2. 路点、网格、NavMesh 与稀疏体素八叉树适用于不同维度、精度和动态性要求。
3. BFS、Dijkstra 和 A* 的差异，核心在于如何利用边代价与目标方向信息。
4. A* 通过 $f(n)=g(n)+h(n)$ 兼顾已走成本和目标估计；合适的启发函数决定效率与最优性。
5. NavMesh 的价值不只在搜索，还在于通道平滑、区域语义、增量构建和对动态世界的适应。

参考资料

• 第 16 节（上）：游戏引擎 Gameplay 玩法系统：基础 AI｜GAMES104-现代游戏引擎：从入门到实践（Bilibili 合集第 19 集）