我不明白A*寻路

Question

据我所知:

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

查找当前节点的相邻节点,如果它们不是不可移动的节点而不是关闭的列表,则将该节点添加到打开列表中,父节点是当前节点,并计算F,G和H值.如果节点已经存在于打开列表中,请检查通过当前节点转到该节点是否会导致较低的G值 - 如果是,则使该节点的父节点成为当前节点.

在具有最高F值的打开列表中查找节点,并使当前节点成为该节点.

重复直到最终到达目的地,然后浏览目标节点的父节点,然后您将返回到起始节点.这将是最好的途径.

所以,这对我的大脑来说是有意义的,但是当我在图表上实际尝试时,我想我并没有正确地理解它.

(从下面的图片)从起始绿色瓷砖下来,F值为60的那个.这是在打开的列表上,并且具有比右下角74更低的F值.为什么选择74一个而不是60？

Answer 1

我认为，您应该看看Amit 的 A* Pages。他们确实很好地解释了算法的工作原理以及如何使其发挥作用。

对于您的情况，该图显示了打开列表中第一个节点的 G 分数。当你看网站时，整个图首先是为第一个节点评估而构建的，作者表明第一个最佳节点是右边的那个。然后，向前移动使用基于当前节点的得分加上下一个节点的移动成本的G得分，图中未示出。

不过网站上是这么说的：

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

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