« Back to tutorial listing

— Creating a Run and Gun game —
Part 10: Adding a quadtree

Note: this tutorial assumes knowledge of C, as well as prior tutorials.

Introduction

We've added in a lot of different collision checks now, many of which are irrelevant in the context of the entity and/or bullet that is performing the test. There's no need for the player to check if it has made contact with a door that is on the other side of the map. Equally, a bullet doesn't need to test if it has hit an oil drum that is far out of range. In this part, we'll introduce a quadtree, to reduce the number of checks we're making.

Extract the archive, run cmake CMakeLists.txt, followed by make, and then use ./gunner10 to run the code. You will see a window open like the one above. The same controls from past tutorials apply. Keep an eye on the debug information in the bottom right, informing us of the number of collision checks that are being performed. Notice how it changes as we perform different actions. Once you're finished, close the window to exit.

Inspecting the code

The idea behind a quadtree is to divide up our game world, so that only entities within one sector will collide with entities within the same sector. A quadtree divides the map into quarters. However, it then subdivides those quarters into smaller quarters. And those into even small quarters. This process continues until we reach a set limit, either the "depth" or the size of the quarter (otherwise known as nodes or cells).

Below is an example of how a map is split into quarters (note: this isn't entirely accurate, as the illustration is only considering the screen, rather than the entire level)

When it comes to determining the number of splits we want to make, we can either limit ourselves to depth or by the dimensions of the quadtree cell, stopping once we reach a certain size. In our game, we're going to limit by depth. It is worth experimenting with this, however, as you will soon find that there is a limit to the benefits you will see from splitting up the game world. The more we split, the more memory we require, and it might not always have a positive impact. Consider the table below:

You might be wondering why we don't just grab all the entities that are currently on screen and only consider those for collisions and drawing. To a point, this approach can be made to work and does indeed cut down on the amount of entities that are processed. However, it comes with a number of drawbacks. First, the game would need to be designed in a way in which that off-screen entities aren't important to the flow of the gameplay. Consider a moving platform, for example. The moment it leaves the screen, it will stop moving, as it's no longer a candidate for processing. A solution is to then tag the platform as always being processed. However, there is a further drawback - if an entity was sitting on a platform that was moving and the platform went offscreen, the entity would stop moving, while the platform would continue to do so. This would mean that as soon as the item came back on screen, there's a good chance it wouldn't be supported by the platform and would drop. These sorts of bugs and unwanted behaviour would plague our game without careful management, and may not be worth it in the long run.

Now, let's look at the code. Starting with defs.h:

#define MAX_QT_CANDIDATES      128

We've added a new define called MAX_QT_CANDIDATES. This define will be used to specify the maximum number of entities that can be gathered and placed into a results list when we query the quadtree. We'll see this in use much later on.

Next, we've added a new struct to structs.h, to define our Quadtree:

struct Quadtree {
	int depth;
	int x, y, w, h;
	Entity **ents;
	int capacity;
	int numEnts;
	int addedTo;
	Quadtree *node[4];
};

This struct actually represents a cell within a Quadtree. Notice how it has four child Quadtrees (node), that can be drilled down into. The other fields are as follows: `depth` is the depth at which this cell resides. `x`, `y`, `w`, and `h` are the coordinates and dimensions of the cell. `ents` is an array of pointers to Entities that currently reside in the cell. `capacity` is the size of the array. numEnts tells us how many entities currently occupy the cell. addedTo is a flag to tell us whether the cell (including its children) have had entities added to it.

Our Stage struct is where the Quadtree will live:

typedef struct {
	Entity entityHead, *entityTail;
	Bullet bulletHead, *bulletTail;
	Entity *player;
	int map[MAP_WIDTH][MAP_HEIGHT];
	SDL_Point camera;
	Quadtree quadtree;
} Stage;

This is effectively the top level quadtree, at depth 0.

Now, let's look at the code for the quadtree itself. It all lives in quadtree.c. Plenty of functions in this file. We'll start with initQuadtree:

void initQuadtree(Quadtree *root)
{
	Quadtree *node;
	int i, w, h;

	/* entire map */
	if (root->depth == 0)
	{
		root->w = MAP_WIDTH * MAP_TILE_SIZE;
		root->h = MAP_HEIGHT * MAP_TILE_SIZE;
		root->capacity = QT_INITIAL_CAPACITY;
		root->ents = malloc(sizeof(Entity*) * root->capacity);
		memset(root->ents, 0, sizeof(Entity*) * root->capacity);

		numCells = 0;
	}

	if (root->depth < MAX_DEPTH)
	{
		w = root->w / 2;
		h = root->h / 2;

		for (i = 0 ; i < 4 ; i++)
		{
			node = malloc(sizeof(Quadtree));
			memset(node, 0, sizeof(Quadtree));
			root->node[i] = node;

			node->depth = root->depth + 1;
			node->capacity = QT_INITIAL_CAPACITY;
			node->ents = malloc(sizeof(Entity*) * node->capacity);
			memset(node->ents, 0, sizeof(Entity*) * node->capacity);

			node->w = w;
			node->h = h;

			switch (i)
			{
				case 0:
					node->x = root->x;
					node->y = root->y;
					break;

				case 1:
					node->x = root->x + w;
					node->y = root->y;
					break;

				case 2:
					node->x = root->x;
					node->y = root->y + h;
					break;

				default:
					node->x = root->x + w;
					node->y = root->y + h;
					break;
			}

			numCells++;

			initQuadtree(node);
		}
	}

	if (root->depth == 0)
	{
		SDL_LogMessage(SDL_LOG_CATEGORY_APPLICATION, SDL_LOG_PRIORITY_INFO, "Quadtree: [numCells = %d, memory = %.2fkb]", numCells, (double)((sizeof(Quadtree) * numCells) / 1024.0));
	}
}

As you might have noticed, this is a recursive function. The function takes a quadtree as its argument (`root`). The first thing we're doing is testing the `depth` of the quadtree that has been passed into the function. If `depth` is 0, we're considering this the top level of the quadtree. It therefore encompasses the entire map. We're setting `root`'s `w` and `h` (width and height) to be the size of the whole map. We're then setting its `capacity` as QT_INITIAL_CAPACITY (defined as 8). This means that at first it will be able to hold 8 entities. We're then mallocing and memsetting its `ents` field as an array of Entity pointers of the same size as `capacity`. We're finally setting a variable named numCells as 0. This is just for some debug output at the end of the function.

With our top level cell created, we're once again testing the `depth` of the current cell (`root`). Remember that this is a recursive function, so `root`'s `depth` could be anything. If `depth` is less than MAX_DEPTH (defined as 3), we're going to start splitting up this cell into smaller ones. We start by assigning a variable named `w` the value of half the quadtree's width, and a variable named `h` as half the quadtree's height. We're then setting up a for-loop that will create our quadrants.

For each iteration of our loop, we're mallocing and memsetting a new Quadtree, assigning it to a variable called `node`. Each `node` will be assigned to `root`'s `node` array at the same `i` index. As with creating the initial quadtree cell, we're setting its `ents` array and `capacity`, but notice that the `depth` is set as the root node's `depth`, plus one. This is because this cell is the child of the current quadtree and is therefore at a lower depth. We then set `node`'s `w` and `h` as the values of `w` and `h` that we assigned earlier. This will make the cell half the width and height of the parent.

We now need to determine the location of the node. We do this by performing a switch against `i`. If `i` is 0, we want the node to be in the top quarter of the parent. We therefore assign it root's `x` and `y`. If `i` is 1, we'll make it the top-right quarter of the parent. The `node`'s `x` will therefore be the parent's `x` plus `w`. Remember that `w` is half of the parent's width, meaning we'll move the node midway over. Setting `node`'s `y` as the parent's `y` will mean it now occupies the top-right of the parent. We repeat this process with cases 2 and 3 (default), putting the node in the bottom-left and bottom-right respectively.

With that done, we increment numCells (again, just for debugging info) and then call initQuadtree, passing in the node that was just created. This is a highly important step, as this will mean our recursive initQuadtree function will continue to break our quadtree into quadrants until we reach MAX_DEPTH. At this point, we will no longer recurse and initQuadtree will stop being called. It is at this point that we'll return to the top of our call stack and reach the final if-statement that will output our debug info. This call is only made for the top level of the quadtree (`depth` is 0).

That's our quadtree setup. We can now look at adding entities to it. We have one function to do that - addToQuadtree:

void addToQuadtree(Entity *e, Quadtree *root)
{
	int index;

	root->addedTo = 1;

	if (root->node[0] != NULL)
	{
		index = getIndex(root, e->x, e->y, e->texture->rect.w, e->texture->rect.h);

		if (index != -1)
		{
			addToQuadtree(e, root->node[index]);
			return;
		}
	}

	if (root->numEnts == root->capacity)
	{
		resizeQTEntCapacity(root);
	}

	root->ents[root->numEnts++] = e;
}

This is another recursive function, as you can see from the parameter list. We'll start with a summary of what this function does. The idea is to take the entity passed into the function and find the smallest quadrant into which it can be placed. We'll test each of the quadtree's four nodes, recursing down into those nodes as we find a match. Once we've found a quadtree node into which we can place the entity, we'll add it. We'll now detail this fully.

The function takes two parameters - the entity (`e`) to add and the reference to a quadtree (`root`). When we first call this function, we'll pass over the top-level quadtree (stage.quadtree).

The first thing we do in the function is set `root`'s addedTo flag to 1, to say that an entity has been added to it (or even one of its children). We then check to see if the quadtree has any child nodes. We do this by simply testing if the first item in the `node` array is not NULL. This test is required to ensure we're not at the very bottom of the quadtree before proceeding. Next, we're calling a function called getIndex, to find the quadrant into which we'll be placing our entity (more on this function in a bit). The function will return a number between 0 and 3, or -1 if the entity cannot fit into a node. We'll assign this result to `index`. If `index` isn't -1, we'll call addToQuadtree again, passing in the entity and the quadrant (`node` array index) that was determined could hold our entity.

If, however, `index` was -1 or we reached the bottom of our quadtree, we'll be adding the entity to the current node. We'll first check if we need to expand the size of our entity array within the node, by testing if the `root`'s numEnts is equal to `capacity` (meaning it's full), and call resizeQTEntCapacity if so. With that done all, we'll add the entity into `root`'s `ents` array, at the next free index.

