Implementing a Quadtree
The following was converted to C# from a Java tutorial by Steven Lambert, Quick Tip: Use Quad Trees to Detect Collisions in 2D Space.
A quadtree starts as a single node. Objects added to the quadtree are added to the single node.
When more objects are added to the quadtree, it will eventually split into four subnodes. Each object will then be put into one of these subnodes according to where it lies in the 2D space. Any object that cannot fully fit inside a node’s boundary will be placed in the parent node.
Each subnode can continue subdividing as more objects are added.
We’ll start off by creating the main Quadtree class.
public class Quadtree {
private int MAX_OBJECTS = 10;
private int MAX_LEVELS = 5;
private int level;
private List<myGameObject> objects; //convert to your object type
private Rectangle bounds;
private Quadtree[] nodes;
/*
* Constructor
*/
public Quadtree(int pLevel, Rectangle pBounds) {
level = pLevel;
objects = new List<myGameObject>;
bounds = pBounds;
nodes = new Quadtree[4];
}
}
The Quadtree class is straightforward. MAX_OBJECTS defines how many objects a node can hold before it splits and MAX_LEVELS defines the deepest level subnode. Level is the current node level (0 being the topmost node), bounds represents the 2D space that the node occupies, and nodes are the four subnodes.
In this example, the objects the quadtree will hold are Rectangles, but for your own quadtree it can be whatever you want.
Next, we’ll implement the five methods of a quadtree: clear, split, getIndex, insert, and retrieve.
/*
* Clears the quadtree
*/
public void Clear() {
objects.Clear();
for (int i = 0; i < nodes.Count; i++) {
if (nodes[i] != null) {
nodes[i].Clear();
nodes[i] = null;
}
}
}
The clear method clears the quadtree by recursively clearing all objects from all nodes.
/*
* Splits the node into 4 subnodes
*/
private void Split() {
int subWidth = (int)(bounds.Width / 2);
int subHeight = (int)(bounds.Height / 2);
int x = (int)bounds.X;
int y = (int)bounds.Y;
nodes[0] = new Quadtree(level+1, new Rectangle(x + subWidth, y, subWidth, subHeight));
nodes[1] = new Quadtree(level+1, new Rectangle(x, y, subWidth, subHeight));
nodes[2] = new Quadtree(level+1, new Rectangle(x, y + subHeight, subWidth, subHeight));
nodes[3] = new Quadtree(level+1, new Rectangle(x + subWidth, y + subHeight, subWidth, subHeight));
}
The split method splits the node into four subnodes by dividing the node into four equal parts and initializing the four subnodes with the new bounds.
/*
* Determine which node the object belongs to. -1 means
* object cannot completely fit within a child node and is part
* of the parent node
*/
private int GetIndex(Rectangle pRect) {
int index = -1;
double verticalMidpoint = bounds.X + (bounds.Width / 2);
double horizontalMidpoint = bounds.Y + (bounds.Height / 2);
// Object can completely fit within the top quadrants
boolean topQuadrant = (pRect.Y < horizontalMidpoint && pRect.Y + pRect.Height < horizontalMidpoint);
// Object can completely fit within the bottom quadrants
boolean bottomQuadrant = (pRect.Y > horizontalMidpoint);
// Object can completely fit within the left quadrants
if (pRect.X < verticalMidpoint && pRect.X + pRect.Width < verticalMidpoint) {
if (topQuadrant) {
index = 1;
}
else if (bottomQuadrant) {
index = 2;
}
}
// Object can completely fit within the right quadrants
else if (pRect.X > verticalMidpoint) {
if (topQuadrant) {
index = 0;
}
else if (bottomQuadrant) {
index = 3;
}
}
return index;
}
The getIndex method is a helper function of the quadtree. It determines where an object belongs in the quadtree by determining which node the object can fit into.
public void insert(Rectangle pRect) {
if (nodes[0] != null) {
int index = getIndex(pRect);
if (index != -1) {
nodes[index].Insert(pRect);
return;
}
}
objects.Add(pRect);
if (objects.Count > MAX_OBJECTS && level < MAX_LEVELS) {
if (nodes[0] == null) {
Split();
}
int i = 0;
while (i < objects.Count) {
int index = GetIndex(objects[i]);
if (index != -1) {
nodes[index].Insert(objects.Remove(i));
}
else {
i++;
}
}
}
}
The insert method is where everything comes together. The method first determines whether the node has any child nodes and tries to add the object there. If there are no child nodes or the object doesn’t fit in a child node, it adds the object to the parent node.
Once the object is added, it determines whether the node needs to split by checking if the current number of objects exceeds the max allowed objects. Splitting will cause the node to insert any object that can fit in a child node to be added to the child node; otherwise the object will stay in the parent node.
/*
* Return all objects that could collide with the given object (recursive)
*/
public List<myGameObject> Retrieve(List<myGameObject> returnObjects, Rectangle pRect) {
int index = GetIndex(pRect);
if (index != -1 && nodes[0] != null) {
nodes[index].Retrieve(returnObjects, pRect);
}
returnObjects.AddRange(objects);
return returnObjects;
}
The final method of the quadtree is the retrieve method. It returns all objects in all nodes that the given object could potentially collide with. This method is what helps to reduce the number of pairs to check collision against.
Using This for 2D Collision Detection
Now that we have a fully functional quadtree, it’s time to use it to help reduce the checks needed for collision detection.
In a typical game, you’ll start by creating the quadtree and passing the bounds of the screen.
Quadtree quad = new Quadtree(0, new Rectangle(0,0,600,600));
At every frame, you’ll insert all objects into the quadtree by first clearing the quadtree then using the insert method for every object.
quad.Clear();
for (int i = 0; i < allObjects.Count; i++) {
quad.Insert(allObjects[i]);
}
Once all objects have been inserted, you’ll go through each object and retrieve a list of objects it could possibly collide with. You'll then check for collisions between each object in the list and the initial object, using a collision detection algorithm.
List<myGameObject> returnObjects = new List<myGameObject>();
for (int i = 0; i < allObjects.Count; i++) {
returnObjects.clear();
quad.Retrieve(returnObjects, objects[i]);
for (int x = 0; x < returnObjects.Count; x++) {
// Run collision detection algorithm between objects
// i.e. your Rectangle.IntersectsWith(x)
}
}
Note: Collision detection algorithms are beyond the scope of this tutorial. See this article for an example.
Conclusion
Collision detection can be an expensive operation and can slow down the performance of your game. Quadtrees are one way you can help speed up collision detection and keep your game running at top speeds.
