The world we've built can move, collide and look natural, but the things in it still can't find their way through it. An enemy that wants to reach the player, or a unit sent across a maze of walls, needs a route: around the obstacles, and as short as it can be. That's pathfinding, one of the most visibly clever things a game does, and it's the subject of this chapter and the next. This one builds the foundation, a search that finds the shortest path across a grid. The next adds the guidance that makes it fast.
The search is old and simple. Flood outward from the start, one ring of cells at a time, and the first time the flood reaches the goal, it has found a shortest way there. That's breadth-first search. We'll treat a grid as a graph, flood it, and follow the flood back from the goal to find the path. Then we'll give the ground costs, a swamp that's slow to cross, and meet Dijkstra's algorithm, which finds the cheapest path rather than the shortest.
In this chapter, we will:
- Treat a grid as a graph of cells and their neighbors
- Flood a grid with breadth-first search, and see why a queue finds the shortest path
- Follow the came-from links back from the goal, and turn them into a path to walk
- See why many paths tie, and how the order of neighbors chooses between them
- Find the cheapest path over costly ground, with Dijkstra's algorithm and a priority queue
- Build Flood, which shows both searches spreading, live, as you paint walls and swamp
We'll start with the grid.
A Grid Is a Graph
Pathfinding works on a graph: a set of nodes, joined by edges. That sounds abstract, but a grid is a graph already. Each cell is a node, and an edge joins it to each of its neighbors: right, left, down and up. A wall is a cell that nothing joins, since you can't step into it. Finding a path across the grid is finding a route through that graph, from the start's node to the goal's.
Flood's grid is 40 cells across and 24 down, and like Chapter 19's grid, it keeps its cells in one list, row by row. A cell is a number, its row times COLS plus its column. Its column is that number's remainder after dividing by COLS, and its row is the quotient. Each cell holds a Tile: ground, wall or swamp. A cell's edges are its open neighbors, which this function finds:
// The open neighbors of a cell, up to four, in out: those on the grid that
// aren't walls. They're tried right, left, down, then up, or with zigzag
// on, the other way around on every other cell.
int openNeighbors(const std::vector<Tile>& tiles, int cell, bool zigzag,
int out[4])
{
const int dx[4] = { 1, -1, 0, 0 };
const int dy[4] = { 0, 0, 1, -1 };
int col = cell % COLS;
int row = cell / COLS;
bool backward = zigzag && (col + row) % 2 == 1;
int count = 0;
for (int k = 0; k < 4; ++k)
{
int d = backward ? 3 - k : k;
int c = col + dx[d];
int r = row + dy[d];
if (c < 0 || c >= COLS || r < 0 || r >= ROWS) continue;
if (tiles[r * COLS + c] == WALL) continue;
out[count++] = r * COLS + c;
}
return count;
}In the preceding code, the arrays dx and dy give the four directions as steps across and down. The order is right, left, down, then up. A neighbor off the grid is skipped, and so is a wall. The rest go into out, and the function returns how many there are, from 0 to 4. The zigzag setting turns the order around on every other cell, for a reason that Ties explains.
Breadth-First Search
Breadth-first search explores in waves. The start is wave 0. Its neighbors are wave 1, every cell one step away. Their neighbors that haven't been reached yet are wave 2, two steps away, and so on. The waves spread like water filling a room, around walls and through gaps, until every cell that can be reached has been.
A Queue Makes the Waves
The engine is a queue: a line that's first in, first out. The start goes in first. Then, over and over, the cell at the front comes out. Each of its neighbors that hasn't been reached yet joins the back, one step further from the start than the cell that found it.
That's enough to make the waves. At the start, the queue holds just the start, at distance 0. Taking out a cell at distance d puts cells at d + 1 at the back. So while there are cells at d at the front, everything behind them is at d + 1, and when the last d comes out, the queue holds only d + 1's. Those come out next, and put d + 2's behind them. The queue never holds more than two distances, one after the other, and the cells come out in order of their distance from the start.
That order is why the search finds shortest paths. When a cell is first reached, every cell closer to the start has already come out of the queue, so no shorter way to it can turn up later. The first time the flood reaches the goal, it has arrived by a shortest route. The next image follows a flood around a wall, on a small grid.
The start is 0, and its open neighbors are 1. The flood goes around both ends of the wall, and meets itself on the far side, where the goal is 8 steps away. Each arrow points to the cell that first reached its cell, and following them back from the goal gives the path. The row of numbers is the queue's order: three 1s after the 0, four 2s after them, and never a smaller number after a larger one.
The Code
Here's Flood's breadth-first search:
// Breadth-first search from start. Each cell's distance from it, in steps,
// goes in dist, or -1 if it can't be reached, and the cell it was reached
// from goes in came. A swamp is just ground to it, since it counts steps.
void bfs(const std::vector<Tile>& tiles, int start, bool zigzag,
std::vector<int>& dist, std::vector<int>& came)
{
std::fill(dist.begin(), dist.end(), -1);
std::fill(came.begin(), came.end(), -1);
std::queue<int> waiting;
dist[start] = 0;
waiting.push(start);
while (!waiting.empty())
{
int cell = waiting.front();
waiting.pop();
int next[4];
int count = openNeighbors(tiles, cell, zigzag, next);
for (int k = 0; k < count; ++k)
{
if (dist[next[k]] != -1) continue; // Queued already.
dist[next[k]] = dist[cell] + 1;
came[next[k]] = cell;
waiting.push(next[k]);
}
}
}In the preceding code, every dist starts at −1, meaning not reached. Every came starts at −1 too, meaning reached from nowhere. The queue is a std::queue<int> of cell numbers. Its front is the cell that's waited longest, and pop removes it. Each of the cell's open neighbors that's still at −1 gets a distance one more than the cell's, records the cell as where it came from, and joins the back. When the queue is empty, every cell the start can reach has its distance, and each of those except the start has a cell it came from.
Marked When Queued
A neighbor's distance is set when it joins the queue, not when it comes out. That matters. A cell can be the neighbor of several cells in the same wave. If it were marked only when it came out, each of them would see it as unreached, and queue it again. On an open grid, most cells would join the queue two or three times, and each copy would queue its own neighbors again. Marking it at once means the second neighbor to find it sees a distance there, and leaves it alone.
Stopping at the Goal
A search for one path can stop as soon as the goal comes out of the queue, since its distance is final by then. Here's a sketch of the line that does it, just after a cell is taken out:
// A sketch: stop as soon as the goal comes out of the queue.
if (cell == goal) return;On Flood's starting map, that takes 786 cells out of the queue instead of all 929 it can reach, since the goal is fairly far from the start. A goal close by saves far more. Flood floods everything anyway, since it shades every cell by its distance, and since some searches want every cell's distance, as the FAQ explains.
Following the Path Back
The flood gives every cell a distance, but a path is a list of cells to walk through. That's what came is for. Each cell remembers the cell that reached it, which is one step closer to the start. So starting at the goal, and following came from cell to cell, walks back to the start along a shortest path, one step at a time:
// The path from start to goal, by the came-from links: followed back from
// the goal, then turned around. Empty if the goal wasn't reached.
std::vector<int> pathTo(const std::vector<int>& came, int start, int goal)
{
std::vector<int> path;
if (goal != start && came[goal] == -1) return path;
for (int cell = goal; cell != start; cell = came[cell])
path.push_back(cell);
path.push_back(start);
std::reverse(path.begin(), path.end());
return path;
}Following the links gives the path from the goal to the start, which is backward for anything that wants to walk it. So std::reverse turns it around, and the path starts at the start. If the goal was never reached, it has no came, and the path is empty. A path from the start to itself is just the start.
There's another way to get the order right: search from the goal instead. Every cell's came then points one step toward the goal, so a walker anywhere on the grid only has to follow the arrows. That's a flow field, like Chapter 21's, with every arrow pointing the quickest way home.
Ties
A grid usually has many shortest paths. Walking from one corner of an open rectangle to the other, any mix of steps across and up, in any order, takes the same number of steps. The search keeps the first one it finds, and the neighbor order decides which that is. The next image shows two ties, on an empty grid.
With neighbors always tried in the same order, right before up, each wave comes out of the queue bottom row first. So a cell above the bottom row is first reached from the cell below it, and a cell on the bottom row from its left. Followed back from the goal, the links run straight down, then along the bottom to the start. So the path runs along the bottom, then straight up: correct, but it looks like a robot's. Turning the order around on every other cell, as openNeighbors does with zigzag on, makes neighboring cells prefer different directions. The path then alternates, and climbs in a staircase, which reads as more natural. Both are 8 steps, and Flood's Z key switches between them.
Costs and Dijkstra's Search
Breadth-first search counts steps, as if every step cost the same. Real ground doesn't. A road is quick, and mud, water or a swamp is slow.
When Steps Cost Different Amounts
In Flood, a step onto ground costs 1, and a step into a swamp costs 5:
// The cost of a step into a cell.
int stepCost(Tile tile) { return (tile == SWAMP) ? SWAMP_COST : 1; }Now the fewest steps isn't always the cheapest route. On Flood's starting map, a swamp lake lies across the straight way from the start to the goal. Breadth-first search goes straight through it: 39 steps, 11 of them into swamp, costing 83. Going around the lake takes 49 steps, all on ground, costing 49. A search that counts costs instead of steps should find that.
Cheapest First
Dijkstra's algorithm, published by Edsger Dijkstra in 1959, is breadth-first search with one change. Instead of the cell that's waited longest, the cell taken out next is always the one that's cheapest to reach so far. A line that's ordered by a number, rather than by arrival, is a priority queue.
The argument that it works is the same as before, with costs for distances. When a cell comes out, it's the cheapest of all the cells still waiting. Any other route to it would have to leave the cells already taken out through one of the cells still waiting, which already costs at least as much. Every step after that only adds to the cost, so that route can't be cheaper. So by the time a cell comes out, nothing cheaper can reach it any more, and its cost is final.
That argument needs one condition: no step may cost less than nothing. If a step could subtract, a route through an expensive cell could come back below a cost already called final, and the search would have stopped too soon. Costs of 0 are fine, but never negative.
The Code
Here's Flood's Dijkstra's search:
// Dijkstra's search from start. Each cell's cost from it goes in cost, or -1
// if it can't be reached, and the cell it was reached from goes in came. The
// cell taken next is always the cheapest one waiting.
void dijkstra(const std::vector<Tile>& tiles, int start, bool zigzag,
std::vector<int>& cost, std::vector<int>& came)
{
std::fill(cost.begin(), cost.end(), -1);
std::fill(came.begin(), came.end(), -1);
// Each entry is a cost and a cell; std::greater puts the least on top.
using Entry = std::pair<int, int>;
std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> waiting;
cost[start] = 0;
waiting.push({ 0, start });
while (!waiting.empty())
{
int sofar = waiting.top().first;
int cell = waiting.top().second;
waiting.pop();
if (sofar > cost[cell]) continue; // Stale: a cheaper way was found.
int next[4];
int count = openNeighbors(tiles, cell, zigzag, next);
for (int k = 0; k < count; ++k)
{
int through = sofar + stepCost(tiles[next[k]]);
if (cost[next[k]] == -1 || through < cost[next[k]])
{
cost[next[k]] = through;
came[next[k]] = cell;
waiting.push({ through, next[k] });
}
}
}
}In the preceding code, each entry in the queue is a std::pair of a cost and a cell. A std::priority_queue normally keeps its largest entry on top, so std::greater turns it around, to keep the least. Pairs compare by their first members, then their second. So the cheapest cost comes out first, and between equal costs, the lower cell number. A neighbor gets a new cost if it has none yet, or if the way through this cell is cheaper than the cost it has. Then it records where it came from, and joins the queue.
Stale Entries
A std::priority_queue can't change the cost of an entry already inside it. So when a cheaper way to a cell turns up, the search pushes the cell again, with its new cost, and leaves the old entry where it is. The old entry comes out later, with a cost higher than the cell's, and the line marked "Stale" skips it.
In Flood, that never happens. A step's cost depends only on the cell it steps into, and cells come out cheapest first. So the first cell to reach a neighbor offers the least that any cell ever will, and the neighbor's first cost is its final one. The check costs almost nothing, and it's part of the usual form of the search for a reason. Chapter 23 lets steps go diagonally, at a higher cost than straight steps, and then a cheaper way to a waiting cell can turn up after all.
What It Costs
Breadth-first search takes each cell out of the queue once, and looks at four neighbors. So its work grows in step with the number of cells: 960 on Flood's grid, which is nothing, every frame. Dijkstra's search does the same, plus the priority queue's upkeep. Putting an entry in and taking the cheapest out each cost time in step with the logarithm of the queue's size, a few steps for a queue of hundreds. On big maps, both searches spend most of that work in directions that lead nowhere near the goal, which is the problem Chapter 23 solves.
Building Flood
Flood is a grid of ground, walls and swamp, with a search spreading across it. Each cell is shaded by its distance from the green start, with bands so that the waves show, and the path to the red goal is drawn in amber. Space switches between breadth-first search and Dijkstra's. Drag to paint walls, or swamp after B, right-drag to erase, and drag the green and red cells to move them. Z switches the neighbor order, Enter replays the flood spreading, C clears the grid, and R brings back the starting map.
Get the code. The complete project is in the
Floodfolder of the book's repository.
Flood starts from the skeleton, with its timing and its mouse. It reuses setColor, from Chapter 8, and Chapter 8's lerp, which is in Vec2.h. Its Vec2.h is Noise Fields', since this chapter adds nothing to it. Here are its includes and its colors:
#include <algorithm>
#include <functional>
#include <queue>
#include <string>
#include <utility>
#include <vector>
#include "Vec2.h"
constexpr int WINDOW_WIDTH = 1000;
constexpr int WINDOW_HEIGHT = 700;
constexpr SDL_Color TEXT = { 235, 238, 242, 255 };
constexpr SDL_Color GREY = { 90, 100, 112, 255 };
constexpr SDL_Color GREEN = { 47, 158, 68, 255 };
constexpr SDL_Color RED = { 224, 49, 49, 255 };
constexpr SDL_Color AMBER = { 232, 89, 12, 255 };
constexpr SDL_Color STONE = { 55, 60, 70, 255 };
constexpr SDL_Color MUD = { 50, 46, 28, 255 };The start is green and the goal red, and the path is amber. Walls are stone grey, and swamp that the flood hasn't reached yet is dark mud. Then come the constants and the two enums:
// The grid: cells CELL pixels square, COLS across and ROWS down, below a
// strip GRID_TOP pixels high for the readout.
constexpr int CELL = 25;
constexpr int COLS = 40;
constexpr int ROWS = 24;
constexpr int GRID_TOP = 50;
// What a step into a swamp costs, where a step onto ground costs 1.
constexpr int SWAMP_COST = 5;
// How long a replay of the flood takes to spread, in seconds, and how many
// steps (or how much cost) each band of the shading spans.
constexpr float REPLAY_SECONDS = 3.0f;
constexpr int BAND = 4;
// What a cell holds, and what a drag with the mouse is doing.
enum Tile { GROUND, WALL, SWAMP };
enum Drag { NONE, PAINT, ERASE, MOVE_START, MOVE_GOAL };The grid's cells are 25 pixels square, so 40 of them fill the window's width, and 24 rows fill all but the 100 pixels kept for the readout and the controls. A replay spreads the flood over 3 seconds. The shading's bands are 4 steps wide. A Drag says what a drag with the mouse is doing, from the moment a button goes down until it comes up.
Drawing and Finding Cells
Two functions turn cell numbers into places on the screen and back. The first fills a cell:
// Fill a cell, a pixel in from its edges, so that the gaps between cells
// show as the grid's lines. A cell is a number: its row times COLS, plus its
// column.
void fillCell(SDL_Renderer* renderer, int cell, SDL_Color color)
{
setColor(renderer, color);
SDL_FRect r = { (float)(cell % COLS * CELL + 1),
(float)(GRID_TOP + cell / COLS * CELL + 1),
CELL - 2.0f, CELL - 2.0f };
SDL_RenderFillRect(renderer, &r);
}A cell's column times CELL is its left edge, and its row times CELL, below the readout's strip, is its top. Filling a pixel in from each edge leaves a 2-pixel gap between cells, which shows as the grid's lines. The second finds the cell under a point:
// The cell at a point in the window, or -1 if the point is off the grid.
int cellAt(float x, float y)
{
if (x < 0.0f || y < GRID_TOP) return -1;
int col = (int)(x / CELL);
int row = (int)((y - GRID_TOP) / CELL);
if (col >= COLS || row >= ROWS) return -1;
return row * COLS + col;
}Dividing by CELL and dropping the fraction gives a column and a row. A point left of the window, or above the grid, or past its right or bottom edge, gives −1.
The Starting Map
The starting map is built by a function, so that R can build it again:
// The starting map: a wall with a gap near the start, a swamp lake in the
// middle, and a wall hanging down from the top near the goal.
std::vector<Tile> startingMap()
{
std::vector<Tile> tiles(COLS * ROWS, GROUND);
for (int row = 3; row <= 20; ++row)
if (row != 11 && row != 12) tiles[row * COLS + 11] = WALL;
for (int row = 0; row < ROWS; ++row)
for (int col = 0; col < COLS; ++col)
{
float dx = (col - 21) / 5.5f;
float dy = (row - 11.5f) / 8.0f;
if (dx * dx + dy * dy <= 1.0f) tiles[row * COLS + col] = SWAMP;
}
for (int row = 0; row <= 14; ++row) tiles[row * COLS + 30] = WALL;
return tiles;
}The first wall runs down column 11, from row 3 to row 20, with a gap at rows 11 and 12, in line with the start. The swamp lake is every cell whose column and row put it inside an ellipse, centered on column 21 and row 11.5, reaching 5.5 columns to each side and 8 rows up and down. The test is Chapter 11's test for a point in a circle, squared distance against 1, with each axis stretched first. The second wall hangs from the top of column 30 down to row 14, so that both searches must pass below it.
The functions from A Grid Is a Graph to Stale Entries come next in the file. After them comes one more for the readout, which adds up what a path costs:
// What a path costs: the cost of each step, into every cell after the first.
int pathCost(const std::vector<Tile>& tiles, const std::vector<int>& path)
{
int total = 0;
for (size_t i = 1; i < path.size(); ++i) total += stepCost(tiles[path[i]]);
return total;
}The first cell is where the path starts, so it costs nothing. Every cell after it is a step into it. The last function picks each reached cell's color:
// A reached cell's color, from dark when it's near to light when it's far:
// blue on ground, and brown in a swamp. On ground, every other band of
// BAND steps is a little lighter, so that the flood's waves show.
SDL_Color shade(Tile tile, int d, int farthest)
{
float t = (float)d / farthest;
float lift = (tile == GROUND && (d / BAND) % 2 == 1) ? 18.0f : 0.0f;
if (tile == SWAMP)
return { (Uint8)(lerp(70, 150, t) + lift),
(Uint8)(lerp(60, 130, t) + lift),
(Uint8)(lerp(30, 60, t) + lift), 255 };
return { (Uint8)(lerp(40, 70, t) + lift), (Uint8)(lerp(70, 180, t) + lift),
(Uint8)(lerp(120, 210, t) + lift), 255 };
}The fraction t runs from 0 at the start to 1 at the farthest cell, and lerp blends from a dark color to a light one by it, as Chapter 8 blended colors. On ground, every other band of 4 steps is lifted by 18 in each channel, so the shading shows rings, the flood's waves. A swamp isn't banded, since under Dijkstra's search its costs rise 5 at a step, and its bands would be a cell wide.
The State
The state goes after the font is loaded:
// The map, and the start and the goal. Then the settings: the search,
// the brush and the neighbor order. Then the drag in progress, the
// replay's time so far, or -1 when there's no replay, and the search's
// results: each cell's distance or cost, and where it was reached from.
std::vector<Tile> tiles = startingMap();
int start = 11 * COLS + 4;
int goal = 11 * COLS + 35;
bool useDijkstra = false;
Tile brush = WALL;
bool zigzag = false;
Drag drag = NONE;
float replay = -1.0f;
std::vector<int> dist(COLS * ROWS);
std::vector<int> came(COLS * ROWS);The start and the goal sit in row 11, at columns 4 and 35, either side of everything. The search's results, dist and came, are made once at the grid's size. Each search fills them afresh, with std::fill, rather than making new ones every frame.
The Events
The keys change the settings or the map, and a mouse button starts a drag:
// Events: quitting, and the keys and clicks that happen once.
SDL_Event event;
while (SDL_PollEvent(&event))
{
if (event.type == SDL_EVENT_QUIT) running = false;
else if (event.type == SDL_EVENT_KEY_DOWN)
{
if (event.key.key == SDLK_ESCAPE) running = false;
else if (event.key.key == SDLK_SPACE)
useDijkstra = !useDijkstra;
else if (event.key.key == SDLK_B)
brush = (brush == WALL) ? SWAMP : WALL;
else if (event.key.key == SDLK_Z) zigzag = !zigzag;
else if (event.key.key == SDLK_RETURN) replay = 0.0f;
else if (event.key.key == SDLK_C)
tiles.assign(COLS * ROWS, GROUND);
else if (event.key.key == SDLK_R) tiles = startingMap();
}
else if (event.type == SDL_EVENT_MOUSE_BUTTON_DOWN)
{
// A left drag from the start or the goal moves it, and any
// other left drag paints. A right drag erases.
int at = cellAt(event.button.x, event.button.y);
if (at < 0) continue;
if (event.button.button == SDL_BUTTON_LEFT)
{
if (at == start) drag = MOVE_START;
else if (at == goal) drag = MOVE_GOAL;
else drag = PAINT;
}
else if (event.button.button == SDL_BUTTON_RIGHT) drag = ERASE;
}
else if (event.type == SDL_EVENT_MOUSE_BUTTON_UP) drag = NONE;
}In the preceding code, B switches the brush between wall and swamp, and Enter starts a replay by setting replay to 0. C fills the map with ground by assign, and R builds the starting map again. A button pressed off the grid does nothing, since continue skips to the next event. A left button on the start or the goal starts moving it, and anywhere else starts painting. The right button starts erasing, and letting go of either ends the drag.
Each Frame's Work
After the mouse is read, the drag does its work, and the search runs:
// The drag works on the cell under the mouse. Painting and erasing
// leave the start and the goal alone, and neither can move onto a
// wall or onto the other.
int hover = cellAt(mx, my);
if (hover >= 0)
{
bool free = hover != start && hover != goal;
if (drag == PAINT && free) tiles[hover] = brush;
else if (drag == ERASE && free) tiles[hover] = GROUND;
else if (drag == MOVE_START && free && tiles[hover] != WALL)
start = hover;
else if (drag == MOVE_GOAL && free && tiles[hover] != WALL)
goal = hover;
}
// The search runs afresh every frame, since the map may have changed.
if (useDijkstra) dijkstra(tiles, start, zigzag, dist, came);
else bfs(tiles, start, zigzag, dist, came);
std::vector<int> path = pathTo(came, start, goal);
int farthest = std::max(1, *std::max_element(dist.begin(), dist.end()));In the preceding code, painting and erasing skip the start and the goal, so that neither can be painted over. Neither can move onto a wall, or onto the other. Then the search runs, every frame, since the map may have changed. On 960 cells, that's no burden. The path comes from pathTo, and farthest is the largest distance or cost, at least 1, so that the shading's division is safe even when the start is walled in.
A replay shows only some of the cells:
// A replay shows the flood spreading: only the cells whose distance
// is within its share of the farthest, so far.
int shown = farthest;
if (replay >= 0.0f)
{
replay += dt;
shown = (int)(farthest * replay / REPLAY_SECONDS);
if (replay >= REPLAY_SECONDS) replay = -1.0f;
}Over its 3 seconds, the replay raises shown from 0 to the farthest distance, and a cell is drawn only once its distance is within shown. Breadth-first search reaches cells in order of distance, and Dijkstra's in order of cost, so this shows each search reaching cells in the order it really does.
Drawing
After the skeleton clears the screen, every cell is drawn:
// Each cell: walls in stone, reached cells shaded by how far they
// are, and swamp that isn't reached yet in mud.
for (int cell = 0; cell < COLS * ROWS; ++cell)
{
if (tiles[cell] == WALL)
fillCell(renderer, cell, STONE);
else if (dist[cell] >= 0 && dist[cell] <= shown)
fillCell(renderer, cell,
shade(tiles[cell], dist[cell], farthest));
else if (tiles[cell] == SWAMP)
fillCell(renderer, cell, MUD);
}A cell that isn't reached, or isn't shown yet, stays the background. A swamp cell shows as mud instead, so that you can see where it is. Then come the path and the two ends:
// The path, once the flood has reached the goal, then the start and
// the goal on top.
if (!path.empty() && dist[goal] <= shown)
for (int cell : path) fillCell(renderer, cell, AMBER);
fillCell(renderer, start, GREEN);
fillCell(renderer, goal, RED);The path waits until the replay has reached the goal, and the start and the goal go on top of it. Last come the readout and the controls:
// The readout: the search and its path, then the settings.
int reached = (int)std::count_if(dist.begin(), dist.end(),
[](int d) { return d >= 0; });
std::string result = "no path: the goal is walled off";
if (!path.empty())
result = "a path of " + std::to_string(path.size() - 1) +
" steps, costing " + std::to_string(pathCost(tiles, path));
drawText(renderer, font,
std::string(useDijkstra ? "Dijkstra's search" :
"breadth-first search") + ": " + result,
12, 8, TEXT);
drawText(renderer, font,
"cells reached " + std::to_string(reached) + " brush " +
(brush == WALL ? "wall" : "swamp") + " neighbor order " +
(zigzag ? "zigzag" : "fixed"), 12, 26, GREY);
drawText(renderer, font,
"[Drag] paint [Right-drag] erase [B] wall or swamp "
"drag the green or red cell", 12, WINDOW_HEIGHT - 46, GREY);
drawText(renderer, font,
"[Space] BFS or Dijkstra [Z] zigzag [Enter] replay "
"[C] clear [R] reset [Esc] quit", 12, WINDOW_HEIGHT - 26,
GREY);In the preceding code, std::count_if counts the cells with a distance of 0 or more. Its test is a lambda: a small function with no name, written where it's used. The [] begins it, and could list variables from the code around it for it to use, though this one needs none. Then come its parameter, int d, and its body, which says whether d is 0 or more. The std::count_if function calls it once for each cell, and counts the times it says yes.
The path's length in steps is one less than its number of cells. The readout gives the steps and the cost, whichever search found the path, so that the two searches can be compared on the same map.
Trying It Out
Run the demo. It starts with breadth-first search, on the starting map. The next image shows it.
The bands are the waves: diamonds around the start, since four-way steps make every ring of equal distance a diamond. They pour through the gap in the first wall, and bend around the second. The path goes straight through the swamp, since breadth-first search counts it as ground: 39 steps, costing 83. Then try it, step by step:
- Switch to Dijkstra's search. Press Space. The path swings around the swamp: 49 steps, costing 49.
- Watch it spread. Press Enter. The flood spreads over three seconds, in the order Dijkstra's search takes the cells. It runs around the swamp before it gets far into it.
- Zigzag. Press Space for breadth-first search again, then Z. The path is still 39 steps, but it drops out of row 11 at once, and stairs its way down. By chance, it crosses the swamp lower down, where it's narrower, so it costs 75.
- Paint a swamp. Press Space for Dijkstra's search, and B for the swamp brush. Then paint a band of swamp, at least two cells wide, from the bottom of the lake to the bottom edge. The path goes over the top of the lake instead, along the first wall: 55 steps, costing 55.
- Wall in the goal. Press B for walls again, and paint a ring around the red cell. The readout says there's no path.
- Move the ends. Press R for the starting map, then drag the green or red cell somewhere new. The flood and the path follow at once.
The next image shows step 1.
The path is ten steps longer, and 34 cheaper. On ground, the bands are still diamonds. Inside the swamp, the shading grows lighter fast, since each step in costs five. The next image shows step 2, held part of the way through.
The flood has gone around both sides of the lake, and passed it, while the swamp's middle is still unreached. Every cell shown costs up to 29 to reach. Three steps into the swamp cost 15, where three steps on ground cost 3. That's Dijkstra's search, taking the cheap cells first.
FAQ
Q) Can a tile cost less than nothing, such as a speed pad?
A) Not with Dijkstra's search. Its rule that a cell's cost is final when it comes out of the queue depends on every step adding to the cost. With a negative step, a cheaper way could turn up after a cell was settled, and the search would have used the wrong cost. A speed pad can cost 0, or the rest of the map can cost more, so that the pad is the cheapest step but still not negative.
Q) Why flood the whole map, rather than search for one path?
A) When many things share one target, such as twenty monsters chasing the player, one flood from the target serves them all. Every cell then knows its distance to the player, and each monster steps to whichever neighbor has the smallest. That's often called a Dijkstra map, and it costs the same as one search, however many monsters use it. A search for a single path from one place to another is Chapter 23's A*.
Q) Can paths go diagonally?
A) Yes, with eight neighbors instead of four. A diagonal step covers more ground, about 1.41 times a straight one, so it should cost more, or paths will zigzag diagonally for no reason. And a diagonal step shouldn't squeeze between two walls that touch at a corner. Chapter 23 adds both.
Exercises
The first three exercises need only a pencil. The others change Flood.
- Flood by hand (paper). On a 4 by 4 grid with no walls, the start is the top-left cell. Label each cell with its distance. How many cells are at each distance, and what shape does each set of equal distances make?
- Dijkstra by hand (paper). A row of five cells runs from the start to the goal, and the middle one is swamp, costing 5. Below the row is a second row of ground. What's the cheapest path's cost, and its number of steps? How expensive must the swamp be before the path goes around it?
- Marked too late (paper). In Figure 22.1, suppose cells were marked only when they came out of the queue. Which cells would join the queue more than once, in the first three waves?
- Roads (code). Add a third terrain, road, painted with a third brush. Make ground cost 3 and road cost 1, and watch Dijkstra's paths go out of their way to follow a road. What happens to breadth-first search's paths?
- Follow the arrows (code). Add a key that searches from the goal instead of the start, and draws each reached cell's
cameas a short line, pointing toward the goal. Then let a dot wander from the mouse, following the lines home.
For the code exercises, work on a copy of the demo's folder, so that the original stays as the chapter describes it.
AI Exercise (Optional)
One flood can steer a whole crowd. With an AI's help, you can turn Flood into a small chase, where a pack of monsters hunts the player through a maze. Open your AI chatbot of choice, and try a prompt like this:
"I have a C++ demo using SDL3 with a 40 by 24 grid of tiles (ground, wall, swamp) stored row by row in a std::vector, and these functions: openNeighbors(tiles, cell, zigzag, out), which fills out with up to four open neighbors, and dijkstra(tiles, start, zigzag, cost, came), which fills cost with every cell's cost from start, or -1, where a swamp costs 5 and ground 1. Please add a player that moves one cell at a time with the arrow keys, and ten monsters at random open cells. Every time the player moves, run dijkstra once from the player's cell. Then move each monster one cell, to its open neighbor with the lowest cost, but never onto another monster. Draw the player in green and the monsters in red, and end the game when a monster reaches the player. Explain why one search serves all ten monsters."
That prompt describes your functions, so the AI builds on them, rather than writing a search of its own. It uses one search from the player, which is the Dijkstra map from this chapter's FAQ. And it asks why that works, which you can check against Following the Path Back: costs from the player point every monster the cheapest way to it.
Then paint some swamp, and watch the monsters go around it, unless going through is cheaper. Then try monsters that move only every other turn, and see whether you can lead them into a loop.
Summary
A grid is a graph: cells are the nodes, and each is joined to its open neighbors, while walls are joined to nothing. Breadth-first search floods it from the start with a first-in, first-out queue. The queue holds one distance, then the next, so cells come out in order of distance, and each is first reached by a shortest route. A cell is marked when it's queued, so that it's queued once. Each cell's came remembers the cell that reached it, and following those links back from the goal, then reversing them, gives a path to walk. Many shortest paths tie, and the neighbor order picks one: a fixed order makes long straight runs, and an order that alternates makes a staircase. When steps cost different amounts, such as 5 for a swamp, Dijkstra's search takes the cheapest waiting cell first, from a priority queue. Its argument, that a cell's cost is final when it comes out, needs every step to cost 0 or more. A priority queue can't lower an entry, so the search pushes again and skips stale entries, though with costs paid on entering a cell, none ever arise. On Flood's starting map, breadth-first search crosses the swamp in 39 steps costing 83, and Dijkstra's goes around in 49 costing 49. Chapter 23 makes the search head toward its goal, with A*, so that it no longer floods in every direction.