Posted on August 20, 2008
8bitrocket Diatribe: Quad Tree Collision Research.
Along with many other little projects, I have begun research into creating a AS3 Quad Tree implementation to extend the optimized code in my series on creating an optimized Asteroids Game. A couple other blogs have also started their own implementations, including Fatal Exception and Polygonal Labs. Neither have any code to look at yet, but they both have nice examples to view and are far ahead of where I am right now. Although it is not directly related to quad trees, I also found a very interesting discussion on Grid Based Collision detection at the N site. I am far behind the curve on advance math based collision routines, so it has taken me a while just to get this far.
I have a huge library of game programming an design books across multiple different languages and disciplines. I first checked out a great volume called Data Structures and Algorithms for Game Developers. This book has a section on trees, especially BSP and Quad trees. A BSP or Binary Space Partitioning Tree is used mostly for 3d development. Basically is creates a hierarchy of objects from front to back based in the z-order (I’m simplifying here). This type of tree splits the virtual space into planes and creates the hierarchical tree based on which side of a dissection plane and object resides. Maybe we’ll explore this one in detail some day, but we are interested in seeing how another type, the Quad tree can help us with our collision detection. A quad is mostly used for 2d games. The tree would first split our play screen into 4 distinct quadrants (0-3). So if we have a 400 x 400 game play area, we would end up with a set of quads that look like this:
These four boxes are child nodes of the screen. A object would be in node 0,1,2, or 3. Node 0 contains the red helicopter and node 3 contains the skull and cross-bones. Inside of each node, a recursive quad split would occur when a condition is met. That condition could be something like is 4 objects exist in a quad, and would spit that quad further. For example:
In the above example, quad 0 has 5 objects in it, so we have split it into 4 more quads (numbered 0.0 – 0.3). Quad 0.1 contains two objects, both a helicopter and a skull and cross-bones. This is useful because on the frame there this occurred, instead of matching all helicopters in a loop against all skulls, we would only need to check if the two objects in quad 0.1 were colliding. If implemented properly, this would greatly lower the process time needed for collision detection. Since I am using BitmapData collision detection, this would help immensely with optimization for my game.
One more note on this type of structure: The above is an over simplification of how a game’s quads would look in a real game. In reality, objects would be in more than one quad frequently:
In the above example, a skull is in both 0.1 and 0.3 at the same time. If we just used the upper right-hand corner x,y values for positioning, then we would only be adding this to the object list of quad 0.1. That would make us miss the actual collision that occurs in quad 0.3 between the skull and the helicopter. I’m not quite sure how the experts would handle this, but I would take the bounding box of the skull and use that to decide what quads it reside in, then add it to the list of objects to be tested in each of those quads.
Of course, I might be wrong here because after reading through a chapter in Game Programming Gems (the first volume) I find that the prevailing opinion is that two objects MUST be COMPOLTETELY in the same quad to be tested against one another. Hmm, that doesn’t see to work very well, but of course I have not tried it in code yet. If that is the case, then let’s first attempt to split quad 0.1 and 0.3 into more quads and see what we come up with:
Hmm, that just leaves more questions, Now that 0.1 and 0.3 have been split again into 4 more nodes each, we get even more problems. Every object in those nodes now crosses at least 2 sub nodes. What a nightmare. I think I will go back and suggest that when I attempt to actually code this up I will allow an object to exist in more than one node based on all the nodes it’s bounding box touches. I’m not sure how this will affect performance, but I will give it a shot. Reading further in the Game Programming Gems chapter I find that the author (Thatcher Ulrich) agrees that in some cases this is allowable. He doesn’t go into how to detect what objects a node is in, but I will have to experiment with that anyway. He solves this problem with what he calls LOOSE trees. He allows the quad (in his case octree) boundary to be loose and expand when needed. This is an interesting concept that I don’t completely understand at this time.
My next Tutorial:
Maybe I am making this more complicated than necessary. Next time I will attempt an actual implementation. BUT not in my next tutorial as I have a new addition to the basic blitting tutorials I have been working on coming up next. In this one I will create a tile sheet of 36 rotations for an object and then use those to blit an object to the screen that is rotating around a point. We will blit the correct sprite from the sheet so the object is always facing in the direction that it is rotating. It would look something like this: