滴水逆向联盟

标题: 浅谈游戏自动寻路A*算法 [打印本页]

作者: admin 时间: 2014-5-8 15:35
标题: 浅谈游戏自动寻路A*算法
寻路是游戏中非常重要的一个元素，如何找到一条最短的路径是程序需要设计的算法，现在最为流行的寻路算法是A*算法。A*算法与状态空间搜索结合的相当紧密。
状态空间搜索，就是将问题求解的过程表现为从初始状态到目标状态寻找这个路径的过程，通俗的说就是在解一个问题的时候找到一条解题过程可以从求解的开始到问题的结束。
由于求解过程中求解条件的不确定与不完备性使得问题的求解过冲中的分支有很多，这就产生了多条求解的路径，这些路径过程一个图这个图就是状态空间。问题的求解时机上就是在这个图中找个一个路径可以从开始到结束，这个过程就是状态空间搜索。

常用的状态空间搜索有深度优先和广度优先，广度优先是从初始状态一层一层的向下找，知道找到结果目标为止，深度优先是按照一定的顺序先查找完一个分支再查找另一个分支，知道找到目标结果为止。这两种搜索方法有的很大缺陷是它们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很适合的算法，但是当空间很大并且不可预测的情况下就不可取。这个时候这两种算法的效率太低甚至有时是无法完成，所以要用到另一种算法---启发式搜索。
启发式搜索就是在状态空间中对每一个搜索为止进行评估，指导找到最好的为止，再从这个位置进行搜索直到目标位置为止。在启发式搜索中对为止的评估是十分重要的，采用不同的估价可能有不同的结果。
启发式搜索中的估价函数表示为：
f(n)=g(n)+h(n)
其中f(n)是节点n的估价函数，g(n)是在状态空间中从初始点到n节点的实际代价，h(n)是从n节点到目标节点最佳路径的估价代价。这个里主要是h(n)体现了搜索的启发信息，因为g(n)是己知的。换个说法就是g(n)代表了索索的广度优先趋势但是当h(n)>>g(n)时，可以省略g(n)，从而提高效率。
启发式搜索其实也有很多算法，比如局部择优搜索，最好优先搜索等。A*也是如此，这些算法都启用了启发函数，但在具体的选取最佳搜索节点时的策略不同。比如局部择优算法就是在搜索的过程中选取了最佳节点候舍弃了其他的兄弟节点，父亲节点并且一直搜索下去。这种搜索结果很明显，由于舍弃了其他的节点因此可能也把最佳的节点舍去偶尔。最好优先就聪明一点搜索的时候并没有舍去节点，除非该节点是死节点。在没一步的估价中都吧当前的节点和以前的节点的估价值进行比较从而得到最佳节点，这样防止了最佳节点的丢失。
A*算法也是一种最好优先的算法，只是加上了一些特定的约束条件，由于在一些问题求解时，希望能够求解出状态空间搜索的最短路径也就是用最快的方法求解出问题，A*算法的目的就是这样。其估价的函数可以表示为：
f'(n)=g'(n)+h'(n)
这里的f'(n)是估价函数，g'(n)是起点到终点的最短路径值，h'(n)是n到目标的最短路径的启发值。由于f'(n)是无法提前预先知道的，因此用前面的估价函数f(n）做近似g(n)代表g'(n)，但是g(n)≥g'(n)才可以通常都是大于所以不要考虑，但是h(n)代替h'(n)时候需要h(n)≤h'(n)才可以。可以证明应用这样的评估函数是可以找到最短路径的，因此应用这种评估函数的最好的优先算法就是A*算法。
至于h(n)的启发函数的信息性，就是在估计一个节点值的约束条件，如果信息越多或者约束条件越多则排除节点就越多，估价函数就越好或者说这个算法就越好。这就是为什么广度优先算法很不好的原因，因为起h(n)=0一点启发信息都没有，但是在游戏的开发中由于实时性的要求，h(n)的实质信息越多计算量也大消耗的时间就长，其次在牺牲算法准确性的前提下就可以适当的减少h(n)的启发信息。

作者: admin 时间: 2014-5-8 15:36
们先看下最好优先算法的逻辑（起始为止为A结束位置是P，字母后数字为节点的估价值）：



搜索的过程中设置两个表：OPEN和CLOSE。OPEN表保存了所有已生成的未考察的节点。CLOSE表中记录了已访问的节点。算法中有一步是根据估价函数重新排列OPEN表，这样循环中的每一步值考虑OPEN中状态最好的节点搜索过程如下：

1.初始状态

OPEN = [A5];CLOSED=[ ] ;

2.估算A5，取得所有子节点，并放入OPEN表中

OPEN = [B4,C4,D6];CLOSED = [A5];

3.估算B4,取得所有子节点，并放入OPEN表中

OPEN = [C4,E5,F5,D6];CLOSED = [B4,A5];

4.估算C4，取得所有子节点，并放入OPEN表中

OPEN = [H3,G4,E5,F5,D6];CLOSED = [C4,B4,A5];

5.估算H3，取得所有子节点，并放入OPEN表中

OPEN = [O2,P3,G4,E5,F5,D6];CLOSED = [H3,C4,B4,A5];

6.估算O2，取得所有子节点，并放入OPEN表中

OPEN = [P3,G4,E5,F5,D6];CLOSED = [O2,H3,C4,B4,A5];

7.估算P3得到解

伪代码如下：

Best_First_Seach()

{

  Open = [起始节点]；

  Closed = [ ];

  while(Open表非空)

  {

从Open中取得一个节点X，并从Open表中删除。

if(X节点是目标节点)

{

   求的路径PATH;

   return PATH;

}

for(每个X的子节点Y)

{

   if(Y不在OPEN表和CLOSE表中)

   {

   求Y的估价值；

   将Y插入OPEN表中；

   }

   else if(Y在OPEN表中)

   {

      if(Y的估价值小于OPEN表的估价值)

      更新OPEN表中的估价值；

   }

   else

   {

   if(Y的估价值小于CLOSE表的估价值)

   更新CLOSE表中的股价值

   从CLOSE表中移出节点，放入OPEN表中；

   }

}

讲X节点插入CLOSE表中；

按照估价值讲OPEN表中的节点排序；

  }

}

作者: admin 时间: 2014-5-8 15:42
种高效的寻路算法 - B*寻路算法
在此把这个算法称作B* 寻路算法（Branch Star 分支寻路算法，且与A*对应），本算法适用于游戏中怪物的自动寻路，其效率远远超过A*算法，经过测试，效率是普通A*算法的几十上百倍。

通过引入该算法，一定程度上解决了游戏服务器端无法进行常规寻路的效率问题，除非服务器端有独立的AI处理线程，否则在服务器端无法允许可能消耗大量时间的寻路搜索，即使是业界普遍公认的最佳的A*，所以普遍的折中做法是服务器端只做近距离的寻路，或通过导航站点缩短A*的范围。

算法原理
本算法启发于自然界中真实动物的寻路过程，并加以改善以解决各种阻挡问题。
前置定义：
1、探索节点：
为了叙述方便，我们定义在寻路过程中向前探索的节点（地图格子）称为探索节点，起始探索节点即为原点。（探索节点可以对应为A*中的开放节点）

2、自由的探索节点：
探索节点朝着目标前进，如果前方不是阻挡，探索节点可以继续向前进入下一个地图格子，这种探索节点我们称为自由探索节点；

3、绕爬的探索节点：
探索节点朝着目标前进，如果前方是阻挡，探索节点将试图绕过阻挡，绕行中的探索节点我们成为绕爬的探索节点；
算法过程
1、起始，探索节点为自由节点，从原点出发，向目标前进；
2、自由节点前进过程中判断前面是否为障碍，
   a、不是障碍，向目标前进一步，仍为自由节点；
   b、是障碍，以前方障碍为界，分出左右两个分支，分别试图绕过障碍，这两个分支节点即成为两个绕爬的探索节点；
3、绕爬的探索节点绕过障碍后，又成为自由节点，回到2）；
4、探索节点前进后，判断当前地图格子是否为目标格子，如果是则寻路成功，根据寻路过程构造完整路径；
5、寻路过程中，如果探索节点没有了，则寻路结束，表明没有目标格子不可达；

演示如下：


B*与A*算法的性能比较

寻路次数比较（5秒钟寻路次数）


B*与A*性能比较实例
1、无障碍情况
此种情况，根据以上测试数据，B*算法效率是普通A*的44倍（左为A*，右为B*)




2、线形障碍
此种情况，根据以上测试数据，B*算法效率是普通A*的28倍（左为A*，右为B*)

3、环形障碍
此种情况，根据以上测试数据，B*算法效率是普通A*的132倍（左为A*，右为B*)



4、封闭障碍（目标不可达）
此种情况，根据以上测试数据，B*算法效率是普通A*的581倍（左为A*，右为B*)


衍生算法
通过以上封闭障碍，可以看出，这个方法在判断地图上的两个点是否可达上，也是非常高效的，在不可达情况下，时间复杂度与封闭障碍的周长相当，而不是整个地图的面积。

作者: admin 时间: 2014-5-8 15:43
http://www.myexception.cn/program/1054683.html 原文地址

欢迎光临滴水逆向联盟 (http://dtdebug.com/)