基础 AI

June 25, 2023About 21 min

基础 AI

游戏AI是玩法系统重要的组成部分，其中最基本的功能是选择目的地进行**导航(navigation)**。

导航算法构成的三个部分：

Map Representation：对世界需要有不同的表达(节点，点线面), 有这个才能描述当前在那，目标在那。
Path finding: 通过地图表达的信息寻找到从起点到目的地的最短路径。
Path smoothing：有时还需要结合一些其它算法来获得更加光滑的路线。

Map Representation

因此我们首先需要考虑游戏中如何来表达地图，我们可以认为地图是玩家和NPC可以行动的区域。
游戏中常见的地图形式包括**路点网络图(waypoint network)、网格(grid)、寻路网格(navigation mesh)以及八叉树(sparse voxel octree)**等。

同一块Walkable Area对于不同的AI的影响不同，比如骑马的AI可以跨越步行AI不可通过区域。

Waypoint Network 路点网络图

waypoint network是早期游戏中最常用的地图表示方式。
我们可以把地图上的路标使用节点来表示，然后可通行的节点使用边来连接起来就形成了一个网络结构。

当玩家需要进行导航时只需要选择距离起点和目的地最近的两个路标，然后在网络图上进行导航即可。
和搭乘地铁的方式很相似。

waypoint network的优势在于它非常易于实现，而且我们有成熟的路径搜索算法可以直接应用在网络图上；
但它的缺陷在于路网图需要不断地和开发中的地图进行更新，而且使用路网进行导航时角色会倾向于沿路径中心前进而无法利用两边的通道。
因此在现代游戏中路网的应用并不是很多。

Grid 简单网格

路网把空间抽象成一个个点，同样的网格就是把空间抽象为连接的格子。
常用的网格地图包括方格地图、三角形地图或是六边形地图等。

使用网格来表示地图时只需要把不可通行的区域遮挡住就可以了，因此网格可以动态地反映地图环境的变化。

显然网格地图同样非常容易实现，而且支持动态更新，也便于调试(比如用不同颜色输出可通行，不可通行区)；
而它的缺陷在于网格地图的精度受制于地图分辨率，大量的格子比较占用存储空间，效率低;
最严重的问题是网格很难表示重叠区域(上下层)各自的连接关系。

为了克服网格地图的这些问题，人们开发出了寻路网格这样的地图表达形式。
在寻路网格中可通行的区域会使用多边形来进行覆盖，这样可以方便地表达不同区域直接相互连接的拓扑关系。

寻路完成后会形成一个多边形走廊，如图右上
在寻路网格中要求每个多边形都必须是凸多边形，这样才能保证角色在行进中不会穿过其他区域，如图右下。
凸多边形还能确保每个多边形之间有且只有一条共享的边(Portal)

寻路网格是现代游戏中广泛应用的地图表达形式，
而它的缺陷主要在于生成寻路网格的算法相对比较复杂，而且它无法表达三维空间的拓扑连接关系。
--- 实际生成的就是一个二维空间的可通行区域，只能贴地走。

Sparse Voxel Octree 稀疏体素(空间)八叉树

如果要制作三维空间中的地图则可以考虑八叉树这样的数据结构。
在空间不停的求交，发现voxels有其他的occlude(阻塞物),然后进一步细分直到没有或者误差度小于某个阈值。
存储很废，寻路也很麻烦

Path Finding 寻路

得到游戏地图后就可以使用寻路算法来计算路径了，当然无论我们使用什么样的地图表达方式我们首先都需要把游戏地图转换为拓扑地图，然后再使用相应的算法进行寻路。

寻路的要点是先求取是否能到达终点，然后找到近似的最优路径。
是在一个双向的有环图上如何寻路的问题，如右图

Depth-First Search 深度优先

深度优先：从起点开始，一步步地尝试向相邻节点前进，直到找到终点或者无法继续前进为止。
如果无法继续前进，则回溯到上一个节点，尝试其他未访问的路径，直到找到解决方案或确定无解决方案。
可以通过递归或者栈来保存访问的路径，可能存在栈溢出的问题。

