本文将简要介绍一些游戏引擎中Gameplay玩法系统中有关AI的基础部分，包括：

• 寻路系统；
• 转向系统；
• 群体模拟；
• 感知；

寻路系统

要实现一个寻路系统，需要完成如下三步：

1. 表达地图
2. 生成路线
3. 平滑路线

表达地图

首先要告诉AI地图上哪些地方可达：

接下来需要选择表达的形式：

路径点网络

用于早期游戏。通过在地图上人为设置一些重要路径点和边界点，进而插值出一些中间点。AI可以通过这些点达成寻路的目的。

它的优缺点如下：

网格

可以用均匀网格将可达区域分开，通过一些寻路算法让AI在网格间行走。

使用网格进行寻路的一个优点就是适应动态环境，场景发生变化时，只需更新一下网格中的障碍物信息即可。

网格的其他优缺点如下：

NavMesh

前面两种方法忽略了地图的立体性，如果可达区域是立体重叠的，AI可能会不知道怎么走。而导航网格体NavMesh则解决了这个问题，它将场景可达区域用一个个凸多边形覆盖，让AI更自由。

为什么是凸多边形，因为凹多边形会让AI行进路线更曲折，且容易让它走到非可达区域。

接下来看看导航网格体是如何生成的。首先要对地图进行体素化，计算可达区域（蓝色）：

然后要识别可达区域的边界，这需要计算SDF，并通过洪水算法得到边界：

这样就能得到对可达区域的合理划分：

别忘了NavMesh由凸多边形组成，还需要进一步将可达区域进行细分：

此外，高级的NavMesh还拥有如下特点：

1. 自定义标识：用户可以对NavMesh进行自定义标识，例如草原河流。
2. 分块：大世界中只有一小部分场景出现变化，只需更新那一块的NavMesh即可，不需要更新整个地图的NavMesh。
3. 不同Mesh的联系：允许AI通过跳跃或传送的方式进行寻路，而不是单纯的走路。

导航网格体的优缺点如下：

空间八叉树

前面的方法不能支持空中AI的寻路，这需要在空间中用八叉树划分才能实现。

生成路线

接下来需要在这些地图表达中找到一条从起点到终点的路线，这是一个图论中最短路径的问题。

常用的寻路算法有Dijkstra算法，A*算法等，这里看看A*算法。

A*算法和Dijkstra算法相似，但它是一个启发式算法，性能比较好。

在路线代价的计算中，它不仅要计算从起点到当前节点的具体代价，还要估算当前节点到终点的代价（启发函数），找到终点后算法就结束了。

启发函数影响A*算法的速度和精准度，需要在二者中去平衡。

在四向移动的前提下（如网格），可以用曼哈顿距离充当启发函数：

对于在多边形走廊中寻路的NavMesh，路径点是各多边形边的中点，启发函数是该点和终点的欧几里得距离。

平滑路线

生成最短路线后，为了让AI表现得更自然，需要对路线进行平滑操作。常用的算法之一就是Funnel算法，它通过将扇形视线覆盖在路径上，不断减少覆盖范围尽可能走直线，如果覆盖不到下一个路径点说明该转弯了。

转向系统

TODO

参考资料

• GAMES104 (boomingtech.com)

待阅读的资料