Quadtrees in Unreal Engine 4

To follow on from my previous post explaining Octrees in unreal Engine 4, it seemed fair to cover Quadtrees. This time we’ll have to cover the full implementation ourselves, so it’s going to be a much lengthier tutorial.

Why use quadtrees?

Quadtrees are used for spacial partitioning, we can plot elements in the world into quads, and provide performance benefits by only enabling physics on the elements which are in the same node as the player.

Physics on objects is computationally expensive, so the more we ccan divide up the world, the fewer objects we’re likely to be calculating physics on unecessarily.

So why would you use quadtrees over octrees? Quadtrees are typically more suited to 2D games, where we just need to look at the position of elements sat within a flat plane. However, there are certain scenarios where this is beneficial for a 3D game too. For example, if a player was walking through a desert, then a quadtree is perfect, because we typically don’t expect many objects to be floating above the players height with physics enabled.

Quadtree Diagram

Above there is a diagram of how quadtrees may work in the desert example. The root node is labelled 1, while our player sits in node 5 and 1. We can look at this diagram and say “The player is in node 1, and in child node 5 of node 1, this means it is not in child nodes 2, 3, and 4”. So from this we can see that the only close object that we should bother calculating physics for is the cactus, saving us from calculating physics on the flower, water and treasure chest unecessarily.

C++ Implementation

In an ideal world, you should do this with templated types and make this completely flexible to and adaptable to any class. I don’t have enough elements in my game to make this worth the time, if you’re really bothered, what you could do is make every element you add to the tree of type AActor and you’ll be to add as many actors as you like providing each class inherits from AActor.

Our quadtree is going to consist of two core classes, one for the quadtree container and one for the nodes. The container class will simply be called ‘Quadtree’, and the nodes class will be called ‘QuadtreeNode’.

Recursion

As we go through, you’ll notice this tutorial uses a whole load of recursion. Some of you may be worried about how many things we’re putting on the stack, but fret not, we’ll pas by reference where we can (to avoid copying and ending up with two instances of a variable sat on the stack), and we will be using pointers so the variables on the stack are fairly small, and not copying solid objects about.

Quadtree Header

First off, we need to define the class for the QuadtreeNode. We’re going to define a new constructor for it, and make the default constructor private so that users can’t define an instance of Quadtree without initialising it properly.

class NINJA_CLIMB_API Quadtree
{
private:
	Quadtree();
public:
	Quadtree(const int kDepth, FVector2D min, FVector2D max);
	~Quadtree();
};

Next step, we’ll need to define a couple more things for this class. Lets tart with private variables, define these at the bottom of the class.

private:
	// The top most node of our tree
	TSharedPtr<QuadtreeNode> RootNode;
       
        // The number of layers between top node and bottom
	int MaxDistance;

Now we can define the rest of our public definitions.

public:
    // Get a shared pointer to the node top most node of the quadtree
    TSharedPtr<QuadtreeNode> GetRootNode();

    // Add an element to the quadtree
    void AddElement(APlatformActor* platform);

    // Draw debug boxes around each node in the quadtree
    void DrawBoxes(UWorld* world);

    // Get the deepest node which holds a position
    TSharedPtr<QuadtreeNode> GetNode(FVector position);

    // Get the distance from the top to the bottom of the tree
    int GetMaxDistance() const;

    // Initialise generating platforms inside the quadtree
    void GeneratePlatforms(UWorld* world, const FVector2D maxDistanceBetweenPlatforms);

Finally (for the Quadtree class definition), we need to define some private methods that will be used for initialising the class.

private:
	// Create all nodes within the quadtree
	void InitialiseNodes(TSharedPtr<QuadtreeNode> parentNode, FVector2D min, FVector2D max);

	// Create a node in the quadtree
	TSharedPtr<QuadtreeNode> CreateNode(TSharedPtr<QuadtreeNode> parent, FVector2D min, FVector2D max);

That’s it for the class definition, you can find the completed Quadtree class definition below.

#pragma once

// Custom includes
#include "QuadtreeNode.h"
#include "SharedPointer.h"

#include "CoreMinimal.h"

class NINJA_CLIMB_API Quadtree
{
private:
	Quadtree();
public:
	Quadtree(const int kDepth, FVector2D min, FVector2D max);
	~Quadtree();

	TSharedPtr<QuadtreeNode> GetRootNode();

	void AddElement(APlatformActor* platform);

	void DrawBoxes(UWorld* world);

	TSharedPtr<QuadtreeNode> GetNode(FVector position);

	int GetMaxDistance() const;

	void GeneratePlatforms(UWorld* world, const FVector2D maxDistanceBetweenPlatforms);

private:
	void InitialiseNodes(TSharedPtr<QuadtreeNode> parentNode, FVector2D min, FVector2D max);

	TSharedPtr<QuadtreeNode> CreateNode(TSharedPtr<QuadtreeNode> parent, FVector2D min, FVector2D max);
private:
	// Root Node
	TSharedPtr<QuadtreeNode> RootNode;

	int MaxDistance;
};

Quadtree Implementation

Lets start with the simple bit, here’s the implementation for the constructors and destructor.

Quadtree::Quadtree() { /* Private, should never be called */ }

Quadtree::Quadtree(const int maxDistance, FVector2D min, FVector2D max)
{
	MaxDistance = maxDistance;
	RootNode = CreateNode(nullptr, min, max);
	RootNode->SetNodePosition(ENodePosition::Root);
	InitialiseNodes(RootNode, min, max);
}

Quadtree::~Quadtree() {  }

Next, lets move onto the getters. The GetNode function is a recursive function called on by the root node, which will in turn call each node, until it finds the deepest position which sits within a node. It’ll then pass the pointer to that node up the stack.

// Not const because we'll return a copy of RootNode and it will alter the shared pointer count
TSharedPtr<QuadtreeNode> Quadtree::GetRootNode() 
{ 
    return RootNode; 
}

TSharedPtr<QuadtreeNode> Quadtree::GetNode(FVector position)
{
	if (RootNode->PositionInsideNode(position))
	{
		return RootNode->GetNode(position);
	}
	return nullptr;
}

// Const as this implementation should never be able to change anything
int Quadtree::GetMaxDistance() const 
{ 
    return MaxDistance; 
}

Next lets define the AddPlatform actor. This function is going to instruct the root node of the tree to add the element, which will call recursively to find the correct node to add the element to.

void Quadtree::AddElement(APlatformActor* platform)
{
	RootNode->AddElement(platform);
}

Now we’ll implement the function which draws boxes around each node in the quadtree. Again, this’ll be recursive and we’ll just call upon the root node to call upon each of it’s children to draw the box around it.

void Quadtree::DrawBoxes(UWorld* world)
{
	RootNode->DrawBoxAroundNode(world, FColor().Blue);
}

Great! That’s the easy / boring bits out of the way, now lets implement the functions which actually set up the quadtree. Lets start with the generate platforms function. This is going to call the upon the root node which will recursively call each of it’s children until it hits the deepest node, and then in that child we will have a chance to generate the platform.

void Quadtree::GeneratePlatforms(UWorld* world, const FVector2D maxDistanceBetweenPlatforms)
{
	RootNode->GenerateElementInNode(world, maxDistanceBetweenPlatforms);
}

Now lets define the function which is called from the constructor which has the purpose of actually creating the nodes within our quadtree. It calculates what each boundary should be for each node, and creates it as a child node of the node. You guessed it, there’s recursion in here too so each node that’s created, also calls the function again until our quadtree has hit its depth.

void Quadtree::InitialiseNodes(TSharedPtr<QuadtreeNode> parentNode, FVector2D min, FVector2D max)
{
	// Bottom right node
	FVector2D brMin = min;
	FVector2D brMax = { max.X - ((max.X - min.X) / 2.0f), max.Y - ((max.Y - min.Y) / 2.0f) };
	TSharedPtr<QuadtreeNode> br = CreateNode(parentNode, brMin, brMax);
	br->SetNodePosition(ENodePosition::BottomRight);

	// Bottom left node
	FVector2D blMin = { max.X - ((max.X - min.X) / 2.0f), min.Y };
	FVector2D blMax = { max.X, min.Y + ((max.Y - min.Y) / 2.0f) };
	TSharedPtr<QuadtreeNode> bl = CreateNode(parentNode, blMin, blMax);
	bl->SetNodePosition(ENodePosition::BottomLeft);

	// Top right node
	FVector2D trMin = { min.X, max.Y - ((max.Y - min.Y) / 2.0f) };
	FVector2D trMax = { max.X - ((max.X - min.X) / 2.0f), max.Y };
	TSharedPtr<QuadtreeNode> tr = CreateNode(parentNode, trMin, trMax);
	tr->SetNodePosition(ENodePosition::TopRight);

	// Top left node
	FVector2D tlMin = { max.X - ((max.X - min.X) / 2.0f), max.Y - ((max.Y - min.Y) / 2.0f) };
	FVector2D tlMax = { max.X, max.Y };
	TSharedPtr<QuadtreeNode> tl = CreateNode(parentNode, tlMin, tlMax);
	tl->SetNodePosition(ENodePosition::TopLeft);

	if (bl->GetDistance() < MaxDistance &&
		br->GetDistance() < MaxDistance &&
		tl->GetDistance() < MaxDistance &&
		tr->GetDistance() < MaxDistance)
	{
		InitialiseNodes(br, brMin, brMax);
		InitialiseNodes(bl, blMin, blMax);
		InitialiseNodes(tr, trMin, trMax);
		InitialiseNodes(tl, tlMin, tlMax);
	}

}

Finally, we just need the function which actually allocates memory to a node, and sets the parent of that node.

TSharedPtr<QuadtreeNode> Quadtree::CreateNode(TSharedPtr<QuadtreeNode> parent, FVector2D min, FVector2D max)
{
	// Bottom left node
	TSharedPtr<QuadtreeNode> newNode = MakeShared<QuadtreeNode>();
	if (parent.IsValid())
	{
		parent->AddChildNode(newNode);
	}
	newNode->SetParentNode(TWeakPtr<QuadtreeNode>(parent));
	newNode->SetBoundingBox(min, max);
	return newNode;
}

The complete implementation of my class looks like this.

// Fill out your copyright notice in the Description page of Project Settings.

#include "Quadtree.h"

Quadtree::Quadtree()
{
	RootNode = nullptr;
}

Quadtree::Quadtree(const int maxDistance, FVector2D min, FVector2D max)
{
	MaxDistance = maxDistance;
	RootNode = CreateNode(nullptr, min, max);
	RootNode->SetNodePosition(ENodePosition::Root);
	InitialiseNodes(RootNode, min, max);
}

Quadtree::~Quadtree()
{

}

TSharedPtr<QuadtreeNode> Quadtree::GetRootNode()
{
	return RootNode;
}

void Quadtree::AddElement(APlatformActor* platform)
{
	RootNode->AddElement(platform);
}

void Quadtree::DrawBoxes(UWorld* world)
{
	RootNode->DrawBoxAroundNode(world, FColor().Blue);
}

TSharedPtr<QuadtreeNode> Quadtree::GetNode(FVector position)
{
	if (RootNode->PositionInsideNode(position))
	{
		return RootNode->GetNode(position);
	}

	return nullptr;
}

int Quadtree::GetMaxDistance() const
{
	return MaxDistance;
}

void Quadtree::GeneratePlatforms(UWorld* world, const FVector2D maxDistanceBetweenPlatforms)
{
	RootNode->GenerateElementInNode(world, maxDistanceBetweenPlatforms);
}

