我正在创建一个带有 10,000 x 10,000 地图的游戏。
我希望用户能够设置位置并让计算机立即找到最佳路径。
然而，由于地图是10,000 x 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* 的直接实现是不切实际的，并且肯定不会使游戏在地图大小上可扩展。
我建议您使用以下解决方案，这基本上就是您的想法：
HPA*（分层路径 A*）。该方法创建不同层次的地图。您可以通过说每个 100x100 像素块都是一个区域来自动化该过程。然后，对于每个块，我们需要找到相邻的块以及每个块的入口和出口在哪里。
如果两个块之间的连接多于一个节点，那么我们使用两个节点来表示问题。此图解释了我们正在尝试构建的新图表。 （黑色=障碍物，灰色是块之间的连接节点）。
该方法提供了良好的结果，从使用博德之门游戏中每个块为 10x10 的地图的执行中可以看出。
如需了解更多信息，请阅读 Nathan Sturtevant 的这篇文章（他是游戏领域最成功的寻路研究员之一）。https://skatgame.net/mburo/ps/path.pdf https://skatgame.net/mburo/ps/path.pdf
有关 HPA 的解释请查看 Sturtevant 的讲座（HPA 时间为 43:50）。https://www.youtube.com/watch?v=BVd5f66U4Rw https://www.youtube.com/watch?v=BVd5f66U4Rw
另外，如果您想了解 HPA* 的实际应用，请观看 Sturtevant 制作的这段视频：https://www.youtube.com/watch?v=l7YQ5_Nbifo https://www.youtube.com/watch?v=l7YQ5_Nbifo
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
