Keeping the Framerate in Retribution

[Reprinted from ...]

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.

Getting Spatial

I knew that I needed to spatially divide the planet to allow me to quickly reduce the list of game objects that needed to be tested.  I had many ideas but ran into some snags along the way.  The planet was a giant sphere which lead me down a path of trying to find crafty ways of storing game objects into a spherical spatial system.

I tried breaking the planet into a collection of cones/frustums that infinitely protruded from the center, but it was often computationally inaccurate and caused objects to pass through each other.  I tried to split the world along all 3 axis to generate quadrants but this was too coarse and only gave around a 20% improvement at best during gameplay testing.  Also, the worst case scenarios performed even more poorly due to the additional overhead of managing those quadrants and cones.

I tried your typically hierarchical systems, kd-trees, BSP, and Oct-tree; a quad tree was not applicable for spherical space.  I found them to be too expensive to handle in a C# environment with over 1000 dynamic game objects.  I even tried converting their spherical coordinates into a 2D grid, using a latitude/longitude from their orientation to generate a [0 - 1] mapping, but this became cumbersome to manage objects with volume.  Since ships were of very different sizes this made it difficult to judge the cell size for the 2D grid without missing collisions.

Eureka!

Finally I settled on a solution that was inexpensive to the CPU for both registering new AI and performing volumetric queries.  I took the general concepts behind all of the hashing approaches I tried before and applied them to 3D space instead of 2D.  I created a 3D Collision Grid (CG) that covered all of the playable regions of the planet.  The Class I created allowed me to pass in an arbitrary number, and a square grid would be generated to that specification.  This allowed me to tweak the grid size to find a balance of memory and speed by changing 1 line of code.  The volume of each cell was calculated from the area that needed to be covered and the number of cells used to subdivide that space.  It let me reduce it to 1x1x1 which gave me near original performance, or 9x9x9 which proved to be around the sweet spot.  It used very little memory since each cell only stored a List<> of game objects for that 3D volume of space.

Instead of dealing with converting between spherical and linear coordinates then back again, causing computation errors and missed collisions, all game objects were tracked using the same bounding sphere that was used by the rendering system.  Since all objects already maintained an accurate bounding sphere for rendering, it meant that no additional CPU was required to submit the object into the Collision Grid.  Also, since the grid was using linear coordinates it was easy to generate a min and max of the game object and submit that object to all of the grid cells in that range.

Min = (Entity.Pos - Entity.Radius - CG.Min) / CG.CellSize;
Max = (Entity.Pos + Entity.Radius - CG.Min) / CG.CellSize;

It's important to note that the Min and Max grid positions needed to be clamped against the bounds of the Collision Grid.  Since enemies dropping from outer orbit were not officially in play yet, and larger enemies had bounding spheres that reached far outside of the grid, the values could not immediately be assumed as safe.  The alternative would have been to overcompensate with a larger Collision Grid but it wasn't worth the additional CPU and memory when a few quick conditional checks worked just as good.

Is Anybody Out There?

It's all good if you can find a clever way to store objects spatially but it is just as important to be able to quickly and accurately query for those objects as well.

Using the same equations as listed above, it was easy to query for nearby objects by simply finding the effective cells for any given bounding area and generating a unique set of results; "set" being the keyword.  I used a HashSet<> as my result structure since neighboring cells had a high likelihood of having duplicate references, especially for large ships and asteroid clusters.  The HashSet<> ensured that, even if duplicates were found, the final result was the smallest possible collection that avoided enemies being processed more than once per query.

Submitting entities into the Collision Grid as well as performing queries was so streamlined that it was more memory and CPU efficient to simply wipe the grid clean and resubmit all objects once per frame than create some kind of "smart" system than transferred ownership of an object from cell to cell as the physics were updated.  Smart broad phase physics systems work better for environments where a small island of crates are the only active physics objects while the rest of the world is inactive.  I could not make that assumption. 

This brute approach did result in rare instances where an object may miss a collision if it just crossed into a crowded cell but, in practice, those errors self-corrected themselves the very next frame.  It was more efficient because it assumed the most likely scenario; every object in the game world was dynamic.  Every asteroid, enemy, and projectile had physics properties and could be pushed around and moved each and every frame.

Better Than I Could Have Imagined

After this redesign, the framerate shot up so high that I found myself pushing more enemies than I could have imagined.  This approach, coupled with a multi-core solution for AI and physics updates (to be detailed another time) allowed me to increase my enemy counts by more than 10x.  In additional to this swell of enemies, I was able to add collision to each and every asteroid.  Previously asteroids passed through each other as a way of cutting down the CPU cost of having so many on the OG.  Even projectiles swelled from 20-something to over 500, making some scenarios in the game feel just as they should for any bullet-hell or shoot'em up; downright frightening.

Conclusion

In the end I found a simplistic, near O(1), solution to organizing a loose bag of game objects that resided in spherical coordinates.  Though there was some memory wasted in parts of the Collision Grid, such as the core of the planet, it was well worth the benefits gained on the CPU.  Gaining back this much horsepower allowed me to not only reach my targets but exceed them with full collisions across the map, over 10x the enemies of the original game, and increasingly complex AI behaviors.

I'll be posting some "Let's Play" videos of the campaign from Retribution soon, and I hope you like what you see...  I hope it gives you a little more insight into the blood, sweat, and tears behind Retribution.