« Back to tutorial listing

— Creating a simple roguelike —
Part 6: A* Pathfinding

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

Introduction

Our monsters can now move towards us, but don't do it very well. What would be better is if they were able to navigate the dungeon floor, moving around obstacles, etc., and also not doing anything until we move within range. A* pathfinding and an alert status on our monsters would suit our needs very well. We'll be implementing both in this part.

Extract the archive, run cmake CMakeLists.txt, followed by make, and then use ./rogue06 to run the code. You will see a window open like the one above, showing our main character in a dungeon environment. Use the same controls as before to move around and battle the mice. The mice will be dormant until you come near them, after which they will start chasing you. If you move out of their line of sight, they'll move to where they last saw you, then start to wander the dungeon randomly, looking for you. Once you're finished, close the window to exit.

Inspecting the code

The main thing that we've added to this part is the A* pathfinding. To support it, we've made some updates to structs.h:

struct Node {
	int x;
	int y;
	int g;
	int f;
	int h;
	int closed;
	Node *parent;
	Node *next;
};

Node is a structure that will be used with the A* pathfinding. `x` and `y` are the locations of the node within our dungeon, `g`, `f`, and `h` are the scores that are assigned to this Node. `closed` tells us that the Node has been checked and shouldn't be processed any further. `parent` is the parent of this node, and `next` is the next Node in our linked list. All these will be explained in more detail in the A* implementation.

We've also added in some new fields to Monster:

typedef struct {
	int hp, maxHP;
	int minAttack;
	int maxAttack;
	int defence;
	int alert;
	int visRange;
	SDL_Point patrolDest;
} Monster;

`alert` is a field to specify whether the Monster is active. They won't move unless they are. visRange is the distance at which the player can be detected. patrolDest is a position to which the monster will move, while patrolling or moving about randomly.

