c# - 将许多单元的 A* 路径拆分为单独的游戏框架

Question

所以我的问题是，对于大量单位，尝试在同一帧中为所有单位寻路会导致相当明显的减速。当路径为 1 或 2 个单位时，减速通常不明显，但对于更多单位，取决于路径的复杂性，它可能会变得非常慢。

虽然我的 A* 可能可以稍微调整一下，但我也知道另一种加速寻路的方法是将寻路分配给多个游戏帧。什么是完成此任务的好方法？

如果这是一个明显或容易搜索的问题，我深表歉意，我真的想不出如何将它放入可搜索的字符串中。

更多信息:这是直线网格上的 A*，使用 C# 和 XNA 框架进行编程。我计划可能有多达 50-75 个单元需要路径。

谢谢。

Answer 1

可扩展性

有多种方法可以针对这种情况进行优化。一方面，您可能不必分成多个游戏框架。在某种程度上，可扩展性似乎是个问题。 100 件至少比 1 件贵 100 倍。

那么，我们如何才能针对可扩展性对路径进行更优化？好吧，这确实取决于您的游戏设计。我将(可能是错误的)假设一个典型的 RTS 场景。几组单位，每组之间的距离相对较近。许多靠近的单位的路径解决方案将非常相似。这些单位可以从某种路径求解器请求路径。该寻路求解器可以保留最近的寻路请求及其解决方案的表格，并避免多次从相同的输入计算相同的输出。这叫做 memoization .

对此的另一个补充可能涉及从您的网格或图形中创建层次结构。先解决简单的图形，然后切换到更详细的图形。多个单元可以使用相同的低分辨率路径，利用内存，但如果高分辨率路径太多而无法合理内存，则每个单元都会单独计算自己的高分辨率路径。

多帧计算

至于尝试在帧之间拆分计算，我可以立即想到一些方法。

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

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

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

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

使用部分解决方案

使用上述任何一种方法，您都可能会遇到这样的问题，即在获得完整的路径解决方案之前，单位会被命令去某个地方空转多帧。在典型情况下，这可能是可以接受的并且实际上是检测不到的。如果不是，您可以尝试按原样使用不完整的解决方案。但是，如果每个不完整的解决方案差异太大，单元将表现得相当优柔寡断。在实践中，这种“优柔寡断”的发生频率可能​​还不足以引起关注。