寻路算法:A*寻路初探

译者序:很久以前就知道了A*算法但是从未认真读过相关文章也没有看过代码只是脑子里有个模糊概念这次决定从头开始研究下这个被人推崇备至简单思路方法作为学习人工智能开始
这篇文章非常知名国内应该有不少人翻译过它我没有查找觉得翻译本身也是对自身英文水平锻炼经过努力终于完成了文档也明白A*算法原理毫无疑问作者用形象描述简洁诙谐语言由浅入深讲述了这神奇算法相信每个读过人都会对此有所认识(如果没有那就是偶翻译太差了--b)
原文链接:http://www.gamedev.net/reference/articles/article2003.asp
以下是翻译正文(由于本人使用ultraedit编辑所以没有对原文中各种链接加以处理(除了图表)也是为了避免未经许可链接嫌疑有兴趣读者可以参考原文

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

这篇文章并不试图对这个话题作权威陈述取而代的是它只是描述算法原理使你可以在进步阅读中理解其他相关资料

最后这篇文章没有细节你尽可以用任意计算机语言实现它如你所愿我在文章末尾包含了个指向例子链接 压缩包包括C和Blitz Basic两个语言版本如果你只是想看看它运行效果里面还包含了可执行文件

我们正在提高自己让我们从头开始

序:搜索区域

假设有人想从A点移动到墙的隔B点如下图绿色是起点A红色是终点B蓝色方块是中间墙


[图1]

你首先注意到搜索区域被我们划分成了方形网格像这样简化搜索区域是寻路第步这思路方法把搜索区域简化成了个 2维每个元素是网格个方块方块被标记为可通过和不可通过路径被描述为从A到B我们经过方块集合旦路径被找到我们人就从个方格中心走向另个直到到达目地

这些中点被称为“节点”当你阅读其他寻路资料时你将经常会看到人们讨论节点为什么不把他们描述为方格呢？有可能你路径被分割成其他不是方格结构他们完全可以是矩形 6角形或者其他任意形状节点能够被放置在形状任意位置－可以在中心或者沿着边界或其他什么地方我们使用这种系统无论如何它是最简单

开始搜索

正如我们处理上图网格思路方法旦搜索区域被转化为容易处理节点下步就是去引导次找到最短路径搜索在A*寻路算法中我们通过从点A开始检查相邻方格方式向外扩展直到找到目标

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


1从点A开始并且把它作为待处理点存入个“开启列表”开启列表就像张购物清单尽管现在列表里只有个元素但以后就会多起来你路径可能会通过它包含方格也可能不会基本上这是个待检查方格列表
2寻找起点周围所有可到达或者可通过方格跳过有墙水或其他无法通过地形方格也把他们加入开启列表为所有这些方格保存点A作为“父方格”当我们想描述路径时候父方格资料是十分重要后面会解释它具体用途
3从开启列表中删除点A把它加入到个“关闭列表”列表中保存所有不需要再次检查方格

在这点你应该形成如图结构在图中暗绿色方格是你起始方格中心它被用浅蓝色描边以表示它被加入到关闭列表中了所有相邻格现在都在开启列表中它们被用浅绿色描边每个方格都有个灰色指针反指他们父方格也就是开始方格


[图2]

接着我们选择开启列表中临近方格大致重复前面过程如下但是哪个方格是我们要选择呢？是那个F值最低

路径评分

选择路径中经过哪个方格关键是下面这个等式:

F = G + H

这里:
* G = 从起点A沿着产生路径移动到网格上指定方格移动耗费
* H = 从网格上那个方格移动到终点B预估移动耗费这经常被称为启发式可能会让你有点迷惑这样叫原因是它只是个猜测我们没办法事先知道路径长度路上可能存在各种障碍(墙水等等)虽然本文只提供了种计算H思路方法但是你可以在网上找到很多其他思路方法

我们路径是通过反复遍历开启列表并且选择具有最低F值方格来生成文章将对这个过程做更详细描述首先我们更深入看看如何计算这个方程

正如上面所说G表示沿路径从起点到当前点移动耗费在这个例子里我们令水平或者垂直移动耗费为10对角线方向耗费为14我们取这些值是沿对角线距离是沿水平或垂直移动耗费根号2(别怕)或者约1.414倍为了简化我们用10和14近似比例基本正确同时我们避免了求根运算和小数这不是只我们怕麻烦或者不喜欢数学使用这样整数对计算机来说也更快捷你不就就会发现如果你不使用这些简化思路方法寻路会变得很慢

既然我们在计算沿特定路径通往某个方格G值求值思路方法就是取它父节点G值然后依照它相对父节点是对角线方向或者直角方向(非对角线)分别增加14和10例子中这个思路方法需求会变得更多我们从起点方格以外获取了不止个方格

H值可以用区别思路方法估算我们这里使用思路方法被称为曼哈顿思路方法它计算从当前格到目格的间水平和垂直方格数量总和忽略对角线方向然后把结果乘以10这被成为曼哈顿思路方法是它看起来像计算城市中从个地方到另外个地方街区数在那里你不能沿对角线方向穿过街区很重要点我们忽略了切障碍物这是对剩余距离个估算而非实际值这也是这思路方法被称为启发式原因想知道更多？你可以在这里找到方程和额外注解

F值是G和H和第步搜索结果可以在下面图表中看到F,G和H评分被写在每个方格里正如在紧挨起始格右侧方格所表示F被打印在左上角G在左下角H则在右下角




[图3]

现在我们来看看这些方格写字母方格里G = 10这是它只在水平方向偏离起始格个格距紧邻起始格上方下方和左边方格G值都等于10对角线方向G值是14

H值通过求解到红色目标格曼哈顿距离得到其中只在水平和垂直方向移动并且忽略中间墙用这种思路方法起点右侧紧邻方格离红色方格有3格距离H值就是30这块方格上方方格有4格距离(记住只能在水平和垂直方向移动)H值是40你大致应该知道如何计算其他方格H值了～

每个格子F值还是简单由G和H相加得到

继续搜索

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

4把它从开启列表中删除然后添加到关闭列表中
5检查所有相邻格子跳过那些已经在关闭列表中或者不可通过(有墙水地形或者其他无法通过地形)把他们添加进开启列表如果他们还不在里面话把选中方格作为新方格父节点
6如果某个相邻格已经在开启列表里了检查现在这条路径是否更好换句话说检查如果我们用新路径到达它话G值是否会更低些如果不是那就什么都不做
另方面如果新G值更低那就把相邻方格父节点改为目前选中方格(在上面图表中把箭头方向改为指向这个方格)最后重新计算F和G值如果这看起来不够清晰你可以看下面图示

好了让我们看看它是如何运作我们最初9格方格中在起点被切换到关闭列表中后还剩8格留在开启列表中这里面F值最低那个是起始格右侧紧邻格子它F值是40因此我们选择这格作为下个要处理方格在紧随图中它被用蓝色突出显示


[图4]

首先我们把它从开启列表中取出放入关闭列表(这就是他被蓝色突出显示原因)然后我们检查相邻格子哦右侧格子是墙所以我们略过左侧格子是起始格它在关闭列表里所以我们也跳过它

其他4格已经在开启列表里了于是我们检查G值来判定如果通过这格到达那里路径是否更好我们来看选中格子下面方格它G值是14如果我们从当前格移动到那里G值就会等于20(到达当前格G值是10移动到上面格子将使得G值增加10)G值20大于14所以这不是更好路径如果你看图就能理解和其通过先水平移动格再垂直移动格还不如直接沿对角线方向移动格来得简单

当我们对已经存在于开启列表中4个临近格重复这过程时候我们发现没有条路径可以通过使用当前格子得到改善所以我们不做任何改变既然我们已经检查过了所有邻近格那么就可以移动到下格了

于是我们检索开启列表现在里面只有7格了我们仍然选择其中F值最低有趣是这次有两个格子数值都是54我们如何选择？这并不麻烦从速度上考虑选择最后添加进列表格子会更快捷这种导致了寻路过程中在靠近目标时候优先使用新找到格子偏好但这无关紧要(对相同数值区别对待导致区别版本A*算法找到等长区别路径)

那我们就选择起始格右下方格子如图


[图5]

这次当我们检查相邻格时候发现右侧是墙于是略过上面格也被略过我们也略过了墙下面格子为什么呢？你不能在不穿越墙角情况下直接到达那个格子你确需要先往下走然后到达那格按部就班走过那个拐角(注解:穿越拐角规则是可选它取决于你节点是如何放置)

这样来就剩下了其他5格当前格下面另外两个格子目前不在开启列表中于是我们添加他们并且把当前格指定为他们父节点其余3格两个已经在开启列表中(起始格和当前格上方格子在表格中蓝色高亮显示),于是我们略过它们最后格在当前格左侧将被检查通过这条路径G值是否更低不必担心我们已经准备好检查开启列表中下格了

我们重复这个过程知道目标格被添加进开启列表就如在下面图中所看到


[图6]

注意起始格下方格子父节点已经和前面区别的前它G值是28并且指向右上方格子现在它G值是20指向它上方格子这在寻路过程中某处发生当应用新路径时G值经过检查变得低了－于是父节点被重新指定G和F值被重新计算尽管这变化在这个例子中并不重要在很多场合这种变化会导致寻路结果巨大变化

那么我们如何确定这条路径呢？很简单从红色目标格开始按箭头方向朝父节点移动这最终会引导你回到起始格这就是你路径！看起来应该像图中那样从起始格A移动到目标格B只是简单从每个格子(节点)中点沿路径移动到下个直到你到达目标点就这么简单


[图7]

A*思路方法整理总结

好现在你已经看完了整个介绍说明让我们把每步操作写在起:

1把起始格添加到开启列表
2重复如下工作:
a) 寻找开启列表中F值最低格子我们称它为当前格
b) 把它切换到关闭列表
c) 对相邻8格中每个？
* 如果它不可通过或者已经在关闭列表中略过它反的如下
* 如果它不在开启列表中把它添加进去把当前格作为这格父节点记录这格F,G,和H值
* 如果它已经在开启列表中用G值为参考检查新路径是否更好更低G值意味着更好路径如果是这样就把这格父节点改成当前格并且重新计算这格G和F值如果你保持你开启列表按F值排序改变的后你可能需要重新对开启列表排序

