Yet Another Quad Tree Tutorial

There was nothing to show for Screenshot Saturday this week, but that doesn't mean there hasn't been any progress! I spent the weekend writing a quad-tree implementation and integrating it into the existing engine. It was not a very hard process, and there are already dozens of tutorials available online for this, but this guide may still come in handy for someone.

How Do Quad Trees Work

You may be familiar with a binary tree. Essentially there's a "root" structure (known as a "node") that branches out into two nodes (binary = two). Then, each of these nodes splits into two of their own. This continues as long as necessary. The nodes that aren't split are called "leaf" nodes.
Quad trees work exactly the same way, except the nodes are split into four parts rather than two. This is useful for video games because the screen is a rectangle, and can thus easily be split into smaller subsequent rectangles. Here's a screenshot of a stress-test quad tree in progress:

The small, 8x8 quads represent particles with physics. Each quad you see can contain a maximum of 32 (an arbitrary value) particles before it automatically splits into 4 nodes. The tree cannot go more than 6 levels deep, though, because that would eventually cause a stack overflow due to the recursion inherent to quad trees.

You can see this live, in-action by downloading a demo here (pardon the dependencies, I used my old wrapper classes to write this). Hold keys to generate particles, or use the mouse to set them in certain locations. Right-click the mouse to test for a collision with the large blue quad. The result will show up in the console window as a 1 (true) or 0 (false). You can notice that the operation is performed incredibly quickly, even with an insane amount of particles on the screen. That is the power of a quad tree.

Note: If you get DLL errors, you may need to install the VC++ redistributable from here.

Nodes

At the core of a quad tree is each individual quad itself, called a node. This node should contain information about the collide-able objects it holds, its dimensions, its depth, its child nodes (if any), its parent node (if any). Here is a sample bare-bones quad tree node structure:

	#include <list>
	#include <cstdint>
	// A generic object class (supporting collision) that is within the nodes.
	// See here: https://github.com/Ruskiy69/IronClad/blob/master/Source/include/Entity/RigidBody.hpp
	// For a real definition of the objects I use.
	class CQuadTree;
	class CEntity;
	// This is a rectangle representation containing x, y position, and
	// w, h dimensions. Something barebones could be this:
	struct rect_t { float x, y; uint32_t w, h; };
	// The quad tree node.
	struct QTNode
	{
	QTNode* pParent;
	QTNode** pChildren;
	rect_t Rect;
	uint16_t depth;
	std::list<CEntity*> nodeObjects;
	};
	// This defines a BAREBONES entity class. This is nowhere
	// near complete, and has only the essential members
	// necessary for the quad tree to update it.
	class CEntity
	{
	public:
	CEntity() : pCurrentNode(nullptr), needs_update(false) {}
	// You should know how to do this :)
	bool CheckCollision(const rect_t& Other);
	// The class needs access to the private data members.
	friend class CQuadTree;
	private:
	QTNode* pCurrentNode;
	bool needs_update; // The entity should track if it has moved
	// since the last frame. For example, if
	// CEntity::Adjust() is called with non-zero values.
	float x, y;
	rect_t Dimensions;
	};

view raw QTreeNode.hpp hosted with ❤ by GitHub

This is the structure we'll be using in this tutorial. For a more full-featured node class, you can see the actual implementation I use in IronClad here.

Recursion

Quad trees rely heavily on recursion. If you want to insert an object into the tree, you have to check the root node for children, then check which child the object belongs in, and then repeat that for every child in the child until you reach the leaf node, which has no children. This is easily modeled with recursion. One of the issues that arises with this is a stack overflow, which happens when you are too nested in the tree. This is why a depth limit is necessary; I use a depth limit of 6.

The CQuadTree Class

This class will essentially act as a wrapper around a single node, the root node. It will also provide the recursive functions for insertion, deletion, and collision detection. Here is the class definition we will be using in this tutorial. For the sake of brevity and not splitting this into separate files per method, here is the entire class with explanations as comments within it. The implementation, though, will be split up into parts so I can explain each part in full.

	// See this here: https://gist.github.com/Ruskiy69/5257421
	#include "gists/QTreeNode.hpp"
	class CQuadTree
	{
	public:
	// Provide the starting dimensions to the root node.
	// This will likely be something like Window::GetWidth()
	// and Window::GetHeight() in a game.
	CQuadTree(const uint16_t w, const uint16_t h);
	// Inserts an object into the tree.
	// This will call RInsert() on the head.
	// It returns TRUE if it found a node to put it in.
	// The only time it would return false is if the pBody's
	// location is outside of the root node (e.g. offscreen).
	bool Insert(CEntity* pBody);
	// This will remove the pBody from the tree.
	inline bool Remove(obj::CRigidBody* pBody)
	{ return this->RRemove(pBody, &m_Root); }
	// This checks if a pBody collides with any object (other than itself)
	// in the tree. It returns the object it collided with (or NULL if none).
	inline CEntity* Collides(const CEntity* pBody) const
	{ return this->RCollides(pBody, &m_Root); }
	// Updates the objects to see if they have moved.
	// This requires that the object have a private "needs_update" value
	// and contains the QTNode* it belongs to.
	// See here: https://github.com/Ruskiy69/IronClad/blob/master/Source/include/IronClad/Entity/RigidBody.hpp
	// For a real definition of the objects I use.
	void Update();
	private:
	// Maximum number of objects in a node before splitting is necessary.
	static const uint8_t QT_MAX_OBJECTS = 32;
	// Maximum tree depth. If this is reached all subsequent object adds to
	// this node will override the QT_MAX_OBJECTS value.
	static const uint8_t QT_MAX_DEPTH = 6;
	// Actual recursive implementation of the Insert() method.
	bool RInsert(CEntity* pBody, QTNode* pStart);
	// Actual recursive implementation of the Remove() method.
	bool RRemove(CEntity* pBody, QTNode* pStart);
	CEntity* RCollides(const CEntity* pBody,
	const QTNode* pStart) const;
	// Splits a node into 4 child nodes.
	void Split(QTNode* pNode);
	// The first node, encompassing all of the others.
	QTNode m_Root;
	// All of the objects in this tree.
	std::vector<CEntity*> mp_allBodies;
	};

view raw QuadTree.hpp hosted with ❤ by GitHub

Step 1: Splitting

The primary appeal of a quad tree is the ability to split into sub-nodes as needed, so this needs to be done first, for insertion to work properly. The process looks complicated, but is actually fairly simple. All nodes have a QTNode** member, which is a pointer to QTNode*. This is used to create an array of 4 QTNode*'s, each of which is then used to create a new QTNode. It's much cleaner to use an std::vector<QTNode*>, but for simplicity sake we'll do this.
So, after we've created the nodes, we set some default parameters (depth, children, etc) then give each one its respective dimensions, based on the parent node. The position is offset properly, width and height are divided in half, then made 1 pixel larger than usual to account for integer division errors that occur as depth increases. Each child node then gets the objects from the parent node that belong to it.
Comments in the code should further explain what's going on:

	void CQuadTree::Split(QTNode* pNode)
	{
	// Children already exist? This shouldn't happen.
	if(pNode->pChildren != nullptr)
	{
	// Delete the actual nodes.
	for(size_t i = 0; i < 4; ++i) delete pNode->pChildren[i];
	// Then delete the pointer array to the nodes.
	delete[] pNode->pChildren;
	}
	// Array of pointers (16 bytes).
	pNode->pChildren = new QTNode*[4];
	// Starting position of the node, so we can adjust as
	// necessary for the split.
	float x = pNode->Rect.x;
	float y = pNode->Rect.y;
	// Iterate over each child.
	for(size_t i = 0; i < 4; ++i)
	{
	pNode->pChildren[i] = new QTNode; // Actually make the new node.
	pNode->pChildren[i]->pChildren = nullptr; // No children
	pNode->pChildren[i]->pParent = pNode; // Assign parent node
	pNode->pChildren[i]->Rect = rect_t(pNode->Rect.x,
	pNode->Rect.y,
	pNode->Rect.w,
	pNode->Rect.h); // Give it the parent
	pNode->pChildren[i]->depth = pNode->depth + 1; // Depth is one lower level
	// Rect should be half size. The w++ and h++ parts are because
	// as the nodes get smaller, they may gain an odd value (like
	// 800/2/2/2/2/2 = 25) and the next split will be off-by-one due
	// to integer division. Then, a failure to insert an object may occur
	// because it doesn't fit in a node due to the spacing. Thus we compensate
	// by making the node 1x1 bigger than it needs to be.
	pNode->pChildren[i]->Rect.w /= 2; pNode->pChildren[i]->Rect.w++;
	pNode->pChildren[i]->Rect.h /= 2; pNode->pChildren[i]->Rect.h++;
	// Assign position of the node.
	pNode->pChildren[i]->Rect.x = x;
	pNode->pChildren[i]->Rect.y = y;
	// Add the objects from the parent node to the current child, if
	// they belong there.
	for(auto j = pNode->nodeObjects.begin();
	j != pNode->nodeObjects.end(); )
	{
	if((*j)->DetectCollision(pNode->pChildren[i]->Rect))
	{
	pNode->pChildren[i]->nodeObjects.push_back(*j);
	j = pNode->nodeObjects.erase(j);
	}
	else
	{
	++j;
	}
	}
	// Adjust the offset (goes from left to middle)
	x += pNode->pChildren[i]->Rect.w;
	// If we've reached the end, start on the next row.
	// (goes from top-middle to middle-left)
	if(x >= pNode->Rect.x + pNode->Rect.w)
	{
	x = pNode->Rect.x;
	y += pNode->pChildren[i]->Rect.h;
	}
	}
	// The parent object list should already be empty, but
	// this is just in case.
	pNode->nodeObjects.clear();
	}

