寻路算法揭秘(4):实用 A* 算法

介绍

本系列的前三篇文章从寻路算法的基础知识开始,最后非常清晰明了地阐述了A *算法。这在理论上是很好的,但对于理解如何在实践中应用它却是一个不同的主题。

例如,如果你的世界不是网格怎么办?

如果你的角色不能瞬间旋转90度怎么办?

如果你的世界是无限的,你又该如何建立一个图表?

如果您不关心路径上的长度,但是您依赖太阳光并且需要尽可能地在阳光下呢?

如何找到两个目标节点中任何一个的最短路径?

成本(Cost)函数

在最初的示例中,我们搜索了从开始节点到目标节点之间的最短路径。然而,我们没有将路径长度存储在一个变量 length 中,而是将其命名为 cost,为什么呢?

A* 搜索不仅仅能搜索到最短路径,还可以搜索到你定义的“最好”的路径,这对我们的目标是有好处的。当我们想要最短路径时,代价时路径的长度;但当我们想要最小化,比如说,燃料消耗,那就得把它当作消耗成本(cost);如果你想最大化“阳光下的时间”,那么成本就是没有阳光的时间。诸如此类…

这通常意味着图中的每一条边都与一个特定的成本相关。在最初的例子中,因为我们在计算路径上的步长,路径的成本是隐式的,假设它总是为 1,但是你可以根据你想要的最小化的任何值来调整每条边的成本。

目标(Goal)函数

假设你是一辆汽车,需要去加油站。任何加油站都可以。您想要到最短的路径的最近加油站。

一种天真的方法是依次计算到每个加油站的最短路径,然后选择最短的路径。这会奏效,但这会非常浪费。

你可以做的是用过一个方法来替换单一的目标节点(goal_node),这个方法根据给定的节点来判断是否是目标节点。这样你可以同时寻找多个目标,你还可以调整启发式算法,以返回所有可能目标的最小估计成本。

根据你的具体情况,你可能无法准确到达目标,或者这样做成本很高(如果你在一张巨大的地图中传送一个角色,你会在一哪怕一英寸的差距吗?),因此,方法 is_goal_node 可以在“足够接近”时返回 true

不需要很明确

将世界表示为离散的网格对于许多游戏来说可能不够好。例如,考虑第一人称射击游戏或赛车游戏,世界是离散的,你不能用网格来表示它。

但这还有一个更大的难题,如果世界是无限大的呢?在这种情况下,即使你可以把它表示成为一个网格,你也不能建立与网格相对应的图形,因为它是一个无限大的图像。

然而,希望并没有丧失。我们确实需要一个图表来运行图形搜索算法,但是没人说图表必须是明确的。

如果仔细查看算法,你会注意到我们对图表整体没有做任何事情。相反,我们通过正在考虑的节点中获取可以到达的节点,正如 A* 算法演示中看到的,图中的一些节点根本没有被探索过。

那么,如果我们只是在搜索时才去构建图形该怎么办?

我们将起始节点设置为当前角色的位置。无论何时调用方法 get_adjacent_nodes,它都可以找出角色从给定节点移动的可能方向,并在运行中创建相邻节点。

超越三重维度

即使您的世界是 2D 网格,也需要考虑其他因素。例如,如果你的角色不能瞬间转90度或180度,这种情况该怎么办?

每个搜索节点所代表的状态步兵局限于某个位置,相反,它可以包括一组任意复杂的值。例如,如果旋转90度从一个方块走到另外一个方块所需的时间相同,那么角色的状态可以是: [坐标(position), 航向(heading)]。现在,每个节点不仅仅表示角色的位置,还表示角色的航向,图的每一条新边(隐式或显示)反应了这一点。

回到最初的 5x5 的网格,现在搜索的起始坐标可能是 [A, East],相邻节点现在则是 [B, East] 和 [A, South]。如果你想到达 F 节点,首先你需要先修正你的航向,所以路径将是 [A, East] -> [A, South] -> [F, South]。

而第一人称射击游戏呢?你至少需要四个维度:[X, Y, Z, 航向],设置可能是:[X, Y, Z, 航向, 血量, 弹药]。

请注意,状态越复杂,启发式函数也就会越复杂。

结论

这几篇文章的目的是一劳永逸的消除 A* 算法是一种神秘的,难以理解的感觉。相反,我已经证明了它没有什么神秘之处。事实上,它可以用一种非常直接的方式从0开始推导出来。

进一步阅读

阿米特·帕特尔(Amit Patel)有一篇非常好的关于 A* 算法介绍,当然他的其他主题文章也是非常棒的。