分类: 2009 November 06

对于A*算法的一些疑问

一点声明
本文译自http://www-cs-students.stanford.edu/~amitp/Articles/AStar5.html,
版权归Amit所有.
本文谢绝任意形式的转载,演绎

Article 13518 of comp.games.development.programming.algorithms:
Path: nntp.stanford.edu!newsfeed.stanford.edu!logbridge.uoregon.edu
!cyclone-west.rr.com!news.rr.com|news-west.rr.com
!newsfeed2.earthlink.net!newsfeed.earthlink.net
!newsmaster1.prod.itd.earthlink.net
!newsread2.prod.itd.earthlink.net.POSTED!not-for-mail
From: “Tom Hatfield” <rskorpion@NOSPAMearthlink.net>
Newsgroups: comp.games.development.programming.algorithms
References: <8bvf90$rto$1@duke.telepac.pt>
Subject: Re: Path-finding algorithm
Lines: 97
Message-ID: <mXDF4.13013$64.467989@newsread2.prod.itd.earthlink.net>
Date: Sun, 02 Apr 2000 08:56:50 GMT
NNTP-Posting-Host: 63.27.26.87
Organization: EarthLink Inc. — http://www.EarthLink.net

> Hi,
>   我在寻找着一种路径-查找算法(我觉得是这么叫的).我正在写着基于瓷砖的游戏,我需要一种可以找到
>   绕过障碍物(无法被穿越的瓷砖)到达目的瓷砖的算法.

因为你并没有要求特定的编程语言,因此我仅仅是给出了算法的一个框架.下面是一个对于A*算法的半编码的描述,A*算法对于你所要求的找到穿越障碍物的路径的问题是快速而且高效的.你可以用它来处理很多其他的问题.

基本上,A*算法作用于以下3个部分:Opem表(存储需要被扫描的结点),Closed表(存储并不需要被扫描的结点)以及启发函数.在这里的问题中,一个”结点”包含一片瓷砖的简单信息.每片瓷砖有它自己的结点,但是扫描地图上的所有瓷砖的可能是很小的;事实上,一切顺利的话,你仅会扫描很少的一部分.

启发函数是A*算法效率的关键.它是从任意给定瓷砖到目标瓷砖的距离的估计.你的启发函数越接近真实距离,你寻找到的路径将越优.你能使用的最好的启发函数是连接起始结点到目标结点的直线:

d=|gx-sx|+|gy-sy|

为了让代码能够运行起来,你需要一个数组来保存Open表中的结点,另一个数组来保存Closed表中的结点.为了安全起见,Closed表的数组需要与你的地图大小(x*y)一样大,而Open表的数组大约是地图大小的一半.你的结点的结构大概就像下面的样子:

structure Node(n)

.XCoord

.YCoord

.Cost

.XParent

.YParent

现在让我们更深入地讨论该算法.我不能保证这一定是A*算法的最佳版本,因为这是我特别为Visual Bacis设计的(你步可能从因特网上找到一份VB语言编写的路径-查找算法,相信我).它的确含有一个我遇到过的不足,但是你可以稍作调整来满足你的需要.代码如下:

将起始结点压入Open表

Do:

找出Open表中拥有最佳的估计值的结点(耗散值+启发值)
把该结点压入Closed表中

If 该结点就是目标结点,结束程序,返回真值
Else,对该结点可达的所有邻居结点n:

计算结点n的估计值e(耗散值+启发值)

If 结点n已经在Open表中

If 结点n先前的估计值比当前的估计值e更优,那么仍保持结点n在Open表中
Else,把结点n移至Closed表中(它当前的估计值e更槽糕,因此我们可以无视n已经在Open表的事实)

If 结点n已经在Closed表中

If 结点n先前的估计值比当前的估计值e更优,把结点n移至Open表中
Else,那么仍保持结点n在Closed表中

If 结点n既不在Open表中,也不在Closed表中,那么把结点n移至Open表中

Loop while Open表中仍然有结点

当程序结束时,递归地查找结点的父亲位置得到最终的路径.

就是这样子.如果你在理解上有什么问题,我建议你可以在一张简单地图上,跟踪你是如何遍历结点的.这可以让你更好地理解算法如何运转.(我自己就这么做了)