view raw QuadTreeSplit.hpp hosted with ❤ by GitHub

Step 2: Insertion

First and fore-most is the necessity of being able to insert objects into the quad tree.To do this, we first check to see if a node has any children. If it does, it checks to see if the object "fits" into any of the children, via collision detection on the node. On the child that it does fit into, the method calls itself, but using the child as the starting node (recursion!). If the node has no children, the object is added to the nodes list of objects, but only if there is space. If the node is full, it calls Split() on the node and then calls RInsert again, using itself as the starting node since it now has children.

That's the English explanation, and you're probably thinking "what." But let's take a look at the code.

	// The one used by the public, all it does is start
	// the recursive algorithm with the root.
	bool CQuadTree::Insert(CEntity* pEnt)
	{
	// If inserted, we want to add to the whole internal list of
	// objects, which is used later in CQuadTree::Update().
	if(this->RInsert(pBody, &m_Root))
	{
	mp_allBodies.push_back(pBody);
	return true;
	}
	return false;
	}
	// The real work-horse.
	bool CQuadTree::RInsert(CEntity* pEnt, QTNode* pStart)
	{
	if(pStart == nullptr) return false;
	// Leaf node.
	if(pStart->pChildren == nullptr)
	{
	// The node is full?
	if(pStart->nodeObjects.size() >= QT_MAX_OBJECTS)
	{
	// Can't split further, add anyway.
	if(pStart->depth >= QT_MAX_DEPTH)
	{
	pStart->nodeObjects.push_back(pEnt);
	// Assign the node to the entity, for CQuadTree::Update() later.
	pEnt->pCurrentNode = pStart;
	return true;
	}
	// We can split, so split and then recurse on self,
	// since now it's not a leaf node.
	else
	{
	this->Split(pStart);
	return this->RInsert(pEnt, pStart);
	}
	// Assign the node to the entity, for CQuadTree::Update() later.
	pEnt->pCurrentNode = pStart;
	return true;
	}
	// Assign the node to the entity,
	pEnt->pCurrentNode = pStart;
	pStart->nodeObjects.push_back(pEnt);
	pStart->is_full = (pStart->nodeObjects.size() > QT_MAX_OBJ);
	return true;
	}
	// Branch
	else
	{
	for(uint8_t i = 0; i < 4; ++i)
	{
	if(pEnt->DetectCollision(pStart->pChildren[i]->Rect))
	{
	return this->RInsert(pEnt, pStart->pChildren[i]);
	}
	}
	}
	// This shouldn't happen, unless called by Update().
	// If it does, though, we go up the tree to the root,
	// to find a node that we can fit in.
	// Return false if we've reached the root node and
	// still can't insert.
	return (pStart->pParent == nullptr) ? false :
	this->RInsert(pEnt, pStart->pParent);
	}

view raw QuadTreeInsert.cpp hosted with ❤ by GitHub

Step 3: Removal

Often times objects get destroyed, whether that be a particle whose time has expired, or an enemy tank that has blow up. In that case, we would want to remove this object from the quad tree, so collisions with it no longer occur (though not necessarily for a blown up tank, if it doesn't disappear, but that's another matter entirely). The algorithm basically follows the same pattern as insertion.

	bool CQuadTree::RRemove(CEntity* pEnt, QTNode* pStart)
	{
	// Leaf node?
	if(pStart->pChildren == nullptr)
	{
	// Iterate over the entities and remove a match (if any).
	for(auto i : pStart->nodeObjects)
	{
	// Is this the object we are looking for?
	if(*i == pEnt)
	{
	// Erase and break out.
	nodeObjects.erase(i);
	return true;
	}
	}
	// No match :(
	return false;
	}
	// Branch with children.
	else
	{
	// Recurse on all children.
	for(size_t i = 0; i < 4; ++i)
	{
	// Only break out if there was a match found, because if
	// we broke out regardless we wouldn't get to all the kids!
	if(this->RRemove(pBody, pStart->pChildren[i])) return true;
	}
	}
	// No match found ever.
	return false;
	}

view raw QuadTreeRemove.cpp hosted with ❤ by GitHub

Step 4: Collision Detection

