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

Question

我正在制作一个简单的RTS游戏.我希望它运行得非常快,因为它可以与数千个单位和8个玩家一起使用.

一切似乎都完美无缺,但似乎视线计算是一个瓶颈.这很简单:如果一个敌方单位比我单位的任何一个LOS范围更近,它将是可见的.

目前我使用了一个非常天真的算法:对于每个敌方单位,我检查我的单位是否有人看到他.它是O(n ^ 2)

因此,如果有8个玩家并且他们每个拥有3000个单位,那么在最坏的情况下每个玩家将需要3000*21000 = 63000000个测试.这很慢.

更多细节:它是一个愚蠢的简单2D空间RTS:没有网格,单位在任何地方沿着直线移动,没有碰撞,所以它们可以相互移动.因此,即使数百个单位也可以在同一地点.

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

编辑:

更多细节:

Answer 1

使用空间数据结构有效地按位置查找单位.

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

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

并有:

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

一个非常简单的空间数据结构是网格:您在游戏区域上覆盖粗网格.区域是这个网格的单元格.您分配一个区域数组,并为每个区域保留当前在此区域中的单位列表.