游戏中的AI算法总结与改进_碰撞寻路

(1) 有限状态机：

 

3.1 A Star寻路算法

        A Star算法又形象的称为A*算法，是一种启发式函数路径计算搜索算法，算法中通过设计合理的启发函数可以大大减少寻路过程中的计算量，提高计算效率，而估计不精确是启发式函数的特点，因此使用A*算法计算的路径可能不是人所理解的最优路径，但A*可以高效的提供一种在游戏中相对合理的路径，在游戏寻路中应用广泛。

 

1. A*中的结点（Node）

        结点是A*算法计算的基本单位。由于A*算法可应用于多种导航图，在不同的导航图中结点的表示各不相同，在多边形导航图中一个多边形为一个A*结点，可视点导航图中每一个可视点为一个A*结点，删格化导航图中每一个矩形格子为一个A*结点。

 

2. 估价函数

        估价函数用于评价一个结点被选做路径点的概率，其利用了结点自身与起始点位置关系的信息，启发算法搜索较合理的路径，路径即相邻结点的集合序列，估价函数表达式如下：

 F(N) = G(n) + H(n)

        公式中的F(n)表示第n个结点的估价值，G(n)表示结点按照某种距离规则到起点的距离值，H(n)表示结点按照某种距离规则到终点的距离值，因此估价值F(n)越小，代表路径行走消耗越少，则被选为路径点的概率越大。

        距离计算规则主要有曼哈顿距离、欧几里得距离和对角线距离三种。曼哈顿距离指的是两点之间水平距离与竖直距离之和，欧几里得距离指的是两点之间的几何距离，对角线距离指的是水平距离和竖直距离中的较大者。

在P1、P2两点之间构成的直角三角形中，假设水平直角边长度为A，竖直直角边长度为B，斜边距离为C，则：

曼哈顿距离： D1 = A + B

欧几里得距离：D2 = C

对角线距离： D3 = max{A,B}

在算法的实际应用中，根据[13]沈健的研究结论欧几里得距离在寻路计算效率上表现更佳，具体根据不同情形常常进行混合应用以更好提高计算效率和算法适应性。

 

3. A*算法的执行过程

算法维护Open表和Closed表两个表，前者存放可能的待访问的结点，后者不断加入估价计算后的结点。

(1) 算法初始将起点加入Closed表，其估价函数值：F(0) =H(0), 其中G(0) = 0,为其到自身的距离。

(2) 然后将所有与当前点(暂时是起点)相邻的结点加入Open表，如果已经加入则不操作。在当前结点估价函数值的基础上，累加计算所有相邻结点的F、G、H值，如果已在Closed表中的结点的新的估价值比之前的小，则更新为更小的值，将F值最小的结点选为新路径点，设置成当前结点的子节点，新路径点继续做为当前结点继续遍历相邻的结点。

(3) 重复(2)的操作当终点加入Closed表时，算法结束，根据父子结点的关系可得到最终路径，如果Open表为空时终点依旧不在Closed表中，则搜索失败。

(4) 以上算法执行过程中障碍物结点不加入Open表中计算。

 

        A*算法最简单的应用是在经典的砖块地图（Tile）中，每一个方格看做一个结点，从当前方格结点可以往上、下、左、右、左上、右上、左下、右下八个方向到下一个相邻结点，实际开发中需要考虑结点单元的大小，即贴图方格的密度。典型的《坦克大战》游戏即基于砖块地图。地图中的方格分为可行走（Moveable）和不可行走（Not Moveable）两种，不可行走的结点算法中会忽略跳过不加入计算。在砖块地图中，为了计算简便，的计算常采用欧几里得距离，的计算采用曼哈顿距离。

 

4. 拐点法优化A*路径

        在可视点导航图中可视关键点即算法的结点。这样设置结点的好处是结点的设置自由灵活，可以通过权衡减少A*结点的数量，减少计算量，也可以根据设计师的要求快速调整。问题是在大地图中，如果设置的结点比较稀疏，得到的路径会显得死板生硬，造成不自然的视觉体验。在导航网格（Navigation Mesh，又称Navmesh）也就是多边形导航图中可以很大程度上避免以上问题。

        在多边形导航图中，使用凸多边形作为结点，一方面可以大大减少结点的数量，另一方面可以更好的覆盖整个地形。此外，通过计算起点和终点之间直线与多边形导航网格相邻点的位置关系可以得出可否直接无障碍通过，基于此优化后，可避免像可视导航点搜索路径那样出现折返“Z”型路线，使角色产生多余的绕行。

        使用A*算法在NavMesh中搜索的路径是一系列相邻的多边形组成的通路，事实上在很多情况下多个多边形组成的行走区域是可以直接通过的，此时可将这些多边形合并，形成直线路径，只在必须拐弯的拐点处使路径转折，多边形的合并和拐点的寻找方法如下。

        按照多边形导航图的生成规格，相邻的两个多边形之间只有一条共同边，共同边上有两个可能作为拐点的端点，从一个多边形到另一个多边形两个端点可记为左端点、右端点，结点到两个端点的方向向量记为左向量Vleft、右向量Vright。根据多边形结点的代表点与两个端点的坐标可以计算出左右向量，另外根据目的地坐标可以计算一个目的方向向量Vd，因此一个结点数据结构可设计如下：

