在大地图上寻路
Jam*_*ell 19 java algorithm a-star path-finding
我正在创建一个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 = 17YQ5_Nbifo