So, again, we're searching our quadtree to find a quadrant into which to place our entity. Next, we'll look at the getIndex function. This is a very important function, that will help us to determine where our entity lives within the tree:

static int getIndex(Quadtree *root, int x, int y, int w, int h)
{
	int verticalMidpoint, horizontalMidpoint, topHalf, bottomHalf;

	verticalMidpoint = root->x + (root->w / 2);
	horizontalMidpoint = root->y + (root->h / 2);
	topHalf = (y < horizontalMidpoint && y + h < horizontalMidpoint);
	bottomHalf = (y > horizontalMidpoint);

	if (x < verticalMidpoint && x + w < verticalMidpoint)
	{
		if (topHalf)
		{
			return 0;
		}
		else if (bottomHalf)
		{
			return 2;
		}
	}
	else if (x > verticalMidpoint)
	{
		if (topHalf)
		{
			return 1;
		}
		else if (bottomHalf)
		{
			return 3;
		}
	}

	return -1;
}

The idea behind this function is to take the coordinates and dimensions of an entity and check to see which quadrant within our quadtree node can fully contain it. Based on the result, we'll return the index of the quadrant: 0 - top left, 1 - top right, 2 - bottom left, 3 - bottom right.

We start by setting up 4 variables: verticalMidpoint, as this node's x location, plus half its width; horizontalMidpoint, as this node's y location, plus half its height; topHalf, as a boolean to say whether the entity fits vertically into the top half of the node; and bottomHalf as a boolean to say whether the entity fits into the bottom half of the node.