算法执行过程如下：

(1) 算法维护一个拐点表P，表示优化后路径的关键点，作为算法的运算结果；

(2) 算法初始将起点结点的代表点设置为多边形中心点，并加入拐点表P，然后计算到下一个结点的左右向量与目的方向向量的夹角，夹角较小方向上的端点设置为下一个结点的代表点；

(3) 根据下一个结点的代表点和左右端点计算左右向量，如果向量都不为零，执行和

起点结点相同操作；如果左向量为零，说明代表点和左端点重合，将左端点记为一个拐点加入拐点表P；

(4) 直到到达终点所在的结点时，将当前代表点和终点先后一起加入拐点表P，算法结束。

A*路径经拐点法优化后会出现沿导航图边界行走的情况，只要设置游戏角色的自身半径作为offset校正即可实现与导航图边界保持一定距离行进，避免与边界的碰撞卡顿。

 

3.2 电势矩阵寻路算法

        电势矩阵寻路算法将移动的物体也就是Unity中的NavAgent看做一个负电荷，模拟电势场中负电荷向电势高的地方移动的特点，通过改变电势场来引导负电荷沿着电势场线向目的地寻路移动。基于电势场的设置方法此算法最好应用在栅格化的导航图中，以更精确的描述电势场的细节，并且算法使用一个地图矩阵来存储地形每个点的电势整数值。

        设置目的点的方法即建立一个新的目的矩阵将目的点的电势设置成一个极大值，然后以圆形或者矩形向四周递减散播开来，离目的点越远电势值越小，直到0为止，然后将目的矩阵与原地图矩阵相加，改变电势分布，从而使负电荷沿着电势场分布向目的点移动。

        此算法本质上是一种贪心算法（GreedyAlgorithm），缺点是不保证一定能找到正确路径，可能计算无解。此算法可在一些比较规则的、简单的地形中完成寻路计算任务。

＊图中的路径不是很准确，第二次到97后应该走向98；同时在搜索时要通过排除同电势之间节点重复经过的方法，避免在同电势节点之间进入死循环出现徘徊走不出去的情况；

 

3.3群体行为（Flocking Behavior）寻路

        有些游戏中会需要角色群体的共同寻路功能，如果对每一个个体都进行单独寻路计算，会造成计算量膨胀，造成大量不必要的重复。因此角色单位的移动可采用行为控制（SteeringBehavior）来实现，即选择群体中的一个角色单位作为群体的领导者（Leader），对齐使用寻路算法进行寻路计算，然后其他的群体成员按照一定的Flocking规则对Leader进行跟随移动。

Flocking规则的设计主要考虑以下三个方面：

(1)  一致性：

即群体成员的的移动方向要同整体的移动方向（此即Leader的移动方向）保持一致；

(2) 分离性：

即每个群体成员需要与其他成员保持一定距离，避免重合在一起，这个可参照SterringBehavior的碰撞避免（Collision Avoidance）算法来类似实现；

(3) 聚合性：

即群体的成员向群体成员整体的平均位置靠近，使群体的整体寻路前进效果更真实。

 

3.4碰撞避免（Collision Avoidance）

Collision Avoidance可用于简单地形的随机寻路，其性能很差，主要用于障碍物的躲避。实现的逻辑为维护两个向量：一个为代表角色对象当前的移动方向和移动速度的移动方向向量Vd；一个为表示离其最近的障碍物的方向和距离的碰撞检测向量Vc;

        如图中绿色方块为游戏角色，红色方块为目的地，移动方向向量Vd根据角色当前位置和目的地位置不断更新，使其总是趋向于指向目的地，碰撞检测向量为角色位置指向最近的障碍物的向量，向量的模为到障碍物的距离，当距离小于一定值时开始避让障碍物，避让的方法为将移动方向向量与碰撞检测向量的反向量Vc'相加得到校正的移动方向向量Vd':

  Vd' = Vd + Vc'

  Vd = Vd'

        校正的瞬间角色的移动方向向量设置为Vd'，使其避开当前最近的障碍物，之后更新调整继续向目的地移动。

 

