我正在创建一个10，000乘10，000地图的游戏。
我希望用户能够设置位置并让计算机立即找到最佳路径。
但是，由于地图是10，000×10，000，因此有100，000，000个节点，并且通过A *或Dijkstra等常规方法找到此路径将需要大量的内存和很长时间。
所以我的问题是：我怎样才能找到最好的路径？
我正在考虑的算法将世界划分为100个部分，每个部分有1，000，000个节点。然后，每个部分将分为100个小节。将重复此操作，直到每个子节包含 100 个节点。然后，该算法将找到截面的最佳路径，然后是子节，然后是子节，直到找到最佳的节点集。这行得通吗，有没有更好的方法？
我也在考虑跳点搜索，但我不知道，学习只是发现它做不到会很痛苦。
编辑：我试图添加A *。但是，运行大约需要5秒，比理想时间长约4秒。
由于映射为 10.000 x 10.000，因此节点数为 100.000.000。使用A*的直接实现是不切实际的，当然也不会使游戏在mapsize中可扩展。
我建议您使用以下解决方案，这基本上就是您的想法：
HPA*（分层路径A*）。此方法创建不同的映射层次结构。您可以通过说每个100x100像素的块都是一个区域来自动执行该过程。然后，对于每个区块，我们需要找到相邻的区块以及每个区块的入口和出口的位置。如果两个块之间的连接大于一个节点，那么我们使用两个节点来表示问题。此图说明了我们尝试构建的新图形。（黑色=障碍物和灰色是块之间的连接节点）。
这种方法提供了良好的结果，从使用游戏Baldur's Gate的地图执行中可以看出，每个块都是10x10。
有关更多信息，请阅读Nathan Sturtevant的这篇文章（他是游戏方面最成功的路径发现研究人员之一）。https://skatgame.net/mburo/ps/path.pdf
有关HPA的解释，请查看Sturtevant的讲座（HPA至少43：50）。https://www.youtube.com/watch?v=BVd5f66U4Rw
另外，如果您想观看HPA*的实际应用，请查看Sturtevant制作的这段视频：https://www.youtube.com/watch?v=l7YQ5_Nbifo
