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

Question

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

这样的游戏中的AI路径查找如何工作？标准的图形搜索方法（如DFS，BFS或A *）在这样的设置中似乎是不可能的。

Answer 1

这是一个有点简单的例子，但它表明，你可以从一个非复杂的规则使AI /深部调寻路的错觉：Pac-Man Pathfinding

本质上讲，它是可能的AI来了解本地（接近）信息并根据这些知识做出决策。

Answer 2

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

Answer 3

因为我没有第一人称寻路经验，所以请加上一点盐。这就是说，可能有不同的方法，但我认为标准的图形搜索方法，尤其是（A *的变体）对策略游戏来说是完全合理的。我所知道的大多数策略游戏似乎都基于一个拼贴系统，其中地图由小方块组成，这些小方块很容易映射到图形上。其中一个例子是星际争霸II（Screenshot），我将在这个答案的其余部分继续使用它作为例子，因为我对它很熟悉。

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

1. A *太慢

   由于RTS是通过“实时”定义的，等待计算完成将会使玩家受挫，因为这些单位会滞后。这可以通过几种方法来解决。一种是使用Multi-tiered A*，在考虑较小的障碍之前计算一个粗略的过程。另一个显而易见的优化是将朝向相同目的地的单位归入一个排，并且只为它们计算一条路径。

   除了使图中的每个瓦片成为节点的朴素方法之外，人们还可以构建navigation mesh，该节点具有更少的节点并且可以更快地搜索 - 这需要稍微调整搜索算法，但它仍然会以A *为核心。

2. A *是静态

   A *适用于静态图形，所以做什么的景观变化是什么时候？我不知道这是如何在实际的游戏中完成的，但我想象路线是一再地完成的，以应付新的障碍或消除障碍。也许他们正在使用incremental version of A*（PDF）。

   要观看星际争霸II对付这个问题的演示，请在this video前往7:50。

3. A *拥有完善的信息

   的许多RTS游戏的一部分是未开发的地形。由于你看不到地形，你的部队不应该知道在哪里走路，但他们经常会做。一种方法是惩罚在未开发的地形上行走，因此单位更不愿意利用他们的全知，另一种方法是将全知扫除，并假设未探索的地形是可行的。这可能导致单位陷入死胡同，有时甚至是对玩家来说显而易见的，直到他们最终探索到目标的路径。

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

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

Answer 4

查看可见性图。我相信这是他们用于寻路的东西。