Breadth-First Search 广度优先

广度优先: 从起点开始，先访问它的所有相邻节点，然后再访问这些相邻节点的相邻节点，以此类推直到找到终点或者所有节点都被访问为止。
可以通过队列顺序保留访问节点，适合求解最短路径问题。

Info

深度优先、广度优先算法其实没有办法计算加权最短路径。它们的开销也很大.

Dijkstra Algorithm 迪杰斯特拉算法

https://zhuanlan.zhihu.com/p/346558578 // 最短路径算法

通过Dijkstra计算图G中的最短路径时，需要指定一个起点D(即从顶点D开始计算)。

此外，引进两个数组S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点D的距离)。
初始时，数组S中只有起点D；数组U中是除起点D之外的顶点，并且数组U中记录各顶点到起点D的距离。如果顶点与起点D不相邻，距离为无穷大。
然后，从数组U中找出路径最短的顶点K，并将其加入到数组S中；同时，从数组U中移除顶点K。接着，更新数组U中的各顶点到起点D的距离。
重复第4步操作，直到遍历完所有顶点。

**A Star A*算法**

真实世界中搜索路径往往是大致方向进行，人通常是通过启发式算法去判断的，
在A star算法中通过引入一个启发式函数来控制节点访问的倾向性，使得路径的搜索会更倾向于访问目标点。

在网格地图中最简单的启发函数就是计算棋盘距离(dx+dy)

而在Navigation Mesh中则可以使用欧拉距离作为启发函数。

当找到起始点到终止点的Polugon通道后怎么确认最后路径：终点连接线会超过Polugon的距离

工业上的做法是通过共享边(Portal)的中点连接形成路径 --- 这个就是当前开销
这里的启发算法假设没有阻碍物的的直线路径

从通过场景的NavMesh进行A*搜索的例子

显然启发式算法的设计对于最终计算得到的路径会产生显著的影响。
当启发函数的值过低时可能会需要更多次循环才能寻找到路径，而当启发函数值过高时则可能无法找到最短路径。
因此在实际应用中需要进行一定的权衡。

Path Smoothing

直接使用寻路算法得到的路径往往包含各种各样的折线不够光滑，因此我们还需要使用一些路径平滑的算法来获得更加光滑的路径。

游戏导航中比较常用漏斗(funnel)算法来对折线路径进行平滑，它不仅可以应用在二维平面上也可以应用在寻路网格上。

算法维护一个以路径起点为中心的漏斗形状，并根据收缩后的路径在漏斗上移动。
在每次移动时，算法会检查当前路径的点是否在路径上，如果是则继续前进，否则会寻找漏斗边缘上的点来重新构建漏斗，
最终，算法找到的最短路径就是漏斗的中心线。

示例中可以看到按照Mesh的路径生成的漏斗逐渐变小(无法包含新的Mesh)，确定找不到路后从新点生成新的漏洞直到找到终点。
3D空间计算更复杂，需要注意Mesh是否在同一平面。

NavMesh Generation

如何从游戏地图上生成寻路网格是一个相对困难的问题, 如下图：

蓝色部分是生成出来的walkable area, 受max slope的影响

生成NavMesh的大致方法

找到所有可通行体素(walkable voxel)的边缘体素(edge voxel).
edge voxel指周围存在不可通行区域，如图右的灰色区域。
计算每个体素到边界的距离, 生成distance field(如右图，越黑越接近中心区)

洪水算法(Watershed Algorithm): 把中心的点(距离最远)作为种子，进行细胞("洪水")扩散，
当交叠到一起的时候就生成walkable area的空间划分, 参考下图：

确保3D空间扩散的时候，没有重叠的体素

简单来说会尽可能把空间划分成一块块凸的多边形区域

Info

NavMesh这个生成方法的缺陷是每次变化都需要重新生成，没办法继承。

除此之外我们还可以给不同类型多边形上设置不同的flag来触发不同的动画、声效以及粒子效果。