Now, let's look at the A* code. It all lives in a file called aStar.c. Be aware that A* is quite a complicated system and we won't be covering fully all the ins and outs of it (for example, we're not building the full route tree and are only interested in the first move to take). An in-depth article is available on Wikipedia: https://en.wikipedia.org/wiki/A*_search_algorithm.

initAStar is our first function:

void initAStar(void)
{
	memset(&nodeHead, 0, sizeof(Node));
	nodeTail = &nodeHead;
}

We're preparing our Node linked list by memsetting our nodeHead and assigning the nodeTail to the nodeHead.

resetAStar is next. Again, it's a rather simple function:

void resetAStar(void)
{
	Node *n;

	while (nodeHead.next != NULL)
	{
		n = nodeHead.next;
		nodeHead.next = n->next;
		free(n);
	}

	nodeTail = &nodeHead;
}

We're using a while-loop to clear our nodes. We're checking if nodeHead's `next` is not NULL. If not, we're going to grab a reference to its `next` (as `n`), assign the nodeHead's `next` to `n`'s `next`, and then free `n`. We'll keep doing this until we hit the end of the list, before then resetting nodeTail to nodeHead.

Now for something more complicated - addNodeToOpenList:

static void addNodeToOpenList(Node *node)
{
	Node *n;

	if (node->f != -1)
	{
		for (n = nodeHead.next ; n != NULL ; n = n->next)
		{
			if (n->x == node->x && n->y == node->y)
			{
				if (node->f < n->f)
				{
					n->f = node->f;
					n->g = node->g;
					n->h = node->h;
					n->closed = 0;
					n->parent = node->parent;
				}

				free(node);

				return;
			}
		}

		nodeTail->next = node;
		nodeTail = node;
	}
	else
	{
		free(node);
	}
}

This function takes a pointer to a Node as an argument. The idea behind this function is to add a Node to our node list or replace an existing one, if the `f` score is better than the old one.

We first check that `node`'s `f` score is not -1. If it isn't, we'll search our node list for a node (`n`) that matches `node`'s `x` and `y` values. If found, we'll test whether `node`'s `f` score is lower than `n`'s `f` score (meaning it is better). If so, we'll replace `n`'s data with `node`'s, and set its `closed` flag to 0. We'll then free `node` and return. If we don't find a match, we'll add `node` to our list. Finally, if `node`'s `f` score was -1, we'll free it and do nothing.

The next function is getSmallestNode:

static Node *getSmallestNode(void)
{
	Node *smallest, *n;

	smallest = n = NULL;

	for (n = nodeHead.next ; n != NULL ; n = n->next)
	{
		if (!n->closed && n->f != -1 && (smallest == NULL || n->f < smallest->f))
		{
			smallest = n;
		}
	}

	return smallest;
}

The idea behind this function is to find a non-closed node with the smallest `f` score. The code therefore is quite simple: we use a for-loop to move through our node list, testing each node to see if it is not closed and that its `f` score is not -1. If we find one matching these conditions, it will become the smallest node if `smallest` is NULL or `n`'s `f` score is smaller than the existing `smallest`'s f. At the end of the function, we'll return `smallest` (which may be NULL).

Now onto the big function - buildRouteMap.

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

	start = malloc(sizeof(Node));
	memset(start, 0, sizeof(Node));
	start->x = sx;
	start->y = sy;
	addNodeToOpenList(start);

	currentNode = start;

	count = 0;

	while (1)
	{
		for (y = -1 ; y <= 1; y++)
		{
			for (x = -1 ; x <= 1; x++)
			{
				if (x == 0 && y == 0)
				{
					continue;
				}

				if (currentNode->x + x < 0 || currentNode->y + y < 0 || currentNode->x + x >= MAP_WIDTH || currentNode->y + y >= MAP_HEIGHT)
				{
					continue;
				}

				newNode = malloc(sizeof(Node));
				memset(newNode, 0, sizeof(Node));

				newNode->x = currentNode->x + x;
				newNode->y = currentNode->y + y;

				if (!isBlocked(newNode->x, newNode->y))
				{
					if (x != 0 && y != 0)
					{
						newNode->g = currentNode->g + 14;
					}
					else
					{
						newNode->g = currentNode->g + 10;
					}

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

					newNode->f = newNode->g + newNode->h;
				}
				else
				{
					newNode->f = -1;
					newNode->g = -1;
					newNode->h = -1;
				}

				newNode->parent = currentNode;

				addNodeToOpenList(newNode);

				if (++count >= MAP_HEIGHT * MAP_WIDTH)
				{
					return;
				}
			}
		}

		currentNode = getSmallestNode();

		if (!currentNode)
		{
			break;
		}

		currentNode->closed = 1;

		if (currentNode->x == ex && currentNode->y == ey)
		{
			break;
		}
	}
}

This function is responsible for searching for a path towards our goal. As squares in our map are tested, they will be added our node list and processed. We'll go through this function in stages.

The function takes 4 parameters - `sx`, the starting x; `sy`, the starting y; `ex`, the ending x (or target x); and `ey`, the ending y. We begin by mallocing and memsetting a Node called `start`, assigning its `x` and `y` members as the values of the `sx` and `sy` that we passed into the function, and then passing the node to addNodeToOpenList. We then assign `start` to `currentNode`, and zero a variable called `count`. `count` is used as our sanity counter, to ensure that we don't keep searching for a path forever. We'll see later how we quit search if `count` goes above a certain value.

We then set up a while-loop, set to repeat for ever. Inside this loop, we're creating two for-loops, one with `y` going from -1 to 1 (inclusive) and `x` going from -1 to 1 (inclusive). What we're going to do with these loops is test all the squares around our current square, by adding the values of `x` and `y` to the location. Notice that we're testing that `x` and `y` aren't both 0 before continuing. 0 and 0 will represent the current square, so we want to skip it. We then also check that the map square we are about to test falls within the bounds of the map, by adding `x` and `y` to `currentNode`'s `x` and `y`, and checking the values. If it's outside of our map bounds, we'll ignore this square and continue our loop.