3.5深度优先搜索算法(DFS)与广度优先搜索算法(BFS)

 

        图论算法将地图结点和结点之间的通路信息用有向或者无向邻接矩阵来进行存储，邻接矩阵中相连的两点对应值为1，不相连的对应值为0，同一个图中可以有多种深度优先序列和广度优先序列。在路径搜寻中可以将相邻两点的对应值设置为两者的距离权重值，在算法搜索结束后选择距离最短的路径分支，从而确定一条算法上最优的路径序列。

        深度优先搜索(DFS, Depth First Search)和广度优先搜索(BFS, Breadth First Search)都是按照一定规则进行的盲目搜索。

 

深度优先：

        深度优先搜索的逻辑规则为从起点开始，寻找访问下一个连通的结点，直到没有未访问的连通结点后，回溯到起点并从其他的分支继续寻找深度连通路径，直到所有的结点都被访问到为止。

假设图3-9中无向图的起点为V1，则有以下几种深度优先序列：

V1, V3, V5, V4, V2;

V1, V4, V5, V3;

V1, V4, V2;

V1, V2, V4, V5, V3;

根据确定的目的结点以及连线的权值和可从序列中截取选择最短路径；

 

广度优先：

        广度优先搜索的搜索逻辑为从起点开始，遍历所有相连的结点并设置为起点的子结点，之后在子节点进行同样的递归操作，直到所有结点都加入以起点为根结点的树中。

假设图3-10中有向图的起点依旧为V1，其中一个广度优先搜索序列为：

V1, V3, V4, V2, V5

如图3-11中所示的两棵广度优先搜索树，从第二层开始，树的一层代表一次广度优先搜索。

 

双向广度优先：

双向广度优先算法是为了加快收敛速度，从起点和终点同时进行广度优先搜索设计的算法。

 

 

3.6 Dijkstra单源最短路径搜索算法

 

        Dijkstra算法是A start算法的无启发函数版,同时是一种典型的贪心算法。算法没有利用结点本身与起点和目的点的距离信息进行引导，在整个地图的所有结点中进行搜索，体现其盲目性，效率自然比A*算法低。算法的本质搜索思想是对于A和B两个结点，如果从整个地图中添加某些中间结点可以使A和B之间的加权路径长度更短，则加入中间结点构成A和B之间更短的加权路径，直到没有中间结点可以使A、B两点之间路径更短为止。

        算法初始化时计算各结点到其他结点的直接距离表，结点之间相连的距离为结点连线的权重值，不相连的距离设置为无穷大。构建一个S表，表示计算完成的结点的集合，算法开始时将起点加入S表，然后搜索与起点距离最近的点加入S表，并以新加入的结点为中间结点，计算起点到其他结点的相对更近距离，更新起点的距离表，直到所有的结点都加入S表。起点最终的距离表中的距离值即起点到其他各结点之间的最短路径距离。当终点确定时，记录在算法运行过程中起始点之间加入了那些中间结点，即可找出相应的最短路线。

假设图3-10有向图中的起点为V1，则Dijkstra算法初始化的距离表如表3-1所示：

 

        算法的执行过程可用表3-2表示如下，共六个结点执行五次循环将所有结点加入S表，w为新加入结点，D[Vi]表示起点到结点Vi的最短距离。

 

 

3.7随机寻路算法

 

        游戏中的怪物在玩家还未靠近时要有自己自然的随机动作，以一个随机的方向和随机的速率进行移动，使其看上去是活跃的。当玩家靠近进入怪物的“境界区域”时，怪物会主动寻路靠近玩家，当玩家与怪物足够近进入怪物的“攻击区域”时，怪物开始攻击玩家。

随机寻路算法的实现是设计一种随机移动规则，使游戏角色不断产生不规则、不可预见的行动，从而使角色在游戏中自行保持活跃状态，提高游戏真实感。寻路的随机主要是角色行进的方向和行进速度的随机。方向的表示可用一个随机目的地位置表示，或用一个单位方向向量表示。速度的改变可以通过控制更新的频率或者每次移动的距离实现。

        比如可以用一个向量的方向表示当前行进的方向，的模的大小来表示行进的速度，按照一定周期随机更新的方向和模的大小实现随机移动，同时使用碰撞避免算法来校正寻路，防止游戏角色出现在障碍物处长时间卡顿徘徊的现象。