« Back to tutorial listing

— A simple turn-based strategy game —
Part 5: Enemies and simple AI

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

Introduction

It's time to introduce an AI enemy into the game. Ultimately, our game will feature 5 different ghost types, all with differing AI profiles. Our first ghost, a white one, will be a passive ghost; a bit of a dummy, that will just move around randomly, and not respond to any hostile actions. This will allow us to observe how his AI works, without fear of retribution.

Extract the archive, run cmake CMakeLists.txt, followed by make, and then use ./sdl2TBS05 to run the code. You will see a window open like the one above, showing three wizards in a small room, surrounded by walls, as well as a white ghost. Move the mages around as normal. Press Space to end your turn and allow the AI to take its. Notice how the ghost moves around randomly. Once the AI turn is finished, control will return to the player. Once you're finished, close the window to exit.

Inspecting the code

There are quite a number of bits and pieces we need to add in to our game to support the AI turn, some more involved than others. Let's start with defs.h, where we've added in some new enums:

enum {
	SIDE_NONE,
	SIDE_PLAYER,
	SIDE_AI
};

We've added in SIDE_AI, that will indicate that the entity is on the side of the AI.

enum {
	ET_WORLD,
	ET_MAGE,
	ET_GHOST
};

ET_GHOST will tell us that the entity is a ghost.

enum {
	AI_PASSIVE
};

AI_PASSIVE falls within a new group of enums that will be used as the AI profile of a ghost. Right now, we only have AI_PASSIVE, that will apply to ghosts that wander around and do little else.

enum {
	TURN_PLAYER,
	TURN_AI
};

Finally, we've added two new enums: TURN_PLAYER and TURN_AI, to be used to identify whose turn it is to control the game.

Moving over to structs.h now, where we've also made a few changes:

typedef struct {
	int ap, maxAP;
	int moveRange;
	struct {
		int type;
		SDL_Point goal;
	} ai;
} Unit;

Unit now has an embedded struct called `ai`, that will hold the `type` of ai (AI_PASSIVE, for example) and an SDL_Point called `goal`. `goal` will be used to determine the point on the map to which the AI is moving towards. We'll see more on this in a bit.

Stage has also been tweaked:

typedef struct {
	unsigned int entityId;
	MapTile map[MAP_WIDTH][MAP_HEIGHT];
	Entity entityHead, *entityTail;
	Entity *currentEntity;
	Node routeHead;
	int turn;
	int animating;
	int showRange;
	struct {
		int x;
		int y;
	} selectedTile;
} Stage;

We've added in a new field called `turn`, that will be used to determine whose turn it is (TURN_PLAYER or TURN_AI).

Now we come to ai.c. This is a whole new compilation unit that will house all the code for controlling our AI. There's quite a lot of go through, so we'll work from top to bottom.

Starting with initAI:

void initAI(void)
{
	addAIUnits();
}

Right now, we're just calling addAIUnits. We'll come to this at the end. Next up is doAI:

void doAI(void)
{
	Unit *u;

	if (stage.currentEntity != NULL)
	{
		u = (Unit*) stage.currentEntity->data;

		if (u->ap != 0)
		{
			switch (u->ai.type)
			{
				case AI_PASSIVE:
					doPassive();
					break;

				default:
					u->ap = 0;
					break;
			}
		}
		else
		{
			nextUnit();
		}
	}
	else
	{
		endTurn();
	}
}

doAI is called each loop of the game while it's the AI's turn. We first start by testing if the current entity is not NULL. This is important, in case there are no AI units. Next, we extract the unit data from the entity and test that it has AP remaining, to take an action. If so, we'll test the type of AI this ghost is. Right now, we only have one AI type, and so we call doPassive (we'll come to this next). In the case of an unhandled type, we simply set the unit's `ap` to 0, so we don't get stuck with the unit not doing anything.

If the AI doesn't have any AP remaining, we call a function called nextUnit, to move onto the next AI unit. Ultimately, if the current entity was NULL when we entered into the function, we're calling endTurn. The reason for not aggressively ending the turn and moving onto the next unit in this function is to allow for the actions of the current unit to be processed by our main loop. We could get into weird situations if, for example, the AI attacked, ran out of AP, and then ended its turn, throwing control back to the player while in the middle of an attack. We want to ensure that the AI has truly run out of AP and completed its actions at the start of the loop before moving on.

Moving now onto doPassive:

static void doPassive(void)
{
	moveRandom();
}

A simple function - it just calls moveRandom:

static void moveRandom(void)
{
	int x, y, atGoal, attempts;
	Unit *u;

	u = (Unit*) stage.currentEntity->data;

	attempts = 25;

	atGoal = stage.currentEntity->x == u->ai.goal.x && stage.currentEntity->y == u->ai.goal.y;

	x = u->ai.goal.x;
	y = u->ai.goal.y;

	do
	{
		if (atGoal)
		{
			x = rand() % MAP_WIDTH;
			y = rand() % MAP_HEIGHT;
		}

		createAStarRoute(stage.currentEntity, x, y);

		attempts--;

		atGoal = 1;
	}
	while (stage.routeHead.next == NULL && attempts > 0);

	u->ai.goal.x = x;
	u->ai.goal.y = y;

	if (stage.routeHead.next == NULL)
	{
		u->ap = 0;
	}
}

As the name suggests, this function chooses a random location on the map for the AI to move to. We start by extracting the unit data from the current entity, and then testing to see if the AI unit is already at its goal, by comparing its current `x` and `y` to its ai goal's `x` and `y`. A variable called `attempts` is set to 25. This is to control the number of movement attempts, so that the game doesn't get stuck in an infinite loop (are you beginning to see how these things can happen a lot during turn-based strategy game development?). We assign this to a variable called atGoal. We then assign the AI's `goal` to variables named `x` and `y`. Next, we setup a do-while loop, to attempt to reach our goal. For each iteration of the loop, we test to see if the atGoal flag is set. If so, we'll choose a random location on the map, and update the `x` and `y` variables. We'll then attempt to create an A* route to the destination, decrement `attempts`, and set atGoal to 1.

The while loop will continue so long as we have no route to move to and also the value of `attempts` is greater than 0. Setting the atGoal flag to 1 at the end of the loop means that if the loop repeats, we will select a new position on the map to move to.

Regardless of the outcome, once we exit the loop we assign the AI's `goal` as the last `x` and `y` values we had in the loop. It is unlikely that the AI will get permanently stuck this way, unless it is in a completely walled off area, with literally nowhere to move to. Finally, we test to see if an A* path was created. If not, we set the unit's `ap` to 0, so that it will immediately end its turn, being unable to move.

So, in conclusion, the AI will attempt to move randomly around the map and will end its turn if, after a number of unsuccessful tries, it can't find a place to move to.

Next, we have the nextUnit function:

static void nextUnit(void)
{
	int found;

	found = 0;

	do
	{
		stage.currentEntity = stage.currentEntity->next;

		found = stage.currentEntity == NULL || stage.currentEntity->side == SIDE_AI;
	}
	while (!found);

	if (stage.currentEntity != NULL)
	{
		updateUnitRanges();
	}
}

This function is responsible for moving to the next AI unit. We setup a do-while loop, that will move through our entity list, starting from the current entity and moving to the next. We reassign stage's currentEntity to the next one in the chain upon each iteration. The loop will continue until currentEntity is either NULL (the end of the list) or we encounter another entity with a `side` value of SIDE_AI. We shouldn't assume that an AI unit follows directly after another.

Exiting the loop, we test to see currentEntity is not NULL and then call updateUnitRanges (this function assumes that Stage's currentEntity is not NULL).

Finally, we come to addAIUnits:

static void addAIUnits(void)
{
	Entity *e;
	Unit *u;
	int x, y, ok;

	e = initEntity("White Ghost");

	e->side = SIDE_AI;

	do
	{
		x = rand() % MAP_WIDTH;
		y = rand() % MAP_HEIGHT;

		ok = isGround(x, y) && getEntityAt(x, y) == NULL;
	}
	while (!ok);

	e->x = x;
	e->y = y;

	u = (Unit*) e->data;

	u->ai.goal.x = x;
	u->ai.goal.y = y;
}

This looks a bit like addPlayerUnits, except that we're only created one entity (White Ghost), setting its `side` as SIDE_AI, and also defaulting its AI `goal` position to its starting position, so that it moves to a new goal immediately.

That's it for our AI. As stated earlier, it's very simple, but we now have room to expand with different ghosts and AI units.

Now, let us look at ghosts.c. This is where we'll be defining all our ghosts, much the same as with the mages. The first function is initGhost:

Unit *initGhost(Entity *e, char *filename)
{
	Unit *u;

	e->type = ET_GHOST;
	e->solid = 1;
	e->texture = getAtlasImage(filename, 1);

	u = initUnit(e);

	return u;
}

Again, this will look quite similiar to initMage. The function takes an Entity and a filename for a texture. It sets the entity's `type` as ET_GHOST, makes it `solid`, assigns the `texture`, and then calls initUnit before returning the Unit data.

initWhiteGhost follows:

void initWhiteGhost(Entity *e)
{
	Unit *u;

	STRCPY(e->name, "White Ghost");

	u = initGhost(e, "gfx/units/whiteGhost.png");
	u->ap = u->maxAP = 2;
	u->moveRange = 12;

	u->ai.type = AI_PASSIVE;
}

Not a lot to talk about here, as we've seen it before. THe only major thing to mention is that we're setting the unit's `ai`'s `type` as AI_PASSIVE, so that we know how to control the ghost during the doAI function.

Something we now need to consider in light of what the AI is doing is how to control the AI's movement range. The player can only choose to move into squares that are flagged as inMoveRange. The AI doesn't do this; it is allowed to pick any spot on the map and make its way over. This isn't what we want. You will have noticed that the White Ghost has a movement range of 12. So, what can we do?

If we turn to aStar.c, we've added in a new function called trimRoute:

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

	trim = 0;

	prev = &stage.routeHead;

	for (n = stage.routeHead.next ; n != NULL ; n = n->next)
	{
		if (!stage.map[n->x][n->y].inMoveRange)
		{
			trim = 1;
		}

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

			n = prev;
		}

		prev = n;
	}
}

This function will take our route and remove the points once they fall outside of the move range. We start by assigning a variable called `trim` to 0. We then begin a for-loop, iterating over our A* path. At each iteration of the loop, we test to see if the current node is over a MapTile whose inMoveRange is not set. If so, we'll set `trim` to 1. We then test if `trim` is set, and remove the current node if so (with standard linked-list removal logic).

This means that, for our AI, we can choose a location on the map and tell it to plot a route there, before then limiting the distance that can be walked. And due to the way we have written our AI, the ghost will continue on towards its goal everytime it is its turn (note: this might be harder to appreciate on smaller maps).

To make use of our new trimRoute function, we only need to update createAStarRoute:

void createAStarRoute(Entity *e, int x, int y)
{
	if (!isBlocked(x, y))
	{
		resetAStar();

		buildRouteMap(x, y, e->x, e->y);

		createRoute(e->x, e->y);

		trimRoute();
	}
}

After calling createRoute, we're calling trimRoute, to remove all the nodes that are invalid.

Turning next to units.c, we've updated resetUnits:

void resetUnits(void)
{
	Entity *e;
	Unit *u;

	stage.currentEntity = NULL;

	for (e = stage.entityHead.next ; e != NULL ; e = e->next)
	{
		if ((stage.turn == TURN_PLAYER && e->type == ET_MAGE) || (stage.turn == TURN_AI && e->type == ET_GHOST))
		{
			u = (Unit*) e->data;

			u->ap = u->maxAP;

			if (stage.currentEntity == NULL)
			{
				stage.currentEntity = e;

				updateUnitRanges();
			}
		}
	}
}

Previously, we were resetting all the AP for all our units. However, we now only want to reset the AP for the units belonging to whosever turn it is. We therefore only reset the AP for mages on the player's turn, and the AP for ghosts on the AI's turn. Note: we're assuming in this game that the player only controls mages and the AI only controls ghosts. If we had many different types of units, we would want to test the side the unit belonged to.

We're almost done! We need only update stage.c and a few miscellaneous functions. Let's update initStage first:

void initStage(void)
{
	memset(&stage, 0, sizeof(Stage));

	initEntities();

	initUnits();

	initHud();

	initMap();

	generateMap();

	initPlayer();

	initAI();

	app.delegate.logic = logic;

	app.delegate.draw = draw;
}

After calling initPlayer, we're now calling initAI.

Next up, we want to tweak the `logic` function:

static void logic(void)
{
	int wasAnimating;

	wasAnimating = stage.animating;

	if (!stage.animating)
	{
		if (stage.turn == TURN_PLAYER)
		{
			doHud();

			doPlayer();
		}
		else
		{
			doAI();
		}
	}

	doEntities();

	doUnits();

	stage.animating = stage.routeHead.next != NULL;

	app.mouse.visible = !stage.animating && stage.turn == TURN_PLAYER;

	if (wasAnimating && !stage.animating)
	{
		updateUnitRanges();
	}
}

We're now testing whose turn it is before calling various functions. If it's the player's turn, we want to call doHud and doPlayer. If it's the AI's turn, we just call doAI. This means that the AI can do nothing while its the player's turn, and the player nothing while its the AI's turn. Additionally, we're ensuring that the mouse is only visible during the player's turn.

We've also updated the `draw` function:

static void draw(void)
{
	drawMap();

	drawAStarPath();

	drawEntities();

	if (stage.turn == TURN_PLAYER)
	{
		drawHud();
	}
}

We only call drawHud on the player's go, so things don't look messy or confusing when the AI is taking its turn.

Lastly, we've updated endTurn:

void endTurn(void)
{
	stage.turn = !stage.turn;

	stage.showRange = SHOW_RANGE_NONE;

	resetUnits();
}

Since the turn can now flip between the player and the AI, we're inverting Stage's `turn` value. Since we have TURN_PLAYER and TURN_AI, with values of 0 and 1 respectively, this means the value will swap between 0 and 1 upon each call to endTurn.

Before finishing up, let's look at some miscellaneous functions we've added, and changes we've made. Starting with map.c:

int isWall(int x, int y)
{
	return !isInsideMap(x, y) || stage.map[x][y].tile < TILE_GROUND;
}

We added in a function called isWall, to check if a map location is considered a wall. A location is considered a wall if its outside the map bounds or the MapTile's tile value is less than TILE_GROUND. This will come in useful later on.

A minor update to drawEntities comes next:

void drawEntities(void)
{
	Entity *e;
	int x, y, size;

	for (e = stage.entityHead.next ; e != NULL ; e = e->next)
	{
		e->draw(e);
	}

	if (!stage.animating && stage.turn == TURN_PLAYER)
	{
		size = 48 + sin(selectedUnitPulse) * 8;

		x = MAP_TO_SCREEN(stage.currentEntity->x);
		y = MAP_TO_SCREEN(stage.currentEntity->y);

		blitScaled(selectedUnitTexture, x, y, size, size, 1);
	}
}

We only want to draw the selected unit indicator when its the player's turn, and so we've added an additional clause to our if test, after checking if stage's animating flag is not set.

Wow! Things are really starting to take shape now. We've got AP management, movement ranges, and basic AI-controlled units, as well as turn management. What we're missing is combat. It's about time we took to eliminating these pesky ghosts. So, in the next part we'll look at adding in some basic combat, where we'll shoot the ghosts to destroy them.

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: