Dijkstra Map Pathfinding

The monsters in Part 5 chased you, but they were easily fooled — step behind a pillar and a goblin would mash itself against the wall, because its "AI" was just "move toward the player on the longer axis." It had no idea what a wall was. Part 7 replaces that with one of the most elegant techniques in the whole genre: the Dijkstra map. With it, every monster always knows the true shortest path to you through the dungeon — and, with the very same data read backwards, knows exactly how to run away.

The Idea

Forget per-monster pathfinding. Instead, once per turn, we flood the entire dungeon with a single number per tile: how many steps that tile is from the player. The player's tile is 0, its neighbours are 1, their neighbours are 2, and so on, the numbers flowing around walls like water filling a cave.

That grid of numbers is a Dijkstra map. Once you have it, pathfinding stops being a search and becomes trivial: a monster just looks at its four neighbours and steps to the one with the lowest number. It's walking downhill, and downhill always leads to the player by the shortest route — around pillars, through doorways, down corridors. No monster ever has to "search"; they all read the same shared map.

Because every step costs the same (1), this flood is really a breadth-first search. "Dijkstra map" is the name the roguelike community uses (after the algorithm's weighted cousin), and it stuck — so we'll use it too.

The DijkstraMap Class

It's a grid of distances and one method to fill it. New files DijkstraMap.h / .cpp:

#pragma once
#include "Map.h"

class DijkstraMap
{
public:
    static const int UNREACHABLE = 1 << 30;

    int dist[MAP_HEIGHT][MAP_WIDTH];

    void compute(const Map& map, int goalX, int goalY);

    int at(int x, int y) const { return dist[y][x]; }
};

UNREACHABLE is a deliberately huge sentinel — bigger than any real distance — so walls and sealed-off tiles compare as "infinitely far" and a monster will never choose to step onto one.

The flood — breadth-first from the goal

#include "DijkstraMap.h"
#include <queue>
#include <utility>

void DijkstraMap::compute(const Map& map, int goalX, int goalY)
{
    for (int y = 0; y < MAP_HEIGHT; ++y)
        for (int x = 0; x < MAP_WIDTH; ++x)
            dist[y][x] = UNREACHABLE;

    if (map.tiles[goalY][goalX].type != TileType::Floor)
        return;

    std::queue<std::pair<int, int>> frontier;
    dist[goalY][goalX] = 0;
    frontier.push({ goalX, goalY });

    static const int dx[4] = {  0,  0, -1, +1 };
    static const int dy[4] = { -1, +1,  0,  0 };

    while (!frontier.empty())
    {
        std::pair<int, int> cur = frontier.front();
        frontier.pop();
        int cx = cur.first, cy = cur.second;
        int next = dist[cy][cx] + 1;

        for (int i = 0; i < 4; ++i)
        {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            if (nx < 0 || nx >= MAP_WIDTH || ny < 0 || ny >= MAP_HEIGHT) continue;
            if (map.tiles[ny][nx].type != TileType::Floor) continue;
            if (next < dist[ny][nx])
            {
                dist[ny][nx] = next;
                frontier.push({ nx, ny });
            }
        }
    }
}

A queue visits tiles in order of increasing distance, so the first time we reach any tile, we've reached it by a shortest path — that's the defining property of breadth-first search, and it's why we never need to revisit or second-guess a tile. On the 64×36 grid this is a couple of thousand cheap operations, run once per turn: completely negligible for a turn-based game.

Wiring It Into the Game

Thanks to Part 6, this is a small, contained change. Game gains one member — the map is refreshed each turn — declared in Game.h:

#include "DijkstraMap.h"
// ...
DijkstraMap m_toPlayer;     // distance-to-player field, refreshed each turn

Then monstersAct is rewritten to roll downhill. At the top of the turn we flood once from the player; every monster then reads the shared map:

void Game::monstersAct()
{
    m_toPlayer.compute(m_map, m_player.x, m_player.y);

    static const int dx[4] = {  0,  0, -1, +1 };
    static const int dy[4] = { -1, +1,  0,  0 };

    for (Monster& m : m_monsters)
    {
        if (!m.isAlive()) continue;

        if (!m_map.tiles[m.y][m.x].visible) { m.wander(m_map, m_rng); continue; }

        if (std::abs(m_player.x - m.x) + std::abs(m_player.y - m.y) == 1)
        {
            attack(m, m_player);
            continue;
        }

        bool flee = (m.hp * 3 <= m.maxHp);   // wounded? run

        int bestX = m.x, bestY = m.y;
        int bestVal = m_toPlayer.at(m.x, m.y);

        for (int i = 0; i < 4; ++i)
        {
            int nx = m.x + dx[i], ny = m.y + dy[i];
            if (nx < 0 || nx >= MAP_WIDTH || ny < 0 || ny >= MAP_HEIGHT) continue;
            if (m_map.tiles[ny][nx].type != TileType::Floor) continue;
            if (nx == m_player.x && ny == m_player.y) continue;
            if (monsterAt(nx, ny)) continue;

            int v = m_toPlayer.at(nx, ny);
            if (v == DijkstraMap::UNREACHABLE) continue;

            if (flee ? (v > bestVal) : (v < bestVal))
            {
                bestVal = v; bestX = nx; bestY = ny;
            }
        }

        m.x = bestX; m.y = bestY;
    }
}

We start bestVal at the monster's own tile's distance, so it only moves when a neighbour is genuinely better — no jittering in place. A chaser keeps the comparison v < bestVal (downhill, toward you). And here's the payoff promised back in Part 5:

The Same Map, In Reverse

To make a frightened monster flee, we change exactly one thing: seek the highest neighbour instead of the lowest. That's the flee ternary — v > bestVal when wounded. A monster below a third of its health turns and runs directly away from you, taking the route that increases its distance fastest, all from the identical distance field. One flood, two behaviours. (The "proper" Brogue-style flee multiplies the whole map by a negative number and re-floods so monsters round corners to escape rather than backing into dead ends — a great experiment once you've got this working.)

Try It

Build and run, then test the thing that used to break: let a monster see you, step around a wall or a pillar, and watch it come around instead of bumping the corner. Pull several into a corridor and they queue up to reach you. Wound one — get a goblin low without killing it — and it will break and run. The dungeon finally feels inhabited by things that can think their way to you.

Complete Code

DijkstraMap.h and DijkstraMap.cpp are listed in full above. In Game.h, add #include "DijkstraMap.h" and the m_toPlayer member; in Game.cpp, replace monstersAct with the version above and bump the window-title string to "Part 7". Everything else in Game — and every other file — is unchanged from Part 6.

Common Errors

What's Next

Part 8 begins the loot. We add items lying on the dungeon floor, an inventory you can open, and the classic roguelike identification twist — that unidentified potion might be healing, might be poison, and you won't know until you drink it or identify it. The Game class gives us a clean home for the inventory, and the Dijkstra map you built here will return in later parts to send monsters toward items and stairs, not just the player.