With all these known, we then test to see if the entity we want to add can fit into the left-side of the quadrant, by testing if its `x` value is less than verticalMidpoint and it's `x` plus its texture width is less than the verticalMidpoint. If so, we test the topHalf and bottomHalf values, to see if the entity can be contained within those, and return 0 or 2, to indicate top-left or bottom-left.

If the entity isn't on the left, we check to see if it's contained on the right-hand side. Notice how we're testing if `x` is greater than verticalMidpoint; we want to make sure that the entity is fully contained within the quadrant, so therefore overlaps are not allowed. If the entity is on the right-hand side, we once again test topHalf and bottomHalf, to see if we want to add the entity to the top-right or bottom-right.

If none of these conditions hold true, we'll be return -1, to say that the entity is contained within the current node and not any of its children.

All that might seem complicated, but think it over - we'll move down out quadtree, searching for a quadrant that can fully contain our entity. Once we find one, we'll add it in.

Removing an Entity from our quadtree is much the same, but with a few extra things. Our removeFromQuadtree function handles this nicely for us:

void removeFromQuadtree(Entity *e, Quadtree *root)
{
	int index;

	if (root->addedTo)
	{
		if (root->node[0] != NULL)
		{
			index = getIndex(root, e->x, e->y, e->texture->rect.w, e->texture->rect.h);

			if (index != -1)
			{
				removeFromQuadtree(e, root->node[index]);
				return;
			}
		}

		removeEntity(e, root);

		if (root->numEnts == 0)
		{
			root->addedTo = 0;

			if (root->node[0] != NULL)
			{
				root->addedTo = root->node[0]->addedTo || root->node[1]->addedTo || root->node[2]->addedTo || root->node[3]->addedTo;
			}
		}
	}
}

