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

Question

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

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

Answer 1

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

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

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

1. A* is too slow

(A*速度太慢)

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

与其天真地让每一个瓦片都成为图中的节点，人们还可以构建一个navigation mesh，它有更少的节点，可以更快地搜索-这需要稍微调整搜索算法，但它仍然是核心的A*。

1. A* is static

A*在静态图上工作，那么当环境发生变化时该怎么办？我不知道在实际游戏中是如何做到这一点的，但我可以想象，为了应对新的障碍或移除的障碍，路径会重复进行。也许他们使用的是incremental version of A*。

要查看StarCraft II如何处理此问题的演示，请转到this video中的7:50。

1. A*有完美的信息

许多RTS游戏的一部分是未探索的地形。既然你看不到地形，你的部队也不应该知道该往哪里走，但他们通常还是会知道。一种方法是惩罚在未探索的地形上行走，因此单位更不愿意利用其无所不知的优势，另一种方法是取消无所不知，只是假设未探索的地形是可以步行的。这可能会导致单位陷入死胡同，有时是玩家显而易见的死胡同，直到他们最终探索到目标的路径。

“战争迷雾”是这方面的另一个方面。例如，在StarCraft 2中，地图上有可破坏的障碍物。已经证明，你可以命令一个单位移动到敌人的基地，如果障碍物已经被你的对手摧毁了，它将开始一条不同的路线，从而给你提供了你实际上不应该拥有的信息。

总而言之:您可以使用标准算法，但您可能必须巧妙地使用它们。作为最后一个奖励:我发现Amit’s Game Programming Information在路径方面很有趣。它还提供了进一步讨论该问题的链接。

Answer 2

这是一个有点简单的示例，但它表明您可以从一组不复杂的规则中产生AI /深度寻路的错觉：Pac-Man Pathfinding

从本质上讲，AI可以知道本地(附近)信息，并根据这些信息做出决策。

Answer 3

A*是一种常用的寻路算法。这是一个流行的游戏开发主题--你应该能够找到许多包含信息的书籍和网站。