Dijkstra Maps

The monsters still chase you Chapter 5's simple way: each steps to whichever free neighbor is nearest you as the crow flies. While a monster can see you, that works, since a monster that can see you almost always has a clear line to you. But step around a corner, and it forgets you at once. And a monster that's losing a fight can only fight on, since it has no idea how to run.

This chapter gives the monsters a map. For every cell of the dungeon, the map holds how many steps it is to the player, by the shortest way around the walls. A monster that wants the player steps to its neighbor with the lowest number, and then to that cell's lowest neighbor. It arrives by the shortest way, however twisty.

Roguelike programmers call this a Dijkstra map, after the computer scientist whose algorithm fills it in. The next image shows one, as the debugging aid on F3 draws it.

The same numbers, turned upside down in a clever way, show a badly wounded monster where to run.

In this chapter, we will:

• Work out every cell's distance from the player with Dijkstra's algorithm, once a turn, for every monster to share
• Draw the distances with F3, a debugging aid
• Make the monsters step downhill, by the shortest way, and in straight lines
• Let a monster that loses sight of the player go to where it last saw them
• Turn the map into a flee map, so that a badly wounded monster runs for open ground

There are four checkpoints along the way. Let's start with why a monster needs a map at all.

Planning the Chapter

This chapter adds a class, and changes three files:

The next image shows how the files fit together at the end of the chapter. The new class has a box of its own, below the views, and it uses only the map.

Two ideas carry the chapter. The first is the map: a number on every cell, counting the steps to the nearest goal, which a monster follows downhill without ever planning a route. The second is that one map serves every monster. Whether two monsters are chasing the player or twenty, the map of distances to the player is worked out once a turn, and each of them reads its own way from it.

We'll build it in three steps: the map, and F3 to see it; monsters that walk downhill, and remember where they last saw the player; and a flee map, for running away.

A Map of Distances

The first step builds the map, and a way to see it. Nothing in the game uses it yet, so the monsters behave as they always have.

Why the Chase Needs a Map

Chapter 5's chase looks only at the monster's neighbors, and picks the one nearest the player as the crow flies. In the open, that's the shortest way. But walls don't care how the crow flies. The next image shows a jackal in a room whose door faces away from the player.

On the left, the jackal steps toward the player, reaches the room's top wall, and stops. Every free neighbor is farther from the player as the crow flies, so it has nowhere better to go. But there's a way to the player for anyone who knows it. Nearer as the crow flies isn't the same as nearer on foot.

On the right, every cell holds its real distance: the number of steps by the shortest way. Now the jackal needs no plan at all. It steps to a lower number, then a lower one, out of the door at the bottom, and around the ring to the player. Every step brings it one closer, however far around the way goes.

Dijkstra's Algorithm

The numbers are filled in from the goals outward. Each goal is 0. Its neighbors are one step away, so they're 1. Their neighbors are 2, unless they already have a smaller number, and so on.

Done carelessly, in any old order, a cell could be given the number of a long way around before the short way reaches it. Then it would need fixing, and so would every cell that took its number from it.

Edsger Dijkstra's algorithm, published in 1959, avoids that by always working on the cell with the smallest number so far. The cells waiting to be worked on go into a priority queue, a container that hands back its elements in order, whatever order they went in: here, the smallest first. Each cell handed back offers its neighbors its own number plus one. A neighbor that has no number yet, or a bigger one, takes the offer and joins the queue. The next image shows it on a small map.

The queue always hands back the smallest number first. By the time a cell comes out, nothing smaller can reach it any more, so its number is its shortest. When the queue is empty, every cell has its distance. Notice the cells straight behind the wall, in the last picture: they hold 4, though they look only two or three steps away. The way around the wall is longer.

With every step costing the same, one, there's a simpler way. A plain queue, first in, first out, would hand the cells back in order of their numbers anyway. The priority queue is here because the game needs the general algorithm. The flee map, at the end of this chapter, starts from cells with all sorts of numbers. And in Chapter 19, a closed door costs more than one step.

The DijkstraMap Class

In Solution Explorer, right-click src, choose Add > New Item, and add a Header File (.h) called DijkstraMap.h. Type the first part of the class:

#pragma once
#include <vector>   // std::vector, for the distances
#include "Common.h"
#include "Map.h"

// For every cell of the map, how many steps it is to the nearest of some
// goal cells, walking in eight directions over floor. A monster that steps
// to its lowest neighbor, again and again, reaches a goal by the shortest
// way around the walls. Roguelike programmers call this a Dijkstra map,
// after the computer scientist whose algorithm fills it in
class DijkstraMap
{
public:
    // The distance of a cell that no goal can be reached from
    static constexpr int UNREACHED = 1000000;

