Forever Loop.

Trouble Busters

Thoughts on Pathfinding – 启发式

启发式函数h(n)用于告知A*从图中任意一个顶点n到终点的最小预计花费。因此选择(构造)一个好的启发式函数是非常重要的。

启发式在A*中的体现:

启发式可以用来控制A*的表现。

  • 在极端情况下,如果h(n)为0,那么这时只有g(n)在负责A*,于是A*算法就变成了能够保证找到最短路径的Dijkstra算法。
  • 如果h(n)总是低于(或者等于)从n移动到终点的花费,A*依旧能够保证找到最短路径。h(n) 越小,A*拓展的节点越多,使得运行速度变慢。
  • 如果h(n)正好等于从n移动到终点的花费,那么A*将只快速得追踪生成的最短路径并且不再拓展节点。尽管这种情况并不可能常常发生,但是你可以在某些特别的环境下使用这种特性。只要你给了A*所需要的最佳的信息,A*的表现将非常优秀。
  • 在另一个极端情况下,如果h(n)相对于g(n)实在是太高了,那么这时只有h(n)在负责A*,于是A*算法就变成了贪婪最优优先搜索。

于是,我们对于h(n)如何控制A*的表现有了一个有趣的认识:在非常恰好的情况下,我们会非常快速得获得最短路径。但如果h(n)太低了,尽管我们依然能够获得最短路径,可是运行速度却变慢了。反之如果h(n)太高了,我们不一定能够获得最短路径,但是运行速度会变快。

A*的这个属性是非常有用的。举个例子,在某些情况下,你可能宁可需要一个只要“足够了”的路径而不是“完美”的路径。于是此时只要改变g(n)和h(n)之间的平衡,你就可以获得自己想要的结果。

注意:从技术上来讲,如果启发式功能没被使用,那么A*算法应该只被称为A。但是,我将仍然称之为A*因为它们的实现仍然是相同的,而且社区上几乎从来不会特意区分A还是A*。

速度还是准确?

A*基于启发式和花费(成本、权值)函数而改变特性的能力使它在游戏地图设计中非常有用。你可以自主权衡控制速度和正确性使得你的游戏运行得更加快速。对于大部分的游戏来说,你可能只需要和两点之间最短路径差不多的路径(点击衔接查看英文说明)。因为你需要的东西往往要取决于游戏本身或者计算机的性能。

假设你的游戏中有两种不同的地形,平面和山路,平面的移动成本是1而山路的移动成本是3,A*有可能会搜索到一条约为山路三倍长度的平面路径。这是因为那条平面路径有可能是沿着山路绕了一个圈子。但是你可以通过设置两个区块之间的启发路径为1.5来加快A*的搜索速度。此时A*将只搜索花费成本1.5至3的所能生成的路径,这样生成的路径至少会比比较1至3的成本要好一些。经过这样的设置,A*将不会“不满”山路地形以至于花费更多的时间去搜索绕着山路走的路径。或者,你也可以通过降低A*搜索山路的成本来加速搜索——告诉A*在山路的移动成本是2,而不是3。这样,A*搜索出的平面路径可能只为山路路径的两倍长度。这样的设置放弃了对于最短路径的执着,但是加快了搜索速度。

速度还是准确之间的选择并是一成不变的。你可以基于CPU性能,路径搜索话费的时间,地图区块的数量,目标的重要性,群集的规模,关卡的难度等等因素动态选择。实现这样一个动态调整的方法是构造一个启发式函数假定移动一个网格空间的最小花费是1然后构造一个成本函数,其规模为:

g'(n) = 1 + alpha * (g(n) – 1)

如果alpha值为0,那么改变后的成本函数的值将永远为1.这样的设置使得不同地形的成本被完全忽略,如果alpha的值为1,A*的所有特性会被激活。这样的实现使得你可以在任何时候调整A*的特性。

但是你应当考虑将启发式返回的绝对最低成本转变成预期最小成本。举个例子,如果地图中大部分的地形是成本为2的草地,然后仅有一些地形是成本为1的平面,那么你就应该考虑将启发式设置成假定没有任何平面地形,然后将平面地形返回值设置成2*距离。

速度和准确之间的选择在程序中并不需要全局固定。你可以根据你的需求动态调整性能。举个例子,当移动过程可能存在岔路时,找一个并不是最好的路径就是一个好的选择,何必为了准确的最短路径消耗计算时间呢?同样的,在安全区域移动时同样也不需要准确的最短路径,但是一旦路径中有危险的区域,或者说有潜伏要素时,那么安全又快速的路径就是必不可少的。

规模:

A*计算公式为:f(n) = g(n) + h(n)。为了将两个值相加,这两个值必须是同等规模的。如果g(n)的单位是小时,但h(n)的规模确实米,那么A*会认为g太大了或者h太小了,那么你要么得不到最佳的路径,要么A*的速度将变得非常缓慢。