As you can see, this is another recursive function. When removing an entity, we search for it within the quadtree, in the same way that we added the entity. There is actually an optimization we could do here, by storing the node the Entity was added to and then removing it that way. For the purposes of this tutorial, however, we'll do it this way. In a future tutorial (maybe a sequel to this game), we might look at optimizing this.

Once we've located the node in which the entity resides, we call a function named removeEntity, passing in the entity and the node. We'll see this in a moment. After this, we test how many entities are remaining in the node, by checking numEnts. If numEnts is 0, we default the node's addedTo flag to 0. We then test if this node has any children. If it does (`root`'s node[0] is not NULL), we update the addedTo flag by testing if any of the four child nodes have been added to. The purpose of this is to tell our code not to bother searching this node in future, as it contains no entities. It's a fail-fast approach.

The removeEntity function is next, and is quite simple to understand:

static void removeEntity(Entity *e, Quadtree *root)
{
	int i, n;

	n = root->numEnts;

	for (i = 0 ; i < n ; i++)
	{
		if (root->ents[i] == e)
		{
			root->ents[i] = NULL;
			root->numEnts--;
		}
	}

	qsort(root->ents, n, sizeof(Entity*), entityComparator);
}

It takes two parameters - the entity to remove (`e`) and the quadtree node (`root`) from which to remove it. We assign the current number of entities in `root` (numEnts) to a variable called `n`, so we can record how many entities existed before the removal. Next, we loop through all the entities in the quadtree node, searching for the entity we wish to remove. When we find the entity, we set the array index at which it exists to NULL and decrement numEnts. With the entity removed, we then call qsort, passing in the entity array and a comparator named entityComparator. The purpose of this function is to shift all the non-NULL entities to the front of the array, so that adding new entities in future can be done so at NULL entries.

entityComparator is defined below:

static int entityComparator(const void *a, const void *b)
{
	Entity *e1 = *((Entity**)a);
	Entity *e2 = *((Entity**)b);

	if (e1 == NULL)
	{
		return 1;
	}
	else if (e2 == NULL)
	{
		return -1;
	}
	else
	{
		return 0;
	}
}

This function will push all the NULL items to the back of the list, while non-NULL items will move towards the front. If both items aren't NULL, they won't move from their current position.

We're halfway done. There's quite a lot to quadtrees, as you can well appreciate by now. The next thing we want to look at is fetching the entities within an area of the quadtree. This is something we'll need to do when fetching the candidates for collision tests with things such as bullets and other entities. The main function for fetching our entities is called getAllEntsWithin:

void getAllEntsWithin(int x, int y, int w, int h, Entity **candidates, Entity *ignore)
{
	cIndex = 0;

	memset(candidates, 0, sizeof(Entity*) * MAX_QT_CANDIDATES);

	getAllEntsWithinNode(x, y, w, h, candidates, ignore, &stage.quadtree);
}

