I’ve been working on different approaches to speed up the collision detection stage for some while now (mainly for the motor engine and some games). This includes a Quadtree which I started working on last year, but just recently got around to pick it up again. I’m still fine-tuning the code, so I can’t share it at the moment. But, because I added some visualization stuff to help fix some bugs, I thought I could put together a little demo showing the Quadtree in action :).
I’m also thinking of creating another package (like the data structures) which would include some highly optimized broadphase collision detection algorithms, but this depends how much spare time I have – which is very limited at the moment.
But what exactly is a Quadtree ? Generally speaking, it’s a tree structure using a principle called ‘spatial locality’ to speed up the process of finding all possible collisions. Because objects can only hit things close to them, testing against distant objects should be avoided.
The easiest way to quickly compute a collisions set is to divide the collision space (e.g. your game area) into a uniform grid and register each object with all intersecting grid cells. That’s also called spatial hashing. One disadvantage is that it doesn’t cope well with objects of varying sizes. If the grid cells are too big, many unnecessary collision checks are done, and if they are too small, you end up searching many registered cells containing the same object.
The quad tree tries to overcome this weakness by recursively splitting the collision space into smaller subregions, similar to the RDC algorithm, with the difference that every region is divided exactly into 4 smaller regions of the same size, so you end up having multiple grids with different resolutions, where the number of cells in a region goes go up by a power of two every time the resolution is increased. So every object resides in the cell (called quad node or quadrant) with the highest (finest) possible resolution. A search is made by starting at the object’s node and ‘bubbling’ up to the root node. Wikipedia has a nice explanation, and there exist many variations.
The quad tree in the demo contains 1000 objects. I’m not sure if the quad tree is faster than a regular grid, but I’ll compare both versions soon. And don’t be afraid of the memory usage, it needs tons of memory because I’m storing all tree nodes for drawing them on the screen.