void Quadtree::InitialiseNodes(TSharedPtr<QuadtreeNode> parentNode, FVector2D min, FVector2D max)
{
	// Bottom right node
	FVector2D brMin = min;
	FVector2D brMax = { max.X - ((max.X - min.X) / 2.0f), max.Y - ((max.Y - min.Y) / 2.0f) };
	TSharedPtr<QuadtreeNode> br = CreateNode(parentNode, brMin, brMax);
	br->SetNodePosition(ENodePosition::BottomRight);

	// Bottom left node
	FVector2D blMin = { max.X - ((max.X - min.X) / 2.0f), min.Y };
	FVector2D blMax = { max.X, min.Y + ((max.Y - min.Y) / 2.0f) };
	TSharedPtr<QuadtreeNode> bl = CreateNode(parentNode, blMin, blMax);
	bl->SetNodePosition(ENodePosition::BottomLeft);

	// Top right node
	FVector2D trMin = { min.X, max.Y - ((max.Y - min.Y) / 2.0f) };
	FVector2D trMax = { max.X - ((max.X - min.X) / 2.0f), max.Y };
	TSharedPtr<QuadtreeNode> tr = CreateNode(parentNode, trMin, trMax);
	tr->SetNodePosition(ENodePosition::TopRight);

	// Top left node
	FVector2D tlMin = { max.X - ((max.X - min.X) / 2.0f), max.Y - ((max.Y - min.Y) / 2.0f) };
	FVector2D tlMax = { max.X, max.Y };
	TSharedPtr<QuadtreeNode> tl = CreateNode(parentNode, tlMin, tlMax);
	tl->SetNodePosition(ENodePosition::TopLeft);

	if (bl->GetDistance() < MaxDistance &&
		br->GetDistance() < MaxDistance &&
		tl->GetDistance() < MaxDistance &&
		tr->GetDistance() < MaxDistance)
	{
		InitialiseNodes(br, brMin, brMax);
		InitialiseNodes(bl, blMin, blMax);
		InitialiseNodes(tr, trMin, trMax);
		InitialiseNodes(tl, tlMin, tlMax);
	}

}

TSharedPtr<QuadtreeNode> Quadtree::CreateNode(TSharedPtr<QuadtreeNode> parent, FVector2D min, FVector2D max)
{
	// Bottom left node
	TSharedPtr<QuadtreeNode> newNode = MakeShared<QuadtreeNode>();
	if (parent.IsValid())
	{
		parent->AddChildNode(newNode);
	}
	newNode->SetParentNode(TWeakPtr<QuadtreeNode>(parent));
	newNode->SetBoundingBox(min, max);
	return newNode;
}

Happy days! That’s our container class done. Next we move onto the quadtree node. I hope you’re ready for a whole load more of recursion.

QuadtreeNode Header

The quadtree node represents a node in a graph, it will be contained by the QuadtreeContainer.

We’ll start off by defining a constructor, copy constructor and a destructor.

class NINJA_CLIMB_API QuadtreeNode
{
public:
	QuadtreeNode();
	QuadtreeNode(const QuadtreeNode& copy);
	~QuadtreeNode();
}

Next we have a whole load of public functions to define, you can read what each functions purpose is in the comment above the definition.

public:
	/** Set the bounding box for this node. */
	void SetBoundingBox(const FVector2D min, const FVector2D max);

	/** Get the bounding box for this node. */
	TSharedPtr<FBox2D> GetBoundingBox();

	/** Set the parent node for this node. */
	void SetParentNode(TWeakPtr<QuadtreeNode> parentNode);

	/** Get the parent node to this node. */
	TWeakPtr<QuadtreeNode> GetParentNode();

	/* Add a child node to this node. */
	void AddChildNode(TSharedPtr<QuadtreeNode> node);

	/** Get child nodes belonging to this node. */
	TArray<TSharedPtr<QuadtreeNode>> GetChildNodes();

	/** Add an element to this node. */
	void AddElement(APlatformActor* element);

	/** Get elements belonging to this node. */
	TArray<APlatformActor*> GetElements();

	/** Draw a debug box to outline where the box is. */
	void DrawBoxAroundNode(UWorld* world, FColor colour);

	/** Get the distance from the root node of the tree. */
	int GetDistance();

	/** Find if a given position is inside this node. */
	bool PositionInsideNode(FVector position);

	/** Get the node which contains a given position. */
	TSharedPtr<QuadtreeNode> GetNode(FVector position);

	/** Get all elements belonging to this node and any elements which are contained within it's children. */
	TArray<APlatformActor*> GetAllElements();

	/** Get a copy of the node position member variable. */
	ENodePosition GetNodePosition() const;

	/** Set the value of a node position member variable. */
	void SetNodePosition(ENodePosition position);

	/** Check if this node has any children nodes. */
	bool HasChildNodes() const;

	/** Check if this node has any elements. */
	bool HasElements() const;

	/** Determines wether or not a node in this element. */
	void GenerateElementInNode(UWorld* world, const FVector2D maxDistanceBetweenPlatforms);

Next we have a few private functions which will be called internally within the class

private:
	/** Get the root node of this quadtree. */
	TSharedPtr<QuadtreeNode> GetRootNode();

	/** Get the node which contains a given position. */
	TSharedPtr<QuadtreeNode> GetNodeContainingPosition(FVector2D position);

	/** Acquire the nearest platform to a position. */
	APlatformActor* GetNearestPlatform(FVector2D position);

Finally, we have the class member variables.

private:
	/** The bounding box for this node. */
	TSharedPtr<FBox2D> boundingBox;

	/** The parent node to this node */
	TWeakPtr<QuadtreeNode> parentNode;

	/** Elements held within this node. */
	TArray<APlatformActor*> elements;

	/** Child nodes held by this node. */
	TArray<TSharedPtr<QuadtreeNode>> childNodes;

	/** The position of this node relevant to it's parent. */
	ENodePosition NodePosition;

	/** The chance that there is to spawn an enemy on a node. */
	const float kChanceToSpawnPlatform = 0.25f;

