artificial-intelligence - A*寻路，计算G成本

Question

我在理解如何始终如一地计算正确的 G 成本以实现 A* 寻路时遇到了一些困难。据我了解，这是从起始节点移动到当前节点的成本，但我不完全了解的是如何找到用于增加 G 成本的值。我见过使用 10 和 14 等数字的示例，但这些是任意的吗？它是否取决于实现？

当我开发一个 2D 游戏时，我似乎不得不为 G 成本找到一个“最佳位置”(我应该注意到它似乎接近用作节点的地砖的宽度) 在我一直在寻找最短路径之前。

对此事的任何澄清都是很好的。

Answer 1

您定义它们。当你“走一步”时你添加到 G 的数量就是你告诉算法你真正喜欢什么路径的方式(H 只是对一堆 G 增量求和的可接受的近似值，可以帮助它更快地找到你想要的东西)。使用 10 和 14 是 1 和 sqrt(2) 的近似值，有点像如果你有欧几里得距离但你在每一步都被限制在摩尔邻域内会发生什么，有时这被称为“对角线距离”或“八分之一距离” ”(尽管该术语更恰本地保留用于使用准确的 sqrt(2))。因此，这个选择并非完全凭空而来。

但这取决于您，选择不同的成本会使 A* 更喜欢(或“不喜欢”)某些路径，例如，如果您使对角线成本与“直线”成本相同, 它真的很喜欢对角线移动，它不一定会避免来回曲折(只要曲折以正确的方式进行，这将是免费的，例如路径 /\ 的长度相同如--)。使用高对角线成本 (>2) 将使它找到的路径大部分看起来像您使用 von Neumann 邻域，除了在“紧急情况”下它仍然能够沿对角线移动。在 1 和 2 之间，差异不太明显，但有时会在障碍物周围出现。

因此，使用低于 sqrt(2) 的对角线成本往往会产生不必要的曲折的“奇怪”路径，而使用高于 sqrt(2) 的对角线成本往往会产生无法采用对角线捷径的“愚蠢”路径。但是你可能想要那个，特别是如果它与“实际成本”(如果你有的话)相匹配，例如单位花费的步行时间或类似的东西。再一次，在我自己的一个游戏中，我故意使对角线成本高于基于步行时间的成本，以使路径看起来更自然(否则它太曲折了)。

黄色是“已探索”。由于实现细节，底部路径绕道而行，对角线成本为 10(它从 NW 开始顺时针添加节点，并使用稳定插入 open 而不是像堆这样聪明的东西，所以具有相等 F 的节点是先添加的平局)。