We now have a valid square. We therefore malloc and memset a new Node, called newNode, and set its `x` and `y` to currentNode's `x` and `y`, plus the `x` and `y` of our loop. Next, we calculate the scores. We first check if the current square is blocked, by calling isBlocked (more on this later). If the square isn't blocked, we start by figuring out the `g` score. If newNode is at a diagonal from the currentNode, we'll give it a score of 14, plus the currentNode's `g` score. Otherwise, it will get a score of 10, plus currentNode's `g` score. We then calculate the `h` score, by multiplying the absolute distance between newNode's `x` and `ex` plus the absolute distance between newNode's `y` and `ey` by 10. In short, if we are closer to our goal (`ex`, `ey`) `h` will have a smaller value than the tiles around it. This is what we want - a smaller score, bringing us closer to the end.

Finally, we set newNode's `f` score to be the sum of its `g` and `h` scores. If, however, the square we're testing is blocked, we'll set all newNode's scores (`f`, `g`, and `h`) to -1, to say the square is completely invalid.

With the scores calculated, we set newNode's parent to be currentNode and add it to our open list, by calling addNodeToOpenList and passing it over.

We're then incrementing `count` and testing to see if its value has exceeded MAP_WIDTH * MAP_HEIGHT. If so, we'll exit our aStar calculation. Basically, if `count` has reached such a number (having apparently checked all of our map) there's a good chance that a path cannot be found. To prevent the game from locking up, we're calling return, to exit out of the function right away, thus ending our A* search.

Our two loops continue until done, and then we're calling getSmallestNode and assigning it to currentNode. The idea here is that we'll search for a node that will have the smallest `f` score and is therefore closer to the goal than our current node. If we don't find a node (the function returns NULL), we'll quit our of our while-loop by calling break. Otherwise, we'll set currentNode's `closed` to 1, marking it having been processed. Finally, we'll check if we've reach our goal, by checking if currentNode's `x` and `y` are equal to `ex` and `ey`.

Again, this is a very high level overview of how this route building works. Further reading is recommended if you're not familiar with the subject (it can be hard to understand without visual aids!).

Onto isBlocked:

static int isBlocked(int x, int y)
{
	Entity *e;

	if (dungeon.map[x][y].tile == TILE_HOLE || dungeon.map[x][y].tile >= TILE_WALL)
	{
		return 1;
	}

	e = getEntityAt(x, y);

	if (e != NULL && e != owner && e->solid)
	{
		return 1;
	}

	return 0;
}

A simple function to understand, it takes two parameters - `x` and `y`, the square we want to test. We first check the tile type at the map's coordinates. If it's TILE_HOLE or a TILE_WALL, we'll return 1 (true). Otherwise, we'll check to see if there's an entity at the square we want to move into. If there is, and it's not the owner of the A* pathfinding (`owner` is a static variable within aStar.c) or the entity is solid, we'll return 1 (true). Otherwise, we'll return 0 at the end of the function.

The next function is findNextMove:

static Node *findNextMove(int x, int y)
{
	Node *n;

	for (n = nodeHead.next ; n != NULL ; n = n->next)
	{
		if (n->x == x && n->y == y)
		{
			return n->parent;
		}
	}

	return NULL;
}

It takes two parameters - the `x` and `y` of the Node we're interested in. We then loop through our node list until we find the Node with a matching `x` and `y`, and return its `parent`. If we don't find a matching Node, we'll return NULL. The idea behind this is, given a node, we want to find the next node in our linked list that represent our path.

Something to note here - we're only returning one Node and not building up an entire path. Normally, with A* pathfinding, we would locate the Node we're interested in and then follow the chain of `parent` references to create our full path to the target. We can't exactly do that in this game, since once one thing moves, everything else does. It means the path we calculated could be blocked or otherwise become invalid, leading us to then need to either recalcuate or wait until the thing in the way moves. For this game, we've chosen to calculate the path we need to reach our target and then simply move one step at a time. It serves us well.

Finally we have createAStarRoute:

void createAStarRoute(Entity *e, int x, int y, int *dx, int *dy)
{
	Node *n;

	owner = e;

	*dx = 0;
	*dy = 0;

	resetAStar();

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

	n = findNextMove(e->x, e->y);

	if (n != NULL)
	{
		*dx = n->x - e->x;
		*dy = n->y - e->y;
	}
}

