Unity人工智能编程精粹学习笔记 寻找最短路径并避开障碍物——A*寻路_a*算法流程图

目录

实现A*寻路的3种工作方式

基于单元的导航图

可视点导航图

导航网格

 

A*算法是如何工作的

A*算法的流程图

用一个实例来完全理解A*寻路算法

A*算法实例核心代码及项目工程

A*寻路的适用性

---

实现A*寻路的3种工作方式

A*寻路方式通常有3种：基于单元的导航图、基于可视点导航图与导航网格

 

基本术语

• 地图：“地图”是一个空间，也可以称为“图”，它定义了场景中相互连接的可行走区域，形成一个可行走网络，A*在这个空间内寻找两个点之间的路径。
• 目标估计：是指在寻路过程中估算代价的方法。通过采用不同的目标估计方法，可以实现更为智能、有趣的AI角色。
• 代价：在寻路过程中，有许多影响因素，例如时间、能量、金钱、地形、距离等。对于起始节点与目标节点之间的每一条可行路径，都可以用代价的大小来描述——每条可行路径都有相应的代价（如通过这条路径所需花费的总时间、通过这条路径的难度等），而A*寻路算法的任务就是选取代价最小的那条路径
• 节点：节点与地图上的位置相对应，可以用它来记录搜索进度。节点中存放了A*算法的关键信息，首先，节点的位置信息是必不可少的，除此之外，每个节点还记录了这条路径中的上一个节点，即它的父节点，这样在达到目标节点后，可以通过反向回溯确定最终路径。另外，每个节点还有3个重要的属性值，分别是g、h、f。

g:从起始节点到当前节点的代价

h:从当前节点到目标节点的估计代价。由于无法得知实际的代价值，因此h实际上是通过某种算法得到的估计值

f:g+h，f是对经过当前节点的这条路径的代价的一个最好的估计值，f越小，认为路径越优。

• 导航图：要进行寻路，首先需要将游戏环境用一个图表示出来，这个图称为导航图。导航图有多种形式，这里介绍其中最重要的三种，即基于单元的导航图、可视点导航图和导航网格。

 

基于单元的导航图

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

图3.2是一个基于单元的导航图，其中白色区域表示可行走区域，深灰色区域是不可行走区域。

 

这种方式最容易理解和使用，而且由于它的结构很规则，因此易于动态更新，如动态增加建筑物或其他障碍（如塔楼）等。基于单元的导航图比较适合在塔防游戏、即时战略游戏或其他频繁动态更新的游戏中使用。

采用基于单元的导航图时，寻路是以网格为单位进行的。可以想象，如果单个正方形过大，网格很粗糙，那么很难得到好的路径；而如果单个正方形很小，网格很精细，那么虽然会寻找到很好的路径，但这时需要存储和搜索大量的节点，对内存要求高，而且也影响效率。

另外如果游戏中包含不同的地形，并且不同地形的代价不同，那么还需要为网格中的每个单元（正方形或六边形）记录地形信息。这也需要一定的开销

如果是RTS游戏，还选择了基于单元的导航图进行寻路，那么游戏将会面临更高的性能消耗。

图3.3是一个基于单元的导航图，在这个图中，从a到b的路径实际上只需要19个节点，但是A*算法会搜索96个节点，因此这种方式的效率很低。并且为了将不可行走的区域也表示出来，浪费了大量的存储空间。

总结：优点是实现简单，缺点是A*算法搜索节点更多，且存储节点的空间消耗更多。

 

可视点导航图

另一个受欢迎的表示方式可以称为可视点导航图，也称为“路点图”，路点也称为“轨迹”点。

建立可视点导航图时，一般由场景设计者在场景中放置一些“路径点”，然后由设计人员逐个测试这些“路径点”之间的可视性。如果两个点之间没有障碍物遮挡，即两个点之间相互能“看到”，那么可以用一条线段把两个点连接起来，生成一条“边”（实际操作中，可以对“边施加一些限制，例如长度的限制），最后，这些“路径点”和“边”就组成了可视点导航图。

图3.4中的圆点是手工放置的路径点，路径点之间的连线表示“边”，即可以行走的路径，白色曲线表示从起点A到终点B的路径。图3.4中的右图是同一个区域的导航网格图，从A到B的路径是平滑的直线，可以做个对比。

可视点导航图的最大优点是它的灵活性。分散在各处的路点都是由场景设计者精心选择的，能覆盖绝大部分可行走的区域，还可以将其他一些重要位置的点包含进去，例如，理想的掩护位置、伏击位置等，同时增加相应的信息存储。利用这些可用信息，就可以高效地实现战术寻路，还可以计算出某个位置的战略信息，例如是否为死胡同，是否安全。

但是可视点导航图也有一些缺点:首先，当场景很大时，手工放置路径点是很繁琐的工作，也很容易出错。其次，它只是一些点和线段的集合，无法表示出实际的二维可行走区域，角色只能沿着那些边运动。当起始点或终点既不是路径点，也不在边上的时候，只能先找到距离路径最近的路径点，然后再进行寻路，这样很可能会得到一条z字形的路线，看上去很不自然。甚至可能发生更坏的情况，例如当起始点与最近路径点之间的线段并不完全在可行走区域时，如果让AI角色沿着这条线段行走，它很可能会跌落悬崖，或掉到河里！另外由于只能沿着边行走，因此很难保证生成的路径的质量。路径通常是弯弯曲曲的，甚至包含尖锐的拐角，即使是视线直接可达的路径，也无法进行优化。除此之外，他还存在严重的组合爆炸问题，如果设置了100个路径点，就可能需要测试99*100条路径。

现在的游戏中，越来越广泛地将导航网格用于寻路，这种方式大多将寻路与战术点分开，即导航网格只用于寻路，然后采用设计师手工放置躲藏点、埋伏点进行战术决策。

图3.5是一个H形可行走区域地可视点导航图。从a到b地路径经过11个节点，A*算法总共搜索了31个节点。

 

导航网格

导航网格将游戏中的可行走区域划分成凸多边形，实现中也可以限制多边形的种类，例如，要求只能使用三角形或可以同时使用三角形和四边形等。导航网格表示出了可行走区域的真实几何关系，是一个非均匀网格。Unity3D自带的寻路系统就建立在导航网格的基础上。

图3.6是一个用三角形表示的导航网格，其中，白色部分表示可行走区域，深灰色区域是不可行走区域。可以看出，该导航网格将可行走区域划分成了大小不等的三角形，这里相邻的三角形是直接可达的，寻路时，每个三角形都对应一个节点。

在这个三角形网格上进行A*寻路时，每个节点不再对应一个正方形而是一个三角形，所以相邻的节点即为与这个三角形相邻的其他三角形。另外，估计g和h时，导航网格方式也采用了不同的方法，例如，可以用三角形质心之间的线段长度作为节点之间的代价g，也可以用三角形的边的中点之间的距离作为g值等。

在图3.6所示的导航网格中，仍然用白色区域代表可行走区域，与图3.5不同的是，这里将可行走区域划分成了四边形，寻路用到的节点位于四边形的中央，利用A*算法，可以找到路径所经过的那些多边形。

由于形成的灰色曲线路径显然不理想，那么可以采用“视线确定”的方法，通过向前跳到视线所及的最远途经点，使路径变得更加平滑而自然。

一种方法是，每当达到路径内的一个路径点时，就检查列表中的下几个路径点。通过这种方式，可以跳过一些多余的视线内的途径点，得到更平滑的路径。

与前两种导航图相比，导航网格的优点是可以进行精确的点到点的移动，由于在同一个三角形种的任意两个点都是直接可达的，因此可以精确地寻找到从起始点到目标点的路径。它的另一个重要优点是非常高效。由于多边形的面积可以任意大，因此只需要少量的多边形，就可以表示出很大的可行走区域，不但占用的内存较小，搜索路径的速度也会有很大的提升。

另外，由于场景本身就是由多边形构成的，因此通过事先设计好的算法，能够自动地将可行走区域划分成多边形，生成导航网格。

导航网格地主要缺点是生成导航网格需要较长地时间，因此在地形经常发生动态变化（如经常添加、移除建筑物等）的场景中很少使用，而多用于静态场景中。这时，导航网格只需要在游戏开始时生成一次，便可一直使用。

很多AAA级游戏采用了特殊优化的导航网格，如HavokAI，可以实现动态游戏场景的快速更新。

 

A*算法是如何工作的

