我正在制作一个简单的实时战略游戏。我希望它能运行得非常快,因为它需要处理数千个单位和8个玩家。
一切似乎都很顺利,但是视野计算似乎是瓶颈。它很简单:如果敌人单位比我的任何单位的视野范围更近,那么它将可见。
目前我使用相当幼稚的算法:对于每个敌方单位,我检查是否有任何我的单位可以看到他。这是O(n^2)。
所以,如果有8个玩家,每个玩家都有3000个单位,那么最坏情况下每个玩家要进行3000*21000=63000000次测试。这相当慢。
更多细节:这是一个非常简单的二维空间实时战略游戏:没有网格,单位沿着直线移动,没有碰撞,所以它们可以互相穿过。因此,即使有数百个单位在同一位置,也不会发生碰撞。
我想以某种方式加速这个视野算法。有什么想法吗?
编辑:
因此,额外的细节如下:
- 我的意思是一个玩家甚至可以拥有3000个单位。 - 我的单位有雷达,可以朝所有方向平等地看。
一切似乎都很顺利,但是视野计算似乎是瓶颈。它很简单:如果敌人单位比我的任何单位的视野范围更近,那么它将可见。
目前我使用相当幼稚的算法:对于每个敌方单位,我检查是否有任何我的单位可以看到他。这是O(n^2)。
所以,如果有8个玩家,每个玩家都有3000个单位,那么最坏情况下每个玩家要进行3000*21000=63000000次测试。这相当慢。
更多细节:这是一个非常简单的二维空间实时战略游戏:没有网格,单位沿着直线移动,没有碰撞,所以它们可以互相穿过。因此,即使有数百个单位在同一位置,也不会发生碰撞。
我想以某种方式加速这个视野算法。有什么想法吗?
编辑:
因此,额外的细节如下:
- 我的意思是一个玩家甚至可以拥有3000个单位。 - 我的单位有雷达,可以朝所有方向平等地看。