algorithm - A-Star算法（重构路径）

Question

我已经设法实现了 a* 并且我得到了正确的路径。

问题是我如何重建从头到尾的路径，因为每个节点（从头到尾）都有一个父链接，但不是第一个，所以我的角色不知道先去哪里。

我正在做的是返回封闭列表并从索引 0 开始到 x 直到我到达末尾。这通常效果很好，但我知道必须有另一种方法。

---

另外，检查相邻节点的最佳方法是什么？

我已经让每个节点创建一个矩形并查看它是否相交，这就是我知道它们连接的方式。我还对玩家使用这种技术来了解何时到达节点。

谢谢！！

Answer 1

你有你的目标节点（一旦找到，你可以简单地缓存它）。

沿着树向上（使用该parent字段）直到找到一个没有它的节点，这个节点就是你的根。您通过链接找到的路径是相反顺序的最短路径。

我曾经解决过一个类似的问题，关于 BFS 而不是 A*

编辑：将堆栈反转回原始堆栈的一种简单方法是在从目标到源时将节点放入堆栈中，当您找到源时 - 开始将元素弹出堆栈。