A路径寻找算法

《A路径寻找算法》由会员分享，可在线阅读，更多相关《A路径寻找算法（12页珍藏版）》请在金锄头文库上搜索。

1、A*路径寻找算法：引言：引言：A*路径算法能够保证在任何起点及终点间找到最佳的路径，前提是确实存在这种路径。虽然A*很有效，但仍会 耗费不少CPU运算能力。 定义搜索区域：A*算法是基于节点的。节点设置越多，计算所需要的开销越大。如图：其中，坦克的位置可以根据坐标系统占据任何节点。A* 算法基于这样一个实例来说明A* 算法。 如图的砖块型游戏中。黑色代表障碍物，点代表节点，即可以行走的地方。搜寻的路径起点是蜘蛛所在节点，重点 是人类所在节点。其做法是先从起点的砖块开始搜寻，然后再分别去搜寻周围的节点，一直扩散下去直到抵达目的地节点。由此，需 要某种方式来记录已经被搜寻过的砖块，将他们记入Ope

2、n List。开始时，Open List中只有一个节点，即起始节点。A*路径寻找算法2008年7月4日 10:49分区 AI学习笔记 的第 1 页 如上图。从起始节点开始，搜寻其周围的八个相邻的节点，如果某节点是障碍物，则为无效节点。其他有效节点则 全部加入Open List。除Open List外，A* 算法还需要有一个Closed List。 Closed List中记录的节点都是被检查过的砖块。如上图。已经检查 过了起始砖块的每个相邻砖块，所以起始砖块要被放入Closed List中。结果如下图：此时，有八个新的节点放入了Open List，而有一个节点从Open List中移除。第一轮

3、循环完毕。 除了Open List 及Closed List外，我们还需要记录其他信息。如，我们必须知道这些砖块是怎样连接的。由此引出一个 概念叫“母节点”母节点就是角色移动到当前位置之前的节点。 如图，我们需要将每一个节点与母节点的方向记录下来。分区 AI学习笔记 的第 2 页 接下来要做的就是基于周围的八个加入Open List的节点进行新一轮的循环。现在从Open List中选出新的节点进行检 查。一个问题是，现在有八个节点在Open List中，选取的策略是怎样的呢？我们的确认方式就是为砖块打分。计分： 我们计算每个节点的分数，是把从起点走到该节点的移动成本（最小步数），加上用启发法所

4、得的移动成本（也就 是估算的从该节点到目的地的移动成本）。简单来说：Score= 起点走到该点的步数 + 该点到终点的步数。注：此处启发法得到的步数是不考虑障碍物的结果。如上图。从起点走到上面三个节点的成本都是1，记为S=1。从上面三个节点到终点的移动成本均为三记为h=3，所以 上面三个的总分数都是4，记为 c=4。同理其他节点的分数也可算出。 这样一来。先前提出的从Open List选取下一个要检查的节点的策略问题就有了答案：选择分数（c值）最低的节点。 此时分数最低c=4的节点有三个。我们任选一个来开始进行检查。 假设我们用（行,列）的坐标系统。我们选取右上角的节点开始进行检查，即节点(5

5、,6)。分区 AI学习笔记 的第 3 页 对(5,6)节点进行检查后，Open List 中多了两个节点(5,7)、(6,7)。分数如图分别为c= 5、 c=6。给这两个节点标上方 向，指向其母节点，即(5,6)节点。最后，将(5,6)从Open list中剔除，并放入closed list中。 此时，再从Open list中选择分数最低的节点进行检查。最后选择分数为4的(5,5)节点。因为有障碍物，所以没有新的 节点加入Open List。再选择分数为4的(5,4)节点进行检查。结果如图。此时分数的最小值是5，所以选择分数为5的节点进行检查。 后面步骤相同：不再赘述。 再检查分数为6的节点分

6、区 AI学习笔记 的第 4 页 检查(3,4)检查(2,5) (3,5)检查(1,6) (2,6) (3,6)当终点被加入了Open List。即路径已经找到。停止检查循环。依据所标示的方向从终点走回起点。分区 AI学习笔记 的第 5 页 此时我们得到了一条由(2, 7), (2, 6), (2, 5), (3, 4), (4, 3), (5, 4),(6, 5)所组成的路径。或许还有其他的 等长路径，但不会有更短的了。死路判断死路判断 如何判断遇到死路的情况？当我们不断地检查Open List中的节点，到最后Open List不再有任何节点的时候。就是遇上死路了。如上图。移动成本计算的其他因

7、素移动成本计算的其他因素有时候的情况并不是最短的路径就是最快的路径。如穿越沼泽需要的时间为5，穿越草地需要时间3，穿越普通地形 需要时间1。所以有可能一条绕远的道路时间上可能会更快。此时我们可以将地形的因素加入成本计算。 如下图中所标示的地形成本：分区 AI学习笔记 的第 6 页 移动成本的计算公式改为 Score= 起点走到该点的步数 + 该点到终点的步数 + 地形成本。再进行计算得到：这条路并不是最近的。但却是最快的。其他所有感兴趣的因素都可以加入到成本计算中从而影响角色的移动特性： 如可以考虑敌人火力网的影响成本分区 AI学习笔记 的第 7 页 以下部分来自网络：以下部分来自网络： A*

8、 算法算法 贴个小东西，也许是许多游戏开发爱好者都想要获得算法。下面我来说说我理解的A*算法的原理： A*算法是一个求最短路径的函数，为许多即时战略游戏所用刀（或许人家大型的即时战略游戏笔者算 法更好，不管它）。它由两个函数组成，一个是评估函数，也就是确定人物移动的下一个位置必须离 目标位置最近，评估函数评估的结果越精确，则寻径的速度越快；另一个就是寻径函数，也就根据评 估的结果做出响应，然后从新位置继续评估下一个位置，若无路可走（四周都是障碍什么的），那么 折回一个路径节点，尝试其他方向，这个算法有个缺点，随着游戏中人物增多，相应的处理节点就增 多了，会影响处理速度，而且占用大量的内存。有兴

9、趣的朋友可以改成动态的寻径，就是当入口和出口位置都在变化的时候进行寻径，这个代码也只 有200多行。 我的算法还不能算是最优的，因为评估函数只不过是简单的测试两点距离（这会带来误差），选择离 出口最短的且非障碍物的方向，进行下一个路径节点的移动。这里说一句，我希望大家将我的代码用于学习目的，不希望看见是为了交作业而拷贝过去，我会很伤 心的。 /* AStar.cpp */ /* 设计者： yuki */ typedef unsigned char byte_t; typedef unsigned int uint_t; /* 路径节点 */ typedef struct footprint /

10、* 存放在数组中的位置 */uint_t pos;/* 存放方向信号量 */byte_t direct;上图标示出了受到敌人坦克攻击概率的影响。路径计算的时候就会选择一条较安全的路径来行走。而坦克的移动又 会动态的改变地图上每个点的火力网状况。 参考资料：David M. Bourg, Glenn Seeman AI for Game Developers OReilly July 2004 作者：冰里的虫子（Luo Chong） Email: QQ: 23806653分区 AI学习笔记 的第 8 页 struct footprint *next;struct footprint *pre

11、v; path_t;/*方向信号量查询表0x01(0000 0001) : 上0x02(0000 0010) : 下0x04(0000 0100) : 左0x08(0000 1000) : 右 */ static byte_t d_signal4 = 0x01, 0x02, 0x04, 0x08; /*方向信号量使用表如果指定方向已经走过，那么使用“与”运算去处该方向0x0E(0000 1110) : 上0x0D(0000 1101) : 下0x0B(0000 1011) : 左0x07(0000 0111) : 右 */ static byte_t d_spend4 = 0x0E, 0x0D

12、, 0x0B, 0x07; /* 指定方向移动偏量 */ static int move42 = 0, -1, 0, 1, -1, 0, 1, 0 ; /* 打印迷宫用的符号 */ static byte_t symbolic3 = #,0x20,*; /* 求两点间的距离 */ inline uint_t distance( uint_t pos1X, uint_t pos1Y, uint_t pos2X, uint_t pos2Y ) uint_t ret = 0;/* 距离公式 */ret = (uint_t)sqrt(pow(double)(int)pos1X - (int)pos2X

13、),2) + pow(double)(int) pos1Y - (int)pos2Y),2);return ret; /* 压缩坐标 */ inline uint_t create_pos( uint_t pX, uint_t pY ) uint_t ret = 0;/* 将pX赋给ret，这样pX坐标在ret的低八位 */ret = pX;/* 将pX坐标移到高八位去，这样低位就能存放pY */ret pos 8;pY = p-pos ()()分区 AI学习笔记 的第 9 页 memset(dis, (int)-1, sizeof(int)*4);/* 计算每个方向离开出口的距离，一次存放到

14、dis数组，若没有i方向，则disi任保留-1 */for( i = 0; i direct /* 获得最短距离的方向 */for(i = 0; i direct /* 在移动到新位置之前，在旧位置处留下足迹 */mazepYpX = (byte_t)PATH_FOOTPRINT;/* 构建新的路径节点 */pnode = (path_t *)malloc(sizeof(path_t);assert(pnode);/* 计算下一个位置的坐标 */pX += moveminId0;pY += moveminId1;pnode-pos = create_pos(pX, pY);pnode-prev

15、 = p;pnode-next = (path_t *)0;pnode-direct = 0;/* 在新位置处，计算下一个位置可用的移动方向 */for(i = 0; i direct |= d_signali;return pnode; /* = A*算法寻径函数 = -eX -eY :入口坐标 -qX -qY :出口坐标 -maze :迷宫矩阵 = */ inline path_t * AStar(uint_t eX, uint_t eY, uint_t qX, uint_t qY, byte_t mazeMAZE_HEIGHTMAZE_WIDTH) register int i;/* 压缩坐标 */uint_t quit_pos = create_pos(qX, qY)