d) 停止当你
* 把目标格添加进了开启列表这时候路径被找到或者
* 没有找到目标格开启列表已经空了这时候路径不存在
3.保存路径从目标格开始沿着每格父节点移动直到回到起始格这就是你路径



题外话

离题下见谅值得提是当你在网上或者相关论坛看到有关A*区别探讨你有时会看到些被当作A*算法代码而实际上他们不是要使用A*你必须包含上面讨论所有元素－－特定开启和关闭列表用F,G和H作路径评价有很多其他寻路算法但他们并不是A*A*被认为是他们当中最好Bryan Stout在这篇文章后面参考文档中论述了部分包括他们些优点和缺点有时候特定场合其他算法会更好但你必须很明确你在作什么好了够多了回到文章

实现注解

现在你已经明白了基本原理写你时候还得考虑些额外东西下面这些材料中些引用了我用C和Blitz Basic写但对其他语言写代码同样有效

1维护开启列表:这是A*寻路算法最重要组成部分每次你访问开启列表你都需要寻找F值最低方格有几种区别思路方法实现这点你可以把路径元素随意保存当需要寻找F值最低元素时候遍历开启列表这很简单但是太慢了尤其是对长路径来说这可以通过维护格排好序列表来改善每次寻找F值最低方格只需要选取列表首元素当我自己实现时候这种思路方法是我首选

