Interesting "Discovery"

Discovery is in quotes because my revelation was actually more of a palm-face when I thought about it.  I was doing some optimizations in the engine when I noticed something that smacked of an "area of interest."  In the Asteroids Evolved demo, whenever I had all five bullets on screen in Firefox 3.6, the game would slow down by a factor of 2x to 2.5x!  At first I was wondering what would cause such a noticeable slowdown and then it hit me.



Each bullet and asteroid, during game play, is checking for collisions.  If I had two asteroids on screen and no bullets, everything was fairly smooth.  But as soon as I have those two rocks and all five bullets, the game drops from 60+ FPS to 20 or less.  It makes sense since the game is going from two collision tests every frame to seven.  Each of those tests is performed on the nine grid cells surrounding the object, so assembling the PCLs goes from 18 to 63 cell queries.  With the bullets moving in close proximity to each other, they are triggering potential collisions which must be tested by each bullet.

By moving the collision testing to only exist on the asteroids, I'm reducing the overall number of tests until I have a bunch of asteroids on screen.  This led me to another thought...  Each time a PCL is assembled for a particular grid cell, that grid cell should hold onto it for the remainder of the frame.  Plus, adjacent cells would benefit from a query which was already performed.  Rather than create a PCL for each object which desires the info, the PCLs should be built by sharing information already gathered by other collision tests.

The SpatialGrid is a coarse grid of cells which is used to assemble potential collisions.  As a cell is queried, the results should be stored onto the cell so that the cell doesn't have to re-assemble the list for each object which queries it.  Plus, objects within the same cell should benefit from the same query rather than each assembling their own PCL.  Both of the PCLs will result in the same collection of objects per frame, so there's no reason to reassemble the list within the same frame.

Overall, this is a big "ah hah" moment but also a huge "face-palm" moment too.  It makes so much common sense that this would be a big area of slowdown.  I'm going to work through addressing this in the hopes that the optimizations I was performing, plus this "discovery," will result in even more time available per generated frame which, in the end, will result in higher frame rates.