« Back to tutorial listing

— Simple 2D quest game —
Part 6: Towns, part 1

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

Introduction

We're now able to fully explore our world, by taking boats around to the islands that have been generated. It would be nice if there were more to discover, however. So, in this part we'll be introducing towns, that the player can find by exploring. Ultimately, these towns will be where the player will receive quests, and talk to NPCs. For now, they'll just be entities on the map.

Extract the archive, run cmake CMakeLists.txt, followed by make, and then use ./quest06 to run the code. As before, you can move around with the WASD control scheme. Explore the various islands as you see fit. Each island will have at least one town. The bigger the island, the more towns it will contain. Towns currently cannot be interacted with, and will block player movement. Note how some towns are placed within forests and mountain ranges, and have therefore carved out a path through them, in order for them to become reachable. When you're finished, close the window to exit.

Inspecting the code

Adding in our towns is an extremely simple task; they are nothing more than solid entities that we will be adding to the islands, at random points. The most interesting part will be when we add in towns that reside within forest and other inaccessible locations.

We'll be focusing our attention mainly on overworldGen.c for this part, as it's where we are creating the towns and roads. A quick note on the naming schemes. You will notice how the town entity itself is called "settlement". This is because when it comes to entering the towns and dealing with all their logic, I wanted to call the file town.c. As such, I didn't want to have this file dealing with both the town exploration logic, as well as the entity, and so I chose to use a synonym for the entity (a settlement being a place where people make their homes, build communities, etc.). However, we'll continue to refer to towns as "towns", rather than settlements. Additionally, I wanted to avoid having both town.c and towns.c, as that would be confusing.

With that explained, let's look first at generateOverworldWorker:

static int generateOverworldWorker(void *p)
{
	double **elevation, **moisture;
	long     then;

	// snipped

	addTowns(elevation);

	addAdventurer();

	// snipped

	return 0;
}

We're calling a new function named addTowns, passing over the elevation data when we do so:

static void addTowns(double **elevation)
{
	Island *is;
	Entity *e;
	int     ok, w, h, n, i, x, y;
	SDL_Point dest;

	for (is = game.overworld.islandHead.next; is != NULL; is = is->next)
	{
		n = 1 + (is->size / 10000);

		dest = is->lowPoint;

		for (i = 0; i < n; i++)
		{
			ok = 0;
			w = is->bounds.x2 - is->bounds.x1;
			h = is->bounds.y2 - is->bounds.y1;

			e = initEntity("Settlement");

			do
			{
				e->x = is->bounds.x1 + rand() % w;
				e->y = is->bounds.y1 + rand() % h;

				ok = game.map->data[e->x][e->y] >= MT_LAND;
			} while (!ok);

			if (game.map->data[e->x][e->y] != MT_LAND)
			{
				addRoad(e, &dest, elevation);

				for (x = -1; x <= 1; x++)
				{
					for (y = -1; y <= 1; y++)
					{
						game.map->data[e->x + x][e->y + y] = MT_LAND;
					}
				}
			}

			dest.x = e->x;
			dest.y = e->y;
		}
	}
}

This function is effectively doing two things - adding towns to each island, and generating roads to make them accessible. We'll come to the roads in a bit. First off, this function begins looping through all our islands, dividing their size by 10,000 (just an arbitary number I've chosen..!) and adding that to 1. This will give us the number of towns we wish to add to the island (as `n`). The bigger the island, the more towns will be added. Note that each island contains at least 1 town.

We then create our settlement entity, and attempt to randomly place it somewhere within the island's bounding box. So long as the tile is a land tile are better, we're good. Otherwise, we'll continue to loop until we find a good location. Next, we check which type of tile we placed the town in. If it's not a land tile (meaning it must be forest or mountains), we'll need to construct a road for it, and also flatten the surrounding area, so that it can be reached, and (importantly) bypassed.

Nothing exactly complex to understand. Note how towns in forests and mountains will be calling addRoad, passing across a variable called `dest` (an SDL_Point), which will either be the island's lowest point, or the location of the previous town. This helps us to guarantee that the new town will always be reachable. Let's look next at the addRoad function:

static void addRoad(Entity *e, SDL_Point *dest, double **elevation)
{
	int   x, y;
	Node *n;

	n = createAStarRoute(e->x, e->y, dest->x, dest->y, elevation);

	while (n != NULL)
	{
		for (x = -1; x <= 1; x++)
		{
			for (y = -1; y <= 1; y++)
			{
				game.map->data[n->x + x][n->y + y] = MT_LAND;
			}
		}

		n = n->next;
	}

	resetAStar();
}

As its name implies, this function builds a "road" for the town. We do this with the help of A* pathfinding (we won't be going into this here, as we've seen it in SDL2 Rogue, SDL2 Strategy, and the Isometric adventure game). The starting location will be our town (`e`), with the destination as `dest`. Once again, there's nothing particularly difficult to understand about this function. Of note is that when we're creating our A* route, we're passing over the elevation data. We'll see why in a moment. With our route generated, we're then carving out the area around each node step, so that there is a larger space to move around in; we don't want it to be a single space path, as this can be difficult to navigate, and also looks less natural. Each tile is converted to MT_LAND, to allow the player to access it.

We're almost done..! As you can see, placing the towns on the map was very simple, as they are just entities that must be placed on land. Before wrapping up, let's look at the A* pathfinding logic, starting with buildRouteMap:

static void buildRouteMap(int sx, int sy, int ex, int ey)
{
	int   x, y, count;
	Node *start;
	Node *currentNode;
	Node *newNode;

	// snipped

	while (1)
	{
		for (y = -1; y <= 1; y++)
		{
			for (x = -1; x <= 1; x++)
			{
				// snipped

				if (!isBlocked(newNode->x, newNode->y))
				{
					newNode->g = currentNode->g + 10;

					if (elevation[newNode->x][newNode->y] > elevation[currentNode->x][currentNode->y])
					{
						newNode->g += 8;
					}

					newNode->h = 10 * (abs(newNode->x - ex) + abs(newNode->y - ey));

					newNode->f = newNode->g + newNode->h;
				}

				// snipped
			}
		}

		// snipped
	}
}

Our elevation data comes into play when we're scoring our nodes. If the elevation data of the node we're inspecting has a higher elevation than the one we're currently on, we'll increase its score, to make it less desirable as a potential route step. This is simply to make our resulting roads look a little more natural, since they will be making an effort to move downhill. This can lead to some interesting paths through mountains, etc. rather than straight routes and sharp right-angles (note that isBlocked returns 1 if the tile at the given location is water).

One other function we should look at is trimRoute, which is called before the route data is returned from createAStarRoute:

static void trimRoute(void)
{
	Node *n, *prev;
	int   trim;

	trim = 0;

	prev = &routeHead;

	for (n = routeHead.next; n != NULL; n = n->next)
	{
		if (game.map->data[n->x][n->y] < MT_FOREST)
		{
			trim = 1;
		}

		if (trim)
		{
			prev->next = n->next;

			n = prev;
		}

		prev = n;
	}
}

Here, we're trimming down the route once we hit land tiles. There's no point in returning the full route once it becomes accessible to the player; only the nodes that reside in forest and mountains need to be considered.

And that's our towns and roads added in. A lot easier than you'd think, for sure!

Our overworld is more or less done now. We can explore islands, sail boats, and find towns scattered around the lands. What we should do now is find a way to enable us to actually visit these towns, by walking into them. Before we do all that, we'd best make sure that the player actually has something to explore when they enter the town proper. So, in the next part we'll be looking into town generation itself, as a change from the overworld.

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