Quadtrees and Collision Detection in OpenGL – Part 2 – Making it Work

In the last post I detailed a rough outline for a quadtree data structure and a simple OpenGL program to test that it works. To quickly recap, a quadtree is a way to partition space, usually in two dimensions. Each node in the tree represents a region and a list of objects contained in that space. As you add more objects to this space, it breaks down into 4 smaller children, giving more precise boundaries. A very common use for this is in collision detection which is the program I will be creating below. The user can move a small square around the window, and when it touches a point the user places, the square becomes red. It’s pretty basic but demonstrates the basics of collision detection with quadtrees.
Picking up in the QuadTree header file, I add in the line

, as I’ll be using a set to return all the points later on. Next, in the Point2D struct, a binary less than operator is needed to actually use Point2D’s in a set. Since ordering two dimensional points doesn’t really make sense, I just compare the x-coordinate like so:

In this basic example, the “player” is represented by a square. So, to test if the player is within the boundary of a node in the quadtree, we need a rectangle intersection test, defined below in the Rect2D struct.

You’ll note that the y-axis test might be a bit different than you’d normally see – that’s because OpenGL has opposite the opposite y-axis in other APIs / languages. Interestingly, it does makes more sense in a real-world coordinate sense. With the additional struct functions out of the way, the last thing needed in the QuadTree header file is a function deceleration for what will actually get the points that the player might intersect.

In the QuadTree source file, the actual definition of the getIntersections method is pretty short and sweet. If the player intersects the region of a node, either check the 4 children of a node or add the points of a node if the node is a leaf. This function uses a set to return the points. While it can’t happen with points, should objects be in multiple tree leaves, they would be added more than once to the ultimate collection of points. Not much can be done to combat that then to simply delete any duplicates before the collection is used for more precise collision detection. I use a set because at a certain threshold they actually get rid of duplicates faster than a vector. While a more robust approach might be to use vectors for small amounts of objects and sets for large, we can get away with just picking one or the other. The method definition is below:

Finally, the entirety of the new QuadTreeTest source file is below, with a few modifications to code from the previous post. The user
can place blue points with the left mouse button. The user can also control a green box with the 4 arrow keys. If the player collides with a point, the color changes to red. Purple lines go from the player to all points that are considered possible collisions as well as the command line displaying how many possible collisions there are. Right clicking deletes the tree and player. The code is decently condensed to get to the main point of checking collisions. For example, the movement code is extremely basic and should not be used if you actually want to handle top-down movement. The entire source code is below:


Quadtrees and Collision Detection in OpenGL – Part 1 – Setting it Up

Collision detection is an extremely important part of games and other simulation-like applications. When we have a lot of different objects at once, the amount of checking we need to do will ramp up quickly. If we have n distinct objects to check against each other, we need to perform (n^2 – n) / 2 checks at minimum. That’s because you need to check the first object against the other n-1 objects, then the second against n-2 objects (since the first object already was checked), and so on and so forth. For 100 objects, that’s 4950 checks! If you’re familiar with Big-O analysis, you should recognize this is a O(n^2) algorithm. In layman’s terms, this means that as we add more objects to check (n), the amount of checks ramps up exponentially (thus n^2). Because of the exponential factor, the subtraction of n and division by two actually become negligible. This number of checks can be “alright” for small sets of data, but we can be more efficient!

Say we have a two-dimensional space with 100 random spheres moving around in different directions. How can we efficiently check for collisions? One idea is to only check against objects that are some arbitrary distance away from the current object. This is nice as the calculation is usually quick, but there’s one problem – how can we initially know if an object is far away? We’d still have to do 4950 checks to see if something is close or not! What if we did this check once and stored a list of the closest objects and just checked against them? It’s a bit better in theory, but in practice this list would need to be constantly be updated as objects move around, so ultimately we’re still checking 4950 times more often than we should be.

Well what if something else kept track of the distances between objects? This is essentially the basis of space partitioning – split up the screen and only check objects in each parition. So, what if split up our two-dimensional space in half? We can check against only objects are on our side of the screen. Since our screens are (usually) rectangular, we could go a bit further and split this into 4 quadrants and just check the objects in the same quadrant we are in. We can store this information about who is in what quadrant in what is known as a quadtree.

A quadtree partitions space into smaller and smaller rectangular regions as needed / defined.. Each node in a quadtree represents a rectangular region. It also contains 4 child nodes which will represent the region’s 4 quadrants when further partitioning is needed. Nodes at the leaf level, as in they are not broken down into further quadrants and thus have no child nodes, have a list of objects that represent all of the objects contained within the small region. When this list becomes too full (which is completely up to the programmer), the node will further divide itself into 4 smaller quadrants and partition the objects into these new rectangles. Using the 100 object example, let’s say we split our initial window into 4 quadrants. If 75 objects were inside the top left quadrant, we could break down that rectangle (note: not the other 3 quadrants) into 4 smaller quadrants and (ideally) evenly split up the 75 objects among the new quadrants.

So what happens when you need to check collisions? Starting at the root, which represents the entire area objects are in, you check against objects in each of the 4 quadrants of said area. However, these checks can quickly return if you aren’t even in that region. Let’s take a point in the top left quadrant. When you check for collisions with this point, you do check against the other 3 quadrants but no further since that point isn’t in the other 3 quadrants!. So you just saved yourself from checking against objects in 3/4 of the screen!

You might be wondering about larger objects, which is a valid concern. Some objects have to exist in multiple leaves at the same time because of their shape, size, or even just position (like a square in the exact center of the screen). Because of the ability to cut out large chunks of checks at a time, repeated checks should not be much of a burden. Of course, a bunch of large objects checking against a bunch of other large objects can quickly lead to disaster with even more checks than the initial brute force approach! In scenarios like that, you might be better served with some other way to partition objects, of which there are a variety.

Now that all this theory is out of the way, let’s actually write some code! I’ll be working with C++ and OpenGL to do this. As a disclaimed, I just started working with OpenGL only a short time ago, so there are probably a few “incorrect” things I do. Additionally, I’ve been using the OpenGL SuperBible to get set up with the OpenGL, so if there’s anything “weird” I do there, that’s probably why.


So, to start out, I have QuadTree.h which starts out by defining two structs to represent points and rectangles in two-dimensional space. For convenience I put the struct definitions in this file as well as shortening the code up a bit. One little quirk with OpenGL is that the y-coordinate is relative to the bottom-left of the window as opposed tot he top left. This makes mathematical sense but still feels a bit weird after working with the top left point being the origin of a rectangle. The definition for Point2D and Rect2 is pretty basic. I decide to calculate and store the center and top-right of the rectangle, as well as the bottom left, to help out later when we need to split up a rectangle. I also have quick functions to check for point containment within the rectangle. The final part of the header file is the quadtree definition:


This is a pretty bare-bones implementation although it does rely on the previously defined point / rectangle structs. The nodeValue is the rectangle this node represents. We have a vector of points that represent the points contained within the node (if it is a leaf). The MAX_OBJECTS field lets us set how many points a leaf can contain until it need to further split itself up. The 4 pointers to other quadtrees it contain represent the 4 quadrants of nodeValue, if the node is no longer a leaf. We’ll get into the function definitions now by switching over to QuadTree.cpp which just contains the implementation of the quadtree functions.


As previously stated, each node represents a rectangle boundary. So to create a node means we need to define some rectangle. We also need to set the children to NULL to be safe.


The insert method is the real meat of the quadtree. When we insert a point into a quadtree, we return either true or false depending on whether we actually insert the point. This is because as we go down the tree, we might insert a point into a region where it doesn’t belong, which leads us to the first statement there. If the node’s region doesn’t contain the coordinates of the point, return false since we can’t insert a node there. An extra constraint, to help with the little test program further down the post, is to not add points that are already contained in the point list for a node or points that are a few pixels away from an already existing node. We still return true though, since technically it would be inserted under normal circumstances. Once these pre-conditions are met, we begin the insertion process. If we have children nodes, then we need to insert the point into each child node, defined below. If we are a leaf node, and we have room in our points vector, then insert the node and return true to signify the node was inserted. If neither of these conditions are met, we need to divide the node’s rectangle, insert the current node’s points and the new point into these children. If, for some unknown reason, we don’t return by now then we just return false. Below are the last two method definitions for the class and the destructor.


The insertIntoChildren method, as the name implies, inserts a point into each of the node’s children. Notice that I have a boolean flag that gets set when any insertion succeeds. This means that a point can exist in more than one tree, which will be necessary if we expand this to include polygons at opposed to points. The subdivide function calculates the 4 rectangles that make up the current node’s rectangle, and creates the 4 children with these new rectangles. Finally, the destructor deletes all the points and children contained within a node. As a final note, ‘children[0] == NULL’ is checking if the node is a leaf since a leaf has no children.

So we have a quadtree declared and defined, but how can we test it? Well, let’s try drawing it! The code is below in a separate file named QuadTreeTest.cpp and handles all the drawing and interaction. Since this a very simple example, it is a one-time run. Left clicking will place a new point down and right clicking will remove the tree. Here is the rather lengthy code, complete with comments with an image of the final result after some user interaction.


Global Game Jam 2012

This last weekend I participated in the Global Game Jam. The theme for every game jam at the event was a picture of the ouroboros. The team I was in decided to create a 2D platforming game based using reincarnation as a primary mechanic. The player would reincarnate as a different animal based on the amount of shrines they visited in their previous life. The game can be found .

The original plan was to create this game in Flash. However, I had never made a platformer in Flash and neither had the other programmer with AS3 experience. After several hours of failed engines, we switched over to the engine Game Maker that Brian, another team member, had up and working. This was an important lesson to me as it demonstrated that sometimes deadlines mean that some features can’t be implemented. It also urges me to keep learning and experimenting on my own so that these types of situations occur less in the future.

Because Game Maker is hard to work with in a team environment, I switched over to level design. Level design was a critical part of our game as it had to accommodate characters of various sizes. Certain characters needed to be able to reach certain areas while blocking out others. This was tricky but still doable by placing blocks at just the right height as well as other tricks. I also needed to think up what hazards would block the player proceeding too far into the level. Overall I think I managed to be successful with my level design given I only had less than 48 hours.

You can find the game here!

Microsoft Imagine Cup 2011

In the beginning of December 2011, I participated in the Microsoft Imagine Cup. I was tasked with creating a game using one of several Windows technologies in a team with people I never met before.

I had little exposure to XNA prior to the event so a lot of the learning was on the spot. However, regardless of language, I already had good ideas for how implement the game mechanics. The main concern was translating to the XNA / C# syntax.

The concept for our game was the player controlled a reporter in a war zone who takes pictures of atrocities to raise awareness. The gameplay would be from a top-down perspective and have a main emphasis on stealth. The idea was praised highly by the judges but failed to win any awards. The reasoning was mainly being a lack of features which I accept as valid; But I did learn that implementation is key which outweighs any award I could have received.