c# - A* 寻路.. 保存路径

Question

我被我的寻路程序困住了。目前它可以找到正确的路径，但我无法仅绘制路径。我只在水平和垂直方向上做了一些变化。没有对角线。所以只使用 G 成本而不使用 H 或 F 成本。

使用本教程

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

问：如何找到父方格并返回？

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

Answer 1

当您进行 A* 路径查找时，每个图块还应存储其父图块（例如，哪个图块发现了我的最佳路径）。这样，当您第一次找到到达终点的路径时，您可以按如下方式重构路径：

• 将结束图块添加到路径。
• 将结束 tile 的父级添加到路径中。
• 将结束磁贴的父级添加到路径...

...直到你开始。

如果这不起作用（给你不是最好的路径），你可能不会让第一个到瓷砖的路径被更好的路径覆盖，或者你使用的启发式方法过于自信并且从未测试过实际最快的路径，因为它已经找到了一条通向终点的路径，并且根据启发式和 A* 的贪婪本性假设没有其他路径更快。