AGE – QuadTree implementation
What is the QuadTree ?
If we look at the wikipedia page, we can find a small explanation (it’s the best one I have found so far) :
A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are most often used to partition a two dimensional space by recursively subdividing it into four quadrants or regions.
Why would I add it ?
The first approach to detect collisions between entities was to check for each entity if it collided with one of the others entities in the world. So you can use this method for a really small game, because the number of tests is not that big. But if you have, for example, a game with 100 entities moving around the screen, which can collide with each other, the number of tests between entities will be 100×100 !! And at least half (probably more) of them are not necessary.
The Quadtree allows you to eliminate those unnecessary checks.
How does it work ?
Each time an entity is added to the stage, we just have to look into the tree and find where to put it. A node is simply a rectangular zone with entities and other nodes in it.
So basically, any node will be divided in 4 nodes if more than n entities are completely contained within the node. For AGE, I have decided to use n = 2.
Here is a more concrete example :
Now, our tree has been set. Before checking for collisions, we have to query the tree to determine which entities are worth testing for a rectangular zone (the rectangular zone can correspond to the theoretical position of an entity, to know if we can move it or not). So, the quadtree is going to return each entity contained in a node that have an intersection with our request zone (we have to return entities that are not entirely in a sub node too).
Here is a simple example: use the arrow keys to move the black entity, and look at the nodes (especially when near the entity at the right of the world) :