    DijkstraMap();

    // Works out every cell's distance from the nearest of the goals
    void compute(const Map& map, const std::vector<Point>& goals);

    // A cell's distance. Off the map, it's UNREACHED
    int at(Point cell) const;

In the preceding code, UNREACHED is the distance of a cell that no goal can be reached from: a wall, or floor cut off by walls. It's bigger than any real distance could be, so it's never a monster's lowest neighbor. Being static, it belongs to the class rather than to each map. Other code can name it as DijkstraMap::UNREACHED, without needing a map. The function compute works out the distances from some goals, and at gives a cell's distance.

Then the private part, below at, with a blank line in between:

private:
    void spread(const Map& map);

    std::vector<int> distance_;
};

The distances are in distance_, one for each cell. They're in the same order as Chapter 2's map keeps its cells: row after row, so a cell's index is y * MAP_W + x. The function spread is Dijkstra's algorithm, which fills them in. Now add a C++ File (.cpp) called DijkstraMap.cpp, and type its includes and the constructor:

#include "DijkstraMap.h"
#include <functional>   // std::greater, to make the queue smallest first
#include <queue>        // std::priority_queue, for the cells still to visit
#include <utility>      // std::pair, for a distance and a cell together

DijkstraMap::DijkstraMap()
    : distance_(MAP_W * MAP_H, UNREACHED)
{
}

A new map has a distance for every cell of the map, MAP_W times MAP_H of them, and all of them UNREACHED. Add compute and at below the constructor:

void DijkstraMap::compute(const Map& map, const std::vector<Point>& goals)
{
    distance_.assign(distance_.size(), UNREACHED);
    for (Point goal : goals)
    {
        if (map.inBounds(goal.x, goal.y))
        {
            distance_[goal.y * MAP_W + goal.x] = 0;
        }
    }
    spread(map);
}

int DijkstraMap::at(Point cell) const
{
    if (cell.x < 0 || cell.x >= MAP_W || cell.y < 0 || cell.y >= MAP_H)
    {
        return UNREACHED;
    }
    return distance_[cell.y * MAP_W + cell.x];
}

In the preceding code, compute starts again from nothing: assign sets every distance to UNREACHED, and then each goal that's on the map becomes 0. There can be any number of goals, and each cell gets its distance from the nearest. Then spread does the rest. And at gives UNREACHED for a cell off the map, so code that looks at a monster's neighbors needn't check for the map's edge first.

Now spread, in three parts. Add the first below at:

// Dijkstra's algorithm. Every cell that has a distance waits in a queue,
// which always hands back the one with the smallest distance next. Each
// cell handed back offers its neighbors its own distance plus one step,
// and a neighbor that had a longer distance (or none) takes the offer, and
// joins the queue. When the queue is empty, every distance is the shortest
void DijkstraMap::spread(const Map& map)
{
    // Each entry is a distance and a cell's index. std::greater turns the
    // queue's usual order around, so the smallest distance comes out first
    using Entry = std::pair<int, int>;
    std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> queue;
    for (int i = 0; i < static_cast<int>(distance_.size()); ++i)
    {
        if (distance_[i] < UNREACHED)
        {
            queue.push({ distance_[i], i });
        }
    }

Each entry in the queue is a distance and a cell's index, kept together in a std::pair. A pair's two values are called first and second. The line starting using gives the pair a shorter name, Entry, for this function. Pairs compare by their first values, and then by their second, so the queue orders its entries by distance.

A std::priority_queue takes three types in its angle brackets: what it holds, the container it keeps them in, and how to compare them. Here, the container is a std::vector. Left to itself, the queue hands back its biggest element first. Comparing with std::greater turns that around, so the smallest comes out first. That's what Dijkstra's algorithm needs.

Every cell that already has a distance, the goals, goes into the queue to start. Add the second part below the first, with a blank line in between:

while (!queue.empty())
{
    int distance = queue.top().first;
    int index = queue.top().second;
    queue.pop();

    // A cell can be in the queue more than once, if it was offered a
    // shorter distance after joining it. Only its shortest counts
    if (distance > distance_[index])
    {
        continue;
    }

The loop runs until the queue is empty. Each time around, top looks at the entry with the smallest distance, and pop takes it out of the queue.

A cell can be in the queue more than once, since a shorter distance can reach it after it joined. When an entry comes out whose distance is bigger than the cell's distance now, it's out of date. The cell has been dealt with already, so continue skips it. Add the last part below the second, with a blank line in between:

        Point cell = { index % MAP_W, index / MAP_W };
        for (Point step : DIRECTIONS)
        {
            Point next = { cell.x + step.x, cell.y + step.y };
            if (map.at(next.x, next.y) != Terrain::Floor)
            {
                continue;
            }
            int nextIndex = next.y * MAP_W + next.x;
            if (distance + 1 < distance_[nextIndex])
            {
                distance_[nextIndex] = distance + 1;
                queue.push({ distance + 1, nextIndex });
            }
        }
    }
}

