由于Map是10.000 x 10.000，节点数是100.000.000。使用A* 的直接实现是不切实际的，当然也不会使游戏在Map大小上可伸缩。
我建议你使用以下解决方案，这基本上是你所想的：

HPA（Hierarchical Path A*）。此方法创建不同层次的Map。您可以通过说每个100x100像素的块都是一个区域来自动化该过程。然后，对于每个块，我们需要找到相邻的块以及每个块的入口和出口在哪里。如果两个块之间的连接超过一个节点，那么我们使用两个节点来表示问题。这图片解释了我们正在尝试构建的新图形。（黑色=障碍物，灰色是块之间的连接节点）。

的数据
这种方法提供了良好的结果，可以从使用游戏Baldur's Gate的Map执行中看到，每个块都是10x10。

的
欲了解更多信息，请阅读这篇来自Nathan斯图尔特Vant的文章（他是游戏领域最成功的寻路研究者之一）。https://skatgame.net/mburo/ps/path.pdf
有关HPA的解释，请查看斯图尔特Vant的讲座（HPA最少43：50）。https://www.youtube.com/watch?v=BVd5f66U4Rw
此外，如果您想了解HPA* 的实际应用，请查看斯图尔特Vant制作的视频：https://www.youtube.com/watch?v=l7YQ5_Nbifo

1.确保所有图形数据都在内存中
1.使用双向Dijkstra -假设您有多核
1.考虑使用收缩层次结构，这将大大提高性能。
1.预先计算一切，你可以，如路径权重。

我对问题陈述的最初理解如下：Map上有预定义的终端位置。用户在Map上选择一个位置，必须找到到这些位置中最近的一个的最佳/最短路径。
如果我的理解是正确的，那么你可以通过BFS算法的一个应用程序来预先计算Map上所有位置的最短路径。你可以有效地存储这些信息，每个节点只使用2位（与每个节点相关联的值将告诉你必须从该节点向哪个方向移动，才能保持在最短路径上）。
然而，正如tobias_k所评论的，问题可以被不同地定义-玩家在Map上选择任意位置，并且必须找到从当前位置到该位置的最佳路径。
1.玩家不会在Map上移动得太快，
1.可以容忍一些不准确性。
然后执行上述算法，找出从Map上任何位置到以玩家当前位置为中心的小圆周的最短路径。然后在短时间内，可以使用这些数据快速地将准最短路径路由到Map上的任何位置。当玩家在移动时过于接近该圆的边界时，对于玩家的新位置抢先执行该算法。
这种方法的缺点是消耗大量的CPU资源，优点是简单。

因此，即使在一个n乘n的正方形Map上可能有n^4条最短路径，存储所有路径并不一定需要O(n^4)空间。其思想是，给定Map上两个不同的目标位置及其最短路径树，而不是这两个点在Map上越接近，它们的最短路径树中的公共元素越多。2当使用平面Map时，如带有障碍物的网格时，尤其如此。
因此，我们的想法是只为一小部分目标位置（甚至可能只有一个目标位置）存储一些完整的最短路径树。对于其余的目标位置，只存储其最短路径树与先前存储的最短路径树之一的差异。
然后，寻找从一个位置到目标的最短路径的算法是加载一个完全存储的最短路径树，然后对其进行一些差分，以获得目标位置的最短路径树，然后只需在最短路径树上找到当前玩家位置，其复杂度为O(n^2)。
我没有任何关于存储最短路径树和它们的差异需要多少存储空间的确切事实，但这可能在O(n^2 log(n^2))的范围内。加载一个并应用差异可能只有O(n^2)的时间复杂度。
目标位置的最短路径树表示从Map上的每个位置到目标位置的所有最短路径。
这种解决方案也可以将使用过的最短路径树保存在内存中，并在必要时应用差异，以获得新的最短路径树来使用。这样，获得最短路径树的复杂性就不受Map大小的限制，而只受要应用的差异大小的限制。这种情况可能真的很适合像原始的Sacred或Diablo这样的游戏。

如果您的Map具有统一的权重（当然障碍物除外），则您可以使用以下任一项来获得更好的性能：
1.将网格预处理成图形的算法，将大的空白空间折叠成单个节点。导航网格将可穿越区域分解为凸多边形，每个凸多边形都可以在一个步骤中穿越。L1 path finder将障碍物分组在一起，将它们简化为可见性图，计算通过该图的路径。

1. Jump-point search利用不同路径之间的对称性，只扩展与障碍物相邻的节点，而A* 将沿着最短路径沿着扩展每个节点。

一个高层次的概念可能是找到开始和结束的点-比如点（0，0）和点（10000，10000）-并对从开始到结束的路径进行初步猜测（在这种情况下，它将运行对角线的整个方式向上和向右）然后开始检查，看看它是否可以成功地到达那里（如果在该路径上有障碍物或没有）.如果有然后编程选择类似的路径，或者交替地找到路径失败，并从那里开始，并尝试搜索，直到它的工作，它可能不是100%最快的，但你会得到一个更好的结果比找到每一个可能的方式，然后从中推导出最短路径
执行

• 一种求初始最短路径的方法
• 跑去看看有没有用
• 如果失败，则尝试类似的路径或从失败开始

这将是一个比什么适合一个评论长一点，因此，一个答案。
您的设置需要澄清。10，000 x10，000是好的，但这句话不是：
由于Map是10，000 × 10，000，因此有1亿个节点
为什么每个坐标系的单位都有一个节点？这不是节点寻路的工作原理，相反，节点应该更稀疏，并通过它们的存在来描述路径沿着的单个（稀疏）点。在节点之间，对象通过其他方式处理移动。在最坏的情况下，网格寻路系统可能（如果根本没有障碍物），有100，000，000个点，但是由于Q提到了节点，我假设这是关于节点寻路的。
1亿个节点
100，000，000个节点是381兆字节的内存，如果int 32和763兆字节，如果float 64。此外，还有节点连接。我不知道这些将如何设置在您的情况下，但每个连接需要2个整数，说每个2字节。即。如果有尽可能多的连接节点，另一个381兆字节是需要的。总而言之，我们最终得到的图表数据接近1 TB，我敢说肯定有什么地方出了问题。
如何解决这个问题，假设我们仍然有一个巨大的节点图/一个巨大的区域？我可能会简化，通过创建更大的象限，（正如你提到的）。然而，每个象限将仅沿沿着4条边保存节点-象限内的所有节点将被直线替换。这样，将解析每个象限的入口/出口点。这将是一个单独的节点图，用于粗略计算。然后，在一个象限内，人们总是只在时间加载该象限的内部节点图。这会导致某种错误，但嘿，这是真实的生活，对吧？如果这是关于人类行为的，那么它并不总是完全优化的。
预计算、缓存、速度和小数据是游戏编码中的关键词。