游戏自动寻路A算法.doc

《游戏自动寻路A算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

浅谈游戏自动寻路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)的启发信息。我们先看下最好优先算法的逻辑（起始为止为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;returnPATH;}for(每个X的子节点Y){ if(Y不在OPEN表和CLOSE表中){求Y的估价值；将Y插入OPEN表中；}elseif(Y在OPEN表中){if(Y的估价值小于OPEN表的估价值)更新OPEN表中的估价值；}else{if(Y的估价值小于CLOSE表的估价值)更新CLOSE表中的股价值从CLOSE表中移出节点，放入OPEN表中；}}讲X节点插入CLOSE表中；按照估价值讲OPEN表中的节点排序；} }