Some RTS games, for example games built on the Spring RTS engine, implement a visibility/detection system that checks both whether a hostile unit is within the detection range of a friendly unit, and whether the friendly unit has unobstructed line-of-sight to the hostile unit, before making the hostile unit visible to the player. I'm trying to create an RTS with a system like this. Can someone explain the algorithm used to do this in real-time? The naive way of checking visibility between each pair of units every frame must surely be a no-go, because it would scale horribly on a map with potentially thousands of units.
I have attempted to look at Spring's source code, but it is quite overwhelming and it is difficult to even know where to begin, so I'm hoping someone can summarize a visibility algorithm in human-readable form. Also, I mentioned Spring because it is an open-source example, but I would be interested in any efficient visibility algorithm; I'm just hoping to not have to reinvent the wheel here.