在A*算法中，使用了两个状态表，分别称为Open表和Closed表。这里Open表由待考查的节点组成，而Closed表由已经考查过的节点组成。那么，什么样的节点才算是“已考查过”的呢？对于一个节点来说，当算法已经检查过与它相邻的所有节点，计算出了这些相邻节点的f，g和h值，并把它们放入Open表以待考查，那么这个节点就是“已考查过”的节点。

开始时，Closed表为空，而Open表仅包括起始节点。每次迭代中，A*算法将Open表中具有最小代价值（即f值最小）的节点取出进行检查，如果这个节点不是目标节点，那么考虑该节点的所有8个相邻节点。对于每个相邻节点按下列规则处理：

（1）如果它既不在Open表中，也不在Closed表中，则将它加入Open表中；

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

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

重复上述步骤，直到达到目标节点。如果在达到目标之前，Open表就已经变空，便意味着在起始位置和目标位置之间没有可达的路径。

 

A*算法的流程图

Open表：等待考查的节点的优先级队列（按照代价从低到高排序）。

Closed表：已考查过，无需再考查的节点列表。

 

用一个实例来完全理解A*寻路算法

第一步，取出Open表中当前代价最小的节点，（即为起点（4，C）），检查它的8个相邻节点，看它们能够可行走，由于都是可行走的，因此加入到Open表中，由于已经检查过起始节点周围的8个相邻节点，所以将起始节点从Open表中移除，加入到Closed表中，而它的8个相邻节点放入到Open表中。

这一步执行完成后的结果如下：

 

第二步，进行第2轮循环，从Open表中取出新的节点进行检查，遍历Open表中的8个节点，计算它们的行走代价，选择代价最小的节点最为这一轮的考查对象。

行走代价的计算包括两部分。首先，要计算从起始节点移动到当前节点的移动代价g，其次计算出从当前节点到目标节点的移动代价h，然后把两个代价加起来，就是这个节点的总移动代价f。

g的值很容易计算，它是根据父节点之间的连接关系，算出节点走回到最初位置所需的移动代价，比如，如果和父节点的连接时直线连接，增加1，如果时对角线连接，增加1.414。

但是，如何计算h呢？由于AI角色还没有达到目标位置，因此只能对这个代价做一个大致的估算，采用启发的方法。具体应用中，可以采用欧几里得距离，也可以采用曼哈顿距离，或采用其他的启发方法。

可以看到，这一步计算出的总移动代价最低的是（3，D）这个节点。

 

首先看它的相邻节点，（2，E）是障碍物，其他7个节点中，有三个节点（3，C），（4，C），（4，D）是已经在Open表或Closed表中的，那么需要重新计算当前节点（3，D）所得到的新的g值。以节点（3，C）为例，这一次计算从（3，D）到（3，C）时，用（3，D）的g值加上从（3，D）到（3，C）的距离，其结果为1.41+1=2.41，大于上一轮的计算结果1，因此不需要更新相关信息。

还有4个新的节点分别为（2，C），（2，D），（3，E），（4，E），将这4个新节点加入到Open表中，而此时（3，D）的所有相邻节点都已经检查过，那么它加入到Closed表中。以（2，D）为例，g值为1.41+1=2.41,g值为5，f值为7.41，这一轮循环的结果如下：

 

第三步，现在进入到第3论循环，首先检查Open表，找出其中具有最低代价的节点。可以看到，有两个节点具有相等的最小代价值7.41，那么选择其中一个进行检查，假设选择（3，E）的节点，可以看到，他的相邻节点已经全部在Open表或Closed表中，且没有得到更小的代价值，因此不需要更新信息，将这个节点加入到Closed表中，这一轮就完成了，如图3.13所示。

 

第四步，检查（2，D）这个节点，在它的8个相邻节点中（2，E）是障碍物不能行走，（2，C）（3，C）在Open表中，（3，D）（3，E）在Closed表中，无需更新信息。对于（1，E），由于障碍物（2，E）存在也不能直接可达，只剩下（1，C）g = 2.41+1.41 = 3.82，而（1，D） g = 2.41 + 1 =3.41；

此时，（2，D）的相邻节点都已检查完毕，将（2，D）移出Open表，加入到Closed表中，如图所示：

 

第五步，检查Open表，具有最小代价值的节点有两个，它们的f值都是8，分别位于（3，C）和（4，D）。

