Bounding Box Trees

August 23rd, 2010| Posted by slembcke
Categories: Uncategorized | Tags:

So one item that we knew we would have to do eventually for Solaro was some sort of broadphase for the the collision detection. Up until now, collisions were processed by checking every object against every other object. In computational terms, this is O(n^2) meaning that every time you double the number of objects, the collision detection takes 4x as long!

Say that you have 30 ships flying around the screen and say that running the collision detection takes 1 millisecond. The game could happily run at 100+ fps this way. Now add 120 bullets and missiles flying around in space. The collision detection alone could only run at 40fps now!

What we have now is a bounding box tree instead of a list. It works by putting a bounding box around each object. As you loop over all the objects, it puts pairs of bounding boxes that are near each other together and puts a bounding box around both of them. If an object doesn’t overlap this larger bounding box, it doesn’t overlap either object. After several layers of grouped bounding boxes like this, you can check if an object doesn’t overlap hundreds of bounding boxes with a single check instead of testing them one by one.

This means that we can put hundreds of bullets, ships, and missiles flying around now and still keep the frame rate a smooth 60fps.

Comments are closed.