« Back to tutorial listing

— Making a 2D split screen game —
Part 12: Spatial Grid, part 1

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

Introduction

What we're going to look at now is an optimisation step. As stated earlier, most modern computers won't choke even a little on our game; it's not all that complex. However, there is still potential for our performance to take a huge hit on larger levels. This part might also come in useful to those who might want to make a different type of game, using the concepts laid out in this tutorial. It might be fun to make an exploration game, with the area made up entirely of polygons.

Extract the archive, run cmake CMakeLists.txt, followed by make, and then use ./versus12 to run the code. You will see a window open like the one above, with each player on either side of our zone. Use the default controls (or, at your option, copy the config.json file from a previous tutorial, to use that - remember to exit the game before copying the replacement file). Play the game as normal. There isn't anything new to actually see here (there is no debug information displayed, unlike in the screenshots), so once you're finished, close the window to exit.

Inspecting the code

The idea of a spatial grid probably sounds like an enormously complex beast, but it certainly is not. As we'll see, it simply involves adding our entities to cells, and returning those entries as we query the grid. There are some gotchas involved, but we'll discuss those as we come to them.

Let's get going. To begin with, we've updated defs.h:

#define MAX_WORLD_TRIANGLES 1024

MAX_WORLD_TRIANGLES is the maximum number of triangles we can add in our world.

Next, it's over to structs.h, where we've added a new data type:

typedef struct
{
	int        numTris;
	int        triCapacity;
	Triangle **triangles;
} SpatialGridCell;

SpatialGridCell is a type to hold the data for a single "cell" in our Spatial Grid. numTris is the toal number of triangles in the cell. triCapacity is the maximum number of triangles it can currently hold, and `triangles` is an array of Triangles. This array can be resized according to our needs. For those that have been through the other tutorials involves quadtrees (Gunner and Santa), this will look quite familiar.

Next, we've made a small change to Triangle:

struct Triangle
{
	int        id;
	SDL_FPoint points[3];
	SDL_Color  colors[3];
	Triangle  *next;
};

We've added in an `id` field here. This hold the id of the triangle, that we can increment as we add more triangles.

With that done, we can look at the code for our Spatial Grid, in spatialGrid.c. Before we do that, let's have a look at what we're going to do first.

Above is a visual representation of our spatial grid. Consider each grid cell (outlined in red). The rectangular area occupied by each triangle will be added to every cell it crosses. Consider the red highlighted region below the player. The two triangles that make up the horizontal plain will be added to the five highlighted cells. Anything that requests the triangles that occupy any one of those cells will get back those two triangles, and nothing more.

This will mean that if we then want to check which triangles our player can come into contact with, we will be fetching all triangles in the cells highlighted in green (based on the collision radius we create for our entities). This will be just the two triangles in the top-left, since their square area will fall into that region. Everything else is ignored.

We'll see how this works as we go through our spatial grid. We'll also talk about how we filter out duplicates (one of the gotchas).

So, give to spatialGrid.c, where we'll start with initSpatialGrid:

void initSpatialGrid(void)
{
	int x, y;

	for (x = 0; x < GRID_SIZE; x++)
	{
		for (y = 0; y < GRID_SIZE; y++)
		{
			memset(&grid[x][y], 0, sizeof(SpatialGridCell));
		}
	}
}

Here, we're setting up our spatial grid. Our grid is, as one might expect, a multidimensional array of SpatialGridCells. As our grid is of a fixed size (GRID_SIZE is defined as 50 in spatialGrid.c), we're going to loop through our spatial grid array, and zero all the memory.

Now, over to addTriToSpatialGrid, where something more interesting is going on:

void addTriToSpatialGrid(Triangle *t)
{
	SpatialGridCell *cell;
	int              x, y, x1, y1, x2, y2;

	x1 = MIN(MIN(t->points[0].x, t->points[1].x), t->points[2].x);
	y1 = MIN(MIN(t->points[0].y, t->points[1].y), t->points[2].y);
	x2 = MAX(MAX(t->points[0].x, t->points[1].x), t->points[2].x);
	y2 = MAX(MAX(t->points[0].y, t->points[1].y), t->points[2].y);

	clipAddBounds(&x1, &y1, &x2, &y2);

	for (x = x1; x <= x2; x++)
	{
		for (y = y1; y <= y2; y++)
		{
			cell = &grid[x][y];

			if (cell->numTris == cell->triCapacity)
			{
				increaseTriCapacity(cell);
			}

			cell->triangles[cell->numTris++] = t;
		}
	}
}

This function adds a Triangle (`t`) to our spatial grid. We start by calculating the rectangular area occupied by the triangle, by working out its maximum and minimum `x` and `y` point values (assigned to `x1`, `y1`, `x2`, and `y2`). With the values worked out, we call a function named clipAddBounds, that will ensure our rectangular areas are constrained to our grid - we'll see this function in a little while. With our cell points known, we set up a loop to add the triangle to all the cells it should belong to. As with our Quadtree implementation, we'll increase the size of the SpatialGridCell to hold more triangles if it is currently at capacity (via increaseTriCapacity).

Nothing mindblowing there! Next up, we have getAllTrisFromSpatialGrid:

void getAllTrisFromSpatialGrid(int x, int y, int w, int h, Triangle **candidates)
{
	SpatialGridCell *cell;
	int              x1, y1, x2, y2, i, cIndex;
	uint8_t          added[MAX_WORLD_TRIANGLES];

	cIndex = 0;

	memset(candidates, 0, sizeof(Triangle *) * MAX_WORLD_TRIANGLES);

	memset(added, 0, sizeof(added));

	x1 = x;
	y1 = y;

	clipFetchBounds(&x1, &y1, &x2, &y2, w, h);

	for (x = x1; x <= x2; x++)
	{
		for (y = y1; y <= y2; y++)
		{
			cell = &grid[x][y];

			for (i = 0; i < cell->numTris; i++)
			{
				if (!added[cell->triangles[i]->id])
				{
					candidates[cIndex++] = cell->triangles[i];

					added[cell->triangles[i]->id] = 1;
				}
			}
		}
	}
}

As the name suggests, this function fetches Triangles from our spatial grid, for a given rectangular area: `x`, `y`, width (`w`), and height (`h`). These are added to an array we pass into the function named `candidates` (again, like our quadtree fetching!). We start by setting a variable called cIndex to 0. cIndex is our current index in our candidates array. Next, we zero our `candidates` array (expected to be of size MAX_WORLD_TRIANGLES), as well as an array called `added`.

The `added` array is very important, as it is what we'll use to filter out duplicate Triangles in a very efficient manner. As each of our Triangles has an id, we'll use this as the index in the array to find out if a Triangle has been added. As this is random access within an array, it is very fast! Our array is also a uint8_t, which takes up very little memory. Next, we prepare our fetch loop. We'll call a function named clipFetchBounds, that will convert our world-space into grid-space, and ensure it is constrained correctly. We'll then loop from `x1` to `x2` and `y1` to `y2` through our grid cells, grabbing the Triangles from the affected cell, and adding them to our `candidates` list.

As we do this, we test if the value in our `added` array at the index of the Triangle's `id` is set, and only add the Triangle to `candidates` if not. We then set the value in `added`, to mark it as such. Our return list now contains 100% unique Triangles.

So, in summary, for a given world-space area, we're converting to grid-space, and building a unique list of all the Triangle that are contained within.

That's it for adding and fetching Triangles to our spatial grid. As you can see, it's a pretty simple process. We'll finish off the other functions in spatialGrid.c now, starting with increaseTriCapacity:

static void increaseTriCapacity(SpatialGridCell *cell)
{
	int n;

	n = cell->triCapacity + INITIAL_CAPACITY;

	SDL_LogMessage(SDL_LOG_CATEGORY_APPLICATION, SDL_LOG_PRIORITY_DEBUG, "Increasing cell tri capcity: %d -> %d", cell->triCapacity, n);

	if (cell->triCapacity == 0)
	{
		cell->triangles = malloc(sizeof(Triangle *) * n);
	}
	else
	{
		cell->triangles = resize(cell->triangles, sizeof(Triangle *) * cell->triCapacity, sizeof(Triangle *) * n);
	}

	cell->triCapacity = n;
}

As expected, all this does is increase the size of the `triangles` array the specified SpatialGridCell (`cell`). We saw a similar function in the Gunner tutorial, with its quadtree.

Over now to clipAddBounds:

static void clipAddBounds(int *x1, int *y1, int *x2, int *y2)
{
	*x1 /= CELL_WIDTH;
	*y1 /= CELL_HEIGHT;
	*x2 /= CELL_WIDTH;
	*y2 /= CELL_HEIGHT;

	*x1 = MAX(*x1, 0);
	*y1 = MAX(*y1, 0);
	*x2 = MIN(*x2, (GRID_SIZE - 1));
	*y2 = MIN(*y2, (GRID_SIZE - 1));
}

As we learned earlier, this function is responsible for converting world-space coordinates into grid-space coordinates. We ensure that the values of `x1`, `y1`, `x2`, and `y2` don't exceed our grid bounds. CELL_WIDTH and CELL_HEIGHT are calculated in spatialGrid.c:

#define ZONE_WIDTH      (SCREEN_WIDTH * 5)
#define ZONE_HEIGHT     (SCREEN_HEIGHT * 5)
#define GRID_SIZE        50
#define CELL_WIDTH       (ZONE_WIDTH / GRID_SIZE)
#define CELL_HEIGHT      (ZONE_HEIGHT / GRID_SIZE)

At most, our spatial grid will be 5 screens wide and high (ZONE_WIDTH and ZONE_HEIGHT). That's quite big, and none of the zones in our game are anywhere near as big as that! We can see that our CELL_WIDTH and CELL_HEIGHT is based on the zone being split into 50 cells horizontal and vertical. Base on a SCREEN_WIDTH of 1600 and SCREEN_HEIGHT of 900, this gives us cells of 160 x 90 pixels.

clipFetchBounds acts much the same, but takes a width (`w`) and height (`h`) to work with, as part of its calcuation:

static void clipFetchBounds(int *x1, int *y1, int *x2, int *y2, int w, int h)
{
	*x1 /= CELL_WIDTH;
	*y1 /= CELL_HEIGHT;
	*x2 = *x1 + (w / CELL_WIDTH) + 1;
	*y2 = *y1 + (h / CELL_HEIGHT);

	*x1 = MAX(*x1, 0);
	*y1 = MAX(*y1, 0);
	*x2 = MIN(*x2, (GRID_SIZE - 1));
	*y2 = MIN(*y2, (GRID_SIZE - 1));
}