精确启发:

如果你的启发式生成的路径距离正好等于最优路径距离,那么你会发现A*只会扩展非常少的节点,这种情况下的图像将在下一节为大家展示。这是因为A*在每个节点都会计算f(n) = g(n) + h(n)。当h(n)与g(n)完全相同时,f(n)的值不会随着路径而改变。所有不在正确路径中的节点将有一个比那些正确路径节点更高的f值。由于A*在拥有低f值节点的时候不会考虑那些有高f值的节点,所以在搜索过程中,A*从来不会偏离最短路径。

预先计算的精确启发

构造一个精确启发式的方法是预先计算每对点之间的最短路径长度。尽管这个方法并不适用于大部分的图。但是,也有类似的解决方法:

  • 在较“粗”的网格上“盖上”较“细”的网格。预先计算较粗网格点之间的最短路径。
  • 对于粗网格的一般解决方法就是预先计算任意点之间的最短路径。

然后添加一个预估从任意点至附近点的启发式h’。(如果有必要,也可以预先计算。)那么最后的启发式应该是这个样子:

h(n) = h'(n, w1) + distance(w1, w2) + h'(w2, goal)

线性的精确启发

在一些特殊的情况下,启发式可以不被预先计算就构造出来。如果你有一个没有任何障碍的图,那么最短路径就应该是一条直线。

如果你在使用一个简单的启发式(无法得知图上是不是有障碍物),那么它的结果应该匹配精确启发。如果不是,那么你也许存在一个规模上的问题或者启发类型选择的问题。

网格的精确启发:

在网格中,有一些众所周知的启发式可以使用。

使用符合移动规范的距离启发式:

  • 在一个允许四向移动的方形网格中,使用曼哈顿距离(L1)。
  • 在一个允许八向移动的方形网格中,使用对角线距离(L)。
  • 在一个允许任意方向移动的方形网格中,或许会选择使用欧几里得距离(L2)。如果A*正在一个不允许移动的网格上进行搜索,你应该考虑其他的图的表现方式。
  • 在一个允许六向移动的六边形网格中,曼哈顿距离也同样对之适用。

曼哈顿距离

对于一个方形网格最标准的启发式就是曼哈顿距离。看看的成本函数,找出从一个空间转移到相邻空间的最小成本D。在一个简单的实例中,我们可以把D设置成1。那么这个方形网格的启发式得到的可以移动的空间应该是曼哈顿距离的D倍:

function heuristic(node) =

dx = abc(node.x – goal.x)

dy = abs(node.y – goal.y)

return D * (dx + dy)

那么我们应该如何选择D的值呢?只要选择一个匹配成本函数的规模即可。对于最优路径,以及一个“可容忍”的启发式,把D的值设置成相邻空间的最小值。在那些没有障碍物,地形具有最小移动成本D,每移动近终点一步,我们就应该D对g增加D同时对h减少D。当你加上它们两个,f(f = g + h)将保持一致时;说明启发式和成本函数的规模是匹配的。你可以放弃优化路径并增加D使得A*运行的更快,或者减少D以在最低或者最高成本路径中进行选择。

(注意:上面这张图的启发式是有对当路径拥有相同成本时进行选择功能的。)

对角线距离

如果你的图允许对角线移动,那么你需要一个不同的启发式(有的时候叫做切比雪夫距离)。比如你先往东移动4格,再往南移动4个,曼哈顿距离将是8*D。但是,你也可以直接向东南方向移动4格,所以此时启发式距离就是4*D。这个函数对对角线进行处理,计算所有直边和对角线的花费D:

function heuristic(node) =

dx = abs(node.x – goal.x)

dy = abs(node.y – goal.y)

return D * max(dx, dy)

如果对角线移动的花费并不等于D,而是类似于D2 = sqrt(2)*D这样的存在,那么上面这个启发式可能并不对你使用。你需要一些更复杂的启发式:

function heuristic(node) =

dx = abs(node.x – goal.x)

dy = abs(node.y – goal.y)

return D * (dx + dy) + (D2 – 2 * D) * min(dx, dy)

这将会当你无法对角线移动时计算你移动的步数,然后减去你使用对角线移动剩下的步数。这样的话会有min(dx, dy)的对角线步数,每一步的成本是D2但是省下了2*D的非对角线移动步数。

Patrick Lester对于这个启发式有不同的想法,对于明确情况下dx > dy 与 dx < dy之间,上面的代码拥有的同样的效果但是隐藏了min的实现。

欧几里得距离

如果你可以向任何方向移动(不仅仅是网格的边),那么你应该使用对角线距离:

function heuristic(node) =

dx = abs(node.x – goal.x)

dy = abs(node.y – goal.y)

return D * sqrt(dx * dx + dy * dy)

但是,使用这种方法有可能会使你在使用A*的时候产生一些问题,因为成本函数g将不和启发式h相匹配。尽管你仍然能获得最佳路径,但是却要花费大量的时间去计算:

平方欧几里得距离

我曾经看到过一些有关A*的网页,它们推荐在使用欧几里得距离前将距离进行平方计算以避免算法中消耗资源较多的、对之求平方根的计算:

function heuristic(node) =

dx = abs(node.x – goal.x)

dy = abs(node.y – goal.y)

return D * (dx * dx + dy * dy)

不要这样做!这样做的话很显然会发生规模问题。因为你需要使用g和h来生成f,所以它们的规模必须匹配。当A*计算f(n) = g(n) + h(n)时,距离的平方的规模会比成本g的规模来的多得多,这会导致你的启发式因为预估值过高而停止。对于那些更长的距离,这样做会使得g(n)接近其极值并不再于f(n)产生联系,此时A*就会退化成贪婪最优优先搜索:

为了解决这个问题你可以降低启发式的规模。但此时,你又会面对另一个问题:对于那些较短的距离,启发式会变得不和g(n)产生联系,A*退化成了迪杰斯特拉算法。

经过分析,你最后就会发现花费一点资源去计算平方根带来的优势是显著的,无论你在欧几里得距离中使用逼近法进行计算还是使用对角线距离作为对欧几里得距离的一种近似求解。

多目标

如果你想搜寻任意个目标路径,你可以构建一系列的诸如h1(x),h2(x),h3(x)…的,分别代表至临近节点的启发式。

如果你想搜索一个目标附近的点,只要要求A*去搜索一个到目标区域中心的路径即可。

打破关联

在一些网格图中会有许多相同长度路径。比如,在一个没有任何地形变动的平面中,使用网格图会出现许多相同长度的路径。A*会去探索所有具有相同f值的路径,而不是其中一条。

为了解决这个问题,我们可以调整g或者h的值。这个打破关联的值必须是确切确定的(它不应该是一个随机数),同时它必须能够使f的值各不相同。因为A*通过f的值进行排序,使得f的值不一样能够使之确切肯定某条路径会被探索。

打破关联的一种方法是稍稍改变h的规模。如果我们降低它的规模,那么f的值会随着我们越来越接近终点而逐渐增加。不幸的是,这就意味着A*会更倾向于扩展那些更接近于起点而不是终点的路径。但只要我们稍稍再提高h的规模一点点(甚至是0.1%)。A*将变得更倾向于扩展接近终点的路径了。

heuristic *= (1.0 +p)

因子p应当是慎重选择过的使得p<(移动一步的最小代价)/(期望的最长路径长度)。比如你不希望你的路径长度超过1000步,那么你可以选择p=1/1000。(需要根据实际情况选择。)那么有了这个打破关联特性的A*算法搜索的路径将比之前探索的路径短得多:

当存在障碍物时,A*仍然会沿着障碍物搜索,但是注意当跨过障碍物时,A*只探索了很少的节点:

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 – dy2*dy1)

heuristic += cross*0.001

这段代码计算了从起点到终点的向量和当前位置到终点的向量。当这些向量不是相接的时候,叉积会变得很大。结果就是这段代码选择的路径会倾向选择像一条从起点到终点的直线的路径。当没有障碍物时,A*不仅只搜索最少的区域,而且搜索出的路径也非常棒:

然而,因为这种打破关联的方式倾向于选择一条直线,所以当有障碍物时,就会出现很奇怪的结果(注意这条路径仍然是最佳的,只是看上去很奇怪):

为了交互地演示这些打破关联的方式,你可以参考James Macgill’s A* 演示(或者尝试这个镜像,或者这个镜像)。使用“清除”来清除图,然后选择两个对角的店。当你使用“经典A*”方法时,你会观察到关联给算法带来的印象。当你使用“Fudge”方法时,你可以看到将叉积添加给启发式后带来的效果。

另一种打破关联的方法是小心地构造A*的优先级队列,使得新插入的对象总是低于那些已经插入的,具有相同f值的对象。

还有另一种打破关联的方法就是尽可能的减少转弯。x,y值的改变能够告诉你现在正转向的方向。你可以对发生方向改变的情况添加一个小小的“惩罚”来增加移动成本。

如果关联很常见,上述的一些方法可以帮助你解决效率低下的问题。当有许多相同花费的路径出现时,关联现象就会产生。所以你考虑的方向是“更聪明的工作,而不是更幸苦。”

评论

  1. 憋了好久终于憋出来了,下一篇会是什么时候呢?

  2. 自动引用通知:Thoughts on Pathfinding – 实现(下) | Forever Loop.

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