《a算法详解》word版

《《a算法详解》word版》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、A算法详解A*算法详解A*算法详解虽然掌握了A*算法的人认为它容易，但是对于初学者来说，A*算法还是很复杂的。搜索区域(TheSearchArea)我们假设某人要从A点移动到B点，但是这两点之间被一堵墙隔开。如图1，绿色是A，红色是B，中间蓝色是墙。你应该注意到了，我们把要搜寻的区域划分成了正方形的格子。这是寻路的第一步，简化搜索区域，就像我们这里做的一样。这个特殊的方法把我们的搜索区域简化为了2维数组。数组的每一项代表一个格子，它的状态就是可走(walkalbe)和不可走(unwalkable)。通过计算出从A到

2、B需要走过哪些方格，就找到了路径。一旦路径找到了，人物便从一个方格的中心移动到另一个方格的中心，直至到达目的地。方格的中心点我们成为"节点(nodes)"。如果你读过其他关于A*寻路算法的文章，你会发现人们常常都在讨论节点。为什么不直接描述为方格呢?因为我们有可能把搜索区域划为为其他多变形而不是正方形，例如可以是六边形，矩形，甚至可以是任意多变形。而节点可以放在任意多边形里面，可以放在多变形的中心，也可以放在多边形的边上。我们使用这个系统，因为它最简单。开始搜索(StartingtheSearch)一旦我们把搜寻区

3、域简化为一组可以量化的节点后，就像上面做的一样，我们下一步要做的便是查找最短路径。在A*中，我们从起点开始，检查其相邻的方格，然后向四周扩展，直至找到目标。我们这样开始我们的寻路旅途：1.从起点A开始，并把它就加入到一个由方格组成的openlist(开放列表中。这个openlist有点像是一个购物单。当然现在openlist里只有一项，它就是起点A，后面会慢慢加入更多的项。Openlist里的格子是路径可能会是沿途经过的，也有可能不经过。基本上openlist是一个待检查的方格列表。2.查看与起点A相邻的方格忽略其

4、中墙壁所占领的方格，河流所占领的方格及其他非法地形占领的方格，把其中可走的(walkable)或可到达的(reachable)方格也加入到openlist中。把起点A设置为这些方格的父亲(parentnode或parentsquare)。当我们在追踪路径时，这些父节点的内容是很重要的。稍后解释。3.把A从openlist中移除，加入到closelist(封闭列表中，closelist中的每个方格都是现在不需要再关注的。如下图所示，深绿色的方格为起点，它的外框是亮蓝色，表示该方格被加入到了closelist。与它相邻

5、的黑色方格是需要被检查的，他们的外框是亮绿色。每个黑方格都有一个灰色的指针指向他们的父节点，这里是起点A。下一步，我们需要从openlist中选一个与起点A相邻的方格，按下面描述的一样或多或少的重复前面的步骤。但是到底选择哪个方格好呢?具有最小F值的那个。路径排序(PathSorting)计算出组成路径的方格的关键是下面这个等式：F=G+H这里，G=从起点A移动到指定方格的移动代价，沿着到达该方格而生成的路径。H=从指定的方格移动到终点B的估算成本。这个通常被称为试探法，有点让人混淆。为什么这么叫呢，因为这是个猜测

6、。直到我们找到了路径我们才会知道真正的距离，因为途中有各种各样的东西比如墙壁，水等。本教程将教你一种计算H的方法，你也可以在网上找到其他方法。我们的路径是这么产生的：反复遍历openlist，选择F值最小的方格。这个过程稍后详细描述。我们还是先看看怎么去计算上面的等式。如上所述，G是从起点A移动到指定方格的移动代价。在本例中，横向和纵向的移动代价为10，对角线的移动代价为14。之所以使用这些数据，是因为实际的对角移动距离是2的平方根，或者是近似的1.414倍的横向或纵向移动代价。使用10和14就是为了简单起见。比例

7、是对的，我们避免了开放和小数的计算。这并不是我们没有这个能力或是不喜欢数学。使用这些数字也可以使计算机更快。稍后你便会发现，如果不使用这些技巧，寻路算法将很慢。既然我们是沿着到达指定方格的路径来计算G值，那么计算出该方格的G值的方法就是找出其父亲的G值，然后按父亲是直线方向还是斜线方向加上10或14。随着我们离开起点而得到更多的方格，这个方法会变得更加明朗。有很多方法可以估算H值。这里我们使用Manhattan方法，计算从当前方格横向或纵向移动到达目标所经过的方格数，忽略对角移动，然后把总数乘以10。之所以叫做Ma

8、nhattan方法，是因为这很像统计从一个地点到另一个地点所穿过的街区数，而你不能斜向穿过街区。重要的是，计算H是，要忽略路径中的障碍物。这是对剩余距离的估算值，而不是实际值，因此才称为试探法。把G和H相加便得到F。我们第一步的结果如下图所示。每个方格都标上了F，G，H的值，就像起点右边的方格那样，左上角是F，左下角是G，右下角是H。好，现在让我们看看其中的