Hey look, a quadtree

So what's so special? This is a common data structure that everyone one of you should be able to do from memory. It's extremely simple, and uses recursion. Simply make a tree with each node linking to 4 child nodes that evenly divide space, and let each node store a list of pointers or the data itself.

The special part, is this is a generic quadtree, so, instead of 'storing' objects, it stores XData::Quadtree::Proxy object POINTERS to a XData::List, which means that Proxy lifecycle is left to the user (working on making it pointeriffic and more auto-delete) but that also means that every node stores a list of those proxy pointers, so that your game object:

class MyGameObject : public Game::BaseObject {
private:
XData::Quadtree::Proxy m_proxy;
}

Can simply access the quadtree as such:

qtree.insert( obj.m_proxy );
qtree.remove( obj.m_proxy );
m_proxy.IsValid();
qtree.get( XData::Array &, fptr_to_Collision_Function, collision_function_data );

So what this means, is in the above picture you can draw arbitrary edges for a odin-sphere style level, which get their proxies put into the quadtree. This is dangerous only if you forget to remove the proxy before deleting the object. But it means that you can query arbitrary shapes against the quadtree and get a quick enough broadphase test for intersection. Insertion is always better than O(log(n)), deletion/update is best case O(1), worst case O(log(n) + 1). Access is linked list, so fast iteration is possible.

Quadtree's are good for dynamic data, that is if everything is changing quickly. There are other methods for static data that are far superior, like KDTrees or Spaceblocks or even AxisSweeps, but quadtrees are a general good purpose solution that's still good in performance to be viable for many applications. In fact, you probably won't need much more than this, unless you have severe restrictions that force you to use sorted space blocks.

If you are making a 2D game, please do not use tiles. I will hate you, and you should be competent enough to make a quadtree (think Game Maker) that can handle arbitrary shapes and so forth.

Go look at this game to see one of these methods in action

-Z