A路径寻找算法初涉.doc

A*路径寻找算法入门 来源于: GameD 作?者: Patrick Lester 原文URL:  HYPERLINK /reference/articles/article2003.asp /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这两个值。比例大概对就好，我们还因此避免了平方根和小数的计算。这倒不是因为我们笨或者说不喜欢数学，而是因为对电脑来说，