在大地图上寻路 [英] Pathfinding on large map
问题描述
我正在创建一个带有 10,000 x 10,000 地图的游戏.
我希望用户能够设置位置并让计算机立即找到最佳路径.
但是，由于地图是 10,000 x 10,000，因此有 100,000,000 个节点，通过 A* 或 Dijkstra 等常规方法找到此路径需要大量内存和长时间.
所以我的问题是:我怎样才能找到最佳路径?
我正在考虑的算法会将世界分成 100 个部分，每个部分有 1,000,000 个节点.然后，每个部分将分为 100 个小部分.这将重复，直到每个小节包含 100 个节点.然后，该算法将找到部分的最佳路径，然后是子部分，然后是子子部分，直到找到最佳节点集.这行得通吗，还有更好的方法吗?
我也在考虑跳点搜索，但我不知道，而且学习只是发现它不能这样做会很痛苦.
I'm creating a game with a 10,000 by 10,000 map.
I would like for a user to be able to set a location and have the computer instantly find the best path.
However, since the map is 10,000 by 10,000, there are 100,000,000 nodes, and to find this path through a conventional method such as A* or Dijkstra's would require a large amount of memory and a long time.
So my question is: How can I find the best path?
The algorithm I'm considering would divide the world into 100 sections, each with 1,000,000 nodes. Each section would then be divided into 100 subsections. This would be repeated until each subsection contains 100 nodes. The algorithm would then find the best path of sections, then subsections, then sub-sub sections until it finds the best set of nodes. Would this work and is there a better way?
I'm also considering a jump-point search, but I don't know it, and it'd be a pain to learn just to find that it can't do it.
我试图添加 A*.但是，运行大约需要 5 秒，这比理想情况长了大约 4 秒.
I have attempted to add A*. However, it took about 5 seconds to run, which is about 4 seconds longer than ideal.
推荐答案
由于地图是 10.000 x 10.000，所以节点数是 100.000.000.使用 A* 的直接实现是不切实际的，而且肯定不会使游戏在地图大小方面具有可扩展性.
Since the map is 10.000 x 10.000 the number of nodes is 100.000.000. Using a straightforward implementation of A* would be impractical and certainly wouldn't make the game scalable in mapsize.
我建议您使用以下解决方案，这基本上就是您的想法:
I would recommend you to use the following solution, which is essentially what you were thinking:
HPA*(分层路径 A*).此方法创建地图的不同层次结构.您可以通过说每个 100x100 像素块都是一个区域来自动化该过程.然后，对于每个块，我们需要找到相邻的块以及每个块的入口和出口在哪里.如果两个块之间的连接不止一个节点，那么我们使用两个节点来表示问题.这张图片解释了我们正在尝试构建的新图表.(黑色=障碍物和灰色是块之间的连接节点).
HPA* (Hierarchical Path A*). This method creates different hierarchies of map. You may automate the process by saying every block of 100x100 pixels is a region. Then, for every block, we need to find the adjacent blocks and where the entries and exits for each block is. If the connection between the two blocks is more than a node then we use two nodes to represent the problem. This image explains the new graph that we're trying to build. (Black=obstacle and grey are connecting nodes between blocks).
从使用游戏 Baldur's Gate 中每个块为 10x10 的地图的执行中可以看出，此方法提供了良好的结果.
This method provides good results as can be seen from an execution using maps from the game Baldur's Gate with every block being 10x10.
有关更多信息，请阅读 Nathan Sturtevant 的这篇文章(他是游戏领域最成功的寻路研究人员之一).https://skatgame.net/mburo/ps/path.pdf
For more information read this article from Nathan Sturtevant (he is one of the most succesful path-finding researcher when it comes to games). https://skatgame.net/mburo/ps/path.pdf
有关 HPA 的解释，请查看 Sturtevant 的这个讲座(HPA 最低 43:50).https://www.youtube.com/watch?v=BVd5f66U4Rw
For an explanation of HPA please check this lecture of Sturtevant (min 43:50 for HPA). https://www.youtube.com/watch?v=BVd5f66U4Rw
此外，如果您想查看 HPA* 的实际效果，请查看 Sturtevant 制作的此视频:https://www.youtube.com/watch?v=l7YQ5_Nbifo
Also, if you want to see HPA* in action check this video that Sturtevant made: https://www.youtube.com/watch?v=l7YQ5_Nbifo
这篇关于在大地图上寻路的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