就像我说的,这仅仅是A*算法众多实现中的一种.A*算法有很多变形,这决定于你的要求.也许你可以好好地检查这些实现:

我曾经问过一些人(A*算法的实现),但至今我没有得到任何回复.在下面描述中,你可以很快地做出一些修改,以得到更好的结果:

If 结点n已经在Closed表中

If 结点n先前的估计值比当前的估计值e更优,把结点n移至Open表中
Else,那么仍保持结点n在Closed表中

我不清楚在程序运行时,这会起到什么作用.但是在测试之后,我发现,将一个结点从Closed表中移出是没有什么道理的
不管怎么样,如果你有什么问题的话,尽量去尝试吧.这算法在很多情况下是可以工作的.祝你好运.

A*算法中启发函数的使用(2)

一点声明
本文译自http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html,
版权归Amit所有.
本文谢绝任意形式的转载,演绎

本文接上一篇 : A*算法中启发函数的使用(1)

栅格地图的启发函数

在栅格上,有很多著名的启发函数可以使用.

曼哈顿距离

标准的启发函数正是曼哈顿距离.不妨看一下你的耗散函数,假设从一个栅格移动到相邻的栅格上的最小代价D.因此,在我的游戏中,启发信息是D倍的曼哈顿距离.

h(n) = D * (abs(n.x-goal.x) + abs(n.y-goal.y))

你应该使用符合你的耗散函数的单位来衡量.

manhattan

(注:上面的图像中,启发函数可以找到好几条最优路径(下文称之为平局).)

对角线距离

如果你的地图允许对角线移动,那么你需要另外一个启发函数.在直角坐标中,(0,4)到(4,0)的曼哈顿距离是8*D.然而,你本可以简单的将点从(0,4)按东南方向移动至(4,0),所以启发信息应该是4*D.这个函数处理对角线问题,假定直线移动和对角线移动一个栅格的代价都是D:

h(n) = D * max(abs(n.x-goal.x), abs(n.y-goal.y))

diagonal

如果对角线移动一个栅格的代价并不是D,而是类似于D2=sqrt(2)*D,那么上面的启发函数对你而言又是错误的了.你可以使用一个更为复杂的启发函数代替它.

h_diagonal(n) = min(abs(n.x-goal.x), abs(n.y-goal.y))
h_straight(n) = (abs(n.x-goal.x) + abs(n.y-goal.y))
h(n) = D2 * h_diagonal(n) + D * (h_straight(n) - 2*h_diagonal(n)))

这里我们计算 h_diagonal(n) = 沿着对角线移动的步数, h_straight(n) = 曼哈顿距离,你可以通过考虑所有的对角线移动的步数(每步耗散D2)以及剩下的直线移动的步数(每步耗散D)将这两者结合在一起.

欧几里得距离

如果你的单元可以往任意方向移动(而不是沿着栅格的方向移动),那么你应该使用直线距离:

h(n) = D * sqrt((n.x-goal.x)^2 + (n.y-goal.y)^2)

然而,在这种情况下,由于耗散函数g与启发函数f并不匹配,因此这时A*算法是有问题的.因为欧几里得距离比起曼哈顿距离和对角线距离都更短,你得到的将仍然是最优路径,但A*算法运行时间将更长:

euclidean

平方的欧几里得距离

在好几个A*算法的网页上,我都看见在欧几里得距离关于避免计算量巨大的开方的计算,方法仅仅是对欧几里得距离做平方.

h(n) = D * ((n.x-goal.x)^2 + (n.y-goal.y)^2)

Do not do this!这绝对会导致g和h的比例的问题.当A*算法计算f(n)=g(n)+h(n)的时候,h的平方会导致它远大于g,这意味着你得到的会是过高估计的启发函数.对于更大的h,这会使得g(n)变得无足轻重了,此时A*算法退化成宽度优先搜索.

best-first-search-trap

打破平局

在某些地图中,存在着相同耗散值的路径(Arthur1989注:下文中一律称为平局).比如说,在没有凹凸的平原中,使用栅格将会得到许多路径,他们长度是一样的.A*也许会遍历所有的拥有一样的f值的路径,而不是仅仅遍历一条.(如果你的地图中有很多这样的区域,比起A*算法,对于每个栅格的搜索有其他更好的技巧.)