对于动态的环境我们可以把巨大的场景地图划分为若干个tile。
当某个tile中的环境发生改变时只需要重新计算该处的路径就可以得到新的路径。

需要注意的是使用自动化算法生成的寻路网格是不包括传送点这样的信息的，有时为了提升玩家和场景的互动我们还需要手动设置这些传送点。
当然这会导致寻路算法更加复杂。

Steering

在得到最优路径后就可以根据路径来控制角色前进了。
但实际游戏中物体可能受到自身的运动学约束使得无法严格按照计算出的路径进行运动，这一点对于各种载具尤为明显。
因此还需要结合steering算法来调整实际的行进路径。

Info

这个约束可能会出现意外，物体按照新的轨迹移动时候可能进入不可通行区而被卡住。

steering算法的三种基本行为：

Seek/Flee --- 追赶和逃脱
VelocityMatch -- 通过加减速准确停目标点, 比如火星探测器登陆
Align --- 保持朝向一直，比如炮台旋转瞄准

Seek/Flee

seek/flee的要求是根据自身和目标当前的位置来调整自身的加速度从而实现追赶或是逃脱的行为，像游戏中的跟踪、躲避或是巡逻等行为都可以使用seek/flee来实现。

速度场/方向场(vector field)可模拟群体的seek/flee

VelocityMatch

VelocityMatch的目的是利用当前自身和目标的相对速度以及匹配时间来进行控制，使得自身可以按指定的速度到达目标位置。
在游戏中如果目标移动后，可基于Tick后的变化做分布式运算。

Align

Align则是从角度和角加速度的层面进行控制，使得自身的朝向可以接近目标。

Crowd Simulation

群体模拟(crowd simulation)是游戏AI必须要处理的问题。
在游戏场景中往往会具有大量的NPC，如何控制和模拟群体性的行为是现代游戏的一大挑战。

群体模拟的三种方法

Microscopic Models 微观模型

微观方法的思想是对群体中每一个个体进行控制从而模拟群体的行为，通常情况下我们可以设计一些规则来控制个体的行为。
比如鱼群，距离太近会互斥，距离太远会靠拢，非常像弹簧，另外它们的头部朝向会逐渐靠向相同方向。
问题是结果不可控，存在随机性。

Macroscopic Models 宏观模型

宏观方法更High Level, 思想是在场景中设计一个势场或流场来控制群体中每个个体的行为。
比如虚幻5 MassAI的Demo展示城市街道中行人按规则走来走去。

定义各种Lan --- 人行道，各种车道
把区域分成很多Zone Graph
人在空间中沿着Lan去移动

Mesoscopic Models 混合模型

混合模型则综合了微观和宏观两种模型的思路，它首先把整个群体划分为若干个小组，然后在每个小组中对每个个体使用微观模型的规则来进行控制。
这样的方法在各种RTS游戏中有着广泛的应用。
比如星际中选中一些小兵攻击一个目标点，移动过程中整体是基于Lan移动的，但每个小兵是自主决策的

Collision Avoidance

群体模拟中的一大难点在于如何保证个体之间不会出现碰撞的问题。
比较常用的方法是对每个个体施加斥力来控制它的运动，这样就可以操纵群体的运动行为。
大量个体的寻路计算很废，给所有障碍物增加distance field(距离场), 当个体距离距离场越近的时候，产生的反向斥力会增加
这种情况给一个大致方向，群体就可以模拟出一个真实的行为，如下图示例:

办公楼发生火灾的人群模拟就是通过Force-base的方式来模拟的，个体会避开墙(障碍)和人来行走。

另一种处理的方法是基于速度障碍(velocity obstacle, VO)来进行避免阻挡。

VO的思想是当两个物体将要发生碰撞时相当于在速度域上形成了一定的障碍，因此需要调整自身的速度来避免相撞。

当参与避让的个体数比较多时VO会产生整体混乱，此时可以使用ORCA等算法进行处理。
把空间上的所有速度在假定时间内形成速度空间(一个羽毛球形状的锥形区域)，通过闵可夫和求对所有节点公平的子节点.