选择（3，C），在它的8个相邻节点中，有7个已经在Open表或Closed表中，重新计算它们的g值可以发现，（2，C）需要更新，并且记录它的父节点为（3，C），其他节点的相关信息无需更新。

再计算新节点（2，B）的值，并加入到Open表中，这样（3，C）节点检查完毕，将它移入到Closed表中。

 

重复上面的过程，直到目标点也进入到Open表中，此时，沿着节点回溯，就可以找到从起始点到目标点的路径。

 

图3.16到图3.27给出了之后的A*寻路单步节点计算的示意图。

 

A*算法实例核心代码及项目工程

主要实现了A*算法的寻路过程实例，可单步查看每一步A*算法Open表和Close表的节点状态，也可直接一步查看结果，支持地图的可编辑性，自定义宽高和障碍物及起点终点位置的生成，示例截图如下：

 

核心源码如下：

        public bool PathSearch(Node[,] nodes, Vector2 startPos, Vector2 endPos)
        {
            if (!CheckNodeValid(startPos, endPos))
            {
                return false;
            }
            
            _endPos = endPos;
 
            Node nodeTmp = nodes[(int) startPos.y, (int) startPos.x];
            nodeTmp.G = 0;
            nodeTmp.H = HFun(nodeTmp);
            nodeTmp.F = nodeTmp.G + nodeTmp.H;
            nodeTmp.ParentNode = null;
            nodeTmp.PathType = NodePathType.Start;
 
            do
            {
                if (_openList.Count > 0)
                {
                    nodeTmp = _openList[0];
                }
 
                for (int i = 0, count = _openList.Count; i < count; i++)
                {
                    if (_openList[i].F < nodeTmp.F)
                    {
                        nodeTmp = _openList[i];
                    }
                }
 
                Node pathNode = AStarSearch(nodeTmp);
 
                if (CheckFindPath(pathNode))
                {
                    return true;
                }
 
                _openList.Remove(nodeTmp);
                _closeList.Add(nodeTmp);
                nodeTmp.AStarState = NodeState.IsInCloseList;
 
            } while (_openList.Count > 0);
            
            Debug.LogError($"Path Node Found!");
            return false;
        }

        public Node AStarSearch(Node node)
        {
            Node nodeTmp;
 
            for (int i = 0, count = node.NeighbourNodes.Length; i < count; i++)
            {
                nodeTmp = node.NeighbourNodes[i];
                
                if (nodeTmp == null)
                {
                    continue;
                }
 
                if (nodeTmp.NodeType != NodeType.Movable)
                {
                    continue;
                }
 
                if (nodeTmp.AStarState == NodeState.IsInOpenList)
                {
                    float curG = Vector2.Distance(nodeTmp.Pos, node.Pos);
                    if (nodeTmp.G > curG + node.G)
                    {
                        nodeTmp.ParentNode = node;
                        nodeTmp.G = curG + node.G;
                        nodeTmp.F = nodeTmp.G + nodeTmp.H;
                    }
                }
                else if (nodeTmp.AStarState == NodeState.Free)
                {
                    nodeTmp.ParentNode = node;
                    nodeTmp.G = Vector2.Distance(nodeTmp.Pos, node.Pos) + node.G;
                    nodeTmp.H = HFun(nodeTmp);
 
                    nodeTmp.F = nodeTmp.G + nodeTmp.H;
                    
                    _openList.Add(nodeTmp);
                    nodeTmp.AStarState = NodeState.IsInOpenList;
 
                    if (nodeTmp.H < Mathf.Epsilon)
                    {
                        nodeTmp.PathType = NodePathType.End;
                        return nodeTmp;
                    }
                }
            }
 
            return null;
        }

 

源码工程地址如下：

https://download.csdn.net/download/dmk17771552304/16160607

 

A*寻路的适用性

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

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

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

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

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

为了在战场上做出好的决策，就需要获取高质量的信息，这些信息来自地形分析、路径搜索、视距和许多其他系统。它们的开销很大，为了找到可靠的战斗位置，往往需要评估许多不同的可能性，因此，这些信息的获取过程对系统的效率会有很大的影响。在实际设计中，除了创建更高效的底层系统，更快速地提供信息之外，设计者还需要能够利用更少地信息，做出更好地AI角色，并且在开发过程中，要始终意识到每一部分信息的代价。