Fast algorithm for line of sight calculation in an RTS game

Question

I'm making a simple RTS game. I want it to run very fast because it should work with thousands of units and 8 players.

Everything seems to work flawlessly but it seems the line of sight calculation is a bottleneck. It's simple: if an enemy unit is closer than any of my unit's LOS range it will be visible.

Currently I use a quite naive algorithm: for every enemy units I check whether any of my units is see him. It's O(n^2)

So If there are 8 players and they have 3000 units each that would mean 3000*21000=63000000 tests per player at the worst case. Which is quite slow.

More details: it's a stupid simple 2D space RTS: no grid, units are moving along a straight lines everywhere and there is no collision so they can move through each other. So even hundreds of units can be at the same spot.

I want to speed up this LOS algorithm somehow. Any ideas?

EDIT:

So additional details:

• I meant one player can have even 3000 units.
• my units have radars so they towards all directions equally.

Answer 1

Use a spatial data structure to efficiently look up units by location.

Additionally, if you only care whether a unit is visible, but not which unit spotted it, you can do

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

and have:

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

A very simple spatial data structure is the grid: You overlay a coarse grid over the playing field. The regions are this grid's cells. You allocate an array of regions, and for each region keep of list of units presently in this region.

You may also find Muki Haklay's demonstration of spatial indexes useful.

Answer 2

One of the most fundamental rules in gamedev is to optimize the bejeebers out of your algorithms by exploiting all possible constraints your gameplay defines - this is the main reason that you don't see wildly different games built on top of any given companies game engine, they've exploited their constraints so efficiently that they can't deal with anything that isn't within these constraints.

That said, you said that units move in straight lines - and you say that players can 3000 units - even if I assume that's 3000 units for eight players, that's 375 units per player, so I think I'm safe in assuming that on each step of game play (and I am assuming that each step involves the calculation you describe above) that more units will not change their direction than units that will change direction.

So, if this is true, then you want to divide all your pieces into two groups - those that did change direction in the last step, and those that did not.

For those that did, you need to do a bit of calulating - for units of any two opposing forces, you want to ask 'when will unit A see unit B given that neither unit A nor unit B change direction or speed ?(you can deal with accelleration/decelleration, but then it gets more complicated) - to calculate this you need first to determine if the vectors that unit A and unit B are travelling on will intersect (simple 2D line intersection calculation, combined with a calculation that tells you when each unit hits this intersection) - if they don't, and they can't see each other now, then they never will see each other unless at least one of them changes direction. If they do intersect, then you need to calculate the time differential between when the first and second unit pass through the point of intersection - if this distance is greater than the LOS range, then these units will never see each other unless one changes direction - if this differential is less than the LOS range then a few more (wave hands vigorously) calculations will tell you when this blessed event will take place.

Now, what you have is a collection of information bifurcated into elements that never will see each other and elements that will see each other at some time t in the future - each step, you simply deal with the units that have changed direction and compute their interactions with the rest of the units. (Oh, and deal with those units that previous calculations told you would come into view of each other - remember to keep these in an insertable ordered structure) What you've effectively done is exploited the linear behavior of the system to change your question from 'Does unit A see unit B' to 'When will unit A see unit B'

Now, all of that said, this isn't to discount the spatial data structure answer - it's a good answer - however, it is also capable of dealing with units in random motion, so you want to consider how to optimize this process further - you also need to be careful about dealing with cross region visibility, i.e. units at the borders of two different regions may be able to see each other - if you have pieces that tend to clump up, using a spatial data structure with variable dimensions might be the answer, where pieces that are not in the same region are guaranteed not to be able to see each other.

Answer 3

I'd do this with a grid. I think that's how commercial RTS games solve the problem.

• Discretize the game world for the visibility tracker. (Square grid is easiest. Experiment with the coarseness to see what value works best.)
• Record the present units in each area. (Update whenever a unit moves.)
• Record the areas each player sees. (This has to be updated as units move. The unit could just poll to determine its visible tiles. Or you could analyze the map before the game starts..)
• Make a list (or whatever structure is fitting) for the enemy units seen by each player.

Now whenever a unit goes from one area of visibility to another, perform a check:

• Went from an unseen to a seen area - add the unit to the player's visibility tracker.
• Went from a seen to an unseen area - remove the unit from the player's visibility tracker.
• In the other two cases no visibility change occurred.

This is fast but takes some memory. However, with BitArrays and Lists of pointers, the memory usage shouldn't be that bad.

There was an article about this in one of the Game Programming Gems books (one of the first three, I think.)