The function takes 6 parameters: the `x` and `y` coordinates of an area, along with its width and height (`w` and `h`). We also pass in an array of entity pointers named `candidates`. It is into this array that all the entities we pull out of the quadtree will be placed. A final parameters called `ignore` can also be passed over. This parameter can be used to instruct our fetching routine to ignore an entity and not add it to the results list. This is useful for when finding entities that we want to test for colliding against another. We don't want to include the entity that is doing the colliding in the results, so we can ignore it here.

This first thing the function does is sets a variable called cIndex (short for candidate index) to 0. This is a static variable within quadtree.c, that can be accessed for any function. Next, we memset the `candidates` array, to clear it. We're making an assumption here that the size of the array is always MAX_QT_CANDIDATES (defined as 128). With that done, we're calling another function named getAllEntsWithinNode, passing over the parameters that we received, along with the quadtree root (stage.quadtree). It's from here that we will begin our search.

getAllEntsWithinNode is defined below. It is, once again, a recursive function:

static void getAllEntsWithinNode(int x, int y, int w, int h, Entity **candidates, Entity *ignore, Quadtree *root)
{
	int index, i;

	if (root->addedTo)
	{
		if (root->node[0] != NULL)
		{
			index = getIndex(root, x, y, w, h);

			if (index != -1)
			{
				getAllEntsWithinNode(x, y, w, h, candidates, ignore, root->node[index]);
			}
			else
			{
				for (i = 0 ; i < 4 ; i++)
				{
					getAllEntsWithinNode(x, y, w, h, candidates, ignore, root->node[i]);
				}
			}
		}

		for (i = 0 ; i < root->numEnts ; i++)
		{
			if (cIndex < MAX_QT_CANDIDATES)
			{
				if (root->ents[i] != ignore)
				{
					candidates[cIndex++] = root->ents[i];
				}
			}
			else
			{
				SDL_LogMessage(SDL_LOG_CATEGORY_APPLICATION, SDL_LOG_PRIORITY_CRITICAL, "Out of quadtree candidate space (%d)", MAX_QT_CANDIDATES);
				exit(1);
			}
		}
	}
}

The goal behind this function is to select a rectangular area within our quadtree and then fetch all the entities that are contained within that area. The first thing we do is test if this quadtree node (`root`) has had anything added to it, to fail fast if not. If it does, we check if it has children by testing if the first of its nodes is NULL. If it's not NULL, we'll use getIndex to find out which of its child nodes we need to drill down into to extract the entities from. If the index is -1, we'll be grabbing ALL of the entities from ALL of the children, using a for-loop from 0 to 4 (exclusive), once again in a recursive manner.

Regardless of whether the quadtree node we're working with has child nodes, we'll then setting up a for-loop to fetch all the entities (`ents`) within the current quadtree (`root`). During each iteration of the for-loop, we're checking that cIndex hasn't exceeded our array size (MAX_QT_CANDIDATES) and also checking that the current entity isn't the one we want to ignore. We then add the entity to our candidates array, incrementing cIndex as we go. We'll print an error and exit if we exceed our array size (note that 128 entities is more than generous for our needs, so it's unlikely we'll encounter this).

That's the bulk of the quadtree done. We can now look at some other functions before finishing up. First, the destroyQuadtree function.

void destroyQuadtree(Quadtree *root)
{
	destroyQuadtreeNode(root);
}

We'll use this function to destroy our quadtree, freeing all the data that was involved in its creation. It takes a single argument, which is assumed to be the top level quadtree node (in our case, stage.quadtree). This function delegates to another function called destroyQuadtreeNode:

static void destroyQuadtreeNode(Quadtree *root)
{
	int i;

	free(root->ents);

	root->ents = NULL;

	if (root->node[0] != NULL)
	{
		for (i = 0 ; i < 4 ; i++)
		{
			destroyQuadtreeNode(root->node[i]);

			free(root->node[i]);

			root->node[i] = NULL;
		}
	}
}

We first free the quadtree node's (`root`) entity array, and set it to NULL for good measure. Next, we test if `root` has any children, by once again checking if root->node[0] is NULL. If not, we're going to destroy each of the child nodes. For each of the 4 nodes, we're calling destroyQuadtreeNode (another recursive function!) and passing in the node, so as to free the data within the node before we destroy the node itself. Once destroyQuadtreeNode returns, we'll free the quadtree node itself and NULL it.

