« Back to tutorial listing

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

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

Introduction

In the first part, we setup our spatial grid, and also added in all the Triangles for our world. In this next part, we're going to do the same for the entities.

Extract the archive, run cmake CMakeLists.txt, followed by make, and then use ./versus13 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. Once again, 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

There is a lot of overlap with the approach to adding in our world Triangles and adding in our Entities, so this part won't take very long, at all.

Let's turn first to defs.h:

#define MAX_ENTITIES        256

We're setting up a new define for the maximum number of entities in our game.

Next, to structs.h:

struct Entity
{
	int        id;
	uint8_t    type;

	// snipped

	Entity *next;
};

As with our Triangles, we've added in an `id` field.

Next, we've updated SpatialGridCell:

typedef struct
{
	int        numTris;
	int        numEnts;
	int        triCapacity;
	int        entCapacity;
	Triangle **triangles;
	Entity   **entities;
} SpatialGridCell;

To support adding our entities, we've added in a handful of new fields. numEnts is the number of entities in the cel, entCapacity is the maximum number of entities to add, and `entities` is an array of the entities themselves. This array can be resized, as needed. So, very much like adding in Triangles.

Now for the changes to spatialGrid.c. We've added in several new functions, all of which will be quite similar to the existing one for Triangles.

Starting with addEntToSpatialGrid:

void addEntToSpatialGrid(Entity *e)
{
	SpatialGridCell *cell;
	int              x, y, x1, y1, x2, y2;

	x1 = e->position.x - e->radius;
	y1 = e->position.y - e->radius;
	x2 = e->position.x + e->radius;
	y2 = e->position.y + e->radius;

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

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

			if (cell->numEnts == cell->entCapacity)
			{
				increaseEntCapacity(cell);
			}

			cell->entities[cell->numEnts++] = e;
		}
	}
}

This function adds an Entity (`e`) to our spatial grid. We determine the entity's square area, using its `radius` (and set the results into variables called `x1`, `y1`, `x2`, `y2`), clip the bounds, and then add the entity to the required cells. As with our Triangles, we increase the cell capacity, as needed.

Over to removeEntFromSpatialGrid next:

void removeEntFromSpatialGrid(Entity *e)
{
	int x, y, x1, y1, x2, y2;

	x1 = e->position.x - e->radius;
	y1 = e->position.y - e->radius;
	x2 = e->position.x + e->radius;
	y2 = e->position.y + e->radius;

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

	for (x = x1; x <= x2; x++)
	{
		for (y = y1; y <= y2; y++)
		{
			removeEntity(e, &grid[x][y]);
		}
	}
}

This function removes an entity from our spatial grid. It basically operates like adding, but in reverse. We determine which cells the entity currently occupies, and then call removeEntity for each cell, passing over the entity (`e`) and the cell itself (`grid` indexed by `x` and `y`).

removeEntity is a simple function:

static void removeEntity(Entity *e, SpatialGridCell *cell)
{
	int i, n;

	n = cell->numEnts;

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

	qsort(cell->entities, n, sizeof(Entity *), entityComparator);
}

All this function does is searches for the entity in the cell's `entities` array, and sets it to NULL. It also decreases the numEnts count. Finally, we sort the entities, to push the non-null entries to the top of the array, using qsort, and a function called entityComparator. Once again, this is similiar behaviour to removing entities in our quadtree.

Next up, we have getAllEntsFromSpatialGrid:

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

	cIndex = 0;

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

	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->numEnts; i++)
			{
				if (!added[cell->entities[i]->id])
				{
					candidates[cIndex++] = cell->entities[i];

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

Already, it should be clear that this is more or less the same as fetching Triangles from our spatial grid, except we're doing so for Entities. The same duplicate filtering is performed, using the entity's `id`.

That's really all there is to it! The only major difference is that we can remove entities from our grid, whereas Triangles will remain there for the duration of our match. Before we finish up, we'll look at the two remaining functions. Starting with increaseEntCapacity:

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

	n = cell->entCapacity + INITIAL_CAPACITY;

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

	if (cell->entCapacity == 0)
	{
		cell->entities = malloc(sizeof(Entity *) * n);
	}
	else
	{
		cell->entities = resize(cell->entities, sizeof(Entity *) * cell->entCapacity, sizeof(Entity *) * n);
	}

	cell->entCapacity = n;
}

At the end of the day, just the same as increaseTriCapacity, only that it handles entities.

Finally, we have entityComparator:

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

	e1 = *((Entity **)a);
	e2 = *((Entity **)b);

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

As we can see, this pushes all non-null entities to the top of the array, null entities to the end.

That's all we need to add for spactialGrid.c. We can now look at how we're making use of our new function. None of this is complicated.

First up, let's turn to entities.c, where we've updated doEntities:

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

	prev = &zone.entityHead;

	for (e = zone.entityHead.next; e != NULL; e = e->next)
	{
		removeEntFromSpatialGrid(e);

		// snipped

		if (!e->dead)
		{
			addEntToSpatialGrid(e);
		}
		else
		{
			// snipped
		}

		prev = e;
	}
}

For each entity, we're removing them from the spatial grid. We do this because the entity will move during their `tick` call, and so we want to update its position within the grid. The entity might also be flagged as `dead` during its `tick`. Once all our entity logic is complete, we test if it's not `dead`, and call addEntToSpatialGrid to insert it. As we'll see in a bit, this will prevent dead entities from being eligible for drawing and collision checks.

Nice and simple.

Next up, we have the update to touchOthers:

static void touchOthers(Entity *e)
{
	int     i;
	Entity *candidates[MAX_ENTITIES], *other;

	getAllEntsFromSpatialGrid(e->position.x, e->position.y, e->radius * 2, e->radius * 2, candidates);

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

Here, we're pulling out all the entities from our spatial grid that are in the same vicinity as the passed in entity (`e`). This is much like how we do the collision checks for the world, except we're fetching from our list of entities. Everything else remains the same. Again, this won't pull back dead entities, since they have been removed from the grid.

We've also updated drawEntities:

void drawEntities(SDL_FPoint *camera)
{
	int     i;
	Entity *candidates[MAX_ENTITIES], *e;

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

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

Absolutely no surprises here. We're once again querying our spatial grid, to grab all the entities that are found in our current camera view, and drawing them.

Just a couple of other functions for us to consider. First up, we've made a change to spawnEntity:

Entity *spawnEntity(int type)
{
	Entity *e;

	e = malloc(sizeof(Entity));
	memset(e, 0, sizeof(Entity));

	e->id = getFreeId();
	e->type = type;

	zone.entityTail->next = e;
	zone.entityTail = e;

	return e;
}

We're now assigning the entity's `id`. However, unlike when we assign an id for our world Triangles, we're doing via a call to a function named getFreeId:

static int getFreeId(void)
{
	int     i;
	Entity *e;
	uint8_t ids[MAX_ENTITIES];

	memset(ids, 0, sizeof(ids));

	for (e = zone.entityHead.next; e != NULL; e = e->next)
	{
		ids[e->id] = 1;
	}

	for (e = respawnHead.next; e != NULL; e = e->next)
	{
		if (e->respawnInterval > 0)
		{
			ids[e->id] = 1;
		}
	}

	for (i = 0; i < MAX_ENTITIES; i++)
	{
		if (!ids[i])
		{
			return i;
		}
	}

	SDL_LogMessage(SDL_LOG_CATEGORY_APPLICATION, SDL_LOG_PRIORITY_CRITICAL, "No free entities (%d)", MAX_ENTITIES);
	exit(1);
}

This function returns an unused id for our entities. This works a bit like our spatial grid uniqueness check, except that we're adding into our array the ids of both the current entities AND the entities that are waiting to respawn. Entities that are waiting to respawn will be reserving their ids, so that they cannot be hijacked by a newly created entity. With our used ids flagged, we loop through our array, searching for the first that isn't in use (0).

Our game allows for a maximum of 256 unique entities, a number that, with our setup, we wouldn't actually get near.

Finally, we've updated bullets.c, with a changee to touchEntities:

static void touchEntities(Bullet *b)
{
	int     i;
	Entity *candidates[MAX_ENTITIES], *e;

	getAllEntsFromSpatialGrid(b->position.x - 1, b->position.y - 1, 3, 3, candidates);

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

As with our entity-entity collision check, our bullet is calling getAllEntsFromSpatialGrid, to fetch all the nearby entities. This will help to reduce the number of entities that a single bullet needs to perform a collision check against.

All done! We've fully implemented our spatial grid, allowing us to add and retreive Triangles and Entities. Again, while our game is nice and simple, and such a step might not be entirely necessary, it remains good practice. And 800 collision checks is preferrable to 70,000 (a reduction of almost 99%).

At this point, one can see that our Entity and Triangle linked lists are redundant; we could load both of these into fixed sized arrays, and loop through them at way, instead. Rather than refactor our code at this point, we'll leave things as it is. An exercise for the reader could be to remove the linked list and rely solely on the arrays, so as to discover the advantages and disadvantages of working in such a way. The debate over linked lists vs arrays is a well documented one.

Before to put together our proper game loop, we'll add in one more thing - "aliens". These entities will form hazards in our zone, that can kill the player or otherwise cause them a bit of upset.

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