在小地图这种思路方法工作很好但它并不是最快解决方案更苛求速度A*员使用叫做“binary heap”思路方法这也是我在代码中使用思路方法凭我经验这种思路方法在大多数场合会快2～3倍并且在长路经上速度呈几何级数提升(10倍以上速度)如果你想了解更多有关binary heap内容查阅我文章Using Binary Heaps in A* Pathfinding

2其他单位:如果你恰好看了我例子代码你会发现它完全忽略了其他单位我寻路者事实上可以相互穿越取决于具体游戏这也许可以也许不行如果你打算考虑其他单位希望他们能互相绕过我建议在寻路算法中忽略其他单位写些新代码作碰撞检测当碰撞发生你可以生成条新路径或者使用些标准移动规则(比如总是向右等等)直到路上没有了障碍然后再生成新路径为什么在最初路径计算中不考虑其他单位呢？那是其他单位会移动当你到达他们原来位置时候他们可能已经离开了这有可能会导致奇怪结果个单位突然转向躲避个已经不在那里单位并且会撞到计算完路径后冲进它路径中单位

然而在寻路算法中忽略其他对象意味着你必须编写单独碰撞检测代码这因游戏而异所以我把这个决定权留给你参考文献列表中Bryan Stout文章值得研究里面有些可能解决方案(像鲁棒追踪等等)

