algorithm - 我不懂 A* 寻路

Question

据我了解：

将当前节点添加到关闭列表中。

找到与当前节点相邻的节点，如果它们不是不可行走节点且不在封闭列表中，则将该节点添加到开放列表中，父节点为当前节点，并计算 F、G 和 H 值。如果该节点已经存在于打开列表中，检查是否通过当前节点到达该节点会导致较低的 G 值 - 如果是，则将该节点的父节点设为当前节点。

在打开列表中找到 F 值最高的节点，并将当前节点设为该节点。

重复直到到达目的地，然后通过目的地节点的父节点，您将回到起始节点。那将是最好的道路。

所以，这对我的大脑来说是有意义的，但是当我在图表上实际尝试时，我认为我没有正确理解它。

（从下图）从一开始的绿色瓷砖往下走，F 值为 60 的那一张。那是在打开的列表中，它的 F 值低于右下角的 74 一张。为什么选择 74 而不是 60？

Answer 1

在我看来，你应该看看Amit 的 A* Pages。他们真的很高兴解释算法如何工作以及如何使其工作。

至于您的情况，该图显示了打开列表中第一个节点的 G 分数。看网站的时候，全图是先建的第一个节点评价，作者显示第一个最好的节点是最右边的那个。然后，向前移动使用基于当前节点的分数加上下一个节点的移动成本的G分数，图中未显示。

不过官网上是这么说的：

最后一个格子，在当前格子的左边，如果你通过当前格子到达那里，检查 G 分数是否更低。没有骰子。

如果我没记错的话，它的 G 分数实际上是 24（14（当前成本）+ 10（水平移动成本）），就像它下面的方块一样。

Answer 2

您不移动到 F 值为 60 的方格的原因是因为它在“封闭列表”中。其中 F 值为 88 和 74 的方格在“开放列表”中，可以检查下一步。