Profiling Away

I'm continuing to make good progress, although I took a break from my TODO list to pull out NProf again and do some performance work. Performance has improved ten times over since the first version of Aurora, but it still chugs a bit when there are a lot of units on the screen. I like having a lot of units on the screen, so I wanted to see if there was anything I could do to fix this.

I changed some initialization settings in the code so that there would be over 3000 units for each player on screen. I thought before that performance was being limited by the sprite drawing, which can't really be helped at this point. To my surprise, though, the stress test showed 80% of computation time being spent outside the Draw function, and over 65% being spend doing proximity detection for the game's units.

Now, I knew when starting this project that my proximity detection would be the most difficult part to program efficiently. I've got three factions, each with thousands of units, with each unit floating freely on a plane, and each of which needs to know when it is within a short radius of any other. That's n^2 right off the bat, and that's bad.

My algorithm so far has been for each unit to keep a list of all other units along with the next possible frame that that enemy unit might collide with it. When that frame comes, the unit calculates the distance, checks for a collision, and recalculates the next possible frame of collision. That way, units that are far away are checking for collision with each other only every thousand frames or so, while units nearby are checking every frame.

That worked pretty well, but it's still stressing the game at high unit counts, and all the work with dictionaries and lists is holding back performance. The specific problem is that
For every unit:
For every enemy unit:
I have to check for collision and if there is none,
I find the next frame to check and look up to see if that frame is already accounted for, and
Either make a brand new list of enemy units for that upcoming frame, or else
Retrieve the existing list and add this enemy unit

Profiling reveals that during the stress test the game spent over 25% of its time on the one line of code that corresponds to the last line above. A further 15% was spent on the second-to-last line above. A further 10% on the third-to-last line above. I'm spending a half of my stress test CPU time on an if-else statement that shows up as four lines of code in my game. If I can streamline that process, I might be able to knock out yet another bottleneck. And I think I can do just that.

I think part of the problem right now is that A) there are so many possible upcoming frames to check for (when we decide whether to make a new list of enemies to check or to add to it), and B) when a group of, say, 100 enemy stars clump together on a single frame-to-be-checked, the game retrieves that frame's list, adds a single star, and puts it back 100 times rather than collecting them all first.

One way that has occurred to me to get around this is to use the current algorithm for all units within, say, 100 frames, but beyond that to check enemy units only on 100-frame increments, up to a certain known limit. That way I can create a few relevant lists and add them to the dictionary all at once, and the places where I can add them are already known. It would require more actual distance checks, but it would allow much easier look-up and it would make recording the checks much easier.