Sensing(Perception) 感知世界

对世界的感知(sensing)是AI做出行为决策的依据，
根据获得信息的不同我们可以把感知的内容分为内部信息(internal information)和外部信息(external information)。

内部信息是AI自身的状态。这些信息一般可以被AI直接访问到，而且它们是AI进行决策的基础。

而外部信息则主要包括AI所处的空间中的信息，它会随着游戏进程和场景变化而发生改变。

静态的分散空间信息

通行区域 Navigation Data
战术价值地图 Tactical Map -- 方便AI在通行区域中优先控制关键点

influence map，影响力图或者热力图，场景的变化会直接反映在influence map上。

当AI决策时会同时考虑自身的状态并且查询当前的influence map来选择自身的行为。
比如当空血的AI从A点到B点，如果从Influence map中检查到危险的区域就会避开这个区域。

Sight Area 也是影响AI决策的外部影响之一
在引擎层面需要提供通用扩展接口让角色能访问这些数据

对世界的感知(sense)是AI做决策的重要依据
游戏AI进行感知时需要注意不能假设AI可以直接获得所有游戏的信息，而是希望AI能够像人类(仿生)一样只利用局部感知的信息来进行决策。
AI获取的大量外部信息还经常需要Query来获取关键信息
因此在引擎层需要处理sense的精度避免带来性能瓶颈

Classic Decision Making Algorithms 经典决策算法

在上面这些知识的基础上就可以开始构建游戏AI系统了。
游戏AI算法的核心是决策(decision making)系统，经典的决策系统包括有限状态机(finite state machine, FSM)和行为树(behavior tree, BT)两种。

有限状态机和行为树是经典的前向算法，下面是以目标为驱动的反向算法：

HTN: 层次任务网络
GOAP: 基于目标的行为计划系统
MCTS: 蒙特卡洛搜索树
DL: 深度学习

Finite State Machine

在有限状态机模型中我们认为AI的行为可以建模为在不同状态之间的游走，不同状态之间的切换称为转移(transition)。
以吃豆人游戏为例(如下图），游戏AI可以使用一个包含3个状态的状态机来表示。

有限状态机的缺陷在于现代游戏中AI的状态空间可能是非常巨大的，因此状态之间的转移会无比复杂。

为了克服有限状态机过于复杂的问题，人们还提出了hierarchical finite state machine(HFSM)这样的模型。
在HFSM中我们把整个复杂的状态机分为若干层，不同层之间通过有向的接口进行连接，这样可以增加模型的可读性。

层次有限状态机把状态机通过分层处理，每层之间有接口，只通过有向接口联系，内部维持一个相对可控的状态。

好处：增加了状态机可读性
坏处: 很难直接从某层的子状态切换到另外一层的子状态，除非加特别的处理(飞线)

Behavior Tree

状态机是整个AI逻辑的抽象，但不符合人的真实思考方式。
人脑的决策过程是根据情况分支思考，会生成一个Decision Tree。
行为树就是用决策树的形式化分支逻辑把该做各种行为表达出来。

行为树中的执行节点(excution node)表示AI执行的过程，它包括条件判断以及具体执行的动作两种叶节点。

Condtion Node判断的信息包含自身状态，以及通过AI Sense(perception)系统获取的外部信息
Action Node的动作会有三种状态，成功，失败和运行中

行为树中的另一种节点是控制节点(control node)，它用来表示决策过程的控制流。
control node包括sequence、selector、parallel以及decorator等几种。

sequence是表示对当前节点的子节点依次进行访问和执行，一般可以用来表示AI在当前状态下的行为计划。
sequence就是一个最简单的Task系统
如右图，当任一节点执行返回失败的时候，sequence的剩下部分会跳过，这样避免状态机的飞线连接.
当所有子树都返回执行成功(没有在运行中), 整个sequence才会被认为成功完成，然后可能产生其他变化。