A*寻路初探 原文出处:A* Pathfinding for Beginners 译者序 会者不难,A*(念作A星)算法对初学者来说的确有些难度。 这篇文章并不试图对这个话题作权威的陈述。取而代之的是,它只是描述算法的原理,使你可以在进一步的阅读中理解其他相关的资料。 我们正在提高自己。让我们从头开始...... 序:搜索区域 假设有人想从A点移动到一墙之隔的B点,如下图,绿色的是起点A,红色是终点B,蓝色方块是中间的墙。
你首先注意到,搜索区域被我们划分成了方形网格。像这样,简化搜索区域,是寻路的第一步。这一方法把搜索区域简化成了一个二维数组。数组的每一个元素是网格的一个方块,方块被标记为可通过的和不可通过的。路径被描述为从A到B我们经过的方块的集合。一旦路径被找到,我们的人就从一个方格的中心走向另一个,直到到达目的地。 开始搜索 正如我们处理上图网格的方法,一旦搜索区域被转化为容易处理的节点,下一步就是去引导一次找到最短路径的搜索。在A*寻路算法中,我们通过从点A开始,检查相邻方格的方式,向外扩展直到找到目标。 我们做如下操作开始搜索:
在这一点,你应该形成如图的结构。在图中,暗绿色方格是你起始方格的中心。它被用浅蓝色描边,以表示它被加入到关闭列表中了。所有的相邻格现在都在开启列表中,它们被用浅绿色描边。每个方格都有一个灰色指针反指他们的父方格,也就是开始的方格。
接着,我们选择开启列表中的临近方格,大致重复前面的过程,如下。但是,哪个方格是我们要选择的呢?是那个F值最低的。 路径评分 选择路径中经过哪个方格的关键是下面这个等式: F = G + H 这里:
我们的路径是通过反复遍历开启列表并且选择具有最低F值的方格来生成的。文章将对这个过程做更详细的描述。首先,我们更深入的看看如何计算这个方程。
现在我们来看看这些方格。写字母的方格里,G = 10。这是因为它只在水平方向偏离起始格一个格距。紧邻起始格的上方,下方和左边的方格的G值都等于10。对角线方向的G值是14。 继续搜索 为了继续搜索,我们简单的从开启列表中选择F值最低的方格。然后,对选中的方格做如下处理: 4.把它从开启列表中删除,然后添加到关闭列表中。 好了,让我们看看它是怎么运作的。我们最初的9格方格中,在起点被切换到关闭列表中后,还剩8格留在开启列表中。这里面,F值最低的那个是起始格右侧紧邻的格子,它的F值是40。因此我们选择这一格作为下一个要处理的方格。在紧随的图中,它被用蓝色突出显示。
首先,我们把它从开启列表中取出,放入关闭列表(这就是他被蓝色突出显示的原因)。然后我们检查相邻的格子。哦,右侧的格子是墙,所以我们略过。左侧的格子是起始格。它在关闭列表里,所以我们也跳过它。 那我们就选择起始格右下方的格子,如图。
这次,当我们检查相邻格的时候,发现右侧是墙,于是略过。上面一格也被略过。我们也略过了墙下面的格子。为什么呢?因为你不能在不穿越墙角的情况下直接到达那个格子。你的确需要先往下走然后到达那一格,按部就班的走过那个拐角。(注解:穿越拐角的规则是可选的。它取决于你的节点是如何放置的。) 我们重复这个过程,知道目标格被添加进开启列表,就如在下面的图中所看到的。
注意,起始格下方格子的父节点已经和前面不同的。之前它的G值是28,并且指向右上方的格子。现在它的G值是20,指向它上方的格子。这在寻路过程中的某处发生,当应用新路径时,G值经过检查变得低了-于是父节点被重新指定,G和F值被重新计算。尽管这一变化在这个例子中并不重要,在很多场合,这种变化会导致寻路结果的巨大变化。
A*方法总结 好,现在你已经看完了整个说明,让我们把每一步的操作写在一起:
题外话 离题一下,见谅,值得一提的是,当你在网上或者相关论坛看到关于A*的不同的探讨,你有时会看到一些被当作A*算法的代码而实际上他们不是。要使用A*,你必须包含上面讨论的所有元素--特定的开启和关闭列表,用F,G和H作路径评价。有很多其他的寻路算法,但他们并不是A*,A*被认为是他们当中最好的。Bryan Stout在这篇文章后面的参考文档中论述了一部分,包括他们的一些优点和缺点。有时候特定的场合其他算法会更好,但你必须很明确你在作什么。好了,够多的了。回到文章。 实现的注解 现在你已经明白了基本原理,写你的程序的时候还得考虑一些额外的东西。下面这些材料中的一些引用了我用C++和Blitz Basic写的程序,但对其他语言写的代码同样有效。
另一个在非方形区域搜索RPG地图的例子,查看我的文章:Two-Tiered A* Pathfinding。 进一步的阅读 好,现在你对一些进一步的观点有了初步认识。这时,我建议你研究我的源代码。包里面包含两个版本,一个是用C++写的,另一个用Blitz Basic。顺便说一句,两个版本都注释详尽,容易阅读,这里是链接。 例子代码:A* Pathfinder (2D) Version 1.71 如果你既不用C++也不用Blitz Basic,在C++版本里有两个小的可执行文件。Blitz Basic可以在从Blitz Basic网站免费下载的 litz Basic 3D(不是Blitz Plus)演示版上运行。Ben O''Neill提供一个联机演示可以在这里找到。 你也该看看以下的网页。读了这篇教程后,他们应该变得容易理解多了。
其它一些值得一看的网站: 其它参考文章: 好了,这就是全部。如果你刚好写一个运用这些观点的程序,我想见识见识。你可以这样联系我: 现在,好运!
|
http://blog.vckbase.com/panic/archive/2005/03/20/3778.html