我对如何持续地计算正确的A*寻路算法中的G值有些困难。据我所知，它是从起始节点移动到当前节点的代价，但我不完全明白如何找到用于递增G值的数值。我见过一些示例使用像10和14这样的数字，但是这些数字是任意的吗？是否取决于实现方式？
当我在开发2D游戏时，似乎我必须找到G值的“甜点”（我应该注意到它似乎接近作为节点使用的地板瓷砖的宽度），然后才能持续地找到最短路径。
关于这个问题的任何澄清都将是很好的。
1个回答
3
您自己定义它们。当您“走一步”时，将添加到G的数量是告诉算法您真正喜欢的路径的方法（H仅是一个可接受的逼近，用于加速找到所需内容的一堆G增量的总和）。使用10和14是1和sqrt（2）的逼近，有点像如果您具有欧几里德距离，但在每个步骤上都受到 Moore邻域的限制，有时称为“对角线距离”或“八方向距离”（尽管更恰当的术语是使用准确的sqrt（2））。因此，这个选择并非毫无根据。
但是选择不同的代价取决于您，A *更喜欢（或“不喜欢”）某些路径，例如，如果您使对角线成本与“直线”成本相同，则它将非常喜欢对角线移动，它不一定会避免来回曲折（只要Zig走正确的方式，例如路径/\的长度将与--相同）。使用高对角线成本（> 2）将使其找到的路径大多看起来像您使用的von Neumann邻域，只是在“紧急情况”下仍然能够对角移动。在1和2之间，差异明显小得多，但有时会在障碍物周围出现。
因此，使用小于sqrt（2）的对角线成本倾向于产生“奇怪”的路径，这些路径需要不必要地曲折，而使用大于sqrt（2）的对角线成本则倾向于产生“愚蠢”的路径，无法采取对角线捷径。但是您可能希望如此，特别是如果它匹配“实际成本”（如果您有一个），例如单位所需的步行时间等。另一方面，在我自己的游戏中，我故意使对角线成本高于基于步行时间的成本，以使路径看起来更自然（否则它太曲折了）。
黄色表示“已探索”。底部路径因实现细节而采用对角线成本10的迂回路线（它从西北开始顺时针添加节点，并使用稳定插入到open中，而不是像堆一样聪明地做些事情，因此具有相等F值的节点在哪个先添加了被打破了平局）。
- harold
3
感谢您的解释。在我创建的游戏中，没有对角线移动，即根本不可能进行对角线移动。当实施此算法时，是否通常假定可以进行对角线移动？还是认为它是可选的？我只是觉得奇怪，使用10的成本导致玩家走了更长的路，而当我增加G时，最终它总是选择最短的路径，同样是没有对角线移动的情况下。 - Astronought
1@samcp20，你可以选择任何一组邻居，它甚至适用于任意图形！所以，对角线移动完全是可选的。当然，如果你没有对角线移动，对角线成本就不是问题。无论如何，从你的措辞方式来看，似乎你调整了G但没有调整H，在这种情况下，使G变小会导致它失败（这使得启发式不可接受，因此可能找不到最优解）。 - harold
啊，我明白了。我有机会的时候会再做一些实验。再次感谢您提供如此详细的解释，非常感激。 - Astronought
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接