Adventures in Quad-Trees!

This past week I have been looking into implementing a quad-tree data structure in my game engine.  Although the amount of stuff on-screen in most of my games may not really benefit from it yet, I figured now would be the time to implement it before I face massive slowdown from too much shiny (á la fancy particle effects that bounce off of players, walls, etc.).

For those who are in the dark about what a quad-tree is, it's a specific data structure that can significantly streamline collision detection.  The basic concept is that the screen is split into zones as the number of objects on-screen increases. Once the number of objects on-screen reaches a threshold, the quad-tree splits the screen into exactly four quadrants.  Each quadrant can only contain so many collidable objects. If there are too many objects in any one of these quadrants, that quadrant can then be split into four more quadrants and so on, until each portion of the quad-tree is either at or below capacity.  Once you have the objects placed in different quad-trees, you can then check collision between only those inside the specific quad-tree rectangle and not check against one across the screen.  This can potentially save significantly on collision checks

Now, I know I asked myself, "Why would I want to do this?  Isn't it cheaper to just do collision tests on all of these objects at once?"  After all, all of my games up until this point have had only a handful of objects on the screen at once, and only a few objects cared if they collided with anything.  The first game I made, Log Jam! only cared if the player collided with any log, not if any logs collided with each other.  This led to some really weird problems, where the logs would "ride over" each other.  Although this was purely an aesthetic issue, it has always kind of bothered me.  Implementing collision logic between the logs would add variety in movement to each one, and make the game more dynamic overall at the cost of a LOT more collision checks.  This is where I could have implemented a quad-tree system to minimize the number of checks I would have to do.

An example of a collision issue in Log Jam!

Another example of wonky overlap with the logs

Working with Log Jam! as an example, let's go through the number of checks that we would need to do if we are later into the game, where there are a bunch of logs on-screen at once, such as in this screenshot:

A late game screenshot of Log Jam!

 In this shot, there are ten collidable logs on the screen (the waves are just for polish and aren't affected by the logs).  In this example alone we have 10 log collision checks to do, coming out to 45 checks minimum to make each time through the game loop.  If I was sloppy in coding (as I sometimes am), the number of checks would be closer to 90, assuming that I forgot to cull redundant checks.  Keep in mind that each check is a simple rectangle collision check, relying only on the bounding box of the log.  Even in this example, that is a lot of checks!  Let's break this into a more manageable size:

The same screen broken into a quad-tree

Now in this example, our parent quad (the entire screen) only has two objects in it, the log straddling one and two and the player's raft. quad one has two objects in it, two has one, three has two and four has three.  Let's go through the math: the objects in the parent node have to check against all of the sub-nodes and each other, netting 17 checks. The logs have to be placed into one of the quads, netting in another 24 checks.  Once all of those are into quads we can check each: quad one has 1 check, quad two has no check, quad three has only 1 check and quad four has 3 checks.  This leads to a total of 46 checks.  Hmmm... Not much better, is it?

If we limit our checks of the parent node to only those sub-quads that the object hits we can cut the number of checks.  For example, the player's raft will only hit quads one and three, that check alone netting us 4. we then compare the raft against quads one and three, netting another 4 checks. Doing the same with the log, we net 7 checks, cutting our total collision checks to 15.  When we put this into the our previous calculations, we end up with 44.  Not great, but a modest improvement.  The more objects that appear on-screen, the better the results we will get.

In my example, the quad-tree algorithm adds a lot of overhead to collision checking, so in this case, it may worthwhile for Log Jam! If there was a lot of collision checking that I had to do, such as where I was dealing with something where the logs rotated and the collision checks weren't just dealing with rectangle checks, but whether a rotated object indeed hit another, the quad-tree would make more sense. Having it in the toolkit for speeding up the game loop doesn't hurt, however.

Well, that's my broad-stroke analysis of quad-trees.  I'm sure that I'm missing something in this, but I just wanted to write my way through the problem before diving deep into the code.  If you have any questions/feedback, leave a comment.  Thanks for reading!

- Chandler