Last time I showed off my 162-unit RTS at a stunning 5 seconds per frame. Not FPS, that’s SPF. And that ain’t good.

Clearly it’s not scaling well as I crank up the units. What we’ve got here is your classic O(n^2) problem between entities. There’s a bevy of literature out there regarding space-division in a proper manner for these types of issues, but I had an idea.

The game literature out there deals with LOS for terrain but not for dynamic entities. I decided to roll my own: introducing the Visibility Matrix(tm):

Anybody there? “None.” Seems legit, Bob you’re on point.

You’re blue, the enemy is red but hidden (left the text on to show their position). I turned off the world so it can read better, but remember there’s a slab in the middle of the world blocking each other’s view. Each cell refers to the visibility between the two actors. The “oo”‘s mean “can see”…the “–“‘s mean “can’t see”.

Good ol’ Bob. Never complained about recon.

Visibility between Blue:7 and Red:0-5 has been established in the Visibility Matrix, and the units can query these values rather than generate it on their own expensively.

What makes this faster is these vis checks are time-sliced, i.e. only a few of them are updated every frame instead of the O(n^2) nightmare from the last post. To achieve this we simply walk through the matrix left->right, top->bottom, updating each cell with a fresh LOS.

How many cells do we update each frame? Well if there’s n units, then the Visibility Matrix only needs n * (n – 1) / 2 cells, as visibility is commutative and we assume each actor can see themselves. Best of all we  guarantee that no enemy can see you before you see them, so no ambushes just a little lag.

Finally if we demand a maximum response time for the unit in frames, then the number of checks performed each frame to guarantee an update = max frames / # cells. At 60fps and a 1 second response time your calls are spread out over 60 frames.

Here’s the same 162 units rocking it out at a smoking 9fps. I’m calling it 10fps, that’s a 50x framerate increase.

Where this really takes off is I can store more than just vis data in there — distance calculations, health differential, whose turn it is to do the dishes, whatever I’d normally have to generate at runtime about information for each pair of actors.

Once I move all these calculations to the server I hope to throttle up a gear in terms of units. But maybe I should make a game first…