当两条路径看起来返回相同的"长度"时,无法理解A*Pathfinding算法,但是一条路径会向我发送完全错误的方向

Question

我正在阅读使用启发式和曼哈顿方法的A*寻路,我正在努力理解文章中某个特定位置的逻辑.

我被困在下面的图像之后

并且更好地理解这里是一个引用

这一次,当我们检查相邻的方块时,我们发现右边的那个是一个墙方块,所以我们忽略它.对于正好在上面的那个也是如此.我们也忽略了墙下方的广场.为什么？因为你不能直接从当前的广场到达那个广场,而不会越过附近墙壁的角落.你真的需要先下去,然后转移到那个广场,在这个过程中转移.(注意:关于切角的这条规则是可选的.它的使用取决于节点的放置方式.)

而且 - 我突出了让我困惑的部分

剩下五个正方形.当前方块下方的其他两个方块尚未在开放列表中,因此我们添加它们,当前方块成为其父级.在其他三个正方形中,两个已经在闭合列表中(起始正方形,正好在当前正方形上方,在图中以蓝色突出显示),因此我们忽略它们.然后检查当前正方形左边的最后一个方格,看看如果你通过当前的方格到达那里,G得分是否更低.没有骰子.所以我们已经完成并准备好检查我们的开放列表中的下一个方块.

因此,作者假设左边的F(G + H)现在大于下面的F的F(G + H).从逻辑上讲,通过查看是的,甚至一个孩子都会同意你应该朝着RED走向蓝色的墙壁,但是在数学上(除非有一些明显我错过的东西)我在这一点上这样看待它

因此,如果我在C#中写出这个算法,我会被卡住,因为"现在这里"的左边和底部都会返回相同的数字,60？我怎么知道哪一个我会受益于最多？

即使在这种情况下,这个数字仍然是IMO等于60

• 10直接左转+50(H)

• 10直接向下+ 50(H)

我错过了什么吗？我究竟做错了什么？

Answer 1

G成本是累积的.

从起点开始,往东南方向行驶费用14.从东南方广场(您的"现在这里"广场)向南行驶费用为10,这使得累计G成本为10 + 14 = 24.

再次,从东南方广场(你的"现在这里"广场)向西行驶将花费10点(G)再次给我们24点(因为我们已经支付了14点到达那个广场).但是这个方块已经在你的开放列表中,所以你检查你刚刚得到的结果是否更好.您的打开列表显示该广场的G为​​10,因为24更差,您不会更新它.(这是大胆部分的意思)