Now we can finally implement the actual thing quad trees are used for, collision! Once again, this is done in a recursive fashion similar to that of RRemove() and RInsert().

	CEntity* CQuadTree::RCollides(const CEnity* pBody,
	const QTNode* pStart) const
	{
	// Is leaf?
	if(pStart->pChildren == nullptr)
	{
	// Iterate over each object in the node and check for
	// collision. We also compare the objects to make sure
	// we don't count a collision of an object with itself,
	// which would obviously make no sense.
	for(auto i = pStart->nodeObjects.cbegin();
	i != pStart->nodeObjects.cend(); ++i)
	{
	if((*i)->CheckCollision(pBody) && (*i) != pBody)
	return *i;
	}
	}
	else
	{
	// Iterate over children
	for(size_t i = 0; i < 4; ++i)
	{
	CEntity* pResult = this->RCollides(pBody, pStart->pChildren[i]);
	if(pResult != nullptr) return pResult;
	}
	}
	return nullptr;
	}

view raw QuadTreeCollides.cpp hosted with ❤ by GitHub

Step 5: Updating the Tree

Of course, objects aren't static. Most will move around, be it an enemy tracking the player, bullets flying, or simply the camera panning through the scene. Thus, it's necessary to update the quad tree as objects move. The simplest, and least efficient way, would be to just remove all of the objects, and then insert them again. A much more effective method would be to have the objects themselves keep track of whether or not they have moved since the last frame. In IronClad, this is done with the entity marking a flag (m_update) if CRigidBody::Move() is called with values that are different than the current position, or the m_Force vector before the CRigidBody::Update() call is non-zero. Then, in CQuadTree::Update(), the tree will RInsert() updated objects again by moving up the tree from the old node (CRigidBody::mp_CurrentNode).

A further optimization would be not only to update objects that have moved, but to check the likelier nodes first, rather than starting from the root again. This is done by calling RInsert() on the object with the starting node being the parent of the current node. For example, if a particle moves 5px per frame, and it's exited the current node, the likeliest place it would now be would be another one of the child nodes of the parent.

This is probably the slowest operation in the quad tree, due to the fact that as more objects move (and the farther they move from their original place), the more RInsert() calls have to be performed. I haven't tested this extensively, so I am not sure if a stack overflow could occur due to excessive recursion. It's likely that it won't, since each object needs 6 calls (QT_MAX_DEPTH) at the most to find a proper node, and will usually need just 1 call.

Here is the code, with further explanation:

	void CQuadTree::Update()
	{
	// Iterate over every object in the tree.
	// This is why we stored them locally in Insert()
	for(size_t i = 0; i < mp_allBodies.size(); ++i)
	{
	// Object has moved.
	if(mp_allBodies[i]->needs_update)
	{
	// Remove the reference to the object from its current node.
	// Many thanks to @LorenSchmidt for the catch.
	for(auto i = mp_allBodies[i]->pNode->nodeObjects.begin();
	i != mp_allBodies[i]->pNode->nodeObjects.end();
	/* no third part */)
	{
	if(*i == mp_allBodies[i])
	{
	i = mp_allBodies[i]->pNode->nodeObjects.erase(i);
	// If you can guarantee that you wont Insert() the same object
	// multiple times, you can "break;" out of the loop here.
	}
	else
	{
	++i;
	}
	}
	// RInsert() will keep trying to find a node by moving up the tree
	// until it hits the root node. It will return false if it doesn't
	// fit into the root, either, so that means the object has been moved
	// off-screen, or off-tree.
	this->RInsert(mp_allBodies[i], mp_allBodies[i]->pNode->mp_Parent);
	}
	}
	}

view raw QuadTreeUpdate.cpp hosted with ❤ by GitHub

Using the Quad Tree

Now that we've implemented the quad tree and all of it's functions, it's very easy and simple to use efficiently. For example, if you are loading a level, it might look something like this:

CQuadTree QT;
CLevel Level1("Level1.dat");
const std::vector<CEntity*>& objs = Level1.GetPhysicalObjects();
for(size_t i = 0; i < objs.size(); ++i)
    QT.Insert(objs[i]);

Later, if you wanted to, for example, not allow the player to move if he's colliding with any objects in the level, you could just do


CEntity* pResult = QT.Collides(Player);
if(pResult == nullptr) Player.Move(requested_position);

Simple as that!
You don't necessarily need a single quad tree for the entire game world, either. You could have a separate one containing level objects, another containing enemies, another for particles, etc. That way it'd be even more efficient in terms of what you are trying to test collision for.

That's all for this tutorial, feel free to include comments and questions below! If you'd like to check out the official implementation of a quad tree in IronClad you can check out the full header here and the source code here.