A quadtree is a tree data structure in which each node has either zero or four children nodes. If the number of data elements assigned to a leaf node exceeds a configured limit, then the node is split into four equal quadrant nodes.
Given that each node in a quadtree has boundaries associated with it, this makes them ideal containers for holding and querying for spatially-related data. Their use is most prominent in collision detection systems employed by 2D games.
Being engaged in game developmen t as of late, I eventually needed to implement a quadtree of my own within the Bad Echo Game Framework that would work with a collision detection system running on MonoGame.
This article showcases what I came up with: a quadtree in C# running on .NET 7.
Some Basic Collision Mechanics
The previously linked Wikipedia article should adequately educate the reader on the general characteristics of quadtrees; however, I thought I’d go a bit into why we’re interested in their use regarding collision detection.
With MonoGame, the Update method is going to be called for every frame that a particular entity or sprite is being drawn. This is typically where changes in movement, among other things, are handled.
Therefore, it is the perfect place to check if our entity is colliding with any other collidable object.
Collision Detection Needs to Be Fast
Determining whether two entities collide is simple: take their bounding boxes (typically rectangular) and see if they intersect.
The problem is that there may be many collidable objects on the screen, and we must check each one against all the others for collisions. Furthermore, this needs to happen upon every new frame drawn.
This occurs in a sensitive area of code that can affect our game’s performance if we aren’t careful. Therefore, it’s imperative that our collision detection method be very fast.
The Slow Way: Collision Detection by Brute Force
The most straightforward way to check for collisions is, for each collidable object updated, iterate through a list of all other collidable objects and check whether their bounding rectangles intersect with said object’s bounding rectangle.
Iterating through a list of collidable objects for a single item has a time complexity of 
, which is “fine” by itself.
However, because we need to do this for every collidable object on the screen, we end up with a collision detection system operating at a time complexity of 
and needing to be run every time a frame is rendered.
That’s an expensive operation that could start affecting the game experience as the number of items on the screen increases. A collision detection operation that has a quadratic time complexity is pretty unacceptable.
The Better Way: Quadtree!
Because the data in a quadtree is stored spatially, it allows us to perform our collision queries on a much more refined subset of data.
Each node in a quadtree occupies a portion of a wider rectangular region encompassed by the quadtree as a whole. Items assigned to the quadtree will be grouped and stored according to where they exist spatially.
If I want to check if anything is colliding with an object located in the northwesterly part of the screen, it becomes trivial, during collision detection, to isolate items only located in that area.
Searching for collidable objects for a single item using a quadtree has a time complexity of 
.
More importantly, doing this for every collidable object on the screen gives us a total time complexity of only 
.
This is a much better time complexity, one that is actually viable for where we need to run the code.
Implementing the Quadtree in C#
I’ll go over how all the parts for the quadtree work in C#, show some sample usage, and then provide the complete code at the end of this article.
Initialization and Configuration
There are several configuration parameters defined at the time of the quadtree’s initialization: its boundaries, bucket capacity, and maximum depth.
Constructor and Fields
private readonly List<ISpatialEntity> _elements = new();
private readonly int _bucketCapacity;
private readonly int _maxDepth;
private Quadtree? _upperLeft;
private Quadtree? _upperRight;
private Quadtree? _bottomLeft;
private Quadtree? _bottomRight;
/// <summary>
/// Initializes a new instance of the <see cref="Quadtree"/> class.
/// </summary>
/// <param name="bounds">
/// The bounding rectangle of the region that this quadtree's contents occupy.
/// </param>
/// <remarks>
/// This initializes the <see cref="Quadtree"/> instance with a default bucket capacity of
/// <c>32</c> and a default maximum node depth of <c>5</c>, which are reasonable general-purpose
/// values for these settings.
/// </remarks>
public Quadtree(RectangleF bounds)
: this(bounds, 32, 5)
{ }
/// <summary>
/// Initializes a new instance of the <see cref="Quadtree"/> class.
/// </summary>
/// <param name="bounds">
/// The bounding rectangle of the region that this quadtree's contents occupy.
/// </param>
/// <param name="bucketCapacity">
/// The maximum number of items allowed in this node before it gets quartered.
/// </param>
/// <param name="maxDepth">
/// The maximum number of levels of child nodes allowed across the entire quad tree.
/// </param>
public Quadtree(RectangleF bounds, int bucketCapacity, int maxDepth)
{
_bucketCapacity = bucketCapacity;
_maxDepth = maxDepth;
Bounds = bounds;
}
Bounds
The bounds are the rectangular region that the quadtree encompasses. At the root, this region will be the playable area on the screen. We quadrisect this region each time our quadtree splits.
They are defined using the RectangleF type: a custom value type I made that works with other XNA primitives. Its source can be viewed here.
Alternatively one could also use the RectangleF type found in the System.Drawing namespace.
Bucket Capacity
This is an optional parameter. It defines how many elements can be assigned to a particular node before we split it into quadrants.
While optional, this is an important parameter that may require fine-tuning to get the best out of a quadtree for a particular application. Having a capacity that’s too small or large can negatively impact performance.
Maximum Depth
This is another optional parameter, and one just as critical regarding performance.
The maximum depth specifies how many levels deep the tree can go before we prevent any further splitting. We’ll begin lose any performance gained from switching to a quadtree if this is too large.
Again, fine-tuning for the particular application is recommended.
Insertion
Inserting new elements into a quadtree involves finding the appropriate node, based on the element’s own bounds, and splitting the node if necessary.
As you will see below, we assign elements that fail to fit into a single child leaf node to the parent (split) node.
Some quadtree implementations forbid elements from being assigned to non-leaf nodes. However, I find this approach problematic when we account for elements which overlap multiple children.
To avoid assigning these elements to non-leaf nodes, we would need to assign them to multiple leaf nodes. This complicates matters when we need to perform operations such as removal, as it requires the maintenance of additional (parallel) lists of elements.
I consider that to be kind of a mess.
Insert Method
/// <summary>
/// Inserts the specified spatial element into the quadtree at the appropriate node.
/// </summary>
/// <param name="element">The spatial element to insert into the quadtree.</param>
public void Insert(ISpatialEntity element)
{
Require.NotNull(element, nameof(element));
if (!Bounds.Contains(element.Bounds))
throw new ArgumentException(Strings.ElementOutsideQuadtreeBounds, nameof(element));
// A node exceeding its allotted number of items will get split (if it hasn't been
// already) into four equal quadrants.
if (_elements.Count >= _bucketCapacity)
Split();
Quadtree? containingChild = GetContainingChild(element.Bounds);
if (containingChild != null)
{
containingChild.Insert(element);
}
else
{ // If no child was returned, then this is either a leaf node, or the element's boundaries
// overlap multiple children. Either way, the element gets assigned to this node.
_elements.Add(element);
}
}
The code explains itself fairly well. If we’re at maximum capacity, we engage in a split of the current node.
Following that, we insert the element into either the child node that completely contains it, or the current node.
If the element is getting added to the current node, then that means the current node is a leaf or that our element exceeds the bound of any one child node.
This method uses recursion, as that simplifies its writing a bit. It is also a fairly inexpensive operation, with the bulk of operations actually occurring during manipulation of the _elements List<ISpatialEntity>.
Splitting
If adding an element to a node is going to cause us to exceed our bucket capacity, then it is time to split it up.
Split Method
private void Split()
{ // If we're not a leaf node, then we're already split.
if (!IsLeaf)
return;
// Splitting is only allowed if it doesn't cause us to exceed our maximum depth.
if (Level + 1 > _maxDepth)
return;
_upperLeft = CreateChild(Bounds.Location);
_upperRight = CreateChild(new PointF(Bounds.Center.X, Bounds.Location.Y));
_bottomLeft = CreateChild(new PointF(Bounds.Location.X, Bounds.Center.Y));
_bottomRight = CreateChild(new PointF(Bounds.Center.X, Bounds.Center.Y));
var elements = _elements.ToList();
foreach (var element in elements)
{
Quadtree? containingChild = GetContainingChild(element.Bounds);
// An element is only moved if it completely fits into a child quadrant.
if (containingChild != null)
{
_elements.Remove(element);
containingChild.Insert(element);
}
}
}
Assuming we aren’t already a leaf node and splitting it won’t exceed our maximum depth, we initialize the child node quadrants and redistribute already-assigned elements to them.
Just like in our insertion method, any element that doesn’t fit into a single child node will be left assigned to the current (now parent) node.
Removal
If an item inside the quadtree needs to be updated, maybe because its position has changed (and thus needs to be relocated within the quadtree), the first step that needs to occur is its removal from the tree.
For that, we can make use of our Remove method.
Remove Method
/// <summary>
/// Removes the specified spatial element from the quadtree and whichever node it's been assigned to.
/// </summary>
/// <param name="element">The spatial element to remove from the quadtree.</param>
/// <returns>True if <c>element</c> is successfully removed; otherwise, false.</returns>
public bool Remove(ISpatialEntity element)
{
Require.NotNull(element, nameof(element));
Quadtree? containingChild = GetContainingChild(element.Bounds);
// If no child was returned, then this is the leaf node (or potentially non-leaf node, if
// the element's boundaries overlap multiple children) containing the element.
bool removed = containingChild?.Remove(element) ?? _elements.Remove(element);
// If the total descendant element count is less than the bucket capacity, we ensure the node
// is in a non-split state.
if (removed && CountElements() <= _bucketCapacity)
Merge();
return removed;
}
This is similar to the Insert method, except we’re removing an element from the tree as opposed to adding one.
This also happens to be the perfect place in our code to engage in a little bit of “tree cleanup”. If removing the element causes the number of elements across the current node and all of its descendants to fall within our bucket capacity, we can engage in a merge operation.
Failure to maintain our tree like this as items move around will eventually result in our quadtree having many pockets of empty and useless leaf (and even non-leaf) nodes.
Merging
A merge operation is essentially the opposite of a split operation.
Merge Method
private void Merge()
{ // If we're a leaf node, then there is nothing to merge.
if (IsLeaf)
return;
_elements.AddRange(_upperLeft._elements);
_elements.AddRange(_upperRight._elements);
_elements.AddRange(_bottomLeft._elements);
_elements.AddRange(_bottomRight._elements);
_upperLeft = _upperRight = _bottomLeft = _bottomRight = null;
}
We take all the elements assigned to our children and reassign them back to the current node before nuking the children into oblivion.
No need to do a deep traversal of elements here, as the merge operation should always occur only one level above any leaf node.
Finding Collisions
Here is the main star of the show. Given a spatial element, which comes equipped with a rectangular boundary, we want to return all elements in the tree that collide with it.
FindCollisions Method
/// <summary>
/// Looks for and returns all spatial elements that exist within this node and its children
/// whose bounds collide with the specified spatial element.
/// </summary>
/// <param name="element">The spatial element to find collisions for.</param>
/// <returns>All spatial elements that collide with <c>element</c>.</returns>
public IEnumerable<ISpatialEntity> FindCollisions(ISpatialEntity element)
{
Require.NotNull(element, nameof(element));
var nodes = new Queue<Quadtree>();
var collisions = new List<ISpatialEntity>();
nodes.Enqueue(this);
while (nodes.Count > 0)
{
var node = nodes.Dequeue();
if (!element.Bounds.Intersects(node.Bounds))
continue;
collisions.AddRange(node._elements.Where(e => e.Bounds.Intersects(element.Bounds)));
if (!node.IsLeaf)
{
if (element.Bounds.Intersects(node._upperLeft.Bounds))
nodes.Enqueue(node._upperLeft);
if (element.Bounds.Intersects(node._upperRight.Bounds))
nodes.Enqueue(node._upperRight);
if (element.Bounds.Intersects(node._bottomLeft.Bounds))
nodes.Enqueue(node._bottomLeft);
if (element.Bounds.Intersects(node._bottomRight.Bounds))
nodes.Enqueue(node._bottomRight);
}
}
return collisions;
}
We check if any elements at the current node intersect with the given element, and then perform the same checks on any child node that itself happens to intersect with said element.
We’re using iteration here, as opposed to recursion, since writing an iterative algorithm for the collision search is relatively simple and (more importantly) because it shaves off a significant amount of execution time when ran.
Example Use and Full Source
Using the quadtree to find collisions in the real world context is simple.
For each item found in a list of all collidable objects, we remove it from the quadtree, perform the collision check, and then add it back.
Removing the item prevents the item itself from being returned during the collision check, and adding it back will essentially update the item’s place inside the quadtree in the event that it moved.
Example Use Snippet
foreach (ISpatialEntity collidable in _collidables)
{
_quadtree.Remove(collidable);
IEnumerable<ISpatialEntity> collisions = _quadtree.FindCollisions(collidable);
// Do what you will with the detected collisions...
_quadtree.Add(collidable);
}
And that’s pretty much it!
For a full copy of the source code, you can always check out the latest version of it on the official Bad Echo source repository.
Happy collision detecting!