Exploring Collision Detection

The method that I explored beyond what I learned in AI for Games was broad base collision detection.  Broad base collision detection deals with the problem of scaling up basic collision detection while still using the CPU efficiently.  There are many different methods within the umbrella of broad base, the one that I focused on was Spatial subdivision.  Spatial subdivision determines which objects to check collisions on, by dividing the world into sections and only checking objects in the same sections.  Spatial subdivision is especially useful for games that have many objects split evenly across a world with finite borders.

When checking collisions between objects there are two levels, the narrow phase is checking each individual object, while the broad phase deals with selecting which objects to check.  The narrow phase handles each object that is selected against every other chosen object, without the broad phase the number of checks grows exponentially as the number of objects increases.  While not always necessary, the broad phase allows for more flexible collision detection since it allows objects to be aware of their surroundings.

Spatial subdivision divides the map of the game world into sections; each section keeps track of all objects inside it.  Each section must be larger than the maximum object size otherwise the objects will always exist in multiple sections.  Every update the section that each object is in gets calculated and then every section with more than one object in it checks for collisions.  If a section has one or fewer objects then the section does not check for collisions, similarly if the objects in a section have not moved since the last update it will not check again.  The main problem that must be dealt with in spatial subdivision is that objects will inevitably end up contained in two or more sections and checked in both, this can be dealt with by ignoring adjacent sections containing multiple parts of one object (Nguyen, Hubert).

Spatial subdivision is especially useful to bullet hell shooters with a fixed arena, since the likely number of bullets and actors is very high.  Falling sand simulators also find subdivision to be highly useful since if sections become completely full then they can be ignored for the purposes of collision checking.  The strength of spatial subdivision is that it cuts down on CPU usage but it does not increase memory usage very much, this means that it is suitable for most platforms. 

While researching spatial subdivision I found GPU Gems 3 to be very helpful in codifying the terms.  GPU Gems 3 also contained very helpful illustrations of spatial subdivision being used.  Collision Detection and Particle Interaction is a site that demonstrated spatial subdivision in a particularly compelling manner, the site does focus on a different manner of subdivision than I used but the concept broke my concept of collision detection out of its mold.  Spatial hashing implementation for fast 2D collisions provided several essential code examples as well as illustrating exactly how much easier on the CPU spatial subdivision is.

 Nguyen, Hubert. "32." GPU Gems 3. Upper Saddle River, NJ: Addison-Wesley, 2008. N. pag. Print.

Merlin3d. "Spatial Hashing Implementation for Fast 2D Collisions." The Mind of Conkerjo. N.p., 13 June 2009. Web. 02 Dec. 2013.

"Collision Detection and Particle Interaction." Collision Detection and Particle Interaction. N.p., n.d. Web. 02 Dec. 2013.