A *寻路，计算G成本
宇航员
我在理解如何始终如一地计算出正确的G成本以实施A *寻路时遇到了一些困难。据我了解，这是从起始节点移动到当前节点的成本，但是我不完全了解如何找到用于增加G成本的值。我已经看到了使用数字（例如10和14）的示例，但是这些示例是任意的，并且取决于实现吗？
在开发2D游戏时，似乎几乎要为G成本找到一个“最佳位置”（我应该注意，这似乎与用作节点的地砖的宽度接近）。一直在寻找最短的路径。
关于此事的任何澄清都将是巨大的。
哈罗德
您定义它们。当您“走一步”时，您添加到G的数量就是告诉算法您真正喜欢什么路径的方式（H只是对一堆G增量求和的可允许近似值，可以帮助它更快地找到所需的内容）。使用10和14近似为1和sqrt（2），有点像如果您有欧几里得距离，但每一步都被限制在Moore邻域时会发生的情况，有时这被称为“对角距离”或“闭塞距离” ”（尽管更恰当的是，该术语保留用于使用准确的sqrt（2））。因此，这种选择并非一无是处。
但它是你的，选择不同的成本，使得A *喜欢（或“不喜欢”）某些路径，例如，如果你做的对角成本一样的“直”的成本，它真的会像斜移动时，它会并不一定要避免来回曲折（只要Zig沿正确的方向移动/\就可以了，例如，路径的长度与相同--）。使用较高的对角线成本（> 2）将使它查找的路径看起来几乎与您使用冯·诺依曼（von Neumann）街区相似，只是在“紧急情况”下它仍可以沿对角线移动。在1和2之间，差异并不明显，但有时会出现在障碍物周围。
因此，使用对角线成本低于sqrt（2）往往会形成不必要的锯齿形“奇怪”路径，而使用对角线成本高于sqrt（2）往往会导致“哑”路径无法采用对角线快捷方式。但是您可能想要这样，特别是如果它与“实际成本”（如果有）相匹配，例如单位花费的步行时间或类似的时间。再说一次，在我自己的一款游戏中，我故意使对角线的成本高于根据步行时间而得出的对角线成本，以使路径看起来更自然（否则过于曲折）。
黄色是“已探索”。底部路径由于实现细节而绕道而行，对角线成本为10（它从NW开始顺时针添加节点，并使用稳定插入open而不是像堆一样聪明的东西，因此F相等的节点被平局，首先添加）。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
编辑于
相关文章
Related 相关文章
- 1
A *寻路算法-卡住了计算最短路径的时间
- 2
Python Libtcod：如何在变动的移动成本范围内进行寻路？
- 3
Python Libtcod：如何在变动的移动成本范围内进行寻路？
- 4
复杂的寻路算法
- 5
火车寻路算法
- 6
体贴的寻路AI
- 7
寻路算法
- 8
寻路-StackOverflowError
- 9
A *寻路非常慢
- 10
决策寻路
- 11
实现 A* 寻路算法
- 12
寻路算法名称
- 13
寻路-最少转弯的A *
- 14
在R中实现寻路
- 15
大地图上的寻路
- 16
SKNode无法进行寻路
- 17
A *寻路中的奇怪行为
- 18
寻路Python算法回溯
- 19
Android - 室内寻路建议
- 20
如何使我的寻路算法不反向？
- 21
使用多个代理进行A *寻路
- 22
A *寻路未走最短路径
- 23
A *寻路问题。编译但行为异常
- 24
步数最少的寻路算法
- 25
寻路算法使利润最大化
- 26
多个源和汇的寻路？
- 27
寻路问题。奇怪的路径被返回
- 28
A *寻路Java无法正常工作
- 29
基于线和交点的寻路
我来说两句