Overview
- Although in general most data structures used in programming don’t really have a viable use in game development, I’m going to cover the ones that have helped me in creating useful and efficient solutions in my code.
- For this first post I want to cover Quad trees mainly, but I’ll briefly go over binary trees to provide context as this is an abstract and somewhat difficult concept to grasp.
Binary trees
The basics
My personal go-to source for learning about data structures and algorithms is https://geeksforgeeks.org. They have a nice bunch of sources on binary trees here. In general, a binary tree can be thought of as a simple node. This node has a left and right child, which also happen to be nodes (and will also have left and right childs, which will also be nodes… 
). The concept is difficult to grasp at first, but it is a very useful and efficient way of containing and traversing through data. Think about it this way, if you have 3 items, you’ll need a binary tree with 2 layers to contain it. If you have 43 items, you’ll need 6 layers. And for any x amount of nodes, you’ll be able to store it in math.ceil(lg(x+1)) layers, where lg represents log base 2. So, trees become insanely efficient for large chunks of data. For a million nodes, it would take as many as a million loop iterations to find a specific one if they were stored in an array, but in a binary tree it won’t take more than 20 traversals! For our purposes, we’ll use a special type of a binary tree called a Binary Search Tree (BST), since we want our nodes to be sorted. Note: a traditional binary tree will not have any form of a “remove” function! It is simply a means of storing values and reading them all out in order. If you want to organize your data in such a way that you can always keep it in order and also add/remove elements at your will while maintaining that order, you’ll have to use priority queues, which I might make a tutorial on later.
The functions
For this case I’ll keep it simple and just have functions for inserting nodes and printing out values. When inserting a value, we’ll have to do a bit of traversing the tree to figure out where the node will go. Remember, we’re doing a binary search tree, so for every node we have to maintain the following: given their existence, the left child has to be less than its parent, and the right child has to be greater than its parent. For ordering our tree, a recursive approach will be best suited for our needs. Basically, if a node n has left child a and right child b, it must be true that a<n<b, right? Using this concept and the magic of recursion we’ll easily make a function that prints out our tree in order.
The code
With that, let’s set up the basics of our code:
function NewNode(value, identifier)
return {Value = value, Identifier = identifier}
end
local BinaryTree = {}
BinaryTree.__index = BinaryTree
function BinaryTree.new(node)
return setmetatable({Node = node}, BinaryTree)
endEasy enough. Now we have a simple object that we can instantiate and call functions on. Let’s tackle inserting, as that’s the hardest part:
We want to traverse through the tree until we run into a dead end (i.e. child we’re looking for is null). So, let’s maintain two local variables, current and parent. We loop through the tree until current is nil, and by using the parent variable we can place our node where current should have been.
function BinaryTree:Insert(node)
local parent = self
local current = self
while current do
parent = current
if node.Value < current.Node.Value then
current = current.Left
elseif node.Value > current.Node.Value then
current = current.Right
else
warn("Insert failed; duplicate node") return
end
end
if node.Value < parent.Node.Value then
parent.Left = BinaryTree.new(node)
else
parent.Right = BinaryTree.new(node)
end
endAll we do here is go left if our new value is less than the current node and go right if its greater. Once we hit a dead end we compare the node one last time to determine whether it should be on the left or the right, and create the connection accordingly.
NOTE: There is a much more efficient way to go about this! Instead of adding another level to your code by introducing nodes you could simply store the values and identifiers in the BinaryTree structure itself. The reason I’m going through this redundantly is to better outline the structure that will be used for our QuadTree, where it won’t be as manageable to maintain node properties for every tree as not every tree level might have node information tied to it.
Now that that’s out of the way, I’ll simply paste in the order code as it’s strikingly simple:
function BinaryTree:Order()
if self.Left then self.Left:Order() end
print(self.Node.Identifier)
if self.Right then self.Right:Order() end
endIt might seem too good to be true, but it works!
Here’s some driver code that’ll test out our functionality:
local Tree = BinaryTree.new(NewNode(30, "Adult"))
Tree:Insert(NewNode(16, "Teen"))
Tree:Insert(NewNode(60, "Elder"))
Tree:Insert(NewNode(45, "Old man"))
Tree:Insert(NewNode(130, "(Probably) dead guy"))
Tree:Insert(NewNode(3, "Baby"))
Tree:Insert(NewNode(7, "Kiddo"))
Tree:Order()
--output: Baby Kiddo Teen Adult Old man Elder (Probably) dead guyLook at that! Even though I just put all of those inputs in a random sloppy order, our BST kept them ordered! Imagine trying to do this with an array, with possibly thousands of values… Anyway, I digress.
That’s all I’ll write for binary trees. They have so much more potential and power all around software, but it’s not that useful in game development. However, now that we have a simple understanding of binary trees, let’s jump into their two dimensional analog: Quad trees!
Quad trees
The basics
As complex as binary trees might seem, they’re only one-dimensional. You can only go left and right. Left and right, however, is not enough for 3D. The good news is we can expand binary trees into 2 and 3 dimensions to handle all sorts of collisions! 3 dimensional trees are referred to as octrees and once again I won’t cover those here but might do so in another topic. For now, let’s look at quadtrees. Here’s a nice visual from wikipedia that explains how we might set up a quadtree:
Basically, we set up a huge square that we want to be our world space. Then, we can insert nodes by splitting a square into 4 equal squares in such a way that each quadrant only has 0 or 1 nodes. Note that while this quadtree implementation doesn’t split squares into unit sizes unless new nodes are added, and it continues to infinitely downsize quadrants to accomodate for as many nodes as possible, for our purposes we will maintain a unit size quadrant and quadtrees will only have node values if they meet that size, no higher or lower. Take this example of a dummy map:
For this example, we’ll divide this map into 20x20 units and insert each one as a node, and unlike binary trees we’ll also have a function to locate the closest node to a position. So, we’ll be able to use a quadtree to essentially check grid collisions. This is useful for many things, such as custom streaming systems. In this example, I’ll show how these grid collisions can be used to check when a player enters a new area and display a notification then, similar to what you might see in open world games.
The functions
This’ll be a bit more advanced than the traditional binary tree in that we’ll have both insert and search functions. Along with this we’ll have a simple helper function :Contains() as a safe check to make sure what we’re inserting or searching for is in the bounds of the quadtree. I’ll outline the API for our class so you can get a sense of everything that’ll have to be included:
QuadTree {
Rect Bounds
Node node
QuadTree TopLeft
QuadTree TopRight
QuadTree BotLeft
QuadTree BotRight
}
QuadTree QuadTree(Vector2 point1, Vector2 point2, Node node = nil)
void QuadTree:Insert(Node node)
Node QuadTree:Locate(Vector2 point)
boolean QuadTree:Contains(Vector2 point)Notice how each QuadTree can potentially have 4 other child trees. These trees will default to nil in the constructor. A tree will either be a node holder with values or it’ll be split into 4 smaller quadrants; in our cases it’ll never be both. Both our insert and locate functions will then have to rely on recursion; if we find the quadrant we want, we’ll place or return the node there, otherwise we’ll just call the same function on the correct child node. I’ll do less explaining here and in turn I’ll annotate the code so the step by step process is more clear.
The code
First off, basic constructor setup:
local UNIT_SIZE = 20 --The minimum side length of a quad subtree
function NewNode(pos, identifier)
return {Position = pos, Identifier = identifier}
end
local QuadTree = {}
QuadTree.__index = QuadTree
function QuadTree.new(point1, point2, node)
return setmetatable(
{
Bounds = Rect.new(point1, point2),
Node = node
}, QuadTree
)
endNote the UNIT_SIZE variable; this can be changed to your liking. If you wanted to create a custom 2d collision system, this would be much smaller (<1) and you’d configure this implementation to have a multi-bucket tree (i.e. more than 1 node per quadrant being possible). You’d also have to change up a lot of how the Locate function works. Just something that you can try if you have free time, a lot of cool things can be made with it.
Anyways back on topic, we should have a helper function to see if a point is actually in the bounds of our tree. We don’t want weird results because of bad inputs! In essence, we just check if vector2 values are greater than the minimums and lower than the maximums.
function QuadTree:Contains(point)
local bounds = self.Bounds
return bounds.Min.X <= point.X
and bounds.Min.Y <= point.Y
and bounds.Max.X >= point.X
and bounds.Max.Y >= point.Y
endSo how do we go about inserting? Well, this Contains function is actually similar to a big part of what will go into our recursive function: After doing a sanity check to make sure the node is in the tree’s bounds, we will split up our square into 4 smaller ones. The cool thing about this is that we’ll only have to define one more point. In fact, this is the case for any dimension of tree! Think about it, even with a cube if you placed a dot in the middle and then just connected the dots to center points of the faces, you could split the cube into 8. For our purposes, we’ll split the cube into 4, and use a similar approach to the Contains function to figure our what subdivision the node should go in. If that subdivision isn’t initialized yet, we’ll do so, and add the node!
function QuadTree:Insert(node)
if not self:Contains(node.Position) then
warn("Insert failed; node is not in quad bounds")
return
end
--We don't want to subdivide the quad any further; this serves as the 'base case' for our recursion
if self.Bounds.Height <= UNIT_SIZE and self.Bounds.Width <= UNIT_SIZE then
if self.Node then
warn("Insert failed; quad unit area is already occupied")
else
self.Node = node
return
end
end
--At this point, the node is in our quad bounds but we still have to allocate a unit slot for it
local centerPoint = (self.Bounds.Min + self.Bounds.Max)/2
local halfRight = Vector2.new(self.Bounds.Width/2,0)
local halfDown = Vector2.new(0,self.Bounds.Height/2)
--If we are on the left..
if node.Position.X <= centerPoint.X then
--Check if we are in the top left
if node.Position.Y <= centerPoint.Y then
if not self.TopLeft then
--Subdivide the quad if it hasn't been already
self.TopLeft = QuadTree.new(self.Bounds.Min, centerPoint)
end
--Move into our subdivision and attempt an insert there
self.TopLeft:Insert(node)
--We must be in the bottom left at this point
else
if not self.BottomLeft then
self.BottomLeft = QuadTree.new(self.Bounds.Min + halfDown, centerPoint + halfDown)
end
self.BottomLeft:Insert(node)
end
--Check the right now
else
--Top right
if node.Position.Y <= centerPoint.Y then
if not self.TopRight then
self.TopRight = QuadTree.new(self.Bounds.Min + halfRight, centerPoint + halfRight)
end
self.TopRight:Insert(node)
--Bottom right
else
if not self.BottomRight then
self.BottomRight = QuadTree.new(centerPoint, self.Bounds.Max)
end
self.BottomRight:Insert(node)
end
end
endNow that we’ve done that, the search function will actually be a piece of cake. By using the same splitting function that we did for Insert, we’ll find the subdivision that the point would be in. If that subdivision exists, all we have to do is return the node tied to it!
function QuadTree:Locate(point)
if not self:Contains(point) then
warn("Search failed; point not in quad bounds")
return
end
--Recursive base case
if self.Node then return self.Node end
--Recursive step, similar to search
--However, if we find that a specific sector is unfilled, we will simply return nil
local centerPoint = (self.Bounds.Min + self.Bounds.Max)/2
if point.X <= centerPoint.X then
--Top left, else bottom left
if point.Y <= centerPoint.Y then
return self.TopLeft and self.TopLeft:Locate(point)
else
return self.BottomLeft and self.BottomLeft:Locate(point)
end
else
--Top right, else bottom right
if point.Y <= centerPoint.Y then
return self.TopRight and self.TopRight:Locate(point)
else
return self.BottomRight and self.BottomRight:Locate(point)
end
end
endAs for the driver code that’ll piece it all together, the results are best seen in an actual game. So, I put together a model that has the dummy map I made + two local scripts: one to test the binary tree and one to test the quad tree. The full source code will be there.
https://gyazo.com/b841af56176190e9244f9423eddac6b6.gif
This worked incredibly great on my computer, with on average a 0.03ms search time. Given that was based on 16 nodes, in theory if I divided the map into a million nodes the performance would still be around a mere 0.5ms per node (going back to my statement about BST efficiency earlier). lg(n) efficiency is every programmer’s dream, and now we can have that for grid collisions!
Trees.rbxm (6.4 KB)
I hope this tutorial helped you learn some ways to better handle things like grid collisions in a game. There’s so much more potential to be discovered in octrees, which I may do a tutorial on later. Thanks for reading 
