在大地图上寻路

algorithm java path-finding a-star

2022-09-02 04:35:14

我正在创建一个10，000乘10，000地图的游戏。
我希望用户能够设置位置并让计算机立即找到最佳路径。
但是，由于地图是10，000×10，000，因此有100，000，000个节点，并且通过A *或Dijkstra等常规方法找到此路径将需要大量的内存和很长时间。
所以我的问题是：我怎样才能找到最好的路径？
我正在考虑的算法将世界划分为100个部分，每个部分有1，000，000个节点。然后，每个部分将分为100个小节。将重复此操作，直到每个子节包含 100 个节点。然后，该算法将找到截面的最佳路径，然后是子节，然后是子节，直到找到最佳的节点集。这行得通吗，有没有更好的方法？
我也在考虑跳点搜索，但我不知道，学习只是发现它做不到会很痛苦。

编辑：我试图添加A *。但是，运行大约需要5秒，比理想时间长约4秒。

答案 1

由于映射为 10.000 x 10.000，因此节点数为 100.000.000。使用A*的直接实现是不切实际的，当然也不会使游戏在mapsize中可扩展。

我建议您使用以下解决方案，这基本上就是您的想法：

HPA*（分层路径A*）。此方法创建不同的映射层次结构。您可以通过说每个100x100像素的块都是一个区域来自动执行该过程。然后，对于每个区块，我们需要找到相邻的区块以及每个区块的入口和出口的位置。如果两个块之间的连接大于一个节点，那么我们使用两个节点来表示问题。此图说明了我们尝试构建的新图形。（黑色=障碍物和灰色是块之间的连接节点）。