我正在尝试对A *寻路算法进行this很棒的介绍。但是,由于某些原因,即使本文中的示例的行为有所不同,我的BFS algorithm的JS实现也倾向于90度路径:https://codepen.io/stee1rat/pen/GyeyzB?editors=0010。也许应该有一些条件可以将next
节点从frontier
数组弹出/移出?我不知道如何使它的行为与python示例相同。
最佳答案
您的实现是完美的。您的解决方案与另一种解决方案之间的区别在于,您如何在打开的列表中断开联系,即,如果您有4个节点且成本相同,那么下一个将要扩展。 A *选择一个,而您的算法选择另一个。更改选择以选择下一个要进行不同探索的节点应足以为您提供不同的最短路径解决方案。
通常在游戏地图中会发生这种情况,请看以下示例:
S _ _ _
_ _ _ _
_ _ _ _
_ _ _ G
让我们仅考虑垂直和水平运动,使所有运动成本相同,有许多最短路径解决方案:
S 1 2 3
_ _ _ 4
_ _ _ 5
_ _ _ G
S _ _ _
1 _ _ _
2 _ _ _
3 4 5 G
S _ _ _
1 2 3 _
_ _ 4 _
_ _ 5 G
...
如果您想加深有关在边界处断开联系的知识(对于双向A *),请查看此paper。
关于javascript - 简单的寻路,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/48384675/