At the top of our header, we’re going to define an enumerated type to keep track of the position which each child node is sat within the parent node. E.g. It is the lower left node.

enum NINJA_CLIMB_API ENodePosition
{
	BottomRight = 0,
	BottomLeft = 1,
	TopRight = 2,
	TopLeft = 3,
	Root = 4
};

All together, my class looks like this:

#pragma once

// Custom includes
#include "SharedPointer.h"
#include "WeakObjectPtr.h"
#include "Containers/Array.h"
#include "PlatformActor.h"

// Core includes
#include "CoreMinimal.h"

enum NINJA_CLIMB_API ENodePosition
{
	BottomRight = 0,
	BottomLeft = 1,
	TopRight = 2,
	TopLeft = 3,
	Root = 4
};

class NINJA_CLIMB_API QuadtreeNode
{
public:
	QuadtreeNode();
	QuadtreeNode(const QuadtreeNode& copy);
	~QuadtreeNode();

	/** Set the bounding box for this node. */
	void SetBoundingBox(const FVector2D min, const FVector2D max);

	/** Get the bounding box for this node. */
	TSharedPtr<FBox2D> GetBoundingBox();

	/** Set the parent node for this node. */
	void SetParentNode(TWeakPtr<QuadtreeNode> parentNode);

	/** Get the parent node to this node. */
	TWeakPtr<QuadtreeNode> GetParentNode();

	/* Add a child node to this node. */
	void AddChildNode(TSharedPtr<QuadtreeNode> node);

	/** Get child nodes belonging to this node. */
	TArray<TSharedPtr<QuadtreeNode>> GetChildNodes();

	/** Add an element to this node. */
	void AddElement(APlatformActor* element);

	/** Get elements belonging to this node. */
	TArray<APlatformActor*> GetElements();

	/** Draw a debug box to outline where the box is. */
	void DrawBoxAroundNode(UWorld* world, FColor colour);

	/** Get the distance from the root node of the tree. */
	int GetDistance();

	/** Find if a given position is inside this node. */
	bool PositionInsideNode(FVector position);

	/** Get the node which contains a given position. */
	TSharedPtr<QuadtreeNode> GetNode(FVector position);

	/** Get all elements belonging to this node and any elements which are contained within it's children. */
	TArray<APlatformActor*> GetAllElements();

	/** Get a copy of the node position member variable. */
	ENodePosition GetNodePosition() const;

	/** Set the value of a node position member variable. */
	void SetNodePosition(ENodePosition position);

	/** Check if this node has any children nodes. */
	bool HasChildNodes() const;

	/** Check if this node has any elements. */
	bool HasElements() const;

	/** Determines wether or not a node in this element. */
	void GenerateElementInNode(UWorld* world, const FVector2D maxDistanceBetweenPlatforms);
private:
	/** Get the root node of this quadtree. */
	TSharedPtr<QuadtreeNode> GetRootNode();

	/** Get the node which contains a given position. */
	TSharedPtr<QuadtreeNode> GetNodeContainingPosition(FVector2D position);

	/** Acquire the nearest platform to a position. */
	APlatformActor* GetNearestPlatform(FVector2D position);
private:
	/** The bounding box for this node. */
	TSharedPtr<FBox2D> boundingBox;

	/** The parent node to this node */
	TWeakPtr<QuadtreeNode> parentNode;

	/** Elements held within this node. */
	TArray<APlatformActor*> elements;

	/** Child nodes held by this node. */
	TArray<TSharedPtr<QuadtreeNode>> childNodes;

	/** The position of this node relevant to it's parent. */
	ENodePosition NodePosition;

	/** The chance that there is to spawn an enemy on a node. */
	const float kChanceToSpawnPlatform = 0.25f;
};

QuadtreeNode Implementation

You’ll need to start by including the following in your ‘.cpp’ file. These are the quadtree node class definition, debug helpers for drawing the box around the outline of the quadtree node, and a math library for absolute values (you may not need this depending on what you’re doing to determine if an actor should be spawned in a node).

#include "QuadtreeNode.h"
#include "DrawDebugHelpers.h"
#include "GenericPlatformMath.h"

Next we’ll implement our constructor, copy constructor, and destructor.

QuadtreeNode::QuadtreeNode()
{
}

/** Shallow copies a QuadtreeNode. */
QuadtreeNode::QuadtreeNode(const QuadtreeNode & copy)
{
	SetParentNode(copy.parentNode);
	boundingBox = copy.boundingBox;
	elements = copy.elements;
	childNodes = copy.childNodes;
}

QuadtreeNode::~QuadtreeNode()
{
}

Next our basic getters which should be fairly self explanitory.

TSharedPtr<FBox2D> QuadtreeNode::GetBoundingBox()
{
	return boundingBox;
}

TWeakPtr<QuadtreeNode> QuadtreeNode::GetParentNode()
{
	return parentNode;
}

TArray<TSharedPtr<QuadtreeNode>> QuadtreeNode::GetChildNodes()
{
	return childNodes;
}

TArray<APlatformActor*> QuadtreeNode::GetElements()
{
	return elements;
}

ENodePosition QuadtreeNode::GetNodePosition() const
{
	return NodePosition;
}

bool QuadtreeNode::HasChildNodes() const
{
	return childNodes.Num() > 0;
}

bool QuadtreeNode::HasElements() const
{
	return elements.Num() > 0;
}

Then we proceed to implement the basic setters which should also be fairly self explanitory.

void QuadtreeNode::SetBoundingBox(const FVector2D min, const FVector2D max)
{
	boundingBox = MakeShared<FBox2D>(min, max);
}

void QuadtreeNode::SetParentNode(TWeakPtr<QuadtreeNode> parentNode)
{
	this->parentNode = parentNode;
}

void QuadtreeNode::SetNodePosition(ENodePosition position)
{
	NodePosition = position;
}

Next we’ll implement adding an element to the tree. In this case, the element in our tree is a ‘platform’ which the player can jump on. And of course, we’ll make use of recursion to do this.

void QuadtreeNode::AddElement(APlatformActor* element)
{
	// Exlpore each child belonging to this node
	for (auto childNode : childNodes)
	{
		FVector2D position = { element->GetActorLocation().X, element->GetActorLocation().Z };
		// if the position lies within the bounding box of this child
		if (childNode->boundingBox->IsInside(position))
		{
			// If the child has children of it's own
			if (childNode->HasChildNodes())
			{
				// Explore their children nodes to get the deepest position in the tree
				childNode->AddElement(element);
				return;
			}
			// If this node has no children, we can't be any more accurate
			else
			{
				childNode->elements.Add(element);
				return;
			}
		}
	}

	// Wasn't inside a child node, probably on a boundary, must be in this node.
	elements.Add(element);
	return;
}

We’ll go on to implement drawing boxes around the node. This is a useful debugging tool to ensure that our quadtree sits where we expect it to in the world. This function is called from the quadtree container class.

void QuadtreeNode::DrawBoxAroundNode(UWorld * world, FColor colour)
{
	FVector centre = { boundingBox->GetCenter().X, 0.0f, boundingBox->GetCenter().Y };
	FVector extent = { boundingBox->GetExtent().X, 0.0f, boundingBox->GetExtent().Y };

	DrawDebugBox(world, centre, extent, colour);

	for (auto node : childNodes)
	{
		node->DrawBoxAroundNode(world, colour);
	}
}

We’ll also implement a getter, which calculates how far a node is from the top of the tree. This is required when we are creating the tree so we know how many layers we have created.

int QuadtreeNode::GetDistance()
{
	int i = 0;

	TWeakPtr<QuadtreeNode> parent = GetParentNode();
	while (parent.IsValid() && parent != nullptr)
	{
		i++;
		TSharedPtr<QuadtreeNode> pinnedObserver(parent.Pin());
		parent = pinnedObserver->GetParentNode();
	}

	return i;
}

Next we’ll implement our PositionInNode function, this accepts a position and tells the user if that position is located within this node. It’ll also use recursion to call upon this function for all children nodes.

bool QuadtreeNode::PositionInsideNode(FVector position)
{
	FVector2D pos2d = { position.X, position.Y };
	for (auto childNode : childNodes)
	{
		if (childNode->boundingBox->IsInside(pos2d))
		{
			return childNode->PositionInsideNode(position);
		}
	}

	if (boundingBox->IsInside(pos2d))
	{
		return true;
	}

	return false;
}

Next we need to look at GetNode. This isn’t a brilliant name, but the purpose is to accept a position, and return the deepest node that holds that piosition.

TSharedPtr<QuadtreeNode> QuadtreeNode::GetNode(FVector position)
{
	for (auto childNode : childNodes)
	{
		if (childNode->PositionInsideNode(position))
		{
			return childNode;
		}
	}

	return nullptr;
}

GetAllElements is called by a node to return any platforms that sit within this node, and it’s children nodes. It returns an array of platform actors.

TArray<APlatformActor*> QuadtreeNode::GetAllElements()
{
	TArray<APlatformActor*> result;

	for (auto childNode : GetChildNodes())
	{
		result.Append(childNode->GetAllElements());
	}

	result.Append(elements);

	return result;
}

Now we have a pretty large function, which serves the purpose of deciding whether to create an actor in this node. It should be called by the root node which will recursively call upon children nodes, and determine whether it is an eligible node to spawn a platform in. Most of this is specific to my game, so be sure to adapt it to make it work for you.

void QuadtreeNode::GenerateElementInNode(UWorld * world, const FVector2D maxDistanceBetweenPlatforms)
{

	if (HasChildNodes())
	{
		for (auto child : childNodes)
		{
			child->GenerateElementInNode(world, maxDistanceBetweenPlatforms);
		}
	}
	else
	{
		TUniquePtr<FGenericPlatformMath> genericMaths(MakeUnique<FGenericPlatformMath>());
		if (genericMaths.IsValid())
		{
			const float distanceBetweenNodes = genericMaths->Abs(boundingBox->Max.X - boundingBox->Min.X);

			////////////////////////////
			// Check if any nodes exist nearby
			////////////////////////////

			TSharedPtr<QuadtreeNode> rootNode = GetRootNode();
			if (rootNode.IsValid())
			{
				// North
				FVector2D northPos = boundingBox->GetCenter();
				northPos.Y += distanceBetweenNodes;
				TSharedPtr<QuadtreeNode> northNode = rootNode->GetNodeContainingPosition(northPos);
				if (northNode.IsValid())
				{
					if (northNode->GetElements().Num() > 0)
					{
						return;
					}
				}

				// South
				FVector2D southPos = boundingBox->GetCenter();
				southPos.Y -= distanceBetweenNodes;

				TSharedPtr<QuadtreeNode> southNode = rootNode->GetNodeContainingPosition(southPos);
				if (southNode.IsValid())
				{
					if (southNode->GetElements().Num() > 0)
					{
						return;
					}
				}

				// East
				FVector2D eastPos = boundingBox->GetCenter();
				eastPos.X -= distanceBetweenNodes;

				TSharedPtr<QuadtreeNode> eastNode = rootNode->GetNodeContainingPosition(eastPos);
				if (eastNode.IsValid())
				{
					if (eastNode->GetElements().Num() > 0)
					{
						return;
					}
				}

				// West
				FVector2D westPos = boundingBox->GetCenter();
				westPos.X += distanceBetweenNodes;

				TSharedPtr<QuadtreeNode> westNode = rootNode->GetNodeContainingPosition(westPos);
				if (westNode.IsValid())
				{
					if (westNode->GetElements().Num() > 0)
					{
						return;
					}
				}

				////////////////////////////////
				// No nodes exist nearby, create away!
				///////////////////////////////
				APlatformActor* nearestPlatform = GetNearestPlatform(boundingBox->GetCenter());
				FVector2D nearestPlatformPos = FVector2D::ZeroVector;

				if (nearestPlatform != nullptr)
				{
					nearestPlatformPos = { nearestPlatform->GetActorLocation().X, nearestPlatform->GetActorLocation().Z };
				}

				float xDiff = genericMaths->Abs(nearestPlatformPos.X - boundingBox->GetCenter().X);
				float zDiff = genericMaths->Abs(boundingBox->GetCenter().Y - nearestPlatformPos.Y);

				if (FMath::FRandRange(0.0f, 1.0f) <= kChanceToSpawnPlatform ||
					(xDiff > maxDistanceBetweenPlatforms.X && 
						zDiff > maxDistanceBetweenPlatforms.Y))
				{	
					// Spawn enemy and enemy platform
					if (FMath::FRandRange(0.0f, 1.0f) <= kChanceToSpawnEnemy)
					{
						APlatformActor* platformActor = world->SpawnActor<APlatformActor>(APlatformActor::StaticClass());
						FVector2D location = boundingBox->GetCenter();
						platformActor->SetActorLocation(FVector(location.X, -100.0f, location.Y));
						platformActor->SetActorScale3D({ 5.0f, 2.0f, 0.25f });
						rootNode->AddElement(platformActor);
					}
					// Spawn normal platform
					else
					{
						APlatformActor* platformActor = world->SpawnActor<APlatformActor>(APlatformActor::StaticClass());
						FVector2D location = boundingBox->GetCenter();

						platformActor->SetActorLocation(FVector(location.X, -100.0f, location.Y));
						rootNode->AddElement(platformActor);
					}
				}
			}
		}
	}
}

Next we need a function to get the root node, this should climb the heirarchy of the graph til it hits the top most node.

TSharedPtr<QuadtreeNode> QuadtreeNode::GetRootNode()
{
	TSharedPtr<QuadtreeNode> parentNode = TSharedPtr<QuadtreeNode>(GetParentNode().Pin());

	// If the parent node isn't nullptr
	if (parentNode.IsValid())
	{
		// Grab an instance of the grandparent
		TSharedPtr<QuadtreeNode> parentOfParent = TSharedPtr<QuadtreeNode>(parentNode->GetParentNode().Pin());
		
		// If grandparent is not nullptr
		if (parentOfParent.IsValid())
		{
			// Recursively search the generation above
			return parentNode->GetRootNode();
		}
		else
		{
			// Found the root node, return the immediate parent to this node
			return parentNode;
		}
	}
	
	// Couldn't find a valid parent for whatever reason. Maybe only 2 layers?
	return nullptr;
}

Our GetNodeContainingPosition is used to check if a position sits within a node.

TSharedPtr<QuadtreeNode> QuadtreeNode::GetNodeContainingPosition(FVector2D position)
{
	// Exlpore each child belonging to this node
	for (auto childNode : childNodes)
	{
		// if the position lies within the bounding box of this child
		if (childNode->boundingBox->IsInside(position))
		{
			// If the child has children of it's own
			if (childNode->HasChildNodes())
			{
				// Explore their children nodes to get the deepest position in the tree
				TSharedPtr<QuadtreeNode> result = childNode->GetNodeContainingPosition(position);
				if (!result.IsValid())
				{
					// We got a null ptr, something didn't go quite right. Return the child node we know has something in it, maybe it was on the boundary.
					return childNode;
				}
				else
				{
					return result;
				}
			}
			// If this node has no children, we can't be any more accurate
			else
			{
				// Return the child which has no children yet still contains the 
				return childNode;
			}
		}
	}
	return nullptr;
}

The GetNearestPlatform implementation can be found here, however this is very specific to my implementation.

APlatformActor* QuadtreeNode::GetNearestPlatform(FVector2D position)
{
	TUniquePtr<FGenericPlatformMath> genericMaths(MakeUnique<FGenericPlatformMath>());

	APlatformActor* result = nullptr;

	// If the maths object we defined was valid
	if (genericMaths.IsValid())
	{
		// Explore each platform element
		for (auto platform : GetRootNode()->GetAllElements())
		{
			// If result hasn't been initialised yet, don't bother processing, just assume this is the closest platform
			if (result == nullptr)
			{
				result = platform;
			}
			else
			{
				// Calculate the difference in distance with the current platform
				FVector2D platformPos = { platform->GetActorLocation().X, platform->GetActorLocation().Z };
				const float x = genericMaths->Abs(position.X - platformPos.X);
				const float z = genericMaths->Abs(position.Y - platformPos.Y);
				const FVector2D platformDist = { x, z };

				// Calculate the difference in distance with the current result
				FVector2D resultPos = { result->GetActorLocation().X, result->GetActorLocation().Z };
				const float resultX = genericMaths->Abs(position.X - resultPos.X);
				const float resultZ = genericMaths->Abs(position.Y - resultPos.Y);
				const FVector2D resultDist = { resultX, resultZ };

				// If this platform isn't as far away as the current result
				if (platformDist < resultDist)
				{
					// Update the result
					result = platform;
				}
			}
		}
	}

	return result;
}

That’s it! You can find the full implementation of my node class below.

#include "QuadtreeNode.h"
#include "DrawDebugHelpers.h"
#include "GenericPlatformMath.h"

QuadtreeNode::QuadtreeNode()
{
}

/** Shallow copies a QuadtreeNode. */
QuadtreeNode::QuadtreeNode(const QuadtreeNode & copy)
{
	SetParentNode(copy.parentNode);
	boundingBox = copy.boundingBox;
	elements = copy.elements;
	childNodes = copy.childNodes;
}

QuadtreeNode::~QuadtreeNode()
{
}

void QuadtreeNode::SetBoundingBox(const FVector2D min, const FVector2D max)
{
	boundingBox = MakeShared<FBox2D>(min, max);
}

TSharedPtr<FBox2D> QuadtreeNode::GetBoundingBox()
{
	return boundingBox;
}

void QuadtreeNode::SetParentNode(TWeakPtr<QuadtreeNode> parentNode)
{
	this->parentNode = parentNode;
}

TWeakPtr<QuadtreeNode> QuadtreeNode::GetParentNode()
{
	return parentNode;
}

void QuadtreeNode::AddChildNode(TSharedPtr<QuadtreeNode> node)
{
	childNodes.Add(node);
}

TArray<TSharedPtr<QuadtreeNode>> QuadtreeNode::GetChildNodes()
{
	return childNodes;
}

void QuadtreeNode::AddElement(APlatformActor* element)
{
	// Exlpore each child belonging to this node
	for (auto childNode : childNodes)
	{
		FVector2D position = { element->GetActorLocation().X, element->GetActorLocation().Z };
		// if the position lies within the bounding box of this child
		if (childNode->boundingBox->IsInside(position))
		{
			// If the child has children of it's own
			if (childNode->HasChildNodes())
			{
				// Explore their children nodes to get the deepest position in the tree
				childNode->AddElement(element);
				return;
			}
			// If this node has no children, we can't be any more accurate
			else
			{
				childNode->elements.Add(element);
				return;
			}
		}
	}

	// Wasn't inside a child node, probably on a boundary, must be in this node.
	elements.Add(element);
	return;
}

TArray<APlatformActor*> QuadtreeNode::GetElements()
{
	return elements;
}

void QuadtreeNode::DrawBoxAroundNode(UWorld * world, FColor colour)
{
	FVector centre = { boundingBox->GetCenter().X, 0.0f, boundingBox->GetCenter().Y };
	FVector extent = { boundingBox->GetExtent().X, 0.0f, boundingBox->GetExtent().Y };

	DrawDebugBox(world, centre, extent, colour);

	for (auto node : childNodes)
	{
		node->DrawBoxAroundNode(world, colour);
	}
}

int QuadtreeNode::GetDistance()
{
	int i = 0;

	TWeakPtr<QuadtreeNode> parent = GetParentNode();
	while (parent.IsValid() && parent != nullptr)
	{
		i++;
		TSharedPtr<QuadtreeNode> pinnedObserver(parent.Pin());
		parent = pinnedObserver->GetParentNode();
	}

	return i;
}

bool QuadtreeNode::PositionInsideNode(FVector position)
{
	FVector2D pos2d = { position.X, position.Y };
	for (auto childNode : childNodes)
	{
		if (childNode->boundingBox->IsInside(pos2d))
		{
			return childNode->PositionInsideNode(position);
		}
	}

	if (boundingBox->IsInside(pos2d))
	{
		return true;
	}

	return false;
}

TSharedPtr<QuadtreeNode> QuadtreeNode::GetNode(FVector position)
{
	for (auto childNode : childNodes)
	{
		if (childNode->PositionInsideNode(position))
		{
			return childNode;
		}
	}

	return nullptr;
}

TArray<APlatformActor*> QuadtreeNode::GetAllElements()
{
	TArray<APlatformActor*> result;

	for (auto childNode : GetChildNodes())
	{
		result.Append(childNode->GetAllElements());
	}

	result.Append(elements);

	return result;
}

ENodePosition QuadtreeNode::GetNodePosition() const
{
	return NodePosition;
}

void QuadtreeNode::SetNodePosition(ENodePosition position)
{
	NodePosition = position;
}

bool QuadtreeNode::HasChildNodes() const
{
	return childNodes.Num() > 0;
}

bool QuadtreeNode::HasElements() const
{
	return elements.Num() > 0;
}

