algorithm - 明星寻路。为什么你需要重新评估一个已经在开放列表中的相邻节点，如果它比当前节点具有更低的 g 成本？

Question

关于星形寻路算法，有一件事我不明白。在伪代码中；如果当前节点(正在分析的节点)的 g 成本小于相邻节点的 g 成本，则重新计算相邻节点的 g,h a f 成本并重新分配父节点。 你为什么这么做？

如果gCost大于当前节点的gCost，为什么还要重新计算相邻节点的cost和parent？我是什么情况下你需要这样做？

编辑；我正在看这个视频 https://www.youtube.com/watch?v=C0qCR18gXdU\

在 8 点 19 分，他说:当你遇到已经分析过的 block (节点)时，问题是我们是否应该更改 block 的属性？

Answer 1

先给个提示。实际上，您可以将您想要的时间添加为书签，以获取从您想要的位置开始的视频。在这种情况下 https://www.youtube.com/watch?v=C0qCR18gXdU#t=08m19s是书签时间链接。

现在快速回答您的问题。我们在第一次找到到它的路径时填充一个节点。但是我们找到的第一条路径可能不是最便宜的。我们想要最便宜的，如果我们找到更便宜的一秒钟，我们就想要它。

这是一个视觉隐喻。想象一条旁边有栅栏的跑道。我们想要的地方在栅栏的另一边。把这个画出来，会有帮助。

我们的算法找到的第一条路径是沿着路径运行，跳过栅栏。我们找到的第二条路径是沿着路径走一半，穿过大门，然后到达那个地方。我们不想仅仅因为我们已经发现我们可以通过跳过栅栏到达那里而放弃使用大门的想法!

现在在您的图片中列出从一个地点移动到另一个地点的成本，这些成本对于沿着运行路径、开阔 field 、通过大门和跳过栅栏移动是合理的。手动运行该算法，您会发现您首先发现您可以跳过栅栏，然后您才真正想使用门。