一种快速算法用于实时战略游戏中的视线计算

Question

我正在制作一个简单的实时战略游戏。我希望它能运行得非常快，因为它需要处理数千个单位和8个玩家。

一切似乎都很顺利，但是视野计算似乎是瓶颈。它很简单：如果敌人单位比我的任何单位的视野范围更近，那么它将可见。

目前我使用相当幼稚的算法：对于每个敌方单位，我检查是否有任何我的单位可以看到他。这是O(n^2)。

所以，如果有8个玩家，每个玩家都有3000个单位，那么最坏情况下每个玩家要进行3000*21000=63000000次测试。这相当慢。

更多细节：这是一个非常简单的二维空间实时战略游戏：没有网格，单位沿着直线移动，没有碰撞，所以它们可以互相穿过。因此，即使有数百个单位在同一位置，也不会发生碰撞。

我想以某种方式加速这个视野算法。有什么想法吗？

编辑：

因此，额外的细节如下：

- 我的意思是一个玩家甚至可以拥有3000个单位。 - 我的单位有雷达，可以朝所有方向平等地看。

- Calmarius

---

如果你还没有的话，我建议你也在http://gamedev.stackexchange.com/上提问。 - cHao

3000/8 = 375，在SC2中你最多可以拥有200个食物，谁能够正确地宏观管理375个单位呢！ :) - Mateusz Dymczyk

好的，RTS代表实时战略游戏！ - Lazer

@Zenzen 我的意思是他们每个人都有3000个单位。所以每个人都可以拥有3k个单位。就像在《哥萨克》中一样。但我认为那里有一个诀窍，因为良好的游戏玩法需要玩家设置军队，使得50个单位可以移动为“一个单位”。 - Calmarius

Answer 1

使用空间数据结构可以高效地根据位置查找单位。

此外，如果你只关心一个单位是否可见，而不关心是哪个单位发现了它，你可以这样做

for each unit
    mark the regions this unit sees in your spatial data structure

并且有：

isVisible(unit) = isVisible(region(unit))

一个非常简单的空间数据结构是网格：你在游戏场地上覆盖一个粗糙的网格。这个网格的单元格就是区域。你分配一个区域数组，并为每个区域保留一个当前在该区域的单位列表。

你可能还会发现Muki Haklay的空间索引演示很有用。

- meriton

Answer 2

游戏开发中最基本的规则之一就是通过利用游戏玩法定义的所有可能限制来优化算法，这就是为什么你不会看到在同一公司游戏引擎上构建的截然不同的游戏，因为他们已经高效地利用了这些限制，无法处理不在这些限制范围内的任何事物。

话虽如此，你说单位沿直线移动，并且你说玩家可以拥有3000个单位——即使我假设这是八名玩家每人拥有3000个单位，那么每次游戏步骤（我假设每个步骤都涉及你上面描述的计算）改变方向的单位数量不会比不改变方向的单位数量多。

所以，如果这是真的，那么你需要将所有棋子分成两组——那些在上一步中改变了方向的和那些没有改变方向的。

对于那些改变了方向的棋子，你需要进行一些计算——对于任意两个敌对势力的单位，你需要问：“当单位A和单位B都不改变方向或速度时，单位A何时能看到单位B？”（你可以处理加速度/减速度，但这样就更复杂了）——要计算这个问题，首先需要确定单位A和单位B所在的向量是否会相交（简单的2D线相交计算，加上一个告诉你每个单位何时到达这个交点的计算）——如果它们不会相交，而且它们现在看不见对方，那么除非它们中至少有一个改变方向，否则它们永远不会看到对方。如果它们相交，则需要计算第一个和第二个单位通过交点的时间差异——如果这个距离大于视野范围，那么除非其中一个改变方向，否则这些单位永远不会看到对方——如果这个差异小于视野范围，那么还需要进行更多（猛烈挥手）的计算，才能告诉你这个幸福的事件将在什么时候发生。

现在，你拥有的是一堆信息，分成了永远不会看到彼此的元素和将来某个时刻会看到彼此的元素——每个步骤，你只需处理已改变方向的单位，并计算它们与其他单位的交互。（哦，还要处理那些之前计算告诉你它们会相互看到的单位——记得将它们保持在可插入的有序结构中）你实际上已经利用了系统的线性行为，将你的问题从“单位A是否看到单位B”改变为“单位A何时看到单位B”。

现在，所有这些都不是要否认空间数据结构的答案 - 这是一个好的答案 - 然而，它也能处理随机运动中的单位，因此您需要考虑如何进一步优化此过程 - 您还需要小心处理跨区域可见性，即位于两个不同区域边界的单位可能能够看到彼此 - 如果您有倾向于聚集的碎片，则使用具有可变尺寸的空间数据结构可能是答案，其中不在同一区域的碎片保证无法看到彼此。

- Mark Mullin

---

我的单位视野不是有方向性的，它们有“雷达”，因此可以平等地看到所有方向。如果一个单位靠得太近，它们就会看到它。 - Calmarius

谢谢 - 提供的解决方案并不假设有任何焦点方向，只有一个（相对）固定的行进方向 - 直线相交只是让您排除次要可见性测试的方法，如果直线不相交 - 实际上，稍微复杂一些 - 如果直线分散，仅在起点时有可见性的机会，如果平行，则必须考虑时间，即两个单位何时最接近。 - Mark Mullin

是的，我现在重新阅读了一遍，我明白了。这在大多数情况下都可以很好地工作。但在热点事件中，当单位相互攻击时，一个单位可以追逐另一个单位，因此其目标位置和方向始终在变化。那会拖慢事情。所以我想我只会使用空间数据结构。 - Calmarius

Answer 3

我会用网格来解决这个问题，商业实时战略游戏就是这样解决的。

• 将游戏世界离散化以进行可见性跟踪。（方形网格最简单。尝试不同的粗细度以找到最佳值。）
• 记录每个区域中的现有单位。（当一个单位移动时更新。）
• 记录每个玩家所看到的区域。（必须随着单位移动而更新。单位可以轮询以确定其可见瓦片。或者您可以在游戏开始之前分析地图。）
• 为每个玩家所看到的敌方单位制作列表（或适合的其他结构）。

现在，每当一个单位从一个可见区域到另一个可见区域时，请执行以下检查：

• 从未见过的区域转移到可见区域-将该单位添加到玩家的可见性跟踪器中。
• 从可见区域转移到未见过的区域-从玩家的可见性跟踪器中删除该单位。
• 在另外两种情况下没有发生可见性变化。

这很快但需要一些内存。但是，使用BitArrays和指针列表，内存使用量不应该太大。

在《游戏编程宝典》中有一篇关于此的文章（我想是前三本之一）。

- rtm

---

我相信这是碰撞检测和其他类似于地图上检查所有其他附近物品的问题的行业标准方法。 - Justin L.