我已经设法实现了 a* 并且我得到了正确的路径。
问题是我如何重建从头到尾的路径,因为每个节点(从头到尾)都有一个父链接,但不是第一个,所以我的角色不知道先去哪里。
我正在做的是返回封闭列表并从索引 0 开始到 x 直到我到达结尾。这通常很有效,但我知道必须有另一种方法。
此外,检查相邻节点的最佳方法是什么?
我已经让每个节点创建一个矩形并查看它是否相交,这就是我知道它们已连接的方式。我还对播放器使用这种技术来了解何时到达节点。
谢谢!!
最佳答案
你有你的目标节点(一旦找到你可以简单地缓存它)。
沿着树往上走(使用parent
字段)直到你找到一个没有它的节点,这个节点就是你的根。您通过向上链接找到的路径是倒序的最短路径。
我曾经解决过 similar question , 关于 BFS 而不是 A*
编辑:将堆栈反转回原始状态的一种简单方法是在从目标转到源时将节点放入堆栈中,并且当您找到源时 - 开始弹出元素堆栈。
关于algorithm - A-Star算法(重构路径),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12401481/