First, the index becomes a cell again. The index divided by the map's width is the row, and what's left over, index % MAP_W, is the column. Then each of the cell's eight neighbors, from Chapter 5's DIRECTIONS, is offered the cell's distance plus one. A wall can't take it, and a cell off the map is a wall to map.at. Any neighbor that had a longer distance, or UNREACHED, takes the offer, and joins the queue with it.

Checkpoint: Click in DijkstraMap.cpp, and press Ctrl+F7 to compile it. It compiles. Nothing uses it yet, so the game is unchanged.

Seeing the Map

Numbers you can't see are hard to trust, so the game gets a debugging aid, as F1 is. F3 draws every cell's distance on the map. First, the map itself. Open Game.h, and add the new header below #include "Common.h":

#include "DijkstraMap.h"

Add the map below log_:

// Every cell's distance from the player, worked out once a turn
DijkstraMap toPlayer_;

There's one map of distances to the player, and every monster will use it. Then find the debugging aid's flag:

bool revealMap_ = false;   // the debugging aid on F1

Replace it with these lines:

bool revealMap_ = false;       // the debugging aid on F1
bool showDistances_ = false;   // and the one on F3

The new flag's name is longer, so the old one's comment moves along to stay in line. Last, in Game.h, add a declaration below drawHighlight's:

void drawDistances() const;

The map must be right before the monsters use it, so it's worked out at the start of finishTurn, after the player has moved and before the monsters act. Open Game.cpp, and in finishTurn, add these lines above monstersAct();:

// The player may have moved, so the distances to them are new
toPlayer_.compute(map_, { player_.pos });

The braces make a vector of goals with one in it, the player's cell. The map is also needed before the first turn ends, for F3 to draw, so work it out in the constructor too. Add this line below the constructor's call to Fov::compute:

toPlayer_.compute(map_, { player_.pos });

F3 works as F1 does. In handleKey, add its check above F1's:

if (key.key == SDLK_F3)
{
    // A debugging aid: F3 shows how far every cell is from the player
    if (!key.repeat)
    {
        showDistances_ = !showDistances_;
        redraw_ = true;
    }
    return;
}

The overlay draws each cell's distance as a digit, over a color: warm amber near the player, cooling to deep blue far away. Add its colors to the unnamed namespace, below LOOK_PANEL_LINES:

// The distance overlay's colors: warm near the player, cooling to blue
// by FAR_DISTANCE steps away
constexpr SDL_Color NEAR_BACK = { 95, 70, 20, 255 };
constexpr SDL_Color FAR_BACK = { 20, 28, 80, 255 };
constexpr SDL_Color NEAR_TEXT = { 255, 225, 130, 255 };
constexpr SDL_Color FAR_TEXT = { 130, 160, 255, 255 };
constexpr float FAR_DISTANCE = 40.0f;

The colors are mixed, part of the way from the near color to the far one, by a helper. Add it below withArticle:

// A color part of the way from a to b: t = 0 gives a, and t = 1 gives b
SDL_Color blend(SDL_Color a, SDL_Color b, float t)
{
    auto mix = [t](Uint8 from, Uint8 to)
    {
        return static_cast<Uint8>(from + (to - from) * t);
    };
    return { mix(a.r, b.r), mix(a.g, b.g), mix(a.b, b.b), 255 };
}

The parameter t says how far along the way the color is: 0 gives a, 1 gives b, and 0.5 gives the color halfway between. Each of the color's parts, red, green and blue, is mixed the same way. The work is done by a lambda, mix, used three times. An SDL_Color's parts are Uint8s, SDL's type for a whole number from 0 to 255. So mix takes two of them, and turns its answer back into one with static_cast.

Chapter 6's lambda had empty brackets, since it needed nothing from the code around it. This one needs t, which belongs to blend. Its brackets say so: [t] copies t into the lambda, which can then use it. A lambda can only use what it lists there, or, in C++'s words, what it captures.

Now the overlay. Add drawDistances below drawMap, in two parts. Here's the first:

