游戏开发中的经典算法(配图版，百度文库需下载券)_游戏设计的100个原理pdf下载资源-CSDN文库

游戏开发

A*寻路

5星 · 超过95%的资源需积分: 10 114 浏览量 2014-05-12 15:52:33 上传评论 4 收藏 357KB DOC 举报

资源推荐

资源详情

资源评论

算法一：A*寻路初探

译者序：很久以前就知道了 算法，但是从未认真读过相关的文章，也没有看过代码，只是脑子里

有个模糊的概念。这次决定从头开始，研究一下这个被人推崇备至的简单方法，作为学习人工智能的开

始。

这篇文章非常知名，国内应该有不少人翻译过它，我没有查找，觉得翻译本身也是对自身英文水平的锻

炼。经过努力，终于完成了文档，也明白的 算法的原理。毫无疑问，作者用形象的描述，简洁诙谐的

语言由浅入深的讲述了这一神奇的算法，相信每个读过的人都会对此有所认识。

原文链接：

以下是翻译的正文。由于本人使用  编辑，所以没有对原文中的各种链接加以处理除了图表，

也是为了避免未经许可链接的嫌疑，有兴趣的读者可以参考原文。

会者不难，A*(念作 A 星)算法对初学者来说的确有些难度。

这篇文章并不试图对这个话题作权威的陈述。取而代之的是，它只是描述算法的原理，使你可以在

进一步的阅读中理解其他相关的资料。

最后，这篇文章没有程序细节。你尽可以用任意的计算机程序语言实现它。如你所愿，我在文章的

末尾包含了一个指向例子程序的链接。压缩包包括 和  ! 两个语言的版本，如果你只是想

看看它的运行效果，里面还包含了可执行文件。我们正在提高自己。让我们从头开始。。。

序：搜索区域

假设有人想从  点移动到一墙之隔的  点，如图，绿色的是起点 ，红色是终点 ，蓝色方块是中间的

墙。

!"图 #$

!!!!你首先注意到，搜索区域被我们划分成了方形网格。像这样，简化搜索区域，是寻路的第一步。这一

方法把搜索区域简化成了一个二维数组。数组的每一个元素是网格的一个方块，方块被标记为可通过的

和不可通过的。路径被描述为从  到  我们经过的方块的集合。一旦路径被找到，我们的人就从一个方

格的中心走向另一个，直到到达目的地。

这些中点被称为“节点”。当你阅读其他的寻路资料时，你将经常会看到人们讨论节点。为什么不把他

们描述为方格呢？因为有可能你的路径被分割成其他不是方格的结构。他们完全可以是矩形，六角形，

或者其他任意形状。节点能够被放置在形状的任意位置－可以在中心，或者沿着边界，或其他什么地方。

我们使用这种系统，无论如何，因为它是最简单的。

开始搜索

正如我们处理上图网格的方法，一旦搜索区域被转化为容易处理的节点，下一步就是去引导一次找

到最短路径的搜索。在 寻路算法中，我们通过从点  开始，检查相邻方格的方式，向外扩展直到找到

目标。

我们做如下操作开始搜索：

%%!#，从点  开始，并且把它作为待处理点存入一个“开启列表”。开启列表就像一张购物清单。尽管现在

列表里只有一个元素，但以后就会多起来。你的路径可能会通过它包含的方格，也可能不会。基本上，

这是一个待检查方格的列表。

%%!，寻找起点周围所有可到达或者可通过的方格，跳过有墙，水，或其他无法通过地形的方格。也把他

们加入开启列表。为所有这些方格保存点  作为“父方格”。当我们想描述路径的时候，父方格的资料是十

分重要的。后面会解释它的具体用途。

%%!，从开启列表中删除点 ，把它加入到一个“关闭列表”，列表中保存所有不需要再次检查的方格。

在这一点，你应该形成如图的结构。在图中，暗绿色方格是你起始方格的中心。它被用浅蓝色描边，

以表示它被加入到关闭列表中了。所有的相邻格现在都在开启列表中，它们被用浅绿色描边。每个方格

都有一个灰色指针反指他们的父方格，也就是开始的方格。

!"图 $

接着，我们选择开启列表中的临近方格，大致重复前面的过程，如下。但是，哪个方格是我们要选

择的呢？是那个 & 值最低的。

路径评分：选择路径中经过哪个方格的关键是下面这个等式：

F = G + H

这里：

%%%%!'!(!从起点 ，沿着产生的路径，移动到网格上指定方格的移动耗费。

%%%%!)!(!从网格上那个方格移动到终点  的预估移动耗费。这经常被称为启发式的，可能会让你有点迷

惑。这样叫的原因是因为它只是个猜测。我们没办法事先知道路径的长度，因为路上可能存在各种障碍

墙，水，等等。虽然本文只提供了一种计算 ) 的方法，但是你可以在网上找到很多其他的方法。

我们的路径是通过反复遍历开启列表并且选择具有最低 & 值的方格来生成的。文章将对这个过程做

更详细的描述。首先，我们更深入的看看如何计算这个方程。

正如上面所说，' 表示沿路径从起点到当前点的移动耗费。在这个例子里，我们令水平或者垂直移

动的耗费为 #，对角线方向耗费为 #*。我们取这些值是因为沿对角线的距离是沿水平或垂直移动耗费

的的根号 （别怕），或者约 #*#* 倍。为了简化，我们用 # 和 #* 近似。比例基本正确，同时我们避

免了求根运算和小数。这不是只因为我们怕麻烦或者不喜欢数学。使用这样的整数对计算机来说也更快

捷。你不就就会发现，如果你不使用这些简化方法，寻路会变得很慢。

既然我们在计算沿特定路径通往某个方格的 ' 值，求值的方法就是取它父节点的 ' 值，然后依照它

相对父节点是对角线方向或者直角方向非对角线，分别增加 #* 和 #。例子中这个方法的需求会变得

更多，因为我们从起点方格以外获取了不止一个方格。

H 值可以用不同的方法估算。我们这里使用的方法被称为曼哈顿方法，它计算从当前格到目的格之

间水平和垂直的方格的数量总和，忽略对角线方向，然后把结果乘以 # 。这被成为曼哈顿方法是因为它

看起来像计算城市中从一个地方到另外一个地方的街区数，在那里你不能沿对角线方向穿过街区。很重

要的一点，我们忽略了一切障碍物。这是对剩余距离的一个估算，而非实际值，这也是这一方法被称为

启发式的原因。想知道更多？你可以在这里找到方程和额外的注解。

& 的值是 ' 和 ) 的和。第一步搜索的结果可以在下面的图表中看到。&+' 和 ) 的评分被写在每个方

格里。正如在紧挨起始格右侧的方格所表示的，& 被打印在左上角，' 在左下角，) 则在右下角。

!"图 $

现在我们来看看这些方格。写字母的方格里，'!(!#。这是因为它只在水平方向偏离起始格一个格

距。紧邻起始格的上方，下方和左边的方格的 ' 值都等于 #。对角线方向的 ' 值是 #*。

)!值通过求解到红色目标格的曼哈顿距离得到，其中只在水平和垂直方向移动，并且忽略中间的墙。

用这种方法，起点右侧紧邻的方格离红色方格有  格距离，) 值就是 。这块方格上方的方格有 * 格距

离记住，只能在水平和垂直方向移动，) 值是 *。你大致应该知道如何计算其他方格的 ) 值了～。

每个格子的 & 值，还是简单的由 ' 和 ) 相加得到

继续搜索

为了继续搜索，我们简单的从开启列表中选择 & 值最低的方格。然后，对选中的方格做如下处理：

%%!*，把它从开启列表中删除，然后添加到关闭列表中。

%%!,，检查所有相邻格子。跳过那些已经在关闭列表中的或者不可通过的(有墙，水的地形，或者其他无

法通过的地形)，把他们添加进开启列表，如果他们还不在里面的话。把选中的方格作为新的方格的父节

点。

%%!-，如果某个相邻格已经在开启列表里了，检查现在的这条路径是否更好。换句话说，检查如果我们用

新的路径到达它的话，' 值是否会更低一些。如果不是，那就什么都不做。

%%%%另一方面，如果新的 ' 值更低，那就把相邻方格的父节点改为目前选中的方格（在上面的图表中，把

箭头的方向改为指向这个方格）。最后，重新计算 & 和 ' 的值。如果这看起来不够清晰，你可以看下面

的图示。

好了，让我们看看它是怎么运作的。我们最初的 . 格方格中，在起点被切换到关闭列表中后，还剩 /

格留在开启列表中。这里面，& 值最低的那个是起始格右侧紧邻的格子，它的 & 值是 *。因此我们选择

这一格作为下一个要处理的方格。在紧随的图中，它被用蓝色突出显示。

剩余24页未读，继续阅读

评论收藏

内容反馈

ctohpmiao

2014-11-28

写得听详细的，适合入门者~

YoungXYYX

粉丝: 9
资源: 16

游戏开发中的经典算法(配图版，百度文库需下载券)

最新资源