This function is responsible for building the A* route and informing us how to move. We feed in 5 parameters - the entity the path is for (`e`), the `x` and `y` location we want to move to, and references to the direction we'll be moving (as `dx` and `dy`). We start by assigning `e` to a variable named `owner`. This is a static variable in aStar.c and tells us to ignore this entity when checking for blocked map positions, as this is the entity that is moving and doesn't count. Next, we zero both `dx` and `dy`, to default to no movement. With all that done, we call resetAStar to prepare our pathfinding and then buildRouteMap to search the dungeon for the path we will walk. We're then calling findNextMove, passing in the entity's current position (its `x` and `y`) and assiging the result of this to a Node variable called `n`. So long as `n` isn't NULL, we're going to calculate the `dx` and `dy` directions to move by simply subtracting the entity's `x` and `y` from `n`'s `x` and `y`.

Phew! That was a lot! But we now have a reliable A* pathfinding method that suits our game just fine. Again, it's not producing a full route, due to the turn-based nature of our game, but something like that would be simple to put in if one desired.

Now, let's turn to monsters.c, to see how it is being used. Starting with doMonsters:

void doMonsters(void)
{
	int processing;

	processing = 1;

	do
	{
		think(dungeon.currentEntity);

		nextMonster();

		processing = dungeon.animationTimer == 0 && dungeon.currentEntity != dungeon.player;
	}
	while (processing);
}

We've added in a new call to a function called `think`, passing over currentEntity to it.

`think` is a function that deals with our monster's behaviour:

static void think(Entity *e)
{
	Monster *m;

	m = (Monster*) e->data;

	if (!m->alert)
	{
		lookForPlayer(e, m);
	}
	else if (hasLOS(e, dungeon.player->x, dungeon.player->y))
	{
		moveToPlayer(e, m);
	}
	else
	{
		patrol(e, m);
	}
}

We start by extracting the Monster data from our entity and then testing if the Monster is aware of the player, by checking its `alert` flag. If `alert` is 0 (false), we'll call lookForPlayer. If `alert` is 1 (true), we'll call hasLOS, passing over the monster entity (`e`) and the position of the player, to see if the monster has a line of sight to the player. If so, we'll be calling moveToPlayer. Finally, if the monster is alert but can't see the player, we'll call a function named `patrol`.

We'll go through these functions one at a time, starting with lookForPlayer:

static void lookForPlayer(Entity *e, Monster *m)
{
	m->alert = getDistance(e->x, e->y, dungeon.player->x, dungeon.player->y) <= m->visRange && hasLOS(e, dungeon.player->x, dungeon.player->y);
}

This function is simple - we're setting the `alert` flag of the monster depending on if it can see the player. We're first testing the distance of the player from the monster, by calling getDistance and feeding in the monster's and player's positions. The result of this call is compared against the Monster's visRange. Should getDistance be less than or equal to the Monster's visRange, we'll call hasLOS, passing in the monster entity and the player's position, to see if the monster can see them. In short, we're testing if the player is within a certain distance of the monster and if the monster has a clear line of sight. If so, the Monster's `alert` state is set to 1.

Next up, we've got moveToPlayer:

static void moveToPlayer(Entity *e, Monster *m)
{
	int dx, dy;

	createAStarRoute(e, dungeon.player->x, dungeon.player->y, &dx, &dy);

	moveEntity(e, dx, dy);

	m->patrolDest.x = dungeon.player->x;

	m->patrolDest.y = dungeon.player->y;
}

This function moves the monster towards the player and also sets a "waypoint" to where the player was seen. We start by calling createAStarRoute, passing in all the necessary variables, and then calling moveEntity, passing across the monster entity and the `dx` and `dy` movement variables, to move them. Finally, we're setting the Monster's patrolDest `x` and `y` to the player's `x` and `y`. This allows the monster to move towards where the player was "last seen", in case the player should move out of the Monster's line of sight. They now have somewhere to move towards, in case the player is hiding.

Next up, we have `patrol`:

static void patrol(Entity *e, Monster *m)
{
	int dx, dy;

	if (dungeon.map[m->patrolDest.x][m->patrolDest.y].tile >= TILE_GROUND && dungeon.map[m->patrolDest.x][m->patrolDest.y].tile < TILE_WALL)
	{
		createAStarRoute(e, m->patrolDest.x, m->patrolDest.y, &dx, &dy);

		moveEntity(e, dx, dy);

		if (e->x == m->patrolDest.x && e->y == m->patrolDest.y)
		{
			m->patrolDest.x = rand() % MAP_WIDTH;

			m->patrolDest.y = rand() % MAP_HEIGHT;
		}
	}
	else
	{
		m->patrolDest.x = rand() % MAP_WIDTH;

		m->patrolDest.y = rand() % MAP_HEIGHT;
	}
}

The idea here is to have the Monster move towards their designated patrol destination, which may either be the last place they saw the player or some other random destination. We start by testing if the Monster's patrolDest `x` and `y` location is valid within our dungeon. We do this by checking the dungeon map's tiles at the patrolDest's `x` and `y`, to see if it's a valid ground tile. If so, we'll call createAStarRoute and then moveEntity, to have the monster makes its way to its patrol destination. We next check to see if the monster has arrived at its destination, by comparing its own `x` and `y` to its patrolDest's `x` and `y`. Should they be equal, our Monster has arrived at its destination and so we'll pick a new destination at random within the dungeon, using rand of MAP_WIDTH and MAP_HEIGHT. Note how we don't check at this stage if the destination is valid; we're not bothered if the monster stands still for a few turns.

Finally, if our initial check of the patrolDest location being valid is false, we'll pick a new random destination in the dungeon. Again, we're not bothered if it's valid at this point.

The last tweak in monsters.c we've made is to initMicroMouse:

void initMicroMouse(Entity *e)
{
	Monster *m;

	m = createMonster(e);
	m->hp = m->maxHP = 1 + rand() % 4;
	m->defence = 1;
	m->minAttack = 1;
	m->maxAttack = 3;
	m->visRange = 12;

	STRCPY(e->name, "Micro Mouse");
	e->texture = getAtlasImage("gfx/entities/microMouse.png", 1);
}

Our Micro Mouse will have a visRange of 12, so that it can spot the player from 12 squares away.

Turning now to player.c, we've made a tweak to doPlayer:

void doPlayer(void)
{
	int dx, dy;

	moveDelay = MAX(moveDelay - app.deltaTime, 0);

	if (moveDelay == 0)
	{
		dx = dy = 0;

		if (app.mouse.buttons[SDL_BUTTON_LEFT])
		{
			createAStarRoute(dungeon.player, dungeon.selectedTile.x, dungeon.selectedTile.y, &dx, &dy);
		}

		// snipped
	}
}

Where before when we were detecting a press of the left mouse button to move the player using a crude method of subtraction, we're now calling createAStarRoute, to move a bit better. Again, not the best method of navigation and perhaps something we'll tweak in our final part, during the finishing touches.

We've also made a small tweak to entities.c, in the isBlocked function:

static int isBlocked(Entity *e, int x, int y)
{
	Entity *other;

	for (other = dungeon.entityHead.next ; other != NULL ; other = other->next)
	{
		if (other->x == x && other->y == y)
		{
			switch (other->type)
			{
				case ET_PLAYER:
				case ET_MONSTER:
					if (e->type != other->type)
					{
						doMeleeAttack(e, other);
					}
					return 1;

				default:
					break;
			}
		}
	}

	return 0;
}

To ensure that monsters don't hit monsters, we're testing that `e`'s `type` is not the same as `other`'s `type`, before calling doMeleeAttack. This means that if `e` and `other` are both of type ET_MONSTER no in-fighting will occur. A* should have already taken care of this, but an extra check won't do us any harm.

The last thing we need to do is initialize our A*. Turning to init.c, we've updated initGameSystem:

void initGameSystem(void)
{
	srand(time(NULL));

	initAtlas();

	initFonts();

	initEntityFactory();

	initGame();

	initAStar();
}

We've just added a line to call initAStar.

And that's it for our pathfinding. Again, it's not a full route we're constructing here, but that's because we don't need to. What this does provide us with is more intelligent monsters, who can hunt the player and not stack up behind one another when it comes to attacking.

Our roguelike continues to evolve! What we'll be adding in next is the ability for the player to pickup items and view them in their inventory.

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: