A路径寻找算法入门..doc

A*路径寻找算法入门 来源于: GameD 作?者: Patrick Lester 原文URL: /reference/articles/article2003.asp 翻?译: 孙璨 　 虽然A*（读作A星）算法对初学者来说是比较深奥难懂，但是一旦你找到门路了，它又会变得非常简单。网上有很多解释A*算法的文章，但是大多数是写给那些有一定基础的人看的，而您看到的这一篇呢，是真正写给菜鸟的。 ? 本篇文章并不想给这个算法题目作一些权威性论断，而是阐述它的基本原理，并为你理解更多相关资料与讨论打下基础。文章末尾给出了一些比较好的链接，放在“进阶阅读”一节之后。 ? 最后，本文不是编程规范，你将可能使这里讲述的东西编写成任何计算机语言。在本文的末尾我还给出了一个例子程序包的下载链接，也许正合你意。在这个包中有C++和Blitz Basic两个版本的程序代码，如果你只是想看看A*算法是如何运作的，该包中也有可直接执行的文件供你研究。 ? 我们还是要超越自己的（把算法弄懂），所以，让我们从头开始吧！ 　 初步：搜索区域 ? 我们假设某个人要从A点到达B点，而一堵墙把这两个点隔开了，如下图所示，绿色部分代表起点A，红色部分代表终点B，蓝色方块部分代表之间的墙。 [图一]　 你首先会注意到我们把这一块搜索区域分成了一个一个的方格，如此这般，使搜索区域简单化，正是寻找路径的第一步。这种方法将我们的搜索区域简化成了一个普通的二维数组。数组中的每一个元素表示对应的一个方格，该方格的状态被标记为可通过的和不可通过的。通过找出从A点到B点所经过的方格，就能得到AB之间的路径。当路径找出来以后，这个人就可以从一个格子中央移动到另一个格子中央，直到抵达目的地。 这些格子的中点叫做节点。当你在其他地方看到有关寻找路径的东西时，你会经常发现人们在讨论节点。为什么不直接把它们称作方格呢？因为你不一定要把你的搜索区域分隔成方块，矩形、六边形或者其他任何形状都可以。况且节点还有可能位于这些形状内的任何一处呢？在中间、靠着边，或者什么的。我们就用这种设定，因为毕竟这是最简单的情况。 ? 开始搜索 ? 当我们把搜索区域简化成一些很容易操作的节点后，下一步就要构造一个搜索来寻找最短路径。在A*算法中，我们从A点开始，依次检查它的相邻节点，然后照此继续并向外扩展直到找到目的地。 我们通过以下方法来开始搜索： 1.?????? 从A点开始，将A点加入一个专门存放待检验的方格的“开放列表”中。这个开放列表有点像一张购物清单。当前这个列表中只有一个元素，但一会儿将会有更多。列表中包含的方格可能会是你要途经的方格，也可能不是。总之，这是一个包含待检验方格的列表。 2.?????? 检查起点A相邻的所有可达的或者可通过的方格，不用管墙啊，水啊，或者其他什么无效地形，把它们也都加到开放列表中。对于每一个相邻方格，将点A保存为它们的“父方格”。当我们要回溯路径的时候，父方格是一个很重要的元素。稍后我们将详细解释它。 3.?????? 从开放列表中去掉方格A，并把A加入到一个“封闭列表”中。封闭列表存放的是你现在不用再去考虑的方格。 此时你将得到如下图所示的样子。在这张图中，中间深绿色的方格是你的起始方格，所有相邻方格目前都在开放列表中，并且以亮绿色描边。每个相邻方格有一个灰色的指针指向它们的父方格，即起始方格。 [图二]　 接下来，我们在开放列表中选一个相邻方格并再重复几次如前所述的过程。但是我们该选哪一个方格呢？具有最小F值的那个。 ? 路径排序 ? 决定哪些方格会形成路径的关键是下面这个等式： F = G + H 这里 ???G＝从起点A沿着已生成的路径到一个给定方格的移动开销。 ?? H＝从给定方格到目的方格的估计移动开销。这种方式常叫做试探，有点困惑人吧。其实之所以叫做试探法是因为这只是一个猜测。在找到路径之前我们实际上并不知道实际的距离，因为任何东西都有可能出现在半路上（墙啊，水啊什么的）。本文中给出了一种计算H值的方法，网上还有很多其他文章介绍的不同方法。 我们要的路径是通过反复遍历开放列表并选择具有最小F值的方格来生成的。本文稍后将详细讨论这个过程。我们先进一步看看如何计算那个等式。 ? 如前所述，G是从起点A沿着已生成的路径到一个给定方格的移动开销，在本例中，我们指定每一个水平或者垂直移动的开销为10，对角线移动的开销为14。因为对角线的实际距离是2的平方根（别吓到啦），或者说水平及垂直移动开销的1.414倍。为了简单起见我们用了10和14这两个值。比例大概对就好，我们还因此避免了平方根和小数的计算。这倒不是因为我们笨或者说不喜欢数学，而是因为对电脑来说，计算这样的数字也要快很多。不然的话你会发现寻找路径会非常慢。 ? 我们要沿特定路径计算给定方格的G值