大地图寻路
Pathfinding on large map
我正在创建一个 10,000 x 10,000 地图的游戏。
我希望用户能够设置位置并让计算机立即找到最佳路径。
但是，由于地图是10,000×10,000，有100,000,000个节点，通过A*或Dijkstra等常规方法找到这条路径需要大量内存和长时间。
所以我的问题是：如何找到最佳路径？
我正在考虑的算法会将世界分为 100 个部分，每个部分有 1,000,000 个节点。然后每个部分将分为 100 个小节。这将重复进行，直到每个小节包含 100 个节点。然后该算法将找到部分的最佳路径，然后是子部分，然后是子部分，直到找到最佳节点集。这行得通吗？有更好的方法吗？
我也在考虑跳点搜索，但是我不知道，学了才发现做不到，会很痛苦
编辑：我试图添加 A*。不过，运行用了5秒左右，比理想情况多了4秒左右。
我对问题陈述的初步理解如下。地图上有预定义的终端位置。用户在地图上选择一个位置，并且必须找到到这些位置中最近的位置的 best/shortest 路径。
如果我的理解是正确的，那么您可以通过单次应用 BFS 算法预先计算地图上所有位置的最短路径。您可以使用每个节点仅 2 位有效地存储该信息（与每个节点关联的值将告诉您必须从该节点向哪个方向移动才能保持在最短路径上）。
然而，正如 tobias_k 评论的那样，问题可能有不同的定义 - 玩家在地图上选择任意位置，并且必须找到从当前位置到该位置的最佳路径。可以再次使用前面描述的方法，前提是
- 玩家不会在地图上移动得太快并且
- 有些不准确是可以容忍的。
然后执行已经描述的算法以找到从地图上的任何位置到以玩家当前位置为中心的小圆周的最短路径。然后在很短的时间内，该数据可用于快速将准最短路径路由到地图上的任何位置。当玩家在移动时太靠近该圆圈的边界时，算法会抢先执行玩家的新位置。
这种方法的缺点是它会消耗大量 CPU 资源。优点是简单。
这将比适合评论的内容稍长，因此是一个答案。
您的设置需要说明。 10,000x10,000都可以，但是这个说法不行：
since the map is 10,000 by 10,000, there are 100,000,000 nodes
为什么坐标系的每个单位有1个节点？这不是节点寻路的工作方式，相反，节点应该更稀疏，并且通过它们的存在描述路径上的单个（稀疏）点。在节点之间，对象通过其他方式处理移动。 grid 寻路系统在最坏的情况下（如果根本没有障碍物）可能有 100,000,000 个点，但正如 Q 提到的 nodes，我假设这是关于节点寻路的。
100,000,000 nodes
100,000,000 个节点如果是 int32 则为 381 MB 内存，如果是 float64 则为 763 MB。此外，还有节点连接。我不知道在你的情况下如何设置这些，但每个连接需要 2 个整数，比如每个 2 个字节。 IE。如果连接数与节点数一样多，则还需要 381 MB。总而言之，我们最终得到接近 1 TB 的图形数据，我声称肯定有问题。
如何解决这个问题，前提是我们还有一个巨大的节点graph/a巨大的区域？我可能会通过创建更大的象限（如您所提到的）来简化。然而，每个象限将仅沿 4 条边 保留节点 - 象限内的所有节点都将被直线替换。这样，就可以解决每个象限的 entry/exit 点 。这将是一个单独的节点图，用于粗略计算。然后，在一个象限内，总是只在时间 加载该象限的内部节点图 。 Ofc 会有某种错误 invloved，但是，嘿，这就是现实生活，对吧？如果这是关于人类行为的，那么它并不总是完全优化的。
预计算、缓存、速度、小数据是游戏编码的关键词。
所以即使在正方形 n 乘 n 地图上可能有 n^4 条最短路径。存储所有路径不一定需要 O(n^4) space。这个想法是，给定地图上的两个不同目标位置及其最短路径树，这两个点在地图上越近，它们的最短路径树具有的共同元素就越多。当使用带有障碍物的网格等平面地图时尤其如此。
所以想法是只为一小组目标位置（甚至可能只有一个目标位置）存储一些完整的最短路径树。对于其余目标位置，仅存储其最短路径树与先前存储的最短路径树之一的差异。
那么寻找从一个位置到目标的最短路径的算法是加载一个完全存储的最短路径树，然后对其应用一些差异以获得目标位置的最短路径树。然后只需要在O(n^2)复杂度的最短路径树上找到当前玩家位置。
关于存储最短路径树及其差异需要多少存储 space，我没有任何确凿的事实，但这可能在 O(n^2 log(n^2)) 范围内。加载一个并应用差异可能只有 O(n^2).
的时间复杂度
目标位置的最短路径树表示从地图上的每个位置到目标位置的所有最短路径。
此解决方案还可以将使用过的最短路径树保留在内存中，并根据需要应用差异，以便使用新的最短路径树。那么获得最短路径树的复杂性不受地图大小的限制，而仅受要应用的差异大小的限制。这种情况可能真的适用于像最初的 Sacred 或 Diablo 这样的游戏。
由于地图为 10.000 x 10.000，因此节点数为 100.000.000。使用 A* 的直接实现是不切实际的，而且肯定不会使游戏在地图大小上具有可扩展性。
我建议您使用以下解决方案，这基本上就是您的想法：
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
如果您的地图具有统一的权重（当然障碍物除外），您可能会获得更好的性能：
一种将网格预处理成图形的算法，将大的空白空间折叠成单个节点。导航网格将可遍历区域分解为凸多边形，每个凸多边形都可以一步遍历。 L1 path finder 将障碍物组合在一起，将它们简化为能见度图，计算通过该障碍物的路径。
不展开每个节点的算法。 Jump-point search利用不同路径之间的对称性，只扩展与障碍物相邻的节点，而A*会沿着最短路径扩展每个节点。
一个高级概念可能是找到起点和终点——比如点 (0,0) 和点 (10000, 10000)——并对从起点到终点的路径进行初步猜测 (在这种情况下，它将 运行 沿对角线一直向上和向右）然后开始检查它是否可以成功到达那里（如果该路径上是否有障碍物）。如果然后以编程方式选择相似的路径，或者交替找到路径失败的地方并从那里开始并尝试迭代直到它起作用，它可能不是 100% 最快的，但你会得到比找到每一种可能的方法更好的结果，然后从中推导出最短路径。
实施
- 寻找初始最短路径的方法
- 运行看看行不行
- 如果失败则尝试类似路径或从失败开始
- 确保所有图形数据都在内存中
- 使用双向 Dijkstra - 假设你有多核
- 考虑使用收缩层次结构，这将大大提高性能。
- 尽可能预先计算所有内容，例如路径权重。
我正在创建一个 10,000 x 10,000 地图的游戏。
我希望用户能够设置位置并让计算机立即找到最佳路径。
但是，由于地图是10,000×10,000，有100,000,000个节点，通过A*或Dijkstra等常规方法找到这条路径需要大量内存和长时间。
所以我的问题是：如何找到最佳路径？
我正在考虑的算法会将世界分为 100 个部分，每个部分有 1,000,000 个节点。然后每个部分将分为 100 个小节。这将重复进行，直到每个小节包含 100 个节点。然后该算法将找到部分的最佳路径，然后是子部分，然后是子部分，直到找到最佳节点集。这行得通吗？有更好的方法吗？
我也在考虑跳点搜索，但是我不知道，学了才发现做不到，会很痛苦
编辑：我试图添加 A*。不过，运行用了5秒左右，比理想情况多了4秒左右。
我对问题陈述的初步理解如下。地图上有预定义的终端位置。用户在地图上选择一个位置，并且必须找到到这些位置中最近的位置的 best/shortest 路径。
如果我的理解是正确的，那么您可以通过单次应用 BFS 算法预先计算地图上所有位置的最短路径。您可以使用每个节点仅 2 位有效地存储该信息（与每个节点关联的值将告诉您必须从该节点向哪个方向移动才能保持在最短路径上）。
然而，正如 tobias_k 评论的那样，问题可能有不同的定义 - 玩家在地图上选择任意位置，并且必须找到从当前位置到该位置的最佳路径。可以再次使用前面描述的方法，前提是
- 玩家不会在地图上移动得太快并且
- 有些不准确是可以容忍的。
然后执行已经描述的算法以找到从地图上的任何位置到以玩家当前位置为中心的小圆周的最短路径。然后在很短的时间内，该数据可用于快速将准最短路径路由到地图上的任何位置。当玩家在移动时太靠近该圆圈的边界时，算法会抢先执行玩家的新位置。
这种方法的缺点是它会消耗大量 CPU 资源。优点是简单。
这将比适合评论的内容稍长，因此是一个答案。
您的设置需要说明。 10,000x10,000都可以，但是这个说法不行：
since the map is 10,000 by 10,000, there are 100,000,000 nodes
为什么坐标系的每个单位有1个节点？这不是节点寻路的工作方式，相反，节点应该更稀疏，并且通过它们的存在描述路径上的单个（稀疏）点。在节点之间，对象通过其他方式处理移动。 grid 寻路系统在最坏的情况下（如果根本没有障碍物）可能有 100,000,000 个点，但正如 Q 提到的 nodes，我假设这是关于节点寻路的。
100,000,000 nodes
100,000,000 个节点如果是 int32 则为 381 MB 内存，如果是 float64 则为 763 MB。此外，还有节点连接。我不知道在你的情况下如何设置这些，但每个连接需要 2 个整数，比如每个 2 个字节。 IE。如果连接数与节点数一样多，则还需要 381 MB。总而言之，我们最终得到接近 1 TB 的图形数据，我声称肯定有问题。
如何解决这个问题，前提是我们还有一个巨大的节点graph/a巨大的区域？我可能会通过创建更大的象限（如您所提到的）来简化。然而，每个象限将仅沿 4 条边 保留节点 - 象限内的所有节点都将被直线替换。这样，就可以解决每个象限的 entry/exit 点 。这将是一个单独的节点图，用于粗略计算。然后，在一个象限内，总是只在时间 加载该象限的内部节点图 。 Ofc 会有某种错误 invloved，但是，嘿，这就是现实生活，对吧？如果这是关于人类行为的，那么它并不总是完全优化的。
预计算、缓存、速度、小数据是游戏编码的关键词。
所以即使在正方形 n 乘 n 地图上可能有 n^4 条最短路径。存储所有路径不一定需要 O(n^4) space。这个想法是，给定地图上的两个不同目标位置及其最短路径树，这两个点在地图上越近，它们的最短路径树具有的共同元素就越多。当使用带有障碍物的网格等平面地图时尤其如此。
所以想法是只为一小组目标位置（甚至可能只有一个目标位置）存储一些完整的最短路径树。对于其余目标位置，仅存储其最短路径树与先前存储的最短路径树之一的差异。
那么寻找从一个位置到目标的最短路径的算法是加载一个完全存储的最短路径树，然后对其应用一些差异以获得目标位置的最短路径树。然后只需要在O(n^2)复杂度的最短路径树上找到当前玩家位置。
关于存储最短路径树及其差异需要多少存储 space，我没有任何确凿的事实，但这可能在 O(n^2 log(n^2)) 范围内。加载一个并应用差异可能只有 O(n^2).
目标位置的最短路径树表示从地图上的每个位置到目标位置的所有最短路径。
此解决方案还可以将使用过的最短路径树保留在内存中，并根据需要应用差异，以便使用新的最短路径树。那么获得最短路径树的复杂性不受地图大小的限制，而仅受要应用的差异大小的限制。这种情况可能真的适用于像最初的 Sacred 或 Diablo 这样的游戏。
由于地图为 10.000 x 10.000，因此节点数为 100.000.000。使用 A* 的直接实现是不切实际的，而且肯定不会使游戏在地图大小上具有可扩展性。
我建议您使用以下解决方案，这基本上就是您的想法：
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
如果您的地图具有统一的权重（当然障碍物除外），您可能会获得更好的性能：
一种将网格预处理成图形的算法，将大的空白空间折叠成单个节点。导航网格将可遍历区域分解为凸多边形，每个凸多边形都可以一步遍历。 L1 path finder 将障碍物组合在一起，将它们简化为能见度图，计算通过该障碍物的路径。
不展开每个节点的算法。 Jump-point search利用不同路径之间的对称性，只扩展与障碍物相邻的节点，而A*会沿着最短路径扩展每个节点。
一个高级概念可能是找到起点和终点——比如点 (0,0) 和点 (10000, 10000)——并对从起点到终点的路径进行初步猜测 (在这种情况下，它将 运行 沿对角线一直向上和向右）然后开始检查它是否可以成功到达那里（如果该路径上是否有障碍物）。如果然后以编程方式选择相似的路径，或者交替找到路径失败的地方并从那里开始并尝试迭代直到它起作用，它可能不是 100% 最快的，但你会得到比找到每一种可能的方法更好的结果，然后从中推导出最短路径。
实施
- 寻找初始最短路径的方法
- 运行看看行不行
- 如果失败则尝试类似路径或从失败开始
- 确保所有图形数据都在内存中
- 使用双向 Dijkstra - 假设你有多核
- 考虑使用收缩层次结构，这将大大提高性能。
- 尽可能预先计算所有内容，例如路径权重。