For a project I'm working on I had need of a QuadTree to give me quick and easy access to objects within a given bounds. I learned quite a bit working on it and thought it might be a good idea to share the code with the Bytes community.
To use it, create a new QuadTree and tell it what area it's going to cover. Then simply insert objects into it using the Insert method. You can use the Remove method to take objects out. On a removal, if a quad's children are empty, the children will be removed.
Some notes, in no particular order...
* This QuadTree holds any type, so long as that type inherits from IHasRectangle and implements the property the interface defines. This is so the QuadTree knows what the bounds of an object are.
* In this implementation, a quad will subdivide when it holds more than two objects. That said, a quad will only contain an object that it completely contains. If a quad's children cannot contain an object, it will live in the quad itself.
* The code is built using an XNA rectangle. It should be easy to modify the code to work with System.Drawing, or even a custom Rectangle object if desired. So long as the object provides the appropriate methods (Contains and Intersects), minimal work should be required to port.
* This code is offered freely, enjoy!
* In light of the above, note that it's not guaranteed to be bug free. I've tested it fairly extensively but it's quite possible I missed something. I'm definitely open to feedback, but please keep it constructive.
* I'm still doing a bit of work on this, but it's going to make it a little more XNA specific. This is the generic version of the object. I may post an update later.
Enough rambling... here's the code.
To use it, create a new QuadTree and tell it what area it's going to cover. Then simply insert objects into it using the Insert method. You can use the Remove method to take objects out. On a removal, if a quad's children are empty, the children will be removed.
Some notes, in no particular order...
* This QuadTree holds any type, so long as that type inherits from IHasRectangle and implements the property the interface defines. This is so the QuadTree knows what the bounds of an object are.
* In this implementation, a quad will subdivide when it holds more than two objects. That said, a quad will only contain an object that it completely contains. If a quad's children cannot contain an object, it will live in the quad itself.
* The code is built using an XNA rectangle. It should be easy to modify the code to work with System.Drawing, or even a custom Rectangle object if desired. So long as the object provides the appropriate methods (Contains and Intersects), minimal work should be required to port.
* This code is offered freely, enjoy!
* In light of the above, note that it's not guaranteed to be bug free. I've tested it fairly extensively but it's quite possible I missed something. I'm definitely open to feedback, but please keep it constructive.
* I'm still doing a bit of work on this, but it's going to make it a little more XNA specific. This is the generic version of the object. I may post an update later.
Enough rambling... here's the code.
Code:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.Xna.Framework;
namespace QuadTree
{
/// <summary>
/// Interface to define Rect, so that QuadTree knows how to store the object.
/// </summary>
public interface IHasRectangle
{
/// <summary>
/// The rectangle that defines the object's boundaries.
/// </summary>
Rectangle Rect { get; }
}
/// <summary>
/// A QuadTree Object that provides fast and efficient storage of objects in a world space.
/// </summary>
/// <typeparam name="T">Any object iheriting from IHasRect.</typeparam>
public class QuadTree<T> where T : IHasRectangle
{
#region Constants
// How many objects can exist in a QuadTree before it sub divides itself
private const int MAX_OBJECTS_PER_NODE = 2;
#endregion
#region Private Members
private List<T> m_objects = null; // The objects in this QuadTree
private Rectangle m_rect; // The area this QuadTree represents
private QuadTree<T> m_childTL = null; // Top Left Child
private QuadTree<T> m_childTR = null; // Top Right Child
private QuadTree<T> m_childBL = null; // Bottom Left Child
private QuadTree<T> m_childBR = null; // Bottom Right Child
#endregion
#region Public Properties
/// <summary>
/// The area this QuadTree represents.
/// </summary>
public Rectangle QuadRect { get { return m_rect; } }
/// <summary>
/// The top left child for this QuadTree
/// </summary>
public QuadTree<T> TopLeftChild { get { return m_childTL; } }
/// <summary>
/// The top right child for this QuadTree
/// </summary>
public QuadTree<T> TopRightChild { get { return m_childTR; } }
/// <summary>
/// The bottom left child for this QuadTree
/// </summary>
public QuadTree<T> BottomLeftChild { get { return m_childBL; } }
/// <summary>
/// The bottom right child for this QuadTree
/// </summary>
public QuadTree<T> BottomRightChild { get { return m_childBR; } }
/// <summary>
/// The objects contained in this QuadTree at it's level (ie, excludes children)
/// </summary>
public List<T> Objects { get { return m_objects; } }
/// <summary>
/// How many total objects are contained within this QuadTree (ie, includes children)
/// </summary>
public int Count { get { return this.ObjectCount(); } }
#endregion
#region Constructor
/// <summary>
/// Creates a QuadTree for the specified area.
/// </summary>
/// <param name="rect">The area this QuadTree object will encompass.</param>
public QuadTree(Rectangle rect)
{
m_rect = rect;
}
/// <summary>
/// Creates a QuadTree for the specified area.
/// </summary>
/// <param name="x">The top-left position of the area rectangle.</param>
/// <param name="y">The top-right position of the area reactangle.</param>
/// <param name="width">The width of the area rectangle.</param>
/// <param name="height">The height of the area rectangle.</param>
public QuadTree(int x, int y, int width, int height)
{
m_rect = new Rectangle(x, y, width, height);
}
#endregion
#region Private Members
/// <summary>
/// Add an item to the object list.
/// </summary>
/// <param name="item">The item to add.</param>
private void Add(T item)
{
if (m_objects == null)
m_objects = new List<T>();
m_objects.Add(item);
}
/// <summary>
/// Remove an item from the object list.
/// </summary>
/// <param name="item">The object to remove.</param>
private void Remove(T item)
{
if (m_objects != null && m_objects.Contains(item))
m_objects.Remove(item);
}
/// <summary>
/// Get the total for all objects in this QuadTree, including children.
/// </summary>
/// <returns>The number of objects contained within this QuadTree and its children.</returns>
private int ObjectCount()
{
int count = 0;
// Add the objects at this level
if (m_objects != null) count += m_objects.Count;
// Add the objects that are contained in the children
if (m_childTL != null)
{
count += m_childTL.ObjectCount();
count += m_childTR.ObjectCount();
count += m_childBL.ObjectCount();
count += m_childBR.ObjectCount();
}
return count;
}
/// <summary>
/// Subdivide this QuadTree and move it's children into the appropriate Quads where applicable.
/// </summary>
private void Subdivide()
{
// We've reached capacity, subdivide...
Point size = new Point(m_rect.Width / 2, m_rect.Height / 2);
Point mid = new Point(m_rect.X + size.X, m_rect.Y + size.Y);
m_childTL = new QuadTree<T>(new Rectangle(m_rect.Left, m_rect.Top, size.X, size.Y));
m_childTR = new QuadTree<T>(new Rectangle(mid.X, m_rect.Top, size.X, size.Y));
m_childBL = new QuadTree<T>(new Rectangle(m_rect.Left, mid.Y, size.X, size.Y));
m_childBR = new QuadTree<T>(new Rectangle(mid.X, mid.Y, size.X, size.Y));
// If they're completely contained by the quad, bump objects down
for (int i = 0; i < m_objects.Count; i++)
{
QuadTree<T> destTree = GetDestinationTree(m_objects[i]);
if (destTree != this)
{
// Insert to the appropriate tree, remove the object, and back up one in the loop
destTree.Insert(m_objects[i]);
Remove(m_objects[i]);
i--;
}
}
}
/// <summary>
/// Get the child Quad that would contain an object.
/// </summary>
/// <param name="item">The object to get a child for.</param>
/// <returns></returns>
private QuadTree<T> GetDestinationTree(T item)
{
// If a child can't contain an object, it will live in this Quad
QuadTree<T> destTree = this;
if (m_childTL.QuadRect.Contains(item.Rect))
{
destTree = m_childTL;
}
else if (m_childTR.QuadRect.Contains(item.Rect))
{
destTree = m_childTR;
}
else if (m_childBL.QuadRect.Contains(item.Rect))
{
destTree = m_childBL;
}
else if (m_childBR.QuadRect.Contains(item.Rect))
{
destTree = m_childBR;
}
return destTree;
}
#endregion
#region Public Methods
/// <summary>
/// Clears the QuadTree of all objects, including any objects living in its children.
/// </summary>
public void Clear()
{
// Clear out the children, if we have any
if (m_childTL != null)
{
m_childTL.Clear();
m_childTR.Clear();
m_childBL.Clear();
m_childBR.Clear();
}
// Clear any objects at this level
if (m_objects != null)
{
m_objects.Clear();
m_objects = null;
}
// Set the children to null
m_childTL = null;
m_childTR = null;
m_childBL = null;
m_childBR = null;
}
/// <summary>
/// Deletes an item from this QuadTree. If the object is removed causes this Quad to have no objects in its children, it's children will be removed as well.
/// </summary>
/// <param name="item">The item to remove.</param>
public void Delete(T item)
{
// If this level contains the object, remove it
bool objectRemoved = false;
if (m_objects != null && m_objects.Contains(item))
{
Remove(item);
objectRemoved = true;
}
// If we didn't find the object in this tree, try to delete from its children
if (m_childTL != null && !objectRemoved)
{
m_childTL.Delete(item);
m_childTR.Delete(item);
m_childBL.Delete(item);
m_childBR.Delete(item);
}
if (m_childTL != null)
{
// If all the children are empty, delete all the children
if (m_childTL.Count == 0 &&
m_childTR.Count == 0 &&
m_childBL.Count == 0 &&
m_childBR.Count == 0)
{
m_childTL = null;
m_childTR = null;
m_childBL = null;
m_childBR = null;
}
}
}
/// <summary>
/// Insert an item into this QuadTree object.
/// </summary>
/// <param name="item">The item to insert.</param>
public void Insert(T item)
{
// If this quad doesn't intersect the items rectangle, do nothing
if (!m_rect.Intersects(item.Rect))
return;
if (m_objects == null ||
(m_childTL == null && m_objects.Count + 1 <= MAX_OBJECTS_PER_NODE))
{
// If there's room to add the object, just add it
Add(item);
}
else
{
// No quads, create them and bump objects down where appropriate
if (m_childTL == null)
{
Subdivide();
}
// Find out which tree this object should go in and add it there
QuadTree<T> destTree = GetDestinationTree(item);
if (destTree == this)
{
Add(item);
}
else
{
destTree.Insert(item);
}
}
}
/// <summary>
/// Get the objects in this tree that intersect with the specified rectangle.
/// </summary>
/// <param name="rect">The rectangle to find objects in.</param>
/// <param name="results">A reference to a list that will be populated with the results.</param>
public void GetObjects(Rectangle rect, ref List<T> results)
{
// We can't do anything if the results list doesn't exist
if (results != null)
{
if (rect.Contains(m_rect))
{
// If the search area completely contains this quad, just get every object this quad and all it's children have
GetAllObjects(ref results);
}
else if (rect.Intersects(m_rect))
{
// Otherwise, if the quad isn't fully contained, only add objects that intersect with the search rectangle
if (m_objects != null)
{
for (int i = 0; i < m_objects.Count; i++)
{
if (rect.Intersects(m_objects[i].Rect))
{
results.Add(m_objects[i]);
}
}
}
// Get the objects for the search rectangle from the children
if (m_childTL != null)
{
m_childTL.GetObjects(rect, ref results);
m_childTR.GetObjects(rect, ref results);
m_childBL.GetObjects(rect, ref results);
m_childBR.GetObjects(rect, ref results);
}
}
}
}
/// <summary>
/// Get all objects in this Quad, and it's children.
/// </summary>
/// <param name="results">A reference to a list in which to store the objects.</param>
public void GetAllObjects(ref List<T> results)
{
// If this Quad has objects, add them
if (m_objects != null)
results.AddRange(m_objects);
// If we have children, get their objects too
if (m_childTL != null)
{
m_childTL.GetAllObjects(ref results);
m_childTR.GetAllObjects(ref results);
m_childBL.GetAllObjects(ref results);
m_childBR.GetAllObjects(ref results);
}
}
#endregion
}
}
Comment