As some of you might know, I recently published my latest Xbox LIVE game called Ashlands: Retribution.  In Retribution, I used a lot of sneaky tricks to keep C# running at respectable rates.  This article will cover just one of those tricks.

The original incarnation of Retribution was called Seizonrenda and, in addition to the impossible name, the game had some considerable performance issues.  Resolving the performance issues was a top priority moving into Retribution, a game that turned out so much better than this lone coder could have hoped for.

One of the performance issues that the game had was a result of starving the CPU whenever more than 10 – 20 enemies was on the Orbital Grid (OG: the visible grid around the planet that represented the field that was in play).  Many asteroids could be put into play; ~500 was enough to blanket the Orbital Grid.  Enemies however had a particularly expensive series of behaviors.  The AI would not only chase the player, they would avoid each other and maintain spacing between them and the hundreds of asteroids on the planet.

The AI and projectiles on the OG all had the same issue, they needed to be aware of game objects with a full 360 degrees of freedom since enemies were dropping into orbit and flying around the planet at varying speeds.  The original technique involved a greedy search where each AI and every projectile performed a linear search of the entire registry of game objects.  This quickly devolved into an O(N^2)+ solution.  To avoid some redundancy the projectiles were managed in a separate list, meaning projectiles always checked if they hit something but the AI never bothered to check the reverse of that case.  This didn’t help as much as I had hoped since (in Seizonrenda) the player was the only ship who could shoot.  This would not do in Retribution, where enemy projectiles could blanket the planet as much as asteroids. » Read more..