文档介绍：A* 寻路算法。译者序很久以前就知道了 A* 算法, 但是从未认真读过相关的文章, 也没有看过代码, 只是脑子里有个模糊的概念。这次决定从头开始,研究一下这个被人推崇备至的简单方法,作为学习人工智能的开始。这篇文章非常知名, 国内应该有不少人翻译过它, 我没有查找, 觉得翻译本身也是对自身英文水平的锻炼。经过努力,终于完成了文档,也明白的 A* 算法的原理。毫无疑问,作者用形象的描述,简洁诙谐的语言由浅入深的讲述了这一神奇的算法,相信每个读过的人都会对此有所认识(如果没有,那就是偶的翻译太差了--b )。以下是翻译的正文。( 由于本人使用 ultraedit 编辑,所以没有对原文中的各种链接加以处理( 除了图表),也是为了避免未经许可链接的嫌疑,有兴趣的读者可以参考原文。会者不难, A*( 念作 A星) 算法对初学者来说的确有些难度。这篇文章并不试图对这个话题作权威的陈述。取而代之的是, 它只是描述算法的原理, 使你可以在进一步的阅读中理解其他相关的资料。最后, 这篇文章没有程序细节。你尽可以用任意的计算机程序语言实现它。如你所愿, 我在文章的末尾包含了一个指向例子程序的链接。压缩包包括 C++ 和 Blitz Basic 两个语言的版本,如果你只是想看看它的运行效果,里面还包含了可执行文件。我们正在提高自己。让我们从头开始...... 序:搜索区域假设有人想从 A 点移动到一墙之隔的 B点, 如下图, 绿色的是起点 A, 红色是终点 B, 蓝色方块是中间的墙。[图 1] 你首先注意到, 搜索区域被我们划分成了方形网格。像这样, 简化搜索区域, 是寻路的第一步。这一方法把搜索区域简化成了一个二维数组。数组的每一个元素是网格的一个方块,方块被标记为可通过的和不可通过的。路径被描述为从 A到B 我们经过的方块的集合。一旦路径被找到,我们的人就从一个方格的中心走向另一个, 直到到达目的地。这些中点被称为“节点”。当你阅读其他的寻路资料时, 你将经常会看到人们讨论节点。为什么不把他们描述为方格呢?因为有可能你的路径被分割成其他不是方格的结构。他们完全可以是矩形, 六角形, 或者其他任意形状。节点能够被放置在形状的任意位置-可以在中心,或者沿着边界,或其他什么地方。我们使用这种系统,无论如何,因为它是最简单的。开始搜索正如我们处理上图网格的方法, 一旦搜索区域被转化为容易处理的节点, 下一步就是去引导一次找到最短路径的搜索。在 A* 寻路算法中,我们通过从点 A 开始,检查相邻方格的方式,向外扩展直到找到目标。我们做如下操作开始搜索: A开始,并且把它作为待处理点存入一个“开启列表”。开启列表就像一张购物清单。尽管现在列表里只有一个元素,但以后就会多起来。你的路径可能会通过它包含的方格,也可能不会。基本上,这是一个待检查方格的列表。 ,跳过有墙,水,或其他无法通过地形的方格。也把他们加入开启列表。为所有这些方格保存点 A作为“父方格”。当我们想描述路径的时候,父方格的资料是十分重要的。后面会解释它的具体用途。 A,把它加入到一个“关闭列表”,列表中保存所有不需要再次检查的方格。在这一点,你应该形成如图的结构。在图中,暗绿色方格是你起始方格的中心。它被用浅蓝色描边, 以表示它被加入到关闭