A *寻路径。保存路径

Question

我被我的路径查找程序卡住了。目前它可以找到正确的路径，但我无法仅绘制路径。 我做了一个小小的变化，只有水平的垂直& ..没有对角线。所以只使用G成本而不用H或F成本。

使用这种tutorial

它说： 保存路径。从目标广场向后工作，从每个广场到其父广场，直到您到达起始广场。那是你的道路。

问：我怎样才能找到父广场，并回到工作中？

目前打印我的封闭列表中的节点，并得到这个：

Answer 1

当你做一个A * pathfind，每个瓦片也应存储哪些瓷砖是其母公司（如什么瓷砖发现的最佳路径我） 。这样，当您第一次找到到达结尾的路径时，您将按如下方式重建路径：

• 将结尾图块添加到路径中。
• 将结束图块的父项添加到路径中。
• 结束瓷砖的父亲的父亲的路径添加到...

......直到你在开始。

如果这不起作用（给你不是最好的路径），你可能不会让第一个路径通过更好的路径被重写，或者你使用的启发式过于自信，实际上最快的路径从来没有被测试过，因为它找到了一条已经结束的路径，并且被启发式和A *的贪婪本性所假设，没有其他路径更快。