The only other function to look at is resizeQTEntCapacity. This function increases a quadtree's entity array capacity:

static void resizeQTEntCapacity(Quadtree *root)
{
	int n;

	n = root->capacity + QT_INITIAL_CAPACITY;

	SDL_LogMessage(SDL_LOG_CATEGORY_APPLICATION, SDL_LOG_PRIORITY_DEBUG, "Resizing QT node: %d -> %d", root->capacity, n);

	root->ents = resize(root->ents, sizeof(Entity*) * root->capacity, sizeof(Entity*) * n);
	root->capacity = n;
}

As our quadtree can have a huge number of cells, we're only allowing each node to hold 8 entities to begin with, to reduce the memory load. There's a good chance that our node will require more than that in future, so we're allowing our array to grow. This function helps us with that.

We're first taking the current node's entity capacity and adding QT_INITIAL_CAPACITY to it, assigning the value to `n`. Some debug information follows, before we then call a function named `resize`, passing through the array itself, the old array size, and the new array size. We'll look at resize at the end of this part, as it's a general purpose function. With the array resized, we then set root's capacity to `n`, to reflect the new array size.

That's quadtree.c done! So, how do we use it? For that, let's turn to entities.c. Starting with doEntities:

void doEntities(void)
{
	Entity *e, *prev;

	prev = &stage.entityHead;

	for (e = stage.entityHead.next ; e != NULL ; e = e->next)
	{
		removeFromQuadtree(e, &stage.quadtree);

		e->onGround = 0;

		if (!(e->flags & EF_WEIGHTLESS))
		{
			e->dy = MIN(e->dy + (GRAVITY * app.deltaTime), MAX_FALL_SPEED);
		}

		move(e);

		e->tick(e);

		if (!e->dead)
		{
			addToQuadtree(e, &stage.quadtree);
		}
		else
		{
			prev->next = e->next;

			if (e == stage.entityTail)
			{
				stage.entityTail = prev;
			}

			deadTail->next = e;
			deadTail = e;
			deadTail->next = NULL;

			e = prev;
		}

		prev = e;
	}
}

Our entity processing loop has seen some minor changes. To being with, we're called removeFromQuadtree as the very first thing in the loop, passing through the entity (`e`) and the top level quadtree (`stage.quadtree`). It is very important that we do this here, since we must remove the entity before we move it! If we attempt to remove it after moving, it may have shifted into a new node meaning that we can no longer locate it. This would leave us with dangling references in our quadtree, which will result in our collision detection going wrong, as well as crashes if we delete the entity data.

The rest of the entity processing code remains the same. At the end of the loop, after the entity has moved, we want to add it back into the quadtree. Before doing this, we first check to see if the entity is not dead. Again, we don't want to add dead entities to our quadtree, as there is no point and we also want to avoid any crashes that may occur.

So, now we can add and remove entities from our quadtree. For our collision detections, we've not had to make too many changes. Let's look at moveToEntities to see what has changed:

static void moveToEntities(Entity *e, double dx, double dy)
{
	Entity *other, *candidates[MAX_QT_CANDIDATES];
	int i, adj, y;

	y = (dy > 0 && dy < 1) ? 1 : 0;

	getAllEntsWithin(e->x, e->y, e->texture->rect.w, e->texture->rect.h, candidates, e);

	for (i = 0, other = candidates[0] ; i < MAX_QT_CANDIDATES && other != NULL ; other = candidates[++i])
	{
		app.dev.collisionChecks++;

		if (collision(e->x, e->y + y, e->texture->rect.w, e->texture->rect.h, other->x, other->y, other->texture->rect.w, other->texture->rect.h))
		{
			// snipped
		}
	}
}

We're now declaring an array of entity pointers, of length MAX_QT_CANDIATES. We're then calling getAllEntsWithin, passing in the current entity's `x`, `y`, width, and height, the `candidates` array, and the entity itself (`e`) as the thing to ignore. This call will result in our `candidates` array being filled with all the entities that reside in the same area as the entity we're processing. We then setup a for-loop to step through the results, assigning the current entity to `other`. Our loop will exit if we reach the end of the array or encounter a NULL entity in the `candidates` array.

