目录

1，游戏AI的构架模型

2，A*寻路

---

1，游戏AI的构架模型

游戏AI的构架模型分为：1）运动层：（导航、寻路）决定角色的移动路径。

                                        2）决策层：决定角色下一步该做什么！

                                        3）战略层：一组角色的总行为！

运动层和决策层包含算法只针对单个角色。？

战略层是针对小队乃至更大规模的群体。

那我们应该怎么去判断呢？

——比如只有单个角色，那么他的行为就只能是运动层和决策层，因为他只需要考虑应该怎么移动，或者做出决定怎么样去伏击玩家！

——战略层通常是一组AI小队的配合战略，棋类游戏就只包含战略层（角色不需要自己做决定，也不需要考虑如何移动）

——所以内容丰富的游戏基本都包括这三种构架模型！

2，A*寻路

1，基本术语

• 地图：” 地图 “ 是一个空间，也称为 ” 图 “，它定义了场景中相互连接的可行走区域，形成 一个可行走网络，A*就是在这个空间内寻找俩点之间的路径。
• 目标估计：是指在寻路过程中估计代价的方法。
• 节点：节点与地图上的位置相对应，用来记录搜索进度。节点中存放了A*算法中的关键信息。（每个节点还记录了这条路径中的上一个节点，即它的父节点，这样到达目标后，可以反向回溯确定最终路径）

             每个节点都有3个重要的属性：g、h、f。

             g：从起始位置到当前节点的代价。

             h：从当前节点到目标节点的估计代价。通常用算法得到这个估计值！

             f：g+h，对当前路径代价的估计值，值越小路径越好。 

• 代价：在寻路过程中有很多影响因素，比如时间、距离、地形、金钱等。所以对起始节点到目标点的每一条可行路径，都可以用代价大小描述，所以A*算法就是选取最小代价的路径。

2，A*寻路的三种工作方式

1）创建基于单元的导航图

基于单元的导航图是将游戏地图划分为多个正方形单元或六边形单元组成的规则网格，网格点或者网格中心可以看作是节点。

 如果单个网格过大，就难以得到好的路径，如果单个网格精细，这时就需要存储和搜索大量的节点，对内存要求高，很影响效率！

从一个位置到达另外一个位置，通常需要搜索比较多的节点，导致效率比较低。

优点：容易理解和使用，易于动态更新（如动态增加建筑物或其他障碍——塔楼等）

缺点：占用内存空间大，开销大影响效率。

2）创建可视点导航图

可视点导航图，也称为路点图，路点也称为”轨迹点“

简而言之：就是放置路径点让角色在路径上移动

如下图路径

搜索节点比第一种方式要少

 优点：灵活性好（路径由设计者精心设计选择的，能够覆盖大部分行走区域——包括伏击点、理想位置）

缺点：当场景很大时，手工放置路径点比较繁琐，容易出错，还有就是组合爆炸问题——100个路径点需要测试99*100条路径，以此类推......

3）创建导航网格

导航网格（Navmesh）将区域分为凸多边形（如下图所示）

蓝色区域为角色可行走区域！ 

Unity3D自带的寻路系统就建立在导航网格的基础上。

在unity中我们使用WIndow / AI / Navigation 时，只能对静态物体使用，如果没给在场景地形中挂上静态，则无法生成导航网格！

优点：占用内存小，搜索路径的速度相对快（如上图所示多边形个数用手指头都能够数过来）

缺点：用于静态场景中，在地形发生动态变化的场景中很少使用。

 3，A*算法是如何工作的呢

开始搜索前，需要记录待考察的节点，将这些节点记录在一个表中，称为Open表（易知，刚开始时只有一个节点，那就是起始点）

寻路消耗公式：

                f  (寻路消耗)=g（离起点距离）+  h（离终点距离）

当然一个表肯定是不够的，还需要一个Closed表（来记录考察过的，不再需要考察的节点）

加入原则：（1）如果它不在俩表中，，则将其加入Open表；

                  （2）如果它已经在Open表中，并且新的路径具有更低的价值，则更新它的信息；

                  （3）如果它已经在Closed表中，那么检查新的路径是否具有更低的代价值。如果是                                 的，那么将它从Closed表移出，加入到Open表中，否则忽视！

 4，A*寻路的适用性

A*寻路很好用，但它不是万能的。选择哪种寻路方法要充分考虑到游戏的要求，而不是希望永远它永远好用。一般来说，我们通常都是在设计中建立AI能够处理的情景，而不是对AI做出过高的期待，让它去处理任意复杂的场景。

（1）A*寻路算法在游戏中具有十分广泛的应用，利用它可以找到一条从起点到终点的最佳路径，它的效率在同类算法中也很高，对于大多数路径寻找问题，它是最佳选择。

（2）有一些A*寻路不太适用的场合。例如，如果起点和终点之间没有障碍物，终点直接在视线范围内，就完全不必采用他。另外这个算法虽然高效，但寻路具有较大的工作量，需要多帧才能完成。如果CPU计算能力较弱，或者需要为大地形寻找路径，那么计算起来就比较困难了。而且，他也有一定的使用限制。

（3）如果游戏设计者正在为一个Android平台下的手机游戏选择寻路算法，就需要做更好的权衡，与PC相比，手机内存的资源要珍贵的多，如果需要在很大的空间中进行寻路，那么最好选择其他算法，并且，估价算法的开销也可能会称为瓶颈。因此，在手机游戏中需要针对不同的寻路要求，选择不同的实现方法，例如采用深度优先、广度优先、遗传算法等。

（4）在战斗游戏中，往往希望AI角色能够快速从一个地方跑到另一个地方。绝大多数情况下，想要的路径并不是最短路径。试想，如果一个敌人AI角色试图逃离玩家的枪弹，结果却是从玩家指挥的角色身边跑过去，应该选择更好的路径搜索策略。
 

总结:A*寻路算法在同类算法中效率较高，最短路径并不意味着最好的路径，A*寻路具有较大的工作量对CPU要求高！