0

我的 A* 算法在一定程度上发挥了作用。它会跟随玩家在一个空间中四处走动，但它不会绕过一个需要远离目标才能绕过它的物体。当它意识到下一个节点具有更高的 F 值（离目标更远）时，它会拒绝去那里，并且会继续寻找更低的 F 值（离目标更近的节点）而不找到一个（它卡在一个永无止境的循环）。

我认为我对启发式使用的理解可能是问题所在。

我的 A* 总是移动到具有最低 F 值 (H+G) 的下一个节点。除了将它们添加到 F 之外，我从不考虑 G 或 H 值。

在我读过的教程中，他们谈到使用 G 值，但我认为 F 值是唯一重要的值。

有人可以总结一下我如何使用启发式值。我想我快到了，只是启发式的使用令人困惑。

4

2 回答 2

1

您是否保留了备用路径段的优先级队列？如果你只看成本最低的下一步，你将无法绕过障碍。

于 2012-04-26T22:45:16.767 回答
1

你明白了。H 告诉您到达该节点实际需要多远；G 是您必须走多远的估计值。如果您只考虑 G，那么您会选择最接近目标的路径，即使到达该节点需要很长时间。这就是你使用 F (=H+G) 的原因，这样当你第一次达到一个目标时，你就知道它是最短路径的那个。

现在，如果您有无数条路径，那么试图找到最佳路径可能是个问题。或者您的路径生成算法可能有问题（例如，导致您重新考虑路径）。由于您没有就问题提供更多详细信息，因此我不能说更多可能有用的信息。

再说一次，你可能有一个糟糕的（或更糟糕的，不可接受的）启发式函数......

于 2012-04-26T22:46:39.390 回答