Forever Loop.

Trouble Busters

Thoughts on Pathfinding – A*简介

原文出自:http://theory.stanford.edu/~amitp/GameProgramming/index.html

这是一篇非常适合初学者的算法文章,尽管网络上已经存在一些翻译版本,但是最近作者又对其进行了一些额外的补充,本着分享知识,顺便锻炼一下自己的翻译水平和算法水平的想法,我将结合已有的译文版本以及自己的理解同时配上中文版的插图,竭尽所能为大家带来良好的体验。

A*算法,又称A-Star算法,别名启发式搜索。是一种在静态路网图中求解最短路径的有效的方法之一,在接下来较长的一段时间里我将为大家带来A*算法以及基于A*算法的不同路径搜索策略。

以下,正文开始:

单个对象的移动看上去很简单,但其寻路的过程却是十分复杂的。那么我们为什么说寻路是复杂的呢?请各位考虑以下的这种情况:

如图,假设现在有一个需要进行移动的对象,其初始位置位于图形的底部,最终目标是到达图形的最上端。由于在对象的扫描范围内(以粉红色标识)并没有任何的障碍物,所以对象会一直向上移动。直到在接近图形顶部的时候,对象才发现障碍并改变前进方向,最终沿着红色路径绕过U型障碍物到达终点。但与此相反,拥有路径搜索的对象会在一开始就扫描一块较大的区域(以浅蓝色标识),并生成一条短的多的路径(以蓝色标识),引导对象从一开始就绕过障碍物达到目标。

当然,你也可以改进对象的移动策略,让其可以一开始就避免如上图一样的障碍,或者将障碍物标识成危险的(除非最终目标在其中):

路径搜索让对象从一开始就能计划好前进方向,而不是等到最后一刻才发现问题。但是在加入路径搜索和改进移动策略之间却有一个折衷之处。虽然预先的规划可以获得更好的结果,但是却会消耗较多的时间;尽管改进的移动策略通常会更快但是却有可能在移动过程中卡住。如果路网图经常需要进行变动(比如游戏地图),那么预先的规划的价值就比较 。我推荐复合的使用以上两种策略:路径搜索应用在那些整体规模较大,改动频率较少,路径较长的路网图上;而把改进的移动策略应用在那些整体规模相比较小,改动频率相比较快,路径相比较短的路网图上。

算法:

在计算机科学相关的书籍中,对于图的数学解释是:一系列的由边连接的顶点。比如一张平铺的地图就可以当成是一个由多个彼此相邻的平面块通过顶点和边连接的图:

从现在开始,我会假定以一个游戏世界作为讨论背景,并且使用二维网格来进行说明。在这之后,我会就如何建立其他类型的图进行讨论。

有关二维网格、图的说明我会在稍候补充。

比起网格图,大部分来自AI人工智能以及算法研究的路径搜索策略是用来设计去解决任意图的寻路问题。有一些我们认为是常识的东西算法它却并不明白。比如距离:在一般情况下,当两个物体离得越来越远,在没用所谓虫洞的情况下,从一处移动到另一处所需要的时间就变得越来越长。比如方向:如果你的目标位于东方,那么最好的路径应该是尽可能得向东方移动而不是向西方移动。又比如网格图中关于对称性的特性:在大部分的情况下,先向北移动再向东移动与先向东移动再向北移动是相等的。这些额外的信息可以帮助我们使得路径搜索策略运行的更加快速。

迪杰斯特拉(Dijkstra)算法与最优优先搜索(Best-First-Search):

Dijkstra算法的原理就是以对象的起始点为起点,只要任意两个顶点之间的边没有负权值,则不断访问并检查最近的但并未被检查的顶点,然后将被访问顶点的所连接顶点加入已被检查的顶点系中。直到最后拓展至终点。那么Dijkstra算法能够保证找到从起点到终点的最短路径之一。(我之所以说“之一”是因为通常一个图中会有多个相等的最短路径。)在下面这张图中,粉红色的方块代表起始位置,蓝色的方块代表终点,蓝绿色的方块代表Dijkstra算法所扫描过的区域。而那些淡蓝绿色的方块代表离起点最远的区域,这一系列方块组成了扫描区域的“边界”:

贪婪最优优先搜索的原理与之类似,其不同之处在于它有一些对于任意顶点距离终点的路程有一些预估(称之为启发)。代替选择离起点最近的顶点,最优优先搜索会选择离终点最近的顶点。而且贪婪最有优先搜索算法并不能保证找到的一定是最短路径。然而,它的运行速度比起Dijkstra算法要快的多,因为最优优先搜索拥有的启发式功能使其可以快速的引导对象达到终点。例如,终点位于起点的南边,贪婪最优优先搜索将趋于保持路径的前进方向始终向南。在下面这张图中,黄色代表具有高启发值的节点(需要花费更多时间才能到达终点),黑色代表具有低启发值的节点(花费较少的时间就能到达终点)。从图中可以看出比起Dijkstra算法贪婪最优优先搜索可以更快速的找到路径:

然而,以上两个实例只是最简单的情况——图中没有任何障碍物,而且最短路径是一条直线。那么接下来我们来考虑一下在像前一节中那样,图中有一个U型障碍物的实例。尽管Dijkstra算法看起来更加复杂,但是却保证找到了最短路径:

另一方面,贪婪最优优先搜索看上去比较轻松,但显而易见找到的路径并不是最好的:

原因在于贪婪最优优先搜索是“贪婪的”,即使路径不是正确也要试图直接走向终点。由于只考虑到到达终点的花费而忽略了路径的花费,贪婪最优优先搜索会一直试图持续哪怕路径已经变得非常非常长。

那么如果能结合两者优势的算法那不会变得很棒么?结合了如贪婪最优优先搜索这样启发式方法以及Dijkstra算法这样较为正式的方法,A*算法于1968年被开发出来。比起那些总是只给你解决方案但并不保证是最优结果的启发式方法,A*显得有些不一样。基于启发式方法的A*能够保证找到的一定是最短路径。

A*算法:

我将重点放在了A*算法。A*算法在路径搜索中是一种比较流行的选择,因为它相当灵活而且可以在广泛的环境下使用。

A*就像Dijkstra算法一样可以被用来寻找最短路径。A*也可以像贪婪最优优先搜索一样使用启发式方法来引导自己。在简单的实例中,A*可以表现得和贪婪最优优先搜索一样快速:

在U型障碍物实例中,A*也找到了和Dijkstra算法找到的一样优秀的路径:

 

其成功之处的秘密在于结合了Dijkstra算法所使用的信息(离起点最近的顶点)以及贪婪最优优先搜索所使用的信息(离终点最近的顶点)。在A*算法中,g(n)表示路径从起点到任意顶点n的准确花费,h(n)表示启发式方法中任意顶点n到终点的预估花费。在上面这张图中,黄色的方块(h)表示距离终点较远的顶点,蓝绿色的方块(g)表示距离起点较远的方块。

A*会在从起点移动至终点的过程中对于这两类方块进行取舍。在每次搜索过程中,它会检查顶点n是不是具有最低的f(n) = g(n) + h(n)值。

在稍后,我将探讨有关启发式设计、实施、图的展示以及其他有关路径搜索的主题。有一些部分是较为完善的,然而另一些部分可能是不完整的。

评论

This site uses Akismet to reduce spam. Learn how your comment data is processed.