Generic Loose Quadtree for Unity

Quadtree.cs

using System.Collections.Generic;
using UnityEngine;

public interface QuadtreeItem {
	Rect GetBounds();
}

public class QuadtreeNode<T> where T : QuadtreeItem {
	const int MAX_DEPTH = 10;

	// Child indexes.
	const int UNKNOWN_CHILD = -1;
	const int TOP_LEFT = 0;
	const int TOP_RIGHT = 1;
	const int BOTTOM_LEFT = 2;
	const int BOTTOM_RIGHT = 3;

	//////////////////////////////////////////////////

	public QuadtreeNode(QuadtreeNode<T> parent, Rect bounds, int depth) {
		this.parent = parent;
		this.bounds = bounds;
		this.depth = depth;
	}

	public void Insert(T value) {
		items.Add(value);
	}

	public void GetItems(List<T> results, Rect searchBounds) {
		results.AddRange(items);

		bool right =  bounds.center.x < searchBounds.max.x;
		bool left =   searchBounds.min.x < bounds.center.x;
		bool top =    bounds.center.y < searchBounds.max.y;
		bool bottom = searchBounds.min.y < bounds.center.y;

		if (top &&    right && children[TOP_RIGHT] != null)    { children[TOP_RIGHT].GetItems(results, bounds); }
		if (top &&    left &&  children[TOP_LEFT] != null)     { children[TOP_LEFT].GetItems(results, bounds); }
		if (bottom && right && children[BOTTOM_RIGHT] != null) { children[BOTTOM_RIGHT].GetItems(results, bounds); }
		if (bottom && left &&  children[BOTTOM_LEFT] != null)  { children[BOTTOM_LEFT].GetItems(results, bounds); }
	}

	public void Update() {
		for (int i = 0; i < 4; ++i) {
			if (children[i] != null) {
				children[i].Update();
			}
		}

		if (items.Count > 0) {
			Vector2 quarterSize = bounds.size / 4;

			for (int i = 0; i < items.Count; ++i) {
				var item = items[i];

				var itemBounds = item.GetBounds();
				int childIndex = GetChildIndexForBounds(itemBounds);
				if ((!ContainsPoint(itemBounds.center)) && parent != null) {
					items.RemoveAt(i);
					i--;
					parent.items.Add(item);
				} else {
					bool small = itemBounds.width / 2f < quarterSize.x && itemBounds.height / 2f < quarterSize.y;
					if (small && depth + 1 < MAX_DEPTH) {
						if (childIndex != UNKNOWN_CHILD) {
							items.RemoveAt(i);
							i--;
							// Recurse to the child.
							CreateChildIfNecessary(childIndex);
							children[childIndex].Insert(item);
						}
					}
				}
			}
		} else if (parent != null && children[0] == null && children[1] == null && children[2] == null && children[3] == null) {
			// Destroy this node, since there's no items.
			for (int i = 0; i < 4; ++i) {
				if (parent.children[i] == this) {
					parent.children[i] = null;
					break;
				}
			}
		}
	}

	public void Remove(T item) {
		items.Remove(item);
		for (int i = 0; i < 4; ++i) {
			if (children[i] != null) {
				children[i].Remove(item);
			}
		}
	}

	//////////////////////////////////////////////////

	readonly Rect bounds;
	readonly int depth;
	readonly List<T> items = new List<T>();

	readonly QuadtreeNode<T> parent;
	readonly QuadtreeNode<T>[] children = {null, null, null, null};

	//////////////////////////////////////////////////

	int GetChildIndexForBounds(Rect elementBounds) {
		if (depth + 1 >= MAX_DEPTH) {
			return UNKNOWN_CHILD;
		}

		bool right =  bounds.center.x     <= elementBounds.min.x;
		bool left =   elementBounds.max.x <= bounds.center.x;
		bool top =    bounds.center.y     <= elementBounds.min.y;
		bool bottom = elementBounds.max.y <= bounds.center.y;

		// If the bounds spans two quadrants, we don't have
		// a child index for that bounds.
		if ((left && right) || (top && bottom)) {
			return UNKNOWN_CHILD;
		}

		if (left) {
			if (top) { return TOP_LEFT; }
			if (bottom) { return BOTTOM_LEFT; }
		} else if (right) {
			if (top) { return TOP_RIGHT; }
			if (bottom) { return BOTTOM_RIGHT; }
		}
		return UNKNOWN_CHILD;
	}

	void CreateChildIfNecessary(int childIndex) {
		if (children[childIndex] == null) {
			Vector2 min;
			Vector2 max;

			switch (childIndex) {
			case TOP_LEFT:
				min = new Vector2(bounds.min.x, bounds.center.y);
				max = new Vector2(bounds.center.x, bounds.max.y);
				break;
			case TOP_RIGHT:
				min = new Vector2(bounds.center.x, bounds.center.y);
				max = new Vector2(bounds.max.x, bounds.max.y);
				break;
			case BOTTOM_LEFT:
				min = new Vector2(bounds.min.x, bounds.min.y);
				max = new Vector2(bounds.center.x, bounds.center.y);
				break;
			default:
				min = new Vector2(bounds.center.x, bounds.min.y);
				max = new Vector2(bounds.max.x, bounds.center.y);
				break;
			}

			children[childIndex] = new QuadtreeNode<T>(
				this,
				Rect.MinMaxRect(min.x, min.y, max.x, max.y),
				depth + 1);
		}
	}

	bool ContainsPoint(Vector2 position) {
		return
			bounds.min.x <= position.x &&
			position.x   <= bounds.max.x &&
			bounds.min.y <= position.y &&
			position.y   <= bounds.max.y;
	}
}

public class Quadtree<T> where T : QuadtreeItem {
	public Quadtree(Rect bounds) {
		head = new QuadtreeNode<T>(null, bounds, 0);
	}

	/// Call this whenever something in the quadtree moves
	public void Update() {
		head.Update();
	}

	public void Insert(T item) {
		head.Insert(item);
	}

	public void Remove(T item) {
		head.Remove(item);
	}

	/// Get all items potentially within a rect.
	public void Query(List<T> results, Rect searchBounds) {
		head.GetItems(results, searchBounds);
	}

	//////////////////////////////////////////////////

	QuadtreeNode<T> head;
}