// A debugging aid (F3): every cell's distance from the player, from
// toPlayer_, as its last digit, over a color that cools with distance.
// It's drawn for the whole map, seen or not
void Game::drawDistances() const
{
    for (int y = 0; y < MAP_H; ++y)
    {
        for (int x = 0; x < MAP_W; ++x)
        {
            Point cell = { x, y };
            int distance = toPlayer_.at(cell);
            if (distance == DijkstraMap::UNREACHED ||
                !view_->camera().shows(cell))
            {
                continue;
            }

Every cell is looked at, but walls are UNREACHED and have no distance to show. Cells the camera doesn't show aren't drawn either. Add the rest below the first part:

            float t = SDL_min(1.0f, distance / FAR_DISTANCE);
            SDL_FRect rect = view_->camera().cellRect(cell);
            setColor(blend(NEAR_BACK, FAR_BACK, t));
            SDL_RenderFillRect(renderer_, &rect);
            char digit = static_cast<char>('0' + distance % 10);
            glyphs_.drawInCell(digit, rect.x, rect.y, rect.w,
                               blend(NEAR_TEXT, FAR_TEXT, t));
        }
    }
}

Here, t is the distance as a share of FAR_DISTANCE. It grows from 0 at the player to 1 at 40 steps away, and SDL_min stops it there. The cell is filled with the background's color, and then its distance is drawn in it, with Chapter 1's drawInCell. Only the last digit fits in a cell, and distance % 10 is that digit, as a number. Adding it to the character '0' gives the character for it, since the digits' characters are in order: '0' + 7 is '7'.

The overlay is drawn over the map and under the monsters. In draw, add these lines below drawMap();:

if (showDistances_)
{
    drawDistances();
}

Last, the side panel says when F3 is on, as it does for F1. In drawSidePanel, find the lines from the seed to F1's reminder:

glyphs_.drawText("Seed " + std::to_string(seed_), x, y,
                 Palette::DIM_TEXT);
if (revealMap_)
{
    y += 2 * row;
    glyphs_.drawText("DEBUG: map revealed (F1)", x, y, Palette::DEBUG);
}

Replace them with these lines:

glyphs_.drawText("Seed " + std::to_string(seed_), x, y,
                 Palette::DIM_TEXT);
y += row;

// Each debugging aid that's on, a row each
if (revealMap_)
{
    y += row;
    glyphs_.drawText("DEBUG: map revealed (F1)", x, y, Palette::DEBUG);
}
if (showDistances_)
{
    y += row;
    glyphs_.drawText("DEBUG: distances (F3)", x, y, Palette::DEBUG);
}

A blank row goes below the seed. Then each debugging aid that's on gets a row of its own, so the reminders stack up neatly however many are on.

Checkpoint: Press F5, with seed 42 in Command Arguments, and press F1 and F3. Every floor cell shows its distance from you, as in Figure 10.1. The numbers rise from 1 around you, through your room, out of its doorways and along the corridors, and cool from amber to blue. Walk a few steps, and watch the numbers move with you. Notice that cells just behind a wall have bigger numbers than their place suggests, since the way to them goes around.

Walking Downhill

Now the monsters use the map. A monster that can see the player walks down it, and one that has lost sight of them goes to where it last saw them.

One Step Down

The chase becomes a step down a map. It takes the map as a parameter, so that it can walk down any map, not just the one to the player. In Game.h, change Point chaseStep(const Monster& monster); to Point stepDown(const Monster& monster, const DijkstraMap& distances);.

Then, in Game.cpp, delete everything from // Where a monster that sees the player steps down to the closing brace of chaseStep, along with the blank line above it.

In its place goes stepDown, in two parts. Here's the first:

// A step downhill on a map of distances: to the free neighbor with the
// lowest distance, if that's lower than where the monster stands, or
// nowhere. Diagonal steps count the same as straight ones, so several
// neighbors are often equally low. Of those, a straight step wins, so a
// monster walks in straight lines where it can, not in a zigzag
Point Game::stepDown(const Monster& monster, const DijkstraMap& distances)
{
    Point best = monster.pos;
    int bestDistance = distances.at(monster.pos);
    bool bestIsDiagonal = false;
    for (Point step : DIRECTIONS)
    {
        Point to = { monster.pos.x + step.x, monster.pos.y + step.y };
        if (!isFree(to))
        {
            continue;
        }

The monster starts by thinking it will stay where it is, at its own cell's distance, and then looks at each free neighbor in turn. Add the rest of the function below the first part:

        int distance = distances.at(to);
        bool diagonal = step.x != 0 && step.y != 0;
        bool lower = distance < bestDistance;
        bool asLowButStraight = distance == bestDistance &&
                                bestIsDiagonal && !diagonal;
        if (lower || asLowButStraight)
        {
            best = to;
            bestDistance = distance;
            bestIsDiagonal = diagonal;
        }
    }
    return best;
}

A neighbor wins if it's lower than the best so far. That's all a step downhill needs, but it leaves a problem. A diagonal step costs one, the same as a straight one, so a monster often has several neighbors that are equally low. If the first one found always won, the monster would take some odd ways. The next image shows one.

