将许多单位的路径拆分为单独的游戏框架

可扩展性

有几种方法可以针对这种情况进行优化。首先，您可能不必拆分为多个游戏框架。在某种程度上，可伸缩性似乎是个问题。100个单位至少比1个单位贵100倍。

那么，我们如何使路径更优化以实现可扩展性呢？好吧，这取决于你的游戏设计。我将（也许是错误的）假设一个典型的RTS场景。几个单元组，每组相对较近。许多单元的路径解决方案非常相似。这些单元可以向某种路径求解器请求路径。该路径求解器可以保存最近的路径请求及其解决方案的表，并避免多次从同一输入计算同一输出。这叫做记忆。

另一个附加功能可能包括从网格或图形中创建层次结构。先在较简单的图上求解，然后切换到更详细的图。多个单元可以使用相同的低分辨率路径，利用记忆功能，但如果高分辨率路径太多而无法合理记忆，则每个单元单独计算自己的高分辨率路径。

多帧计算

至于试图在帧之间分割计算，我可以想出一些方法。

如果您想采用多线程路由，可以使用工作线程池模型。每当一个单元请求一条路径时，它都会排队等待解决方案。当工作线程空闲时，将为其分配一个要解决的任务。当线程解决任务时，您可以有一个回调来通知单元，也可以有单元查询，如果任务以某种方式完成，很可能会查询每个帧。

如果没有动态障碍或它们是单独处理的，则路径解算器可以使用恒定状态。如果没有，那么将存在不可忽略的复杂性，甚至可能会被这些线程锁定可变的游戏状态信息所偷听到。从一帧到下一帧，路径可能会变得无效，并且需要对每一帧进行重新验证。多线程可能最终成为一种毫无意义的额外开销，由于锁定和同步，线程很少并行运行。这只是一种可能性。

或者，您可以将路径查找算法设计为以离散步骤运行。在n个步骤之后，检查自算法启动以来经过的时间量。如果超过一定时间，路径算法将保存其进度并返回。调用代码然后可以检查算法是否完成。在下一帧中，从它所在的位置恢复路径算法。重复此步骤，直到解决。

即使使用单线程、自愿的方法来解决路径，如果游戏状态的变化影响了从一帧到另一帧路径的有效性，您也将不得不在一帧到一帧的基础上重新验证当前的解决方案。

使用部分解决方案

使用以上任何一种方法，在获得完整的路径解决方案之前，都可能遇到单元被命令在某个地方空转多帧的问题。在典型情况下，这可能是可以接受的，并且实际上是不可检测的。如果不是，你可以尝试按原样使用不完整的解决方案。然而，如果每个不完整的方案差异太大，单位的行为就会相当犹豫不决。在实践中，这种"优柔寡断"的情况也可能不经常发生，不足以引起关注。

如果你的部队都在同一个目的地，这个答案可能适用，否则，这只是值得思考的。

我使用广度优先的距离算法来路径单元。从您的目的地出发，并将距离标记为0。任何相邻的单元格都是1，与之相邻的单元格是2，等等。不要穿过障碍物，而是穿过整个板。通常O（A）时间复杂性，其中A是板面积。

然后，每当你想确定一个单元需要向哪个方向移动时，你只需找到距离目的地最小的正方形。O（1）时间复杂性。

我会经常在塔防游戏中使用这种路径算法，因为它的时间复杂性完全取决于棋盘的大小（在TD游戏中通常相当小），而不是单位的数量（通常相当大）。它允许玩家定义自己的路径（这是一个很好的功能），由于游戏的性质，我只需要一轮运行一次。