void QuadtreeNode::GenerateElementInNode(UWorld * world, const FVector2D maxDistanceBetweenPlatforms)
{

	if (HasChildNodes())
	{
		for (auto child : childNodes)
		{
			child->GenerateElementInNode(world, maxDistanceBetweenPlatforms);
		}
	}
	else
	{
		TUniquePtr<FGenericPlatformMath> genericMaths(MakeUnique<FGenericPlatformMath>());
		if (genericMaths.IsValid())
		{
			const float distanceBetweenNodes = genericMaths->Abs(boundingBox->Max.X - boundingBox->Min.X);

			////////////////////////////
			// Check if any nodes exist nearby
			////////////////////////////

			TSharedPtr<QuadtreeNode> rootNode = GetRootNode();
			if (rootNode.IsValid())
			{
				// North
				FVector2D northPos = boundingBox->GetCenter();
				northPos.Y += distanceBetweenNodes;
				TSharedPtr<QuadtreeNode> northNode = rootNode->GetNodeContainingPosition(northPos);
				if (northNode.IsValid())
				{
					if (northNode->GetElements().Num() > 0)
					{
						return;
					}
				}

				// South
				FVector2D southPos = boundingBox->GetCenter();
				southPos.Y -= distanceBetweenNodes;

				TSharedPtr<QuadtreeNode> southNode = rootNode->GetNodeContainingPosition(southPos);
				if (southNode.IsValid())
				{
					if (southNode->GetElements().Num() > 0)
					{
						return;
					}
				}

				// East
				FVector2D eastPos = boundingBox->GetCenter();
				eastPos.X -= distanceBetweenNodes;

				TSharedPtr<QuadtreeNode> eastNode = rootNode->GetNodeContainingPosition(eastPos);
				if (eastNode.IsValid())
				{
					if (eastNode->GetElements().Num() > 0)
					{
						return;
					}
				}

				// West
				FVector2D westPos = boundingBox->GetCenter();
				westPos.X += distanceBetweenNodes;

				TSharedPtr<QuadtreeNode> westNode = rootNode->GetNodeContainingPosition(westPos);
				if (westNode.IsValid())
				{
					if (westNode->GetElements().Num() > 0)
					{
						return;
					}
				}

				////////////////////////////////
				// No nodes exist nearby, create away!
				///////////////////////////////
				APlatformActor* nearestPlatform = GetNearestPlatform(boundingBox->GetCenter());
				FVector2D nearestPlatformPos = FVector2D::ZeroVector;

				if (nearestPlatform != nullptr)
				{
					nearestPlatformPos = { nearestPlatform->GetActorLocation().X, nearestPlatform->GetActorLocation().Z };
				}

				float xDiff = genericMaths->Abs(nearestPlatformPos.X - boundingBox->GetCenter().X);
				float zDiff = genericMaths->Abs(boundingBox->GetCenter().Y - nearestPlatformPos.Y);

				if (FMath::FRandRange(0.0f, 1.0f) <= kChanceToSpawnPlatform ||
					(xDiff > maxDistanceBetweenPlatforms.X && 
						zDiff > maxDistanceBetweenPlatforms.Y))
				{	
					// Spawn enemy and enemy platform
					if (FMath::FRandRange(0.0f, 1.0f) <= kChanceToSpawnEnemy)
					{
						APlatformActor* platformActor = world->SpawnActor<APlatformActor>(APlatformActor::StaticClass());
						FVector2D location = boundingBox->GetCenter();
						platformActor->SetActorLocation(FVector(location.X, -100.0f, location.Y));
						platformActor->SetActorScale3D({ 5.0f, 2.0f, 0.25f });
						rootNode->AddElement(platformActor);
					}
					// Spawn normal platform
					else
					{
						APlatformActor* platformActor = world->SpawnActor<APlatformActor>(APlatformActor::StaticClass());
						FVector2D location = boundingBox->GetCenter();

						platformActor->SetActorLocation(FVector(location.X, -100.0f, location.Y));
						rootNode->AddElement(platformActor);
					}
				}
			}
		}
	}
}

TSharedPtr<QuadtreeNode> QuadtreeNode::GetRootNode()
{
	TSharedPtr<QuadtreeNode> parentNode = TSharedPtr<QuadtreeNode>(GetParentNode().Pin());

	// If the parent node isn't nullptr
	if (parentNode.IsValid())
	{
		// Grab an instance of the grandparent
		TSharedPtr<QuadtreeNode> parentOfParent = TSharedPtr<QuadtreeNode>(parentNode->GetParentNode().Pin());
		
		// If grandparent is not nullptr
		if (parentOfParent.IsValid())
		{
			// Recursively search the generation above
			return parentNode->GetRootNode();
		}
		else
		{
			// Found the root node, return the immediate parent to this node
			return parentNode;
		}
	}
	
	// Couldn't find a valid parent for whatever reason. Maybe only 2 layers?
	return nullptr;
}

TSharedPtr<QuadtreeNode> QuadtreeNode::GetNodeContainingPosition(FVector2D position)
{
	// Exlpore each child belonging to this node
	for (auto childNode : childNodes)
	{
		// if the position lies within the bounding box of this child
		if (childNode->boundingBox->IsInside(position))
		{
			// If the child has children of it's own
			if (childNode->HasChildNodes())
			{
				// Explore their children nodes to get the deepest position in the tree
				TSharedPtr<QuadtreeNode> result = childNode->GetNodeContainingPosition(position);
				if (!result.IsValid())
				{
					// We got a null ptr, something didn't go quite right. Return the child node we know has something in it, maybe it was on the boundary.
					return childNode;
				}
				else
				{
					return result;
				}
			}
			// If this node has no children, we can't be any more accurate
			else
			{
				// Return the child which has no children yet still contains the 
				return childNode;
			}
		}
	}
	return nullptr;
}

APlatformActor* QuadtreeNode::GetNearestPlatform(FVector2D position)
{
	TUniquePtr<FGenericPlatformMath> genericMaths(MakeUnique<FGenericPlatformMath>());

	APlatformActor* result = nullptr;

	// If the maths object we defined was valid
	if (genericMaths.IsValid())
	{
		// Explore each platform element
		for (auto platform : GetRootNode()->GetAllElements())
		{
			// If result hasn't been initialised yet, don't bother processing, just assume this is the closest platform
			if (result == nullptr)
			{
				result = platform;
			}
			else
			{
				// Calculate the difference in distance with the current platform
				FVector2D platformPos = { platform->GetActorLocation().X, platform->GetActorLocation().Z };
				const float x = genericMaths->Abs(position.X - platformPos.X);
				const float z = genericMaths->Abs(position.Y - platformPos.Y);
				const FVector2D platformDist = { x, z };

				// Calculate the difference in distance with the current result
				FVector2D resultPos = { result->GetActorLocation().X, result->GetActorLocation().Z };
				const float resultX = genericMaths->Abs(position.X - resultPos.X);
				const float resultZ = genericMaths->Abs(position.Y - resultPos.Y);
				const FVector2D resultDist = { resultX, resultZ };

				// If this platform isn't as far away as the current result
				if (platformDist < resultDist)
				{
					// Update the result
					result = platform;
				}
			}
		}
	}

	return result;
}

Conclusion

If you made it all the way to here, thanks for sticking with me! I know this one was a long one, and a lot of it is rather specific to my own implementation, but hopefully it explains how to do some of the concepts in code. I don’t suspect anyone will find the full implementation useful to copy word for word, much better to take it and adapt it to your own project.

What I will note is that this was purely a learning exercise for me, and in fact much simpler to use a grid. So that’s what I’m off to change it to! Here’s an image of unpopulated quadtrees so you can see what they should look like.

Unpopulated quadtree