Both ways are six steps, and both are the shortest, but only one looks like an animal that knows where it's going. So a neighbor also wins if it's as low as the best so far, but straight, where the best is diagonal. That's asLowButStraight. A neighbor only as low as where the monster stands never wins that way, since bestIsDiagonal is false until best has moved. So a monster never takes a step that gets it no closer.

Where It Last Saw You

A monster can now chase by the shortest way, but it still forgets you the moment it loses sight of you. It should go to where it last saw you, as anyone would. Searching around the spot comes in Chapter 11. Each monster needs to remember that place, if it has one, and Chapter 9's std::optional is just the thing. Open Monster.h, and add its header below #include <SDL3/SDL.h>:

#include <optional>   // std::optional, for where it last saw the player

Replace the comment above struct Monster : Entity with this:

// One monster in the dungeon: an Entity, the kind of monster it is, and
// where it last saw the player, if it has

Then add the place itself below def:

std::optional<Point> lastSeen;

A new monster has seen nothing yet, so its lastSeen starts out empty. Now the monsters' turn. In Game.cpp, replace the comment above monstersAct with this:

// The monsters' turn. A monster that can see the player attacks if it's
// next to them, and otherwise comes closer. One that has lost sight of
// them goes to where it last saw them, and the rest wander. Once the
// player is dead, no monster acts

Then find the lines in its loop that decide what each monster does, and delete them:

if (!seesPlayer(monster))
{
    monster.pos = wanderStep(monster);
}
else if (isNextTo(monster.pos, player_.pos))
{
    monsterAttacks(monster);
}
else
{
    monster.pos = chaseStep(monster);
}

In their place goes a choice of three. First, a monster that can see the player. Add this below the check that the player is alive, with a blank line in between:

if (seesPlayer(monster))
{
    // It attacks, or comes closer by the shortest way around the
    // walls, and remembers where the player is
    monster.lastSeen = player_.pos;
    if (isNextTo(monster.pos, player_.pos))
    {
        monsterAttacks(monster);
    }
    else
    {
        monster.pos = stepDown(monster, toPlayer_);
    }
}

It's the old chase, with two changes: it steps down toPlayer_, and it remembers where the player is, every turn it sees them. Then add the other two branches below the first:

else if (monster.lastSeen && monster.pos != *monster.lastSeen)
{
    // It's lost sight of the player, so it goes to where it last
    // saw them, on a map of its own. If it can't get any closer,
    // it gives up
    Point goal = *monster.lastSeen;
    DijkstraMap toGoal;
    toGoal.compute(map_, { goal });
    Point next = stepDown(monster, toGoal);
    if (next == monster.pos)
    {
        monster.lastSeen.reset();
    }
    monster.pos = next;
}
else
{
    // Nothing to go on: it forgets, and wanders
    monster.lastSeen.reset();
    monster.pos = wanderStep(monster);
}

In the preceding code, a monster that has lost sight of the player, but has a place to go, makes a map of its own. The map, toGoal, has that place as its goal, and the monster steps down it. It's the same class with a different goal. That's why stepDown takes the map as a parameter. Only the monsters that are searching need a map of their own, and there are rarely more than one or two of them.

If it can't get any closer, stepDown gives back the cell it's standing on. Perhaps another monster is in the way, or it has nowhere left to go. Either way, it gives up and forgets.

A monster that has reached the place stops too, since the branch needs monster.pos != *monster.lastSeen. It falls through to the last branch, which forgets and wanders. The * reaches into the optional for the place inside it, as in Chapter 9.

Checkpoint: Press F5, with seed 42, and press F1, so that you can watch the jackal. Walk eight steps down and eleven to the right, and then one up, into the doorway of the jackal's room, where it sees you. Step back down, and walk six steps west along the corridor. The jackal comes out of its door after you, and follows two steps behind. The next image shows it, beside what Chapter 9's jackal does.

On the left, the jackal lost you when you stepped back, and wandered about inside its room. The jackal on the right went to the doorway, where it last saw you. It saw you again from there, and chased you along the corridor.

Running Away

A monster with almost no health left should run, as any animal would. The obvious way to run is to go uphill on the map to the player: away from them. That's the wrong way, and the reason is worth seeing.

The Flee Map

Climbing away from the player is the same as walking downhill on the distances made negative. So the obvious flee map is the distance map, with every number made negative. The trouble is that it only knows "away from the player", and away usually means into the back of the room. The next image shows it, on a small map like the jackal's room.

On the left, the jackal steps away from the player, up into the room. It stops at the top wall, two steps away, with nowhere farther to go. The room's back wall is a dead end, and the player is between the jackal and the way out.

The far end of the corridor is much farther from the player. But to get there, the jackal would have to go near them first. That's uphill on this map, so it never does.

On the right is the trick that Brogue's author published. Every distance is multiplied by -1.2. Then the map is spread again from those numbers, by the same algorithm.

The far end of the corridor is very low now, -37. Spreading lets its lowness flow back along the corridor, one step at a time, through the door, into the cells by the player. A cell is low now if it's near somewhere far away. The jackal steps downhill, right past the player, through the door, and away down the corridor.

The 1.2 sets how much a far place is worth. With 1, the far end's pull would be used up by the time it reached the door. Anything bigger than 1 leaves some left over. With 1.2, running past the player pays if the far side is far enough. Open DijkstraMap.h, and add a declaration below compute's:

// A map for running away from this one's goals. Walking downhill on it
// leads to the places farthest from them that can be reached, and
// around the goals if that's the way to somewhere far
DijkstraMap fleeMap(const Map& map) const;

The function is const, since it doesn't change the map it's called on. It makes a new one. Open DijkstraMap.cpp, and add it below compute:

// Brogue's trick. Every distance is multiplied by -1.2, so the farthest
// cells become the lowest. Downhill on that alone, a monster would run
// into the nearest dead end that's a little farther away. So the map then
// spreads again: a cell next to a very low one can be no more than one
// step higher. Now a cell is low if it's near somewhere far away, and a
// fleeing monster heads for open ground, even if the way passes close to
// the goals. The 1.2 makes running past them worth it if the far side is
// far enough
DijkstraMap DijkstraMap::fleeMap(const Map& map) const
{
    DijkstraMap flee = *this;
    for (int& distance : flee.distance_)
    {
        if (distance < UNREACHED)
        {
            distance = -(distance * 6) / 5;
        }
    }
    flee.spread(map);
    return flee;
}

In the preceding code, DijkstraMap flee = *this; makes a copy of the whole map, its vector of distances and all. The range-based for takes each distance by reference, as int&. Changing distance changes the number in the copy's vector, not a copy of it. A distance of UNREACHED stays as it is, since a wall is still a wall.

The sum -(distance * 6) / 5 is the distance times -1.2, in whole numbers: times 6, divided by 5, and made negative. Then flee.spread(map) runs Dijkstra's algorithm again, starting from every cell, since every cell that isn't a wall now has a number. The function spread is private. But a class's private members are private to the class, not to each object, so fleeMap can call it on flee.

Badly Wounded Monsters Run

Every monster that runs uses the same flee map, so, like toPlayer_, it's worked out once a turn. In Game.h, replace the comment above toPlayer_ with this:

// Every cell's distance from the player, and the map for running away
// from them, worked out once a turn

And add the flee map below toPlayer_:

DijkstraMap fromPlayer_;

Which monsters run? The look panel already has words for it: a monster with less than a third of its health is "badly wounded". The rule for running should be the same test, written once, so that the panel's words and the monsters' behavior can never disagree. In Game.cpp, add it to the unnamed namespace, below capitalized:

// True for a creature with less than a third of its health left. A
// monster this badly wounded runs from the player
bool isBadlyWounded(const Entity& entity)
{
    return entity.hp * 3 < entity.maxHp;
}

Then, in woundsOf, change if (entity.hp * 3 >= entity.maxHp) to if (!isBadlyWounded(entity)), so that the words use the test too. In finishTurn, find the lines that work out the map:

// The player may have moved, so the distances to them are new
toPlayer_.compute(map_, { player_.pos });

Replace them with these lines:

// The player may have moved, so the distances to them are new, and so
// is the way to run from them
toPlayer_.compute(map_, { player_.pos });
fromPlayer_ = toPlayer_.fleeMap(map_);

The flee map is made from the distance map, so it's made after it. Then replace the comment above monstersAct with this:

// The monsters' turn. A monster that can see the player runs if it's badly
// wounded, and otherwise attacks if it's next to them, or comes closer.
// One that has lost sight of them goes to where it last saw them, and the
// rest wander. Once the player is dead, no monster acts

Last, the running itself, first of all the choices. In monstersAct, find the start of the first branch:

if (seesPlayer(monster))

Replace it with these lines:

bool sees = seesPlayer(monster);
if (sees && isBadlyWounded(monster))
{
    // It runs, down the flee map, and stops hunting. Cornered,
    // with nowhere lower to go, it turns and fights
    monster.lastSeen.reset();
    Point next = stepDown(monster, fromPlayer_);
    if (next != monster.pos)
    {
        monster.pos = next;
    }
    else if (isNextTo(monster.pos, player_.pos))
    {
        monsterAttacks(monster);
    }
}
else if (sees)

The monster asks once whether it can see the player, and keeps the answer in sees, since two branches need it. A monster that can see the player while it's badly wounded runs down fromPlayer_. It stops hunting, so it forgets where it last saw them. If there's nowhere lower to go, it's cornered, and it turns and fights if it's next to the player. Otherwise, the old branches carry on as before.

Checkpoint: A jackal starts with five health, and your first blow on seed 42 is a 6, which kills it outright. To see one run, give the jackals more health for a moment. In Monster.h, set the jackal's health, the 5 in its row, to 7. Press F5, with seed 42, and press F1. Walk eight steps down, eleven to the right and two up. The jackal comes to meet you, and stands up and to the right of you. Attack it with u: "You hit the jackal for 6." It has one health left, and runs, right past you, out of the door, and away along the corridor. Take a step or two to the left, and watch it go. The next image shows where it goes, beside where the obvious flee map would send it.

When you've seen it, set the jackal's health back to 5.

Design note: Brogue's maps. Brian Walker, who wrote Brogue, described these maps in an article on RogueBasin, the roguelike developers' wiki. The name he gave them is the one roguelike programmers use. He made two points this chapter leans on. First, every monster hunting the player can share one map, so it's worked out once a turn, however many monsters there are. Second, a monster running away mustn't just climb that map, or it runs into the nearest corner of its room. His answer was to multiply every distance by about -1.2, and spread the map again. The article goes much further: an auto-explore, with every undiscovered cell a goal, and monsters with many wants. Each want, such as treasure, company or safety, is a map, and the maps are weighted and added together.

The next chapter builds on these maps. Its monsters choose each turn whether to hunt, wander or run, and each of those is a walk down one map or another.

Playing the Game

The monsters are harder to shake off now. A jackal that sees you go around a corner comes around it after you, and a goblin follows you down a corridor until it catches up, or loses you. Doorways still help. Step out of sight, and a monster goes to where it saw you last. If you've moved on by then, it may lose you for good.

Watch for monsters that run. A goblin you've beaten down to its last few points of health stops fighting, and runs from you while it can see you, often right past you. You can chase it, but it's as fast as you, so you'll catch it only if it runs into a dead end, where it turns and fights again. Once it's out of sight, it forgets you and wanders, and it may wander back into view and run again.

Press F3 whenever you like, to see the numbers a chasing monster walks down. A monster that runs walks down the flee map instead, which F3 doesn't draw.

Understanding the Code

A DijkstraMap holds every cell's distance from the nearest of some goals, by the shortest way over floor, in eight directions. The function compute sets the goals to 0, and spread runs Dijkstra's algorithm. A std::priority_queue, smallest first by std::greater, hands back the cell with the smallest distance. That cell offers its neighbors that distance plus one. Entries that are out of date are skipped.

The game works out toPlayer_, the map to the player, once a turn, at the start of finishTurn. Every monster shares it. F3 draws it, with each cell's last digit over a color mixed by blend, whose lambda captures t. The function stepDown moves a monster to its lowest free neighbor. A straight step wins a tie, so monsters walk in straight lines.

A monster remembers where it last saw the player, in lastSeen, a std::optional<Point>. Out of sight, it goes there on a map of its own, and forgets if it arrives, or can't get closer.

The flee map, from fleeMap, is Brogue's: every distance times -1.2, then spread again. So it's low near somewhere far away. A monster that sees the player while it's badly wounded, the same test as the look panel's words, runs down it. It fights only when cornered.

Experimenting

The maps are easy to play with, and F3 shows what each change does. Try each of these, and put each back afterward:

• A shorter scale. Set FAR_DISTANCE to 10.0f. The colors cool four times as fast, and most of the map is blue.
• Two goals. In finishTurn, give toPlayer_ a second goal, the first room's middle with seed 42: toPlayer_.compute(map_, { player_.pos, { 8, 5 } });. Walk away from the first room, and press F3: there are two valleys, one around you and one around the room's middle. Each cell counts from the nearer.
• No tie rule. In stepDown, set asLowButStraight to false. Monsters still take the shortest way, but across an open room, it's often a bent one, like Figure 10.5's V.
• The obvious flee map. In fleeMap, change -(distance * 6) / 5 to -distance, and delete flee.spread(map);. With the jackal's health at 7 again, as in the last checkpoint, it runs up into its room, as on the left of Figure 10.8.

The last one is the reason for Brogue's trick. A monster that runs into a corner is still cornered, and it would have been better off going past you while it could.

Common Errors and Fixes

If the game didn't build, or doesn't behave as described, the problem is probably one of these.

C2178: 'UNREACHED' cannot be declared with 'constexpr' specifier, followed by more about UNREACHED. It's missing its static, in DijkstraMap.h. A constexpr member of a class must be static.