And that's all we need to do..! We're using the same method in drawEntities:

void drawEntities(void)
{
	Entity *e, *candidates[MAX_QT_CANDIDATES];
	int i;

	getAllEntsWithin(stage.camera.x, stage.camera.y, SCREEN_WIDTH, SCREEN_HEIGHT, candidates, NULL);

	for (i = 0, e = candidates[0] ; i < MAX_QT_CANDIDATES && e != NULL ; e = candidates[++i])
	{
		e->draw(e);
	}

	if (app.dev.showHitboxes)
	{
		for (i = 0, e = candidates[0] ; i < MAX_QT_CANDIDATES && e != NULL ; e = candidates[++i])
		{
			drawOutlineRect(e->hitbox.x - stage.camera.x, e->hitbox.y - stage.camera.y, e->hitbox.w, e->hitbox.h, 255, 255, 0, 255);
		}
	}
}

The only real difference is that when calling getAllEntsWithin we're using the coordinates of the camera, with SCREEN_WIDTH and SCREEN_HEIGHT as the width and height. We're also passing over NULL as the entity to ignore, as we don't want to ignore anything. Calling getAllEntsWithin will result in us fetching all the entities that can fit into a quadtree node occupied by the screen (which might actually be very high, due to the nature of the quadtree..!).

You will remember that bullets also test for collisions with entities. If we look at bullets.c, we'll see that checkEntityCollisions also implements the new getAllEntsWithin function:

static void checkEntityCollisions(Bullet *b)
{
	Entity *e, *candidates[MAX_QT_CANDIDATES];
	int i;
	SDL_Rect r;

	r.x = b->x;
	r.y = b->y;
	r.w = b->texture->rect.w;
	r.h = b->texture->rect.h;

	getAllEntsWithin(b->x, b->y, b->texture->rect.w, b->texture->rect.h, candidates, b->owner);

	for (i = 0, e = candidates[0] ; i < MAX_QT_CANDIDATES && e != NULL ; e = candidates[++i])
	{
		// snipped
	}
}

When calling getAllEntsWithin here, we're passing over the bullet's `x` and `y` coordinates, it's texture's width and height, and also the bullet's `owner` as the entity that we want to ignore.

At last, our quadtree is finished! Phew, that was a lot to get through. Before ending this part, we'll look quickly at the other minor updates we've made. We'll return to the `resize` function that the quadtree used. `resize` itself lives in util.c:

void *resize(void *array, int oldSize, int newSize)
{
	void **newArray;
	int copySize;

	copySize = newSize > oldSize ? oldSize : newSize;

	newArray = malloc(newSize);
	memset(newArray, 0, newSize);
	memcpy(newArray, array, copySize);
	free(array);

	return newArray;
}

What this function does is creates a new array of size newSize. It does this by using malloc and memset. The first thing we do is test how much data we want to copy into our new array, by finding the larger of newSize and oldSize. This enables use to shrink an array, if we so desire. Next, we malloc data the size of newSize and assign it to a variable named newArray. We memset newArray, to zero all the memory, then use memcpy to copy all the data from the old array (array) into newArray. We only want to copy the memory of copySize. With that done, we free the old array and return the newArray.

That's this part finally done and dusted. Looking at all this you may wonder if it's truly faster than simply testing all the entities against one another in the world. There's a lot going on in the quadtree, especially when it comes to searching. The answer is yes, it is faster. Especially at scale. If you create a large level in a game with dozens of entities (enemies, items, structures, etc.), the benefits will become quite apparent with huge boosts to frame rates. A level with just 100 entities would involve close to 10,000 checks per frame without any sort of partitioning. And that doesn't include checks made by bullets. With a quadtree, far fewer.

In the next part, we'll focus on some bug fixes and gameplay enhancements for our game. You may have noticed, for example, that enemies are able to see through solid objects, such as door.

Purchase

The source code for all parts of this tutorial (including assets) is available for purchase:

From itch.io

It is also available as part of the SDL2 tutorial bundle: