Who doesn’t love trees? Who doesn’t love data? The tricky part is combining them together in a useful way. In this programming explanation / tutorial we’ll take a look at an extremely versatile and useful type of tree... no, not oak - Quad Trees!
Difficulty: Medium (Intermediate programming knowledge helpful, understanding of Unity and how its GameObject system works useful in the example scene)
A quad tree is a data structure made up of elements (commonly called nodes) that are each able to divide itself into 4 child nodes, recursively. Starting from a single root node, it is able to continually partition itself out into four smaller sections. This parent - child relationship is core to the structure of the tree.
Quad trees, like many data structures, are broadly applicable to many situations, from Level-of-Detail (LOD) models, to organizing complex related data, to even image compression algorithms!
This subdivision is (in theory) able to continue ad infinitum, but in a practical application I highly suggest you set an upper limit for how many generations can be spawned, lest you get stuck in infinite recursion. That’s a scary place to be.
Now that we’ve laid out how such a tree should work in theory, we can take a look at how it might be programmed and put into use. To give an example of how to set up a quad tree and how it might physically be represented, I’ve created an example scene in Unity.
To start with, naturally we will need a couple of classes. I’ve found it useful to make each quad (or node) into its own object, which the quad tree class then catalogues and operates on.
First, let’s look at the Quad class.
It contains the following fields:
- quadObject - The Unity GameObject associated with this quad. (may not be applicable to purely data focused or other implementations. Make a quad class that suits your own needs!)
- center - The Unity Vector3 position of this quad. (again, if using a less physical based implementation holding this information would not be necessary)
- generation - An integer representing how far down the tree this quad exists in. (useful for quick referencing where this quad exists and who its relatives are)
- limit - A reference to a high-level variable representing how many generations the quad tree may spawn.
- parent - A reference to the quad that spawned this quad. (the root node’s parent field will be null)
- children - A fixed-size array of quads containing references to its children.
And the following methods:
- Constructor - Accepts the necessary fields to populate newly created quads. In all cases except the root node, this method will be called directly from inside the parent quad.
- Subdivide - The method that allocates and creates each new child quad. The information provided to the children here can be specified on a per-child basis.
- GetDescendants - This method returns an array populated with all descendants from that node onward, following the branches of each child and each of their children.
Now, let’s look at the actual QuadTree class.
It has the following fields:
- nodes - A simple list containing each node. All of the parent - child information is contained within the nodes themselves, relieving the tree from having to keep track of the relationships.
- limit - The integer defining how many generations this tree may recursively produce.
And the following methods:
- Constructor - Simply takes in the limit integer.
- GenerateTree - The public method that kickstarts the quad tree generation from an external caller.
- AddRoot - A private method that declares and initializes the root node at index 0.
- AddGenerations - A private method that starts recursive generation of successive quad generations by subdividing the root node to start. Finally, it adds the entire descendant node tree to the list.
That’s all there is to it! This implementation contains a healthy mix of generic adaptable concepts with some specific to Unity (merely to spawn geometric Quads in-scene to visualize the arrangement of the tree.)
With a little extra tweaks and a proper MonoBehaviour script, the end result in Unity looks like this:
(A quad recursively divided from 1 to 8 generations)
All code from this example is open-source and available to be learned from or used. Hopefully someone finds this information valuable. It would be very easy to branch this project off into an octree or a binary tree from here, simply by reworking how many children are made and placed.
Possible Improvements:
- Improve performance!! This is by no means the most clean or efficient implementation of the concept, merely an introduction
- Allow for different generation limits per-node rather than globally set
- Make the entire quad tree class generic, for use with different data types