RTS游戏中视线计算的快速算法

我正在制作一个简单的RTS游戏。我希望它运行得非常快，因为它可以与数千个单位和8名球员一起工作。RTS游戏中视线计算的快速算法

一切似乎都完美无缺，但似乎视线计算是一个瓶颈。很简单：如果一个敌方单位比我单位的任何LOS距离都更近，它就会显示出来。

目前我使用一个相当天真的算法：对于每个敌方单位，我检查我的任何单位是否看到他。这是O（n^2）

所以，如果有8名球员，他们有3000个单位，每个球员在最坏的情况下意味着3000 * 21000 = 63000000测试。这很慢。

更多细节：这是一个愚蠢的简单2D空间RTS：没有网格，单位沿着直线移动，没有碰撞，因此它们可以相互移动。因此，甚至有数百个单位可以在同一个地点。

我想以某种方式加快这个LOS算法。有任何想法吗？

编辑：

所以额外的细节：

我是一个球员能有3000甚至单位。
我的单位有雷达，所以他们向所有方向平等。

来源

2010-08-21 Calmarius

我建议还问这对http://gamedev.stackexchange.com/，如果你还没有。 – cHao 2010-08-21 10:46:44

3000/8 = 375，在SC2中你可以有最多200个食物，谁能够正确地制作375个单位！ :) – 2010-08-21 12:06:53

Ohkay，RTS =实时战略！ – Lazer 2010-08-21 16:36:32

使用spatial data structure可以按位置高效查找单位。

此外，如果你只关心一个单元是否是可见的，而不是哪个单位看上它，你可以做

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

，并具有：

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

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

您可能还会发现Muki Haklay's demonstration of spatial indexes有用。

来源

2010-08-21 11:00:20 meriton

gamedev中最基本的规则之一是通过利用游戏定义的所有可能的约束条件来优化算法中的贝叶斯 - 这是您没有看到在任何给定的顶部上构建的非常不同的游戏的主要原因公司的游戏引擎，他们已经非常有效地利用了他们的限制，以至于他们无法处理任何不在这些限制之内的事情。这就是说，你说单位直线移动 - 你说球员可以有3000个单位 - 即使我假设这对于8个球员来说是3000个单位，那么每个球员的单位是375个单位，所以我认为我是安全的假设在游戏的每一步（我假设每一步都涉及上述计算）表示更多单位不会改变方向比单位将改变方向。所以，如果这是真的，那么你想把你所有的作品分成两个小组 - 那些在最后一步确实改变了方向，而那些没有做到的小组。你需要做一些调整 - 对于任何两个敌对部队的单位，你想问'单元A何时会看到单元B，因为单元A和单元B都不改变方向或速度？（可以处理加速/减速，但随后会变得更加复杂） - 为了计算这个，首先需要确定单元A和单元B正在行驶的矢量是否相交（简单的2D线交点计算，并结合计算，告诉你什么时候每个单位击中这个交点） - 如果他们不这样做，并且他们现在不能看到对方，那么除非他们中的至少一个改变方向，否则他们永远不会看到对方。如果它们相交，那么你需要计算第一个单位和第二个单位通过交点的时间差 - 如果这个距离大于LOS范围，那么这些单位将永远不会看到对方，除非一个方向改变 - 如果这个差值小于LOS范围，那么再多几次（大力挥手）计算就会告诉你这个祝福事件将发生在。

现在，你所拥有的是一个信息集合，它被分解为永不会彼此看到的元素，以及将来会在某个时间t看到彼此的元素 - 每一步，你只需处理已经发生变化的单位方向并计算它们与其余单位的互动。（哦，并且处理那些先前的计算告诉你会看到彼此的单元 - 记住要将它们保存在一个可插入的有序结构中）你有效地做的是利用系统的线性行为来改变你的问题“并不单元A看到单元B”来“当意志单元A看到单元B”

现在，这一切说，这是不打折的空间数据结构的答案 - 这是一个很好的答案 - 然而，它也能够处理随机运动的单位，所以你想考虑如何进一步优化这个过程 - 你还需要小心处理跨区域的可见性，即在两个不同区域的边界的单位可能是能够看到对方 - 如果你有碎片，往往会聚集在一起，你唱出具有可变尺寸的空间数据结构可能是答案，其中不在相同区域中的片段被保证不能够看到彼此。

来源

2010-08-21 12:38:02

我的部队的视线不具有方向性，他们有'雷达'，所以他们看到所有的方向平等。如果一个单位太近，他们会看到它。 – Calmarius 2010-08-22 09:14:15

虽然很好的答案。 – Calmarius 2010-08-22 09:19:26

谢谢 - 所提供的解决方案并不假定有任何聚焦方向，只有一个（相对）固定的行进方向 - 线相交只是允许您排除次要可见性测试，如果线不相交 - 实际上，a稍微复杂一点 - 如果线条分歧，只有在开始时才有可见性，如果平行，那么你必须考虑时间，即两个单元何时最接近 – 2010-08-22 12:32:59

我会用网格做到这一点。我认为这就是商业RTS游戏如何解决这个问题。

使能见度跟踪器的游戏世界分散。（方格是最容易的，用粗糙的实验看看什么值最好。）
记录每个区域的当前单位。（每当一个单位移动时更新。）
记录每个玩家看到的区域。（必须在单位移动时进行更新，单位可以轮询以确定其可见的图块，或者您可以在游戏开始前分析地图。）
为敌人制作一个列表（或任何适合的结构）每个玩家看到的单位。

现在只要一个单元从另一个知名度的一个区域去，进行检查：

从一个看不见又到了看到区 - 单元添加到玩家的知名度跟踪。
从看到的地方到看不见的地方 - 从玩家的能见度跟踪器中移除单位。
在另外两种情况下，没有发生可见性变化。

这很快但需要一些记忆。但是，使用BitArrays和指针列表时，内存使用情况不会那么糟糕。

有关于这一点的游戏编程精粹的一本书的文章（前三之一，我想。）

来源

2010-08-22 00:35:41 JackKane

我确实认为这是碰撞检测和其他此类检查对所有其他附近项目问题的行业标准方法。 – 2010-08-23 07:13:22

RTS游戏中视线计算的快速算法

回答

相关问题