`x1` and `y1 will already have been set to world-space prior to being passed into the function, leaving us only to convert the rest.

That's all for spatialGrid.c for now. In Part 2, we'll be adding support for entities. Let's move on now to the remainder of the updates.

First, over to world.c, where we've updated initWorld:

void initWorld(void)
{
	// snipped

	numTriangles = 0;
}

We're setting a new variable here call numTriangles to 0. This will be used to track the number of triangles we have so far created for our world.

Next, we've updated loadWorld:

void loadWorld(int zoneNum)
{
	int       i, numLines, n;
	Triangle *t;
	FILE     *fp;
	char      filename[MAX_FILENAME_LENGTH];

	// snipped

	for (t = head.next; t != NULL; t = t->next)
	{
		addTriToSpatialGrid(t);
	}
}

After loading our world, we loop through all the triangles in our list and add them to our spatial grid, via a call to addTriToSpatialGrid.

Simple! Now for drawWorld. Once again, those who have followed the quadtree tutorial will be right at home with the following change:

void drawWorld(SDL_FPoint *camera)
{
	int        i, n;
	SDL_Vertex v;
	Triangle  *candidates[MAX_WORLD_TRIANGLES], *t;

	n = 0;

	getAllTrisFromSpatialGrid(camera->x, camera->y, SCREEN_WIDTH / 2, SCREEN_HEIGHT, candidates);

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

Here, we're calling getAllTrisFromSpatialGrid, passing over the camera's `x` and `y` position as the top-left coordinates, and half the screen width, and its full height, as the width and height of the rectangle we want to grab our triangles for. These are placed into the `candidates` Triangle array that we pass over to the function. Next, we loop through all the candidate Triangles, stopping when we either hit a NULL or our counter (`i`) reached MAX_WORLD_TRIANGLES. Everything else remains the same.

So, we'll only pull back the Triangles that fit into the rectangle of our current camera view, and render just those. This is much better than rendering the entire world view.

Over next to spawnTriangle:

static Triangle *spawnTriangle(void)
{
	Triangle *t;

	if (numTriangles >= MAX_WORLD_TRIANGLES)
	{
		SDL_LogMessage(SDL_LOG_CATEGORY_APPLICATION, SDL_LOG_PRIORITY_CRITICAL, "No free triangles (%d)", MAX_WORLD_TRIANGLES);
		exit(1);
	}

	t = malloc(sizeof(Triangle));
	memset(t, 0, sizeof(Triangle));
	tail->next = t;
	tail = t;

	t->id = numTriangles++;

	// snipped
}

Now, when calling this method, we're checking if we've not exceeded our limit of MAX_WORLD_TRIANGLES. Then, when creating a Triangle, we're assigning its `id` to the next in the sequence of numTriangles.

That's our updates to world.c concluded. From here on, we're just going to be looking mostly at the updates we've made elsewhere, to make use of our spatial grid. To begin with, let's look at the change to entities.c, and the touchWorld function:

static void touchWorld(Entity *e)
{
	int       i, n;
	Triangle *candidates[MAX_WORLD_TRIANGLES], *t;

	getAllTrisFromSpatialGrid(e->position.x - ENTITY_WORLD_RADIUS, e->position.y - ENTITY_WORLD_RADIUS, ENTITY_WORLD_RADIUS * 2, ENTITY_WORLD_RADIUS * 2, candidates);

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

As with rendering our world, when it comes to testing the collisions of the entities against the world, we're making use of the getAllTrisFromSpatialGrid function. For our entities, we're going to pass across a rectangle of fixed size. Here, ENTITY_WORLD_RADIUS is defined as 32. We're then looping through all the Triangles, as before.

We are doing much the same in the touchWorld function in bullets.c:

static void touchWorld(Bullet *b)
{
	int       i;
	Triangle *candidates[MAX_WORLD_TRIANGLES], *t;

	getAllTrisFromSpatialGrid(b->position.x - BULLET_WORLD_RADIUS, b->position.y - BULLET_WORLD_RADIUS, BULLET_WORLD_RADIUS * 2, BULLET_WORLD_RADIUS * 2, candidates);

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

	// snipped
}

Here, we're using a fixed size of 8 for BULLET_WORLD_RADIUS.

While we're here, we've also made small change to drawBullets, to improve the rendering:

void drawBullets(SDL_FPoint *camera)
{
	Bullet    *b;
	SDL_FPoint drawPosition;
	SDL_Rect   r;

	for (b = head.next; b != NULL; b = b->next)
	{
		r.x = b->position.x - b->radius / 2;
		r.y = b->position.y - b->radius / 2;
		r.w = r.h = b->radius;

		r.x -= camera->x;
		r.y -= camera->y;

		if (collision(r.x, r.y, r.w, r.h, 0, 0, SCREEN_WIDTH / 2, SCREEN_HEIGHT))
		{
			drawPosition = b->position;
			drawPosition.x -= camera->x;
			drawPosition.y -= camera->y;

			drawModel(b->model, drawPosition, b->angle);
		}
	}
}

Now, before calling drawModel, we're testing if the bullet is visible to the camera that is making the call. We do this by testing a rectangular area that the bullet will occupy, and then checking if that rectangle is on screen. A small, micro optimisation.

Over to pods.c, where we've tweaked canAddPod:

static uint8_t canAddPod(int x, int y)
{
	Triangle *candidates[MAX_WORLD_TRIANGLES], *t;
	int       i, px, py;

	getAllTrisFromSpatialGrid(x - ADD_POD_RADIUS, y - ADD_POD_RADIUS, x + ADD_POD_RADIUS, y + ADD_POD_RADIUS, candidates);

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

	return 1;
}

Once again, we're using the getAllTrisFromSpatialGrid function here, so that we don't test every Triangle in the world, when we only need to examine a small area.

Before we finish up, let's look at another small optimisation, over in particles.c, in the drawParticles function:

void drawParticles(SDL_FPoint *camera)
{
	int        n;
	double     rot;
	SDL_Vertex v;
	SDL_FPoint points[3];
	Particle  *p;

	SDL_SetRenderDrawBlendMode(app.renderer, SDL_BLENDMODE_ADD);

	for (p = head.next; p != NULL; p = p->next)
	{
		if (collision(p->position.x, p->position.y, 1, 1, camera->x, camera->y, SCREEN_WIDTH / 2, SCREEN_HEIGHT))
		{
			// snipped
		}
	}

	SDL_SetRenderDrawBlendMode(app.renderer, SDL_BLENDMODE_BLEND);
}

As with our bullets, we're going to test if the Particle is inside the camera view before drawing it.

With all that done, it's over to zone.c, for the final step. We just need up tweak initZone:

void initZone(void)
{
	memset(&zone, 0, sizeof(Zone));

	// snipped

	initSpatialGrid();

	initEntities();

	initBullets();

	// snipped
}

With a call to initSpatialGrid, we're all good to go!

That wasn't too bad, was it? In fact, it was probably a lot easier than one first imagined. The only tricky bit about using a spatial grid is ensuring that we don't return the same Triangle more than once. There were a number of way we could've handled this, but I feel that using an array to determine if the Triangle is already being returned is the best bet. The worst approach would be to loop through our array, to see if the Triangle exists in the return list, before adding it. That would lead to a considerable performance hit.

In the next part of our spatial grid implementation, we'll be adding in the entites. They, too, can be subject to a large number of collision checks, and so we want to reduce these as much as possible. As with our Triangles, our entities will also use an id / array combination.

Purchase

The source code for all parts of this tutorial (including assets) is available for purchase, as part of the SDL2 tutorials bundle:

From itch.io