« Back to tutorial listing

— Simple 2D adventure game —
Part 7: Fog of war

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

Introduction

Adding fog of war to our dungeon will add a sense of mystery to it, and also encourage the player to explore. Not being able to see all the items, etc. scattered throughout right away means we need to go and have a good look around. We'll achieve this in our dungeon by overlaying black squares on squares that hasn't been explored or sighted. These squares will brighten as we get closer to them.

Extract the archive, run cmake CMakeLists.txt, followed by make, and then use ./adventure07 to run the code. You will see a window open like the one above, showing the prisoner on a tiled background. Use WASD to move around. You'll find the dungeon is now dark and possibly a bit more difficult to navigate until you uncover all the squares. There are items to be found through exploring. Close the window to exit.

Inspecting the code

The principle behind our fog of war implementation is to overlay a series of black squares over the seen, on tiles that are yet to be explored or uncovered. The alpha value of these squares will change depending on our distance from them (but once lit, they won't darken as we move away from them). Line of sight will play a part in uncovering the tiles. A new file has been created to handle all the fog of war logic, called fogOfWar.c. We'll come to it in just a moment. For now, let's start by looking at structs.h, where we've added a new struct:

typedef struct {
	int lightLevel;
	int hasSolidEntity;
} VisData;

The visData struct (visibility data) will be used to hold the light level of the tile, as well as a flag to say whether the tile has a solid entity within it. We'll show why this has been done in a bit. Now, let's look at the new file, fogOfWar.c. It's not a big file, less than 150 lines. We'll start from the top:

static VisData visData[MAP_WIDTH][MAP_HEIGHT];
static AtlasImage *fogOfWarRect;

We're declaring two static variables, one to hold the visData and one to hold the AtlasImage of our black square (fogOfWarRect). Our visData is an array the same size as our map data, so the two can line up. We could've turned the map data itself into a structure like this, holding the tile, the visibility, and the hasSolidEntity, but I've chosen to keep them separate, so their roles can be better defined. It also means that removing the fog of war doesn't mean needing to change the entire map structure.

The first function we encounter is initFogOfWar:

void initFogOfWar(void)
{
	fogOfWarRect = getAtlasImage("gfx/misc/fogOfWarRect.png", 1);
}

Like many of our init functions, this one is simple - it merely loads the AtlasImage for the black square we want to use. A note on this. The reason we're using a black square image instead of SDL's built-in rectangle drawing is to take advantage of SDL2's sprite batching, so that all our render operations can be done in as few draw calls as possible.

Our next function is where the main fog of war logic come into play. updateFogOfWar is called each time the player makes a move. Have a quick look at its definition below and then we'll go through it:

void updateFogOfWar(void)
{
	int x, y, mx, my, lightLevel;
	double distance;
	Entity *e;

	for (x = 0 ; x < MAP_WIDTH ; x++)
	{
		for (y = 0 ; y < MAP_HEIGHT ; y++)
		{
			visData[x][y].hasSolidEntity = 0;
		}
	}

	for (e = dungeon.entityHead.next ; e != NULL ; e = e->next)
	{
		if (e->solid)
		{
			visData[e->x][e->y].hasSolidEntity = 1;
		}
	}

	for (y = -VIS_DISTANCE ; y <= VIS_DISTANCE ; y++)
	{
		for (x = -VIS_DISTANCE ; x <= VIS_DISTANCE ; x++)
		{
			mx = player->x + x;
			my = player->y + y;

			if (mx >= 0 && my >= 0 && mx < MAP_WIDTH && my < MAP_HEIGHT && visData[mx][my].lightLevel < 255 && hasLOS(player->x, player->y, mx, my))
			{
				distance = getDistance(player->x, player->y, mx, my);

				if (distance <= 1)
				{
					lightLevel = 255;
				}
				else
				{
					lightLevel = 255 - (255 * (distance / VIS_DISTANCE));
				}

				visData[mx][my].lightLevel = MAX(lightLevel, visData[mx][my].lightLevel);
			}
		}
	}
}

The first thing we want to do is prepare our visData array. We want to update each visData to say whether the related map square contains a solid entity. We do this by first setting all the hasSolidEntity flags to 0 (false). Next, we loop through all the entities in the dungeon and set the hasSolidEntity to 1 at their location, if they are solid. Now, to be fair this is somewhat unnecessary in our dungeon right now. The only solid entity that moves is the player. Everything else is static. We could very well just let the positions in the initFogOfWar step. Still, it allows scope for things being removed, such as doors or other barriers. Doing it this way also avoids a lot of micromanagement when it comes to adding and removing things.

The next thing we want to do is perform the visibility check. We do this by testing a square area around the player. VIS_DISTANCE is defined as 8, so we'll be checking the player's position +-8 squares in each direction. On each iteration of the loops, we assign mx and my the player's x and y, plus the value of our x and y loops values, to test the entire square area. This will mean we're testing a total of 289 squares (-8 to +8 includes 0, meaning 17 squares on each axis, for 17 * 17). That's quite a lot of squares to check. We want to first test we're inside the map bounds, so ensure that mx and my fall within those. Next, we test that the light level of the square isn't already at full brightness. This will help to avoid a pointless line of sight test that comes next. Should the bounds and light level checks pass, we'll call hasLOS (has line of sight) passing in the player's position and the position of the square we want to check. We'll come to this function in a moment. Should the LOS check return true, update the light level of the affected tile.

When updating the tile's light level, we want to find out how far away it is. We do this by calling getDistance(), passing over the player's location and the location of the tile (getDistance is a simple function that we'll look into at the end of this tutorial). Now that we know the distance, we'll update the light level accordingly. If the distance is within 1 square of our player, we'll set the light level to maximum (255). Otherwise, we'll adjust according the how far away it is. Dividing the distance by VIS_DISTANCE will give our a value between 0 and 1. We then multiply 255 by this value, to get a value between 0 and 255, then finally subtract this value from 255, assigning the result to a variable called lightLevel. This might sound complicated, so here's a quick breakdown:

The further away the tile, the higher the value of lightLevel will be. The value of lightLevel will increase by 31.875 with each tile, up to 255. The values will therefore go 31.875, 63.75, 95.625, etc. Subtracting this value from 255 will give a final light level for a tile. A tile far away will have a light level of 0 (full dark), while a tile midway will have a value of 127.5 (half bright).

The last thing we do is set the value of lightLevel to the tested visData's lightLevel, but only if it's higher. We do this by calling the MAX macro to determine which value is higher and therefore which to use.

With the light levels covered, let's turn to the hasLOS (has line of sight) function. This is basically Bresenham's line algorithm (https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm), with an additional collision check performed:

static int hasLOS(int x1, int y1, int x2, int y2)
{
	int dx, dy, sx, sy, err, e2;

	dx = abs(x2 - x1);
	dy = abs(y2 - y1);

	sx = (x1 < x2) ? 1 : -1;
	sy = (y1 < y2) ? 1 : -1;
	err = dx - dy;

	while (1)
	{
		e2 = 2 * err;

		if (e2 > -dy)
		{
			err -= dy;
			x1 += sx;
		}

		if (e2 < dx)
		{
			err += dx;
			y1 += sy;
		}

		if (x1 == x2 && y1 == y2)
		{
			return 1;
		}

		if (dungeon.map.data[x1][y1] >= TILE_WALL || visData[x1][y1].hasSolidEntity)
		{
			return 0;
		}
	}

	return 0;
}

I'll not go into the detail of how the line drawing algorithm works; those who are interested can read the Wikipedia page linked above. What we're interested in are the two return statements (the final return statement will never be reached, and only exists to keep the compiler happy). Going from top to bottom, starting with the first return. We want to return 1 if x1 and y1 are equal to x2 and y2, effectively meaning that the line of sight was not blocked. The next return is one that could return 0. This will happen if while tracing the line we hit a tile that is a wall. We do this by simply checking if the tile at x1,y2 is a TILE_WALL or higher.

However, we're also checking to see if the line has hit a solid entity. Earlier, we inserted all the solid entities in the visData structure, and here we're testing the value. If either we hit a wall or a solid entity, our line of sight will be considered blocked. Now, a word on the entity caching. It's not strictly required. We could, if we wanted, simply loop through all the entities in the dungeon, testing the solid ones if they intersect the line, and go from there. Or we could grab just the known solid ones and test those. Again, there would be nothing wrong with either of these approaches and they would work just fine. The trouble is that doing it that way, even with a small number of entities in the dungeon, would lead to thousands of checks (literally) each time doFogOfWar is called. It's unlikely you would notice a dip in performance at all, but seeing the thousands of checks happening would give you pause, and performing the entity checks this way helps to cut down on the execution time a significant amount.

That's the logic for our fog of war done. Now we coming to the rendering phase. It's quite similar to the map rendering:

void drawFogOfWar(void)
{
	int x, y, mx, my, alpha;

	for (y = 0 ; y < MAP_RENDER_HEIGHT ; y++)
	{
		for (x = 0 ; x < MAP_RENDER_WIDTH ; x++)
		{
			mx = dungeon.camera.x + x;
			my = dungeon.camera.y + y;

			if (mx >= 0 && my >= 0 && mx < MAP_WIDTH && my < MAP_HEIGHT)
			{
				alpha = 255 - visData[mx][my].lightLevel;

				SDL_SetTextureAlphaMod(fogOfWarRect->texture, alpha);

				blitAtlasImage(fogOfWarRect, (x * TILE_SIZE) + dungeon.renderOffset.x, (y * TILE_SIZE) + dungeon.renderOffset.y, 0, SDL_FLIP_NONE);
			}
		}
	}

	SDL_SetTextureAlphaMod(fogOfWarRect->texture, 255);
}

We loop through the dungeon's render width and height, work out which map index we're after with consideration for the camera position, and assign those values to mx and my. After the map bounds test, we extract the light level from the visData, substracting this value from 255, and assigning the result to a variable named alpha. We're using this value to affect the alpha of the fogOfWarRect, using SDL_SetTextureAlphaMod. A value of 255 will means the square is rendered completely opaque, a value of 0 will mean it is transparent. This ultimately means that visData with a lightLevel of 255 will be totally bright, while 0 will be in complete darkness. We finally draw the black square using blitAtlasImage. Once our loop is finished, we need to reset the alpha of our texture atlas to 255, using SDL_SetTextureAlphaMod.

We're done with fogOfWar.c now, so we can move on and see how the functions we've defined are using in the game. Starting with player.c, we need only add a single line to movePlayer to process our fog of war:

static void movePlayer(int dx, int dy)
{
	int x, y;
	Entity *e;

	x = player->x + dx;
	y = player->y + dy;

	x = MAX(0, MIN(x, MAP_WIDTH - 1));
	y = MAX(0, MIN(y, MAP_HEIGHT - 1));

	if (dungeon.map.data[x][y] >= TILE_GROUND && dungeon.map.data[x][y] < TILE_WALL)
	{
		e = getEntityAt(x, y);

		if (e == NULL || e->solid == SOLID_NON_SOLID || e == player)
		{
			player->x = x;
			player->y = y;

			dungeon.camera.x = x;
			dungeon.camera.x -= (MAP_RENDER_WIDTH / 2);
			dungeon.camera.x = MIN(MAX(dungeon.camera.x, 0), MAP_WIDTH - MAP_RENDER_WIDTH);

			dungeon.camera.y = y;
			dungeon.camera.y -= (MAP_RENDER_HEIGHT / 2);
			dungeon.camera.y = MIN(MAX(dungeon.camera.y, 0), MAP_HEIGHT - MAP_RENDER_HEIGHT);

			moveDelay = 5;
		}

		if (e != NULL && e->touch != NULL)
		{
			e->touch(e, player);
		}

		updateFogOfWar();
	}
}

Each time the player (successfully) moves, we're calling updateFogOfWar(). That's all we need to do to make the dungeon's fog of war update as we move around. Similarly, drawing the fog of war is very simple. This is done in dungeon.c, in the draw function:

static void draw(void)
{
	drawMap();

	drawEntities();

	drawFogOfWar();

	drawHud();
}

We want to draw our fog of war after we've done the map and entities, so that both the map and the things in the dungeon are affected by it. Drawing the fog of war before the entities would mean the entities are always drawn fully lit, whether the tile is in complete darkness or not.

Before we finish up, we'll see how some other functions are handled. Our initFogOfWar function is called during initDungeon, in dungeon.c:

void initDungeon(void)
{
	Entity *e;

	initMap();

	initFogOfWar();

	initEntities();

	initPlayer();

	initHud();

	initInventory();

	initItem("Rusty key", 51, 23, "gfx/entities/rustyKey.png");

	initGoldCoin(1, 19);

	initGoldCoin(27, 0);

	initGoldCoin(19, 9);

	initGoldCoins(7, 3);

	e = initItem("Eyeball", 0, 0, "gfx/entities/eyeball.png");

	initChest(21, 14, e);

	e = initItem("Red potion", 0, 0, "gfx/entities/redPotion.png");

	initChest(18, 14, e);

	dungeon.renderOffset.x = (SCREEN_WIDTH - (MAP_RENDER_WIDTH * TILE_SIZE)) / 2;
	dungeon.renderOffset.y = 20;

	app.delegate.logic = &logic;
	app.delegate.draw = &draw;
}

We're also scattering some other items about, for the player to find and to demonstrate how the fog of war works. Finally, here's the getDistance function, that can be found in util.c:

int getDistance(int x1, int y1, int x2, int y2)
{
	int x, y;

	x = x2 - x1;
	y = y2 - y1;

	return sqrt(x * x + y *y);
}

A rather standard method for getting the distance between two points.

We've taken another major step forward with building the framework for our game. Next, we'll look at how to produce some dialog boxes, so that other characters in our adventure game can speak to us, those providing a means to give hints and increase engagement.

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: