« Back to tutorial listing

— Simple 2D quest game —
Part 3: Island capture

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

Introduction

A part of our game will be the ability to "discover" islands and towns, in the same way that occurs in RPGs such as Skyrim; upon reaching a new land or settlement, the player is informed of this new discovery. In this part, we're going to look into how we can do this with our islands. It provides quite an interesting challenge, as there are a number of approaches that could be taken, but really only one that is practical for us to implement.

Extract the archive, run cmake CMakeLists.txt, followed by make, and then use ./quest03 to run the code. Open the Quest Log (Tab) to view the new world map, which will now display the islands in different colours. This is just a temporary measure, which we'll be changing in a later part. When you're finished, close the window to exit.

Inspecting the code

As stated before, there are a number of ways in which we could appoach this problem. All of them rely on using a flood fill technique to isolate our islands from the sea. It's what comes next that is the issue. The "wrong" approach would be to hold a separate map data structure, with the ids of the islands. This would be a huge waste of memory, which is something we shouldn't be doing. Our overworld map is 512x512. On a 64-bit system, an int is 4 bytes, which means we'll consume over 1MB memory, just to store this data. Even if we use unsigned chars, we're still looking at over 262k. This, again, is wasteful (can you tell by now that I grew up programming on memory constrained computers?).

Another approach could be to use bounding boxes, to separate our islands from one another. This will work up until a point, and will then begin to fail (more on his later). A more extreme measure could be to attempt to generate a polygon out of the island's outline. Not only is this very hard to do, but has the issue of needing to then determine whether the player's position lies within the polygon. As the resulting polygon could be composed of dozens of points this would kill performance, as each time the player moves we'd need to perform this check (if the island has not already been discovered).

So, we'll be combining bounding boxes with a technique called Run-Length Encoding. We'll create a multi-dimensional array using the width of our island, and a linked list at every point, describing where the y values start and finish. Consider the image below:

Moving from left to right (along the x axis) we can see that the green squares in the column can be defined in RLE as:

0: 6-8
1: 1-2, 5-9
2: 1-9, 14-14
3: 1-10, 13-14
etc.

This will mean that if we're at 2,5, we'll be standing on our island. Likewise if we were standing at 3,13. However, if we're at 3,11, we're not on our island, as this point isn't described by our RLE data. It's important to note that we're only considering the LAND of the island, and not any bodies of water (excluding shallows) that might be contained within it. Trying to include these could lead to errors. As you can see, RLE allows us to accurately describe our island data, without storing every single point.

Now we know how our RLE will work, let's dive into the code. Starting with structs.h. First, we've made a BoundingBox struct:

struct BoundingBox
{
	int          x1;
	int          y1;
	int          x2;
	int          y2;
};

This simply holds the 2D coordinates of the bounds (`x1`, `y1`, `x2`, and `y2` being the corners) of our box. Next, we have RLE (Run-length Encoding):

struct RLE
{
	int  start;
	int  end;
	RLE *next;
};

RLE simply contains two values, `start` and `end`, these being where the y values of our island at a given x point.

Finally, we have Island itself:

struct Island
{
	int         size;
	BoundingBox bounds;
	SDL_Color   color;
	RLE		   *rle;
	Island     *next;
};

We're storing the `size`, `bounds`, `color`, and RLE data for our island (which can also be part of a linked list).

We've also updated Overworld, to hold our Islands:

typedef struct
{
	long         seed;
	Map          map;
	Island       islandHead, *islandTail;
	SDL_Texture *miniMapTexture;
} Overworld;

islandHead and islandTail will form our linked list.

Now, over to islands.c, in the gen directory. This is where we'll do all the work to extract our island data. Buckle up, as there is quite a lot to get through. As stated earlier, we'll be using flood fill technique to pick out our islands, before then extracting the RLE data from each one.

We'll start with initIslands:

void initIslands(double **e)
{
	elevation = e;

	game.overworld.islandTail = &game.overworld.islandHead;

	prepareIslandData();

	collectIslands();

	freeIslandData();
}

This function is the entry point to collecting our island data. It accepts the elevation data we used for creating the overworld as a parameter (`e`), as it's something we will need to work with. Other than that, this function sets up our islands linked list, and then delegates to a number of other functions. We'll come to these in turn.

First, let's look at prepareIslandData:

static void prepareIslandData(void)
{
	int x, y;

	data = (int **)malloc(WORLD_WIDTH * sizeof(int *));

	for (x = 0; x < WORLD_WIDTH; x++)
	{
		data[x] = (int *)malloc(WORLD_HEIGHT * sizeof(int));
	}

	for (x = 0; x < WORLD_WIDTH; x++)
	{
		for (y = 0; y < WORLD_HEIGHT; y++)
		{
			if (game.oveworld.map.data[x][y] >= MT_SHALLOWS)
			{
				data[x][y] = LAND_VALUE;
			}
			else
			{
				data[x][y] = SEA_VALUE;
			}
		}
	}
}

Nothing remarkable here - we're mallocing an array called `data`, of the same size as the world, and then looping over the world data itself (`data` is a static global within this compilation unit). If we encounter a tile in the world data that is shallows or higher (i.e., it's land), we'll mark the data point as LAND_VALUE. Otherwise, it will be marked as SEA_VALUE. What this does is create a lookup map of what is strictly land and what is strictly water.

Next, we come to the collectIslands function. This, again, isn't too difficult to understand:

static void collectIslands(void)
{
	int     x, y, id;
	Island *is;
	double  r, g, b;

	id = 0;

	for (x = 0; x < WORLD_WIDTH; x++)
	{
		for (y = 0; y < WORLD_HEIGHT; y++)
		{
			if (data[x][y] == LAND_VALUE)
			{
				is = createIsland(x, y, id);

				if (is != NULL)
				{
					collectRLE(is, id);

					hsvToRGB(id * 60, 1, 1, &r, &g, &b);

					is->color.r = r;
					is->color.g = g;
					is->color.b = b;

					id++;
				}
				else
				{
					islandToOcean(x, y, id);
				}
			}
		}
	}
}

We're looping over our data array, searching for any tile that is set as LAND_VALUE. When we encounter one, we call another function named createIsland, passing over the current `x` and `y` position. Notice that we're passing over `id`, too. `id` will act as the identifier of the island. If we successfully create an island (`is`), we'll then collect the island's RLE data, and give the island itself a colour (via use of hsvToRGB, found in util.c). `id` is then incremented, so the next island created will have a new id. If we fail to create an Island, we'll convert that island into sea, instead. As we'll see in a bit, we might fail to create an island because the land mass is simply too small. We don't want tiny islands in our game, so we give them up to the sea.

Now for the createIsland function. This is where we actually create our island:

static Island *createIsland(int x, int y, int to)
{
	Node  *n;
	Island *is;
	int    size;
	BoundingBox bounds;

	memset(&fillHead, 0, sizeof(Node));
	fillTail = &fillHead;

	addFillNode(x, y, LAND_VALUE);

	bounds.x1 = WORLD_WIDTH;
	bounds.y1 = WORLD_HEIGHT;
	bounds.x2 = 0;
	bounds.y2 = 0;

	size = 0;

	while (fillHead.next != NULL)
	{
		n = fillHead.next;

		bounds.x1 = MIN(n->x, bounds.x1);
		bounds.y1 = MIN(n->y, bounds.y1);
		bounds.x2 = MAX(n->x, bounds.x2);
		bounds.y2 = MAX(n->y, bounds.y2);

		data[n->x][n->y] = to;

		if (game.oveworld.map.data[n->x][n->y] == MT_LAND)
		{
			size++;
		}

		addFillNode(n->x + 1, n->y, LAND_VALUE);
		addFillNode(n->x - 1, n->y, LAND_VALUE);
		addFillNode(n->x, n->y + 1, LAND_VALUE);
		addFillNode(n->x, n->y - 1, LAND_VALUE);

		fillHead.next = n->next;

		free(n);
	}

	if (size >= MIN_ISLAND_SIZE)
	{
		is = malloc(sizeof(Island));
		memset(is, 0, sizeof(Island));

		is->bounds = bounds;
		is->size = size;

		game.overworld.islandTail->next = is;
		game.overworld.islandTail = is;

		return is;
	}

	return NULL;
}

At first glance it seems that there's quite a lot going on here, but it's much more simple than that. In summary, this function is performing a flood fill, starting from the `x` and `y` position passed into the function, and converting all surrounding data points with a value of LAND_VALUE to the value of `id`. This will therefore convert all the land data points for an island over to the island's `id`. At the same time, we'll work out what the island's bounding box is, by calculating the minimum and maximum `x` and `y` values of our current fill node, and setting them as the `x1`, `y1`, `x2`, and `y2` of bounds. At the same time, each corresponding tile in the overworld's map data with a value of MT_LAND will count towards our `size` variable.

With our land data points converted over and our bounding box calculated, we then check the value of `size`. If it's at least as big as MIN_ISLAND_SIZE, we'll use all the data we've collected so far to actually create an Island, using malloc. The created Island will have its `bounds` and `size` set, will be added to the Overworld's island list, and then the Island returned. If we're unable to create an Island, we'll return NULL. This will result in collectIslands (which calls this function) filling the island with water, to remove it from the overworld.

So far, so good. All of what we've seen so far should make sense; we are, at the end of the day, using a series of flood fills to flip data points over, thereby isolating islands from the sea, and also from one another.

Now we can look at the collectRLE function. This is the most complicated function in islands.c:

static void collectRLE(Island *is, int id)
{
	int  x, y, start, n, l;
	RLE *rle, *tail;

	n = 0;

	l = (is->bounds.x2 - is->bounds.x1) + 1;

	is->rle = malloc(sizeof(RLE) * l);

	for (x = is->bounds.x1; x <= is->bounds.x2; x++)
	{
		memset(&is->rle[n], 0, sizeof(RLE));

		tail = NULL;

		start = -1;

		for (y = is->bounds.y1; y <= is->bounds.y2; y++)
		{
			if (data[x][y] != id || y == is->bounds.y2)
			{
				if (start != -1)
				{
					if (tail == NULL)
					{
						rle = &is->rle[n];
					}
					else
					{
						rle = malloc(sizeof(RLE));
						tail->next = rle;
					}

					memset(rle, 0, sizeof(RLE));
					rle->start = start;
					rle->end = y;

					tail = rle;

					start = -1;
				}
			}
			else if (start == -1)
			{
				start = y;
			}
		}

		n++;
	}
}

As the name implies, this function collects the RLE data for an Island. RLE in our Island is essentially an array of linked lists, spanning the width of the Island. We start by mallocing enough RLE space for the Island's width, by subtracting the Island's bounding box's `x2` from its `x1` (and assigning the result to `l`).

We then start checking every data point in the current column, creating strips of start and end points. Whenever we come to a data point that is not the id of our island, we will create a new RLE object, and add it to the current column's RLE list. We start by setting `start` to -1, and then walking down the column. If we hit a data point that has a value with the same id of our island and `start` is currently set to -1, we'll set `start` to the current `y` value. The next time we encounter a data point that is NOT the id of the island (or we're at the end of the column), we'll create an RLE object. We then set `start` to -1, so the process can begin over for the rest of the column. This will mean that `start` contains the y value where a strip of land begins, and `y` where it currently ends.

If that sounds a bit complicated, consider the 16x16 blue and green island near the top of the page, and reconsider what the code is doing. Again, this loop is creating strips of values for each column.

With our RLE data now collected, we now know the exact area covered by our Island. There's just one more function we'll look at in this file, and that's islandToOcean:

static void islandToOcean(int x, int y, int from)
{
	Node *n;

	memset(&fillHead, 0, sizeof(Node));
	fillTail = &fillHead;

	addFillNode(x, y, from);

	while (fillHead.next != NULL)
	{
		n = fillHead.next;

		data[n->x][n->y] = SEA_VALUE;

		game.overworld.map.data[n->x][n->y] = MT_WATER;

		addFillNode(n->x + 1, n->y, from);
		addFillNode(n->x - 1, n->y, from);
		addFillNode(n->x, n->y + 1, from);
		addFillNode(n->x, n->y - 1, from);

		fillHead.next = n->next;

		free(n);
	}
}

As you can see, this simply uses a flood fill to convert a data value to water. `from` will be the id of the island.

That's islands.c all done with, so we can now look at the rest of the changes. First, over to overworldGen.c, where we've updated generateOverworldWorker:

static int generateOverworldWorker(void *p)
{
	double   maxElevation, maxMoisture, e, m, f1, f2;
	int      x, y;
	double **elevation, **moisture;
	long     then;

	// snipped

	initIslands(elevation);

	freePerlin(elevation, WORLD_HEIGHT);
	freePerlin(moisture, WORLD_HEIGHT);

	SDL_LogMessage(SDL_LOG_CATEGORY_APPLICATION, SDL_LOG_PRIORITY_INFO, "Overworld generated in %ldms\n", SDL_GetTicks() - then);

	worldGenDone();

	return 0;
}

Here, we're calling initIslands, and passing over the `elevation` data for use with the island detection.

Finally, let's move over to questLog.c, where we can witness the fruits of our labour. The function highlightIslands is used to draw the islands in their selected colours:

static void highlightIslands(SDL_Rect *dest)
{
	SDL_Rect src;
	int      i;
	RLE     *rle;
	Island  *is;

	for (is = game.overworld.islandHead.next; is != NULL; is = is->next)
	{
		src.w = (MAP_SCALE * 2);

		for (i = 0; i <= (is->bounds.x2 - is->bounds.x1); i++)
		{
			for (rle = &is->rle[i]; rle != NULL; rle = rle->next)
			{
				src.x = (is->bounds.x1 + i) * MAP_SCALE;
				src.x += dest->x;

				src.y = rle->start * MAP_SCALE;
				src.y += dest->y;

				src.h = (rle->end - rle->start) * MAP_SCALE;

				drawRect(src.x, src.y, src.w, src.h, is->color.r, is->color.g, is->color.b, 128);
			}
		}
	}
}

Here, we're simply looping over our islands, and drawing their RLE data. Is this done by calculating the island's width (bound's `x2` - `x1`) and then walking through the RLE linked list. We're rendering a rectangle at this point (`src`), with the height being the current RLE's `start` - `end` points. So, if we have a series of RLEs with `start` and `end` points of 0-14, 18-45, 90-101, then we'll be rendering rectangles of heights 14, 27, and 11, from the RLE's `start` point. This results in the island's land being filled in exactly as we want.

And we're done! That was quite a lot to get through, but it was worth it, so that we could detect and separate out our islands.

In the end, you're likely wondering if this RLE is making a lot of difference to our memory usage. Well, while counting the size of the RLE data (with the help of sizeof), I found that on average 10k was being used. While this is still higher than I would like, it's a whole lot better than 1MB..!

You might still be wondering if simply using the bounding boxes would be better, since it would've saved us a lot of work. The problems can be illustrated by looking at the following two images:

As you can see, several of the islands are overlapping one another. In some cases, you can get away with it - the top left overlap wouldn't matter, as while the bounding boxes overlap, no land areas do. However, pay attention to the red area in the top right of the two overlapping bounding boxes. Which island are you on? It depends on how you order them. You could attempt to say that the smallest bounding box is likely the one to pick, but that will mean that walking into the red zone on the big island will mark you as being on the smaller. The opposite is also true. In the end, bounding boxes can help to narrow down which island we MIGHT be on, but it isn't as accurate as it needs to be. RLE solves this problem, and also allows us to highlight the entire island body in our Quest Log.

Phew! That was quite a lot to get through. Thankfully, this is one of the more trickier problems to solve; most of everything else from here on out will not be nearly as difficult. So, if you made it through all of that (in particular, the RLE) good job!

It's time for us to add our Robot to the game, so that we can walk around the world properly, rather than just scroll the map around. So, in the next part we'll be adding it in, so that the player can begin exploring.

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