Upgrading (?)

I've made three questionable upgrades to Aurora since my last blog post.

The first upgrade was to move the entire project to XNA 4.0 and .NET 4.0. I just bought and installed a new desktop computer running Windows 7. Naturally, I installed the latest Visual Studio (2010). Naturally, it only integrates with the latest version of XNA. Naturally, the latest version of XNA breaks a bunch of old code. It's all for the best, I'm sure, but I spent the first few hours of development on my new machine just trying to get the game running and get the newly premultiplied alpha values to work like the old system did.

The second upgrade was to start using LinkedLists instead of regular array-based Lists. There was absolutely no reason that two different cheap operations (adding an element to a List and making a new empty List) would ever consume 40% of my CPU time when equally frequent, more intensive calculations (like distances) took 2%. But one of my roommates suggested that maybe the allocation of new Lists and resizing of Lists during the Add functions could be triggering the automated garbage collection. And since I was constantly allocating and deleting small bits of data, that could add a ton of overhead. Using LinkedLists and just moving nodes around should be much cheaper.

The problem came when I implemented this in such a way that my units were no longer aggressively culling their list of enemies that they were "locked on" to. (Units lock on at 100 pixels and then speed towards their targets until a real collision occurs at 10.) So on every frame they would lock on to the same enemies over and over, speeding towards them at an accelerating rate, totally ruining the smooth, flowing feel I liked so much. The best solution to this will probably involve making a Dictionary of locked-on-units with keys based on some unique ID for each unit in the game.

The third upgrade was to move to a grid system of collision detection, as was suggested by my girlfriend Stephanie after my last blog post. I had considered this system before, but threw the idea away due to imagined complications. Since then, Stephanie and my roommates (better programmers than me) have convinced me that the grid system is superior. My collision detection problem is always going to be fundamentally an O(n^2) problem at close distances, but my solution was ultimately O(n^2) at all distances (albeit with some aggressive optimizations). The grid system is O(1) at great distances.

Naturally, the first implementation of this destroyed the game's performance. Naturally, that was caused by my mistakes in the implementation.

My best guess right now is that the problem lies in the way the grid stores units. It currently keeps one LinkedList for all units in each square. When a square has 4000 units of the same team all together (as the stress test starts), each unit checks each other unit to see if it friendly, then does nothing. Doing nothing is cheap, but just checking 4000^2 times every frame might be enough to bring the game to a crawl. It looks like I'll have to set up an array of LinkedLists (ugh) so that each faction can weed out friendly units in one step.

I'm really hoping that these changes will boost performance to its practical best, so that at the very least I shift the bottleneck to the graphics card on most systems. I'm working with a new profiler and an improved system, so it's hard to compare these results to what I had before, but I'm a little worried about the profiling tests I've done already. Running the game at 1fps on a stress test, the profiler reported only a little over half of the time being spent directly in my collision detection sections. Even if that were reduced to zero, wouldn't that only double the current performance? Will that be enough?

In any case, I'll keep working on it, and hopefully I'll be able to add the new levels in time for an early November release. I've got plenty of possible resources and plenty of intelligent people to lean on, so I've got no excuses for failure.