tie-breaking-off

f值相同导致的平局

为了解决这个问题,我们要么可以调整g,要么可以调整h.相对来说,调整h会更加容易.平局的打破对于每个结点的影响必须是确定的(即:它不应该是一个随机数),而且它必须使得每个结点的f值互异.因为A*算法(OPEN表)按结点的f值大小排序,让每个结点的f值互异也就是说,对于有着”相同的”f值的结点,仅有一个会被扩展.

一种打破平局的方法是,稍微的改变h的(单位).如果我们让h的单位减小,(那么h将变大),随着A*算法向目标结点扩展,f值将会增加.不幸的是,这意味着A*算法更偏向于扩展离起始结点较近的结点,而不是扩展离目标结点较近的结点.所以,我们可以将h的单位稍微增大一点(即使是0.1%),此时,A*算法将扩展目标结点旁边的结点.

heuristic *= (1.0 + p)

因子p的选择应该使得 p<(每走一步的最小代价)/(路径的期望最大值).假设你并不希望路径的步数超过1000,你可以将p设定为1/1000.打破平局的微小改变的结果是,A*算法扩展的结点远比原先的算法要少:

tie-breaking-scale-1

在启发信息中改变h或者g的比例

当存在障碍物时,A*算法还是需要找到一条绕过障碍物的路径,但请注意,当绕过障碍物之后,A*算法扩展很少结点:

tie-breaking-scale-2

Steven van Dijk 提议了一种更为直接的方法,即把h传递给比较函数.当结点的f值是相同的时候,比较函数可以通过h值判定结点优先级来打破平局.

另外一种打破平局的方法是计算坐标(二维地图中,结点的位置即为笛卡尔坐标)的哈希值,以此来调整启发函数.比起上述调整h的方法,它可以打乱更多的平局.对提出建议的 Cris Fuhrman 致敬.

还有一种不同的打破平局的方法是,偏向于离从起始结点到目标结点的直线较近的路径.

dx1 = current.x - goal.x
dy1 = current.y - goal.y
dx2 = start.x - goal.x
dy2 = start.y - goal.y
cross = abs(dx1*dy2 - dx2*dy1)
heuristic += cross*0.001

上面的代码计算了起始结点到目标结点的向量和当前结点到目标结点的向量的内积.当这些向量不在一队上的时候,内积会变得很大.结果是A*算法稍微的偏向于扩展分布在从起始结点到目标结点的直线附近的结点.当步存在障碍物的时候,A*算法不仅可以扩展更少的结点,它得到的路径看起来也很漂亮.

tie-breaking-cross-1

启发函数中考虑了内积,生成很漂亮的路径

然而,正如上面提过的,当存在障碍物时,A*算法得到的路径看起来会有点奇怪.(注意:路径仍然是最优的)

tie-breaking-cross-2

为了交互地看出这种打破平局的方法带来的效率的提升,你可以查看James Macgill写的A* applet [如果该网址已经不在了,你可以试试 这个镜像].使用”Clear”命令来清空地图,然后在地图的两个角落选中两个结点.当你使用”经典的A*算法”是,你会看见不同结点拥有相同f值的影响.当你使用”Fudge”命令时,你可以看到上面在启发函数中使用内积信息带来的不同.

还有一种打破平局的方法是仔细的构造你的A*算法的优先级队列,它插入一个启发函数值为f的新结点,新结点比原先队列中存在的启发函数值为f的旧结点总是获得更好(坏)的排名.

也许你还可以读读AlphA* algorithm,虽然该算法打破平局的方法更为复杂,但它仍能确保得到的路径是最优的.AlphA*算法是可适应的,而且它应该比上面提到的两种打破平局的方法表现得要更好.但是,后者更为容易实现,因此你可以从后者开始尝试,当需要算法更快时才使用AlphA*算法.

寻找一个区域

如果你想要寻找任何接近于目标结点的区域,你可以构造一个启发函数h'(x),h'(x)是h1(x),h2(x),h3(x),…中的最小值,其中,h1,h2,h3是对于每个临近结点的区域的启发信息.然而,一种更快的方法是,让A*算法查找目标区域的中心结点.