« Back to tutorial listing

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

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

Being double-teamed by a pair of Micro Mice who have hunted us in the dungeon, after being alerted to our presence.

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.

^ Back to top

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.

^ Back to top

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:

^ Back to top