Optimizing Broad-Phase Collisions

As I mentioned yesterday, I had an "ah-hah" moment when I realized that objects were rebuilding their potential collision list (PCL) over and over.  Plus, each time it would rebuild these lists it would also create a copy of all of the objects in a collision node before adding them all to the PCL.  So, after some work I have come up with a way to perform some caching and optimizations of PCLs.

Each frame that was generated was going through every object which was "curious" about potential collisions and building a PCL for them.  One optimization was to cache the results of a PCL for the given root node.  If you look at the way the SpatialGrid works, it will create a list of nodes which need to be checked, centered at the normalized position of the object.  Normalized being the node's top-left corner for which the object is within. By caching the results and reusing them for any object which is in the same node, there is time saved by not having to perform the rebuild.

Another optimization was to be had by only updating those cached PCLs when one of the nodes was marked as dirty.  Looking again at the way the SpatialGrid works, objects are added to a node within the grid and are removed when they leave the node's bounding rectangle.  So, an object may move within the node but the entire PCL doesn't need to be rebuilt unless a new object has been added to, or removed from, one of its nodes.  Even more time saved.

The third and final optimization here was having nodes return their actual object list, rather than returning a copy of the list.  Creating the copy required precious milliseconds which can be used elsewhere.  The PCL will make a copy of those objects when it adds all of them together into one collection.  This may even be another place I can save some milliseconds, by only reorganizing the head and tail pointers of the node lists to link them together.  Thus, instead of copying the entire list from each node into the PCL, I would only need to create a new head and tail of the collection to link the lists together.  Instead of processing, say, four lists of five objects each (20 objects in total, I would only need to create a new head and tail of each list (4 * 2 - 2 = 6 total changes).

Overall, I have now optimized the SpatialGrid broad-phase collision system and saved several milliseconds to be used elsewhere.  If I get a chance, I will do some math and see if I can't come up with the amount of time gained.  One other thing that I noticed during my updates, when objects move from one edge of the playfield to another, I'm seeing the number of PCL rebuilds jump dramatically.  I will be tracking this down as well...