3些速度方面提示:当你开发你自己A*或者改写我你会发现寻路占据了大量CPU时间尤其是在大地图上有大量对象在寻路时候如果你阅读过网上其他材料你会明白即使是开发了星际争霸或帝国时代专家这也无可奈何如果你觉得寻路太过缓慢这里有些建议也许有效:

* 使用更小地图或者更少寻路者
* 不要同时给多个对象寻路取而代的是把他们加入个队列把寻路过程分散在几个游戏周期中如果你游戏以40周期每秒速度运行没人能察觉但是他们会发觉游戏速度突然变慢当大量寻路者计算自己路径时候
* 尽量使用更大地图网格这降低了寻路中搜索总网格数如果你有志气你可以设计两个或者更多寻路系统以便使用在区别场合取决于路径长度这也正是专业人士做法用大区域计算长路径然后在接近目标时候切换到使用小格子/区域精细寻路如果你对这个观点感兴趣查阅我文章Two-Tiered A* Pathfinding
* 使用路径点系统计算长路径或者预先计算好路径并加入到游戏中
* 预处理你地图表明地图中哪些区域是不可到达我把这些区域称作“孤岛”事实上他们可以是岛屿或其他被墙壁包围等无法到达任意区域A*下限是当你告诉它要寻找通往那些区域路径时它会搜索整个地图直到所有可到达方格/节点都被通过开启列表和关闭列表计算这会浪费大量CPU时间可以通过预先确定这些区域(比如通过flood-fill或类似思路方法)来避免这种情况发生,用某些种类记录这些信息在开始寻路前检查它在我Blitz版本代码中我建立了个地图预处理器来作这个工作它也标明了寻路算法可以忽略死端这进步提高了寻路速度

4区别地形损耗:在这个教程和我附带中地形只有两种－可通过和不可通过但是你可能会需要些可通过地形但是移动耗费更高－沼泽小山地牢楼梯等等这些都是可通过但是比平坦开阔地移动耗费更高地形类似道路应该比自然地形移动耗费更低

这个问题很容易解决只要在计算任何地形G值时候增加地形损耗就可以了简单给它增加些额外损耗就可以了由于A*算法已经按照寻找最低耗费路径来设计所以很容易处理这种情况在我提供这个简单例子里地形只有可通过和不可通过两种A*会找到最短最直接路径但是在地形耗费区别场合耗费最低路径也许会包含很长移动距离－就像沿着路绕过沼泽而不是直接穿过它

种需额外考虑情况是被专家称的为“influence mapping”东西(暂译为影响映射图)就像上面描述区别地形耗费样你可以创建格额外分数系统并把它应用到寻路AI中假设你有张有大批寻路者地图他们都要通过某个山区每次电脑生成条通过那个关口路径它就会变得更拥挤如果你愿意你可以创建个影响映射图对有大量屠杀事件格子施以不利影响这会让计算机更倾向安全些路径并且帮助它避免总是仅仅路径短(但可能更危险)而持续把队伍和寻路者送到某特定路径

5处理未知区域:你是否玩过这样PC游戏电脑总是知道哪条路是正确即使它还没有侦察过地图？对于游戏寻路太好会显得不真实幸运是这是格可以轻易解决问题

答案就是为每个区别玩家和电脑(每个玩家而不是每个单位－－那样话会耗费大量内存)创建个独立“knownWalkability”每个包含玩家已经探索过区域以及被当作可通过区域其他区域直到被证实用这种思路方法单位会在路死端徘徊并且导致选择直到他们在周围找到路旦地图被探索了寻路就像往常那样进行



6平滑路径:尽管A*提供了最短最低代价路径它无法自动提供看起来平滑路径看下我们例子最终形成路径(在图7)最初步是起始格右下方如果这步是直接往下话路径不是会更平滑些吗？

有几种思路方法来解决这个问题当计算路径时候可以对改变方向格子施加不利影响对G值增加额外数值也可以换种思路方法你可以在路径计算完的后沿着它跑遍找那些用相邻格替换会让路径看起来更平滑地方想知道完整结果查看Toward More Realistic Pathfinding篇(免费但是需要注册)Marco Per发表在Gamasutra.com文章

7非方形搜索区域:在我们例子里我们使用简单2D方形图你可以不使用这种方式你可以使用不规则形状区域想想冒险棋游戏和游戏中那些国家你可以设计个像那样寻路关卡为此你可能需要建立个国家相邻关系表格和从个国家移动到另个G值你也需要估算H值思路方法其他事情就和例子中完全样了当你需要向开启列表中添加新元素时候不需使用相邻格子取而代的是从表格中寻找相邻国家

类似你可以为张确定地形图创建路径点系统路径点般是路上或者地牢通道转折点作为游戏设计者你可以预设这些路径点两个路径点被认为是相邻如果他们的间直线上没有障碍话在冒险棋例子里你可以保存这些相邻信息在某个表格里当需要在开启列表中添加元素时候使用它然后你就可以记录关联G值(可能使用两点间直线距离)H值(可以使用到目标点直线距离)其他都按原先做就可以了

另个在非方形区域搜索RPG地图例子查看我文章Two-Tiered A* Pathfinding

进步阅读

好现在你对些进步观点有了初步认识这时我建议你研究我源代码包里面包含两个版本个是用C写另个用Blitz Basic顺便说句两个版本都注释详尽容易阅读这里是链接

* 例子代码:A* Pathfinder (2D) Version 1.71

如果你既不用C也不用Blitz Basic,在C版本里有两个小可执行文件Blitz Basic可以在从Blitz Basic网站WebSite免费下载litz Basic 3D(不是Blitz Plus)演示版上运行Ben O\'Neill提供个联机演示可以在这里找到

你也该看看以下网页读了这篇教程后他们应该变得容易理解多了

* Amit A* 页面:这是由Amit Patel制作被广泛引用页面如果你没有事先读这篇文章可能会有点难以理解值得看尤其要看Amit有关这个问题自己看法
* Smart Moves:智能寻路:Bryan Stout发表在Gamasutra.com这篇文章需要注册才能阅读注册是免费而且比起这篇文章和网站WebSite其他资源是非常物有所值Bryan用Delphi写帮助我学习A*也是我A*代码灵感的源它还描述了A*几种变化
* 地形分析:这是格高阶但是有趣话题Dave Pottinge撰写Ensemble Studios专家这家伙参和了帝国时代和君王时代开发别指望看懂这里所有东西但是这是篇有趣文章也许会让你产生自己想法它包含些对mip-mappinginfluence mapping以及其他些高级AI/寻路观点对\"flood filling\"讨论使我有了我自己“死端”和“孤岛”代码灵感这些包含在我Blitz版本代码中

其他些值得看网站WebSite:

* aiGuru: Pathfinding
* Game AI Resource: Pathfinding
* GameDev.net: Pathfinding

好了这就是全部如果你刚好写个运用这些观点我想见识见识你可以这样联系我:
现在好运！

延伸阅读

• 2009-2-12-- 寻路算法:A*寻路算法(For 初学者)
• 2009-2-12-- 寻路算法: 4种寻路算法并比较