C2039: 'priority_queue': is not a member of 'std', followed by many more. The include for <queue> is missing from DijkstraMap.cpp.

C2065: 'UNREACHED': undeclared identifier, in Game.cpp. Outside the class, its name needs the class's name too: DijkstraMap::UNREACHED.

C3493: 't' cannot be implicitly captured because no default capture mode has been specified, followed by C2326. The lambda in blend has empty brackets. It uses t, so it must capture it, as [t].

C2039: 'optional': is not a member of 'std', in Monster.h, followed by more. The include for <optional> is missing from Monster.h. The build may get this far without it in some files, since Game.h includes it. But not every file that includes Monster.h includes Game.h too.

C2440: 'initializing': cannot convert from 'std::optional<Point>' to 'Point'. The goal is the optional itself. The place inside it is *monster.lastSeen.

C2440: 'initializing': cannot convert from 'const _Ty' to 'int &', in fleeMap. The loop is over distance_, the map's own distances, which a const function can't change. It should be over flee.distance_, the copy's.

The F3 numbers never change as you walk: they count from where you started. The map isn't being worked out each turn. The call to toPlayer_.compute is missing from finishTurn.

A badly wounded monster fights on, or keeps beside you, instead of running. The loop in fleeMap takes each distance by value, as int distance, so it changes copies. The flee map stays the distance map, which leads to you. It should be int& distance.

FAQ

Q) Why not A*, the famous pathfinding algorithm?

A) A* finds one path, from one place to another, quickly. A Dijkstra map gives every cell its way to the goals at once. Twenty monsters hunting the player share one map, where A* would search twenty times. Each is right for its job. In Chapter 23, the player travels to a cell they click, which is one path for one traveler, and that's A*'s job.

Q) Isn't it slow to work out a whole map every turn?

A) The map has 2,304 cells. Each comes out of the queue once, or a few times, and looks at eight neighbors. That's some tens of thousands of simple steps, which a computer does far faster than it draws a frame. The game does it once a turn, and only when you act, so you'll never notice it.

Q) Doesn't the map let every monster find the player from anywhere?

A) It would, if they used it. The map covers the whole dungeon, but the rules decide who reads it: a monster that can see the player, or one heading for where it last saw them. The rest wander, as before. The map is a way to get somewhere, not a way to know where the player is.

Q) Why does a monster that's lost the player give up when it can't get closer?

A) Usually because another monster is in the way, in a corridor. Waiting forever behind it would be silly. It forgets and wanders. If it sees the player again, it's hunting again.

AI Exercise (Optional)

A Dijkstra map can have many goals at once, and that's how Chapter 23's auto-explore works. Every unexplored cell is a goal, and the player walks downhill to the nearest. If you'd like to try a first version with an AI's help, open your AI chatbot of choice, and try a prompt like this:

"I'm writing a roguelike in C++ with SDL 3. A class, DijkstraMap, has compute(const Map& map, const std::vector<Point>& goals), which gives every floor cell its distance from the nearest goal, walking in eight directions, and at(Point cell), which gives a cell's distance, or DijkstraMap::UNREACHED. Map has at(x, y), which gives Terrain::Floor or Terrain::Wall, isExplored(x, y), and inBounds(x, y). A class, Game, has map_, player_.pos, a Point, and playerStep(Point step), which moves the player one step and passes the turn. I'd like the key o, SDLK_O, to take one step toward the nearest floor cell the player hasn't explored: make a DijkstraMap whose goals are every unexplored floor cell, and step to the player's lowest neighbor. If there's none, put 'Nothing left to explore.' in the log. Show me the code, with each curly brace on its own line, and explain it."

Notice what the preceding prompt does. It describes DijkstraMap and the map's functions exactly, so the AI can use them as they are, rather than invent its own. And it asks for one step a key press, which keeps the turn loop the same.

When the answer comes back, check how it picks the goals. Every unexplored floor cell is a lot of goals, but compute takes any number. That's the point: one map, many goals, and the player walks to the nearest. Then try it with seed 42, pressing o again and again, and watch the map open up.

Summary

Every monster now reads its way from a Dijkstra map: every cell's distance to the player, by the shortest way around the walls. Dijkstra's algorithm fills it in with a priority queue, once a turn, and F3 shows it. Monsters step downhill, in straight lines, remember where they last saw you, and go there. A badly wounded monster runs down Brogue's flee map, made by multiplying the distances by -1.2 and spreading them again, so it heads for somewhere far away, even past you, rather than into a corner. In Chapter 11, the monsters get minds of their own: each is asleep, wandering, hunting or fleeing, and noise can wake them.