search - RTS 视频游戏中的寻路是如何工作的？

Question

在《魔兽争霸 3》或《帝国时代》等游戏中，AI 对手在 map 上移动的方式几乎是无限的。 map 很大，其他玩家的位置也在不断变化。

这类游戏中的 AI 寻路是如何工作的？在这样的设置中，标准的图搜索方法(例如 DFS、BFS 或 A*)似乎是不可能的。

Answer 1

对以下内容持保留态度，因为我没有第一人称的寻路经验。

话虽如此，可能有不同的方法，但我认为标准的图搜索方法，特别是 A* 的(变体)对于策略游戏是完全合理的。我知道的大多数策略游戏似乎都基于图块系统，其中 map 由小方块组成，这些小方块很容易映射到图形上。一个例子是星际争霸 II ( Screenshot )，我将在本答案的其余部分继续使用它作为示例，因为我最熟悉它。

虽然 A* 可用于实时战略游戏，但必须通过对核心算法的调整来克服一些缺点:

A* 太慢

由于 RTS 被定义为“实时”，等待计算完成会让玩家感到沮丧，因为单位会滞后。这可以通过多种方式补救。一是用Multi-tiered A* ，它在考虑较小的障碍之前计算粗略的路线。另一个明显的优化是将前往同一目的地的单位分组为一个排，并且只为所有单位计算一条路径。

除了将每个图块都作为图中节点的幼稚方法之外，还可以构建一个 navigation mesh ，它具有更少的节点并且可以更快地搜索——这需要稍微调整搜索算法，但它的核心仍然是 A*。

A* 是静态的

A*适用于静态图，那么当景观发生变化时怎么办？我不知道在实际游戏中这是如何完成的，但我想路径是重复进行的，以应对新的障碍或移除的障碍。也许他们正在使用 incremental version of A* (PDF)。

要查看星际争霸 II 处理此问题的演示，请转至 this video 中的 7:50 .

A*具有完全信息

许多 RTS 游戏的一部分是未开发的地形。由于你看不到地形，你的单位也不应该知道该往哪里走，但他们通常会这样做。一种方法是惩罚在未探索的地形中行走，因此单位更不愿意利用他们的全知，另一种方法是将全知拿走，只假设未探索的地形是可以步行的。这可能导致单位跌跌撞撞地陷入死胡同，有时是玩家很明显的死胡同，直到他们最终探索到目标的路径。

war 迷雾是另一个方面。例如，在星际争霸 2 中， map 上有可破坏的障碍物。事实证明，你可以命令一个单位移动到敌人的基地，如果障碍物已经被你的对手摧毁，它就会走不同的路径，从而为你提供你实际上不应该拥有的信息。

总结:您可以使用标准算法，但您可能必须巧妙地使用它们。作为最后的奖励:我找到了 Amit’s Game Programming Information关于路径很有趣。它还提供了进一步讨论该问题的链接。