Complete roguelike tutorial using C++ and libtcod - extra 3: scent tracking

Complete roguelike tutorial using C++ and libtcod -originally written by Jice Text in this tutorial was released under the Creative Commons Attribution-ShareAlike 3.0 Unported and the GNU Free Documentation License (unversioned, with no invariant sections, front-cover texts, or back-cover texts) on 2015-09-21.

part 1: setting up part 2: map and actors part 3: dungeon building part 4: field of view part 5: preparing for combat part 6: going berserk! part 7: the GUI part 8: items and inventory part 9: spells and ranged combat part 10.1: persistence part 10.2: game menu part 11: dungeon levels and character progression extra 1: about editors and IDE extra 2: debugging extra 3: scent tracking extra 4: makefiles extra 5: more generic items

This article is an optional "extra" that will bring scent tracking to the monster Ai. In can be applied on the article 6 source code.

Even with the wall sliding trick, the monsters are still quite dumb. We'll implement scent tracking so that they can track the player even when they don't see him.

Tiles that smell

The first thing to do is to add a scent level to the tile struct, in Map.hpp :

struct Tile {
    bool explored; // has the player already seen this tile ?
    unsigned int scent; // amount of player scent on this cell
    Tile() : explored(false),scent(0) {}
};

We also add a currentSmellValue to the Map and a helper to get the scent level of a cell :

unsigned int currentScentValue;
unsigned int getScent(int x, int y) const;

The base idea is that every time the player moves, currentScentValue is increased and the scent is updated in every cell in the field of view with the value currentScentValue - distance to player. The monster will track the player based on their surrounding cell scent. The closer a cell's scent is to currentScentValue the higher the scent is for the monster. This way, the closer you are to the player, the higher is the scent. And scent is decreased every new turn in a cell that is not in the player field of view without having to update the scent values in the whole map.

So the first thing to do is to increase the current scent value every new turn, in Engine::update :

if ( gameStatus == NEW_TURN ) {
    map->currentScentValue++;

The Map::getScent method is simple :

unsigned int Map::getScent(int x, int y) const {
    return tiles[x+y*width].scent;
}

The core of the scent field computation is in Map::computeFov :

void Map::computeFov() {
    map->computeFov(engine.player->x,engine.player->y,
        engine.fovRadius);
    // update scent field
    for (int x=0; x < width; x++) {
        for (int y=0; y < height; y++) {
            if (isInFov(x,y)) {
                unsigned int oldScent=getScent(x,y);
                int dx=x-engine.player->x;
                int dy=y-engine.player->y;
                long distance=(int)sqrt(dx*dx+dy*dy);
                unsigned int newScent=currentScentValue-distance;
                if (newScent > oldScent) {
                    tiles[x+y*width].scent = newScent;
                }
            }
        }
    }
}

Monsters with a truffle

Now we must decide how "far" the scent is propagating. "Far" concerns both the distance and time. We use a constant for that, to be able to fine tune it later :

// after 20 turns, the monster cannot smell the scent anymore
static const int SCENT_THRESHOLD=20;

This means that a monster won't detect the scent if the player is 20 cells away or if the player has been here more than 20 turns ago. This translates to : cell scent >= currentScentValue-20. This constant has to be defined in Ai.hpp, not Ai.cpp because we need to access its value in Map.cpp too. Indeed, we will initialize the currentScentValue with the threshold value to keep monsters from detecting smell everywhere during the 20 first turns :

Map::Map(int width, int height) : width(width),height(height),currentScentValue(SCENT_THRESHOLD) {

We don't need the Ai::moveCount field anymore. You can remove it from the header and the constructor. The update function is much simpler : always track the player !

void MonsterAi::update(Actor *owner) {
    if ( owner->destructible && owner->destructible->isDead() ) {
        return;
    }
    moveOrAttack(owner, engine.player->x,engine.player->y);
}

All the actual Ai will be in the new moveOrAttack function. First, handle the case where we're at melee range :

void MonsterAi::moveOrAttack(Actor *owner, int targetx, int targety) {
    int dx = targetx - owner->x;
    int dy = targety - owner->y;
    float distance=sqrtf(dx*dx+dy*dy);
    if ( distance < 2 ) {
        // at melee range. attack !
        if ( owner->attacker ) {
            owner->attacker->attack(owner,engine.player);
        }
        return;

If the player is not at attack range but is in fov, walk towards him :

    } else if (engine.map->isInFov(owner->x,owner->y)) {
        // player in sight. go towards him !
        dx = (int)(round(dx/distance));
        dy = (int)(round(dy/distance));
        if ( engine.map->canWalk(owner->x+dx,owner->y+dy) ) {
                owner->x += dx;
                owner->y += dy;
                return;
        }
    }

Now we're in the case where the player is not visible. We're going to scan the monster's 8 adjacent cells and see which one has the highest scent. First, let's define some variables :

    // player not visible. use scent tracking.
    // find the adjacent cell with the highest scent level
    unsigned int bestLevel=0;
    int bestCellIndex=-1;
    static int tdx[8]={-1,0,1,-1,1,-1,0,1};
    static int tdy[8]={-1,-1,-1,0,0,1,1,1};

bestLevel will contain the best scent level found so far, and bestCellIndex, the number of the cell where this scent was found. The tdx and tdy arrays will make it easy to scan the 8 surrounding cells. They contain the dx,dy movement to reach each 8 cell.

    for (int i=0; i<  8; i++) {
        int cellx=owner->x+tdx[i];
        int celly=owner->y+tdy[i];
        if (engine.map->canWalk(cellx,celly)) {

So we're scanning the cells, taking into account only walkable cells.

            unsigned int cellScent = engine.map->getScent(cellx,celly);      
            if (cellScent > engine.map->currentScentValue - SCENT_THRESHOLD
                && cellScent > bestLevel) {
                bestLevel=cellScent;
                bestCellIndex=i;
            }
        }
    }

All the "intelligence" lies within those few lines. We get the cell's current scent value and check that it's not too old/far :

    cellScent > engine.map->currentScentValue - SCENT_THRESHOLD

If it's better than what we found so far, we update the bestLevel/bestCellIndex values.

If a cell with enough scent has been found, we walk on it.

    if ( bestCellIndex != -1 ) {
        // the monster smells the player. follow the scent
        owner->x += tdx[bestCellIndex];
        owner->y += tdy[bestCellIndex];
    }

You can now compile and enjoy your clever monsters.

Visible smells

It can be convenient to display the smell value in the game, for debugging purposes. You can do that by changing the Map::render code :

for (int x=0; x < width; x++) {
    for (int y=0; y < height; y++) {
        int scent=SCENT_THRESHOLD - (currentScentValue - getScent(x,y));
        scent = CLAMP(0,10,scent);
        float sc=scent * 0.1f;
        if ( isInFov(x,y) ) {
            TCODConsole::root->setCharBackground(x,y,
                isWall(x,y) ? lightWall : TCODColor::lightGrey * sc );
        } else if ( isExplored(x,y) ) {
            TCODConsole::root->setCharBackground(x,y,
                isWall(x,y) ? darkWall : TCODColor::lightGrey * sc );
        } else if (!isWall(x,y)) {
            TCODConsole::root->setCharBackground(x,y,
                 TCODColor::white * sc );
        }
    }
}