Chapter 22's searches find the best path, but they find it the hard way. Breadth-first search and Dijkstra's both spread out evenly in every direction, so they explore just as far away from the goal as toward it. On A-Star Explorer's starting map, Dijkstra's search explores 821 of the map's 930 open cells before it reaches the goal. A person looking at the map wouldn't do that. They'd look toward the goal first, and only search elsewhere when something blocked the way.
A* searches that way. It's Dijkstra's search with one addition, an estimate of the cost still to go, which pulls the search toward the goal. With a good estimate, it explores a small part of the map, and still finds the best path. Peter Hart, Nils Nilsson and Bertram Raphael published it in 1968, for Shakey, an early robot that planned its own moves. It's the search most games use, and this chapter builds it, sees why it works, and shows how to choose the estimate.
In this chapter, we will:
- Guide a search with a heuristic, an estimate of the cost still to go
- Order the search by f = g + h, and walk A*'s main loop
- See why an estimate that never overestimates finds the best path, and when a search never has to look back
- Match the heuristic to the moves: Manhattan, Euclidean, Chebyshev and octile
- Break ties, weight the heuristic for speed, and smooth the path
- Build A-Star Explorer, which shows what each heuristic explores
We'll start with the estimate.
The Heuristic
Dijkstra's search takes the cell that's cheapest to reach so far. That's the right order for finding every cell's cost, but it ignores where the goal is.
An Estimate of the Rest
A heuristic is an estimate of the cost from a cell to the goal, worked out from their positions alone, without searching. On an open grid with steps in four directions, the estimate might be the number of steps across plus the number down, as if there were no walls. It's quick to work out, and it's often exactly right, when no wall is in the way.
The estimate doesn't have to be right. It only has to be good enough to say which cells are worth exploring first. How good it has to be, for the search still to find the best path, is the subject of Why A* Finds the Best Path.
A*
A* keeps Dijkstra's search, and changes only the order in which cells come out of the queue.
f = g + h
Each cell has three numbers. Its g is the cost of the best way to it found so far, as in Dijkstra's search. Its h is the heuristic's estimate of the cost from it to the goal. And its f is their sum, the estimated cost of the whole route from the start to the goal through that cell:
f = g + hA* takes the waiting cell with the least f. Dijkstra's search asks which cell is cheapest to reach. A* asks which cell is on the cheapest-looking route to the goal. The cells behind the start, away from the goal, look expensive, since their h is large. So the search heads toward the goal, and spreads sideways only when the cells ahead turn out dearer than they looked.
The next image follows A* on a small grid, with steps in four directions, each costing 1, and the Manhattan heuristic: the steps across plus the steps down.
The start's f is 4, its h, since the goal is four steps away in a straight line. The cell toward the goal also has an f of 4, and it's explored second. But the wall blocks the way from there. So the cells with an f of 6 come next: the two beside the wall, then the three around the start, even the one behind it. Then come the cells around the wall, with an f of 8, the true cost. The estimate starts optimistic, and as the search learns about the wall, f rises to the truth. A* explores 13 cells, where Dijkstra's search explores 30.
A Step and Its Cost
A-Star Explorer lets steps go diagonally, as well as straight. A diagonal step covers more ground, the square root of 2 times as much, so it costs more. The demo's costs are whole numbers: 100 for a straight step and 142 for a diagonal one. That's 100 times the square root of 2, which is 141.4, rounded up, for a reason that Matching the Heuristic to the Moves explains. Whole numbers make equal costs exactly equal, which Ties needs.
A diagonal step also can't squeeze between two walls that touch at a corner, or cut across the corner of one wall. This function takes one step, in any of the eight directions, and says whether it's allowed:
// The cell one step from cell in direction k, or -1 if the step isn't
// allowed: off the grid, into a wall, or diagonally past a wall's corner.
// Directions 0 to 3 are right, left, down and up, and 4 to 7 are diagonal.
int stepFrom(const std::vector<Tile>& tiles, int cell, int k)
{
const int dx[8] = { 1, -1, 0, 0, 1, 1, -1, -1 };
const int dy[8] = { 0, 0, 1, -1, 1, -1, 1, -1 };
int col = cell % COLS;
int row = cell / COLS;
int c = col + dx[k];
int r = row + dy[k];
if (c < 0 || c >= COLS || r < 0 || r >= ROWS) return -1;
if (tiles[r * COLS + c] == WALL) return -1;
// A diagonal step passes between two cells, and both must be open.
if (k >= 4 &&
(tiles[row * COLS + c] == WALL || tiles[r * COLS + col] == WALL))
return -1;
return r * COLS + c;
}The arrays dx and dy hold the four straight directions first, then the four diagonal ones. A step off the grid or into a wall gives −1. A diagonal step passes between two cells: the one beside the start in its new column, and the one in its new row. Both must be open, or the step would brush a wall's corner, which would let a path squeeze through a gap that a character couldn't.
The Code
A search returns what it found in one struct:
// What a search finds: each cell's cost from the start so far, g, the cell
// it was reached from, and whether it's closed; how many cells it closed,
// and whether one of them was the goal.
struct Search
{
std::vector<int> g;
std::vector<int> came;
std::vector<bool> closed;
int explored;
bool found;
};A cell is closed once it has come out of the queue and been explored, as Dijkstra's search settled a cell. A cell with a g that isn't closed is still open, waiting in the queue. Here's the search:
// A* from start to goal. The cell taken next is the waiting one with the
// least f: its cost so far, g, plus the heuristic's estimate of the rest,
// times a weight in tenths. Between equal f, with tieBreak on, the one with
// the larger g, which is further along, comes out first.
Search aStar(const std::vector<Tile>& tiles, int start, int goal,
Heuristic kind, bool diagonals, int weight, bool tieBreak)
{
Search s = { std::vector<int>(COLS * ROWS, INT_MAX),
std::vector<int>(COLS * ROWS, -1),
std::vector<bool>(COLS * ROWS, false), 0, false };
// Each entry is f, a tie-breaker and a cell; the least comes out first.
using Entry = std::tuple<int, int, int>;
std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> open;
s.g[start] = 0;
open.push({ estimate(kind, start, goal) * weight / 10, 0, start });
while (!open.empty())
{
int cell = std::get<2>(open.top());
open.pop();
if (s.closed[cell]) continue; // Stale: closed already.
s.closed[cell] = true;
++s.explored;
if (cell == goal)
{
s.found = true;
break;
}
for (int k = 0; k < (diagonals ? 8 : 4); ++k)
{
int next = stepFrom(tiles, cell, k);
if (next < 0 || s.closed[next]) continue;
int through = s.g[cell] + (k >= 4 ? DIAGONAL : STRAIGHT);
if (through < s.g[next])
{
s.g[next] = through;
s.came[next] = cell;
int f = through + estimate(kind, next, goal) * weight / 10;
open.push({ f, tieBreak ? -through : 0, next });
}
}
}
return s;
}In the preceding code, every g starts at INT_MAX, the largest int. That means not reached, and any real cost is less. Each entry in the queue is a std::tuple of three numbers. A tuple compares by its first number, then its second, then its third, as a pair does. So with std::greater, the entry with the least f comes out first. The second number is the tie-breaker, which Ties explains, and the third is the cell. The start goes in with a g of 0, so its f is its h alone.
Each time round, the cell with the least f comes out. If it's closed already, the entry is stale, left behind when a cheaper way to the cell was found, and it's skipped. Otherwise the cell is closed and counted. If it's the goal, the search is over. If not, each step from it is tried. A neighbor that's closed already is left alone. Any other gets a new g, if this way to it is cheaper than the best so far, and goes into the queue with its new f.
The weight multiplies h, in tenths, so a weight of 10 leaves it alone. Weighted A* explains the other weights.
When the Goal Comes Out
The search stops when the goal comes out of the queue, not when it first goes in. The first time the goal is reached, it may be by a dear route, from a cell that happened to be explored early. A cheaper route may still be waiting, through a cell whose f is less than the goal's f so far. When the goal comes out, its f is the least in the queue, so nothing waiting can beat it.
Why A* Finds the Best Path
A* finds the best path when its heuristic is admissible: it never overestimates, so it's never more than the true cost from a cell to the goal.
Admissible
The argument is short. Take a best path from the start to the goal. While the goal hasn't come out of the queue, some cell on that path is waiting in the queue, with its true best g. Its f is that g plus an h that doesn't overestimate, so f is no more than the best path's cost. The goal, reached by a worse route, would have an f more than that, so the cell on the best path comes out first. That happens again and again, until the best path's cells have all come out, and the goal comes out last, at the best cost.
An overestimating heuristic breaks the argument. It can make a cell on the best path look dearer than a worse route to the goal, so the worse route comes out first, and the search ends with it.
Consistent
A* in this chapter never looks at a closed cell again. That's safe only if a cell's g is final when it's closed, as it was in Dijkstra's search. For that, the heuristic must be consistent: for every step from a cell a to a neighbor b, the estimate at a is no more than the step's cost plus the estimate at b.
h(a) <= cost(a, b) + h(b)A consistent heuristic never drops by more than a step costs, so along any path, f never goes down. Then cells come out in order of f, just as Dijkstra's search took them in order of g, and the same argument says that when a cell comes out, its g is final. Every consistent heuristic is admissible, too.
All four of this chapter's heuristics are consistent with the moves they suit, and a heuristic that's admissible on a grid usually is. A* that reopened closed cells would cope with a heuristic that's admissible but not consistent. It would explore some cells twice, so A-Star Explorer doesn't bother.
Matching the Heuristic to the Moves
The heuristic should be as close to the true cost as it can be, without ever going over. The closer it is, the less A* explores. And what the true cost is depends on which steps are allowed.
Four Heuristics
With dx the steps across to the goal and dy the steps down, four heuristics are common:
Manhattan = dx + dy
Euclidean = √(dx² + dy²)
Chebyshev = max(dx, dy)
octile = max(dx, dy) + (√2 - 1) × min(dx, dy)Manhattan counts steps in four directions, so on an open grid with those steps, it's exact. Euclidean is the straight-line distance, which no route can beat, whatever the steps. Chebyshev fits steps in eight directions that all cost the same, since a diagonal step then covers one across and one down for the price of one. Octile fits steps in eight directions where a diagonal costs the square root of 2: as many diagonal steps as the smaller of dx and dy, then straight steps for the rest. The next image shows the cells that each heuristic puts within 5 steps of a goal.
The shapes say what each heuristic believes about moving. Manhattan's diamond believes that diagonals don't exist. Chebyshev's square believes they're free. Octile's octagon is the true shape of eight-direction moves. Euclidean's disc is a little bigger, and holds the octagon, since its estimate is never more than octile's.
In the Demo
Here's A-Star Explorer's heuristic, in its whole-number costs:
// The heuristic's estimate of the cost from cell a to cell b, from how far
// apart they are across, dx, and down, dy.
int estimate(Heuristic kind, int a, int b)
{
int dx = std::abs(a % COLS - b % COLS);
int dy = std::abs(a / COLS - b / COLS);
switch (kind)
{
case MANHATTAN:
return STRAIGHT * (dx + dy);
case EUCLIDEAN:
return (int)(STRAIGHT * std::sqrt((double)(dx * dx + dy * dy)));
case CHEBYSHEV:
return STRAIGHT * std::max(dx, dy);
case OCTILE:
return STRAIGHT * std::max(dx, dy) +
(DIAGONAL - STRAIGHT) * std::min(dx, dy);
default:
return 0;
}
}Octile is 100 times the larger distance, plus 42 times the smaller, since each diagonal step costs 42 more than a straight one. The Euclidean distance is cut to a whole number by the cast, which rounds down, so it stays under the true distance.
That's why the diagonal costs 142, not 141. Diagonal steps along a long diagonal of n cells would cost 141n at 141 each. But the straight-line distance is 141.42n, a little more, so Euclidean would overestimate. Rounding the step's cost up keeps the straight line the cheapest route there is, as it should be.
Which Is Best
Each heuristic is admissible for some moves and not for others. With steps in four directions, all four are admissible. Manhattan is exact on open ground, so it's the closest. With diagonal steps, Manhattan overestimates. One diagonal step costs 142, but it closes two of Manhattan's units, worth 200. Then octile is exact on open ground, and Euclidean and Chebyshev are admissible but lower.
To see what that's worth, the demo's own search ran on 300 random maps, with a quarter of the cells walled and the start and goal far apart. Here's how many cells each heuristic explored, typically, with diagonal steps on:
heuristic cells explored longer paths
none 577 none
Chebyshev 191 none
Euclidean 158 none
octile 119 none
Manhattan 76 127 of 300The closer the admissible heuristic, the less it explores: octile, the right one for these moves, explores a fifth of Dijkstra's cells. Manhattan explores fewer still, but it overestimates, and it pays for it. On 127 of the 300 maps, its path was longer than the best one, by up to 13%. With steps in four directions, Manhattan is exact and admissible, and explores a typical 88 cells. Octile, now merely lower, explores 192.
Ties, Weights and Smoothing
Three refinements shape how A* behaves in a game: what it does with ties, how much speed it trades for path length, and how its paths look.
Ties
Many cells can share the least f. On open ground with an exact heuristic, every cell on any best path has the same f, the path's cost. Which one comes out first is up to the queue. Breaking ties toward the cell with the larger g, which is further along its route, makes the search finish the route it's on, rather than widen the front of equal-f cells.
A-Star Explorer does that with the tuple's second number, which is −g when T has tie-breaking on. Among entries with equal f, the larger g has the smaller −g, so it comes out first. With tie-breaking off, the second number is 0, and ties go to the lower cell number. Over the 300 maps, with steps in four directions and Manhattan, tie-breaking cut a typical search from 122 cells to 88. With diagonal steps and octile, f ties less often, since the costs are less alike, and it cut 126 to 119.
Weighted A*
Multiplying h by a weight above 1 makes A* greedier. The estimate counts for more than the cost so far, so the search pushes harder toward the goal, and explores less. The price is the path: it can be longer than the best, though never by more than the weight. A weight of 1.8 can make a path at most 1.8 times the best path's cost.
In practice, the paths are far better than that bound. Over the 300 maps, with diagonal steps and octile, a weight of 1.8 cut a typical search from 119 cells to 41. The paths were 4.1% longer on average, 21.8% at worst, and the same as the best on about a third of the maps. Games use weights when a search must be cheap, and a slightly long path is fine, as it usually is for a crowd of background characters.
Smoothing
A path on a grid can only turn at cell centers, by 45 or 90 degrees, so even the best path looks mechanical. Smoothing straightens it afterward. Starting at the first cell, find the furthest cell of the path that's in sight, which means that the straight line to it crosses no wall, and go straight there. Then do the same from that cell, until the goal. The next image shows a path before and after.
The smoothed path is never longer than the grid's path, and usually shorter, since it isn't bound to the grid's directions. Testing the line of sight means checking the cells that the straight line passes through, for walls. It's done once, after the search, so it costs little.
Beyond the Grid
A* doesn't need a grid. It needs a graph, a heuristic, and costs for the edges. A large world might be a graph of rooms joined by doors, or of waypoints joined where one is in sight of the next. Many 3D games use a navigation mesh: the floor, cut into convex polygons, with an edge wherever two polygons share a side. Searching a few hundred polygons is far cheaper than searching the millions of cells that would cover the same floor, and the straight-line distance is still a good heuristic.
Building A-Star Explorer
A-Star Explorer runs A* across a grid with a cup of walls in the middle. The cells A* explored are blue, the cells still waiting in its queue are teal, and the path is amber. H steps through five heuristics, from none, which makes the search Dijkstra's, to octile. D turns diagonal steps on and off, W weights the heuristic by 1.8, and T turns the tie-breaking on and off. Drag to paint walls, right-drag to erase, and drag the green and red cells to move them. C clears the grid, and R brings back the starting map.
Get the code. The complete project is in the
A-Star Explorerfolder of the book's repository.
A-Star Explorer starts from the skeleton, with its mouse, but without the timing, since nothing moves by itself. It reuses fmt2 and setColor, and three functions from Flood, unchanged: fillCell, cellAt and pathTo. Its Vec2.h is Flood's, since this chapter adds nothing to it. Here are its includes and its colors:
#include <algorithm>
#include <climits>
#include <cmath>
#include <functional>
#include <queue>
#include <string>
#include <tuple>
#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 EXPLORED = { 40, 70, 120, 255 };
constexpr SDL_Color WAITING = { 40, 110, 110, 255 };The <climits> header gives INT_MAX, and <tuple> gives std::tuple. Explored cells are dark blue, and waiting cells teal. Then come the constants, the enums, and the names of the heuristics for the readout:
// The grid, as in Flood: 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 costs: 100 straight, and 142 diagonally, which is 100 times
// the square root of 2, 141.4, rounded up. Whole numbers make equal costs
// exactly equal.
constexpr int STRAIGHT = 100;
constexpr int DIAGONAL = 142;
// The weight on the heuristic when W is on, in tenths: 1.8.
constexpr int HEAVY = 18;
// What a cell holds, what a drag with the mouse is doing, and the
// heuristics, with their names.
enum Tile { GROUND, WALL };
enum Drag { NONE, PAINT, ERASE, MOVE_START, MOVE_GOAL };
enum Heuristic { NO_HEURISTIC, MANHATTAN, EUCLIDEAN, CHEBYSHEV, OCTILE };
const char* const HEURISTIC_NAMES[] = { "none, so Dijkstra's", "Manhattan",
"Euclidean", "Chebyshev", "octile" };The grid is Flood's. A weight of HEAVY, 18 tenths, is 1.8. The heuristics are numbered from 0 to 4 in the enum, so that H can step through them, and HEURISTIC_NAMES gives each a name. The Search struct comes next in the file, as The Code showed it. After the helpers comes the starting map:
// The starting map: a cup of walls, open toward the start, between the
// start and the goal.
std::vector<Tile> startingMap()
{
std::vector<Tile> tiles(COLS * ROWS, GROUND);
for (int row = 5; row <= 18; ++row) tiles[row * COLS + 23] = WALL;
for (int col = 15; col <= 23; ++col)
{
tiles[5 * COLS + col] = WALL;
tiles[18 * COLS + col] = WALL;
}
return tiles;
}The cup's back is column 23, from row 5 to row 18, and its two sides run along rows 5 and 18, from column 15. It opens to the left, toward the start, so a search that heads straight for the goal runs into it. Then come estimate, stepFrom and aStar, and Flood's pathTo.
The State
The state goes after the font is loaded:
// The map, and the start and the goal. Then the settings: the
// heuristic, diagonal steps, the weight and the tie-breaking. Then the
// drag in progress.
std::vector<Tile> tiles = startingMap();
int start = 15 * COLS + 6;
int goal = 9 * COLS + 34;
Heuristic kind = OCTILE;
bool diagonals = true;
bool heavy = false;
bool tieBreak = true;
Drag drag = NONE;The start is at column 6, row 15, low and to the left of the cup. The goal is at column 34, row 9, to its right and a little higher. The demo starts with octile, diagonal steps, no weight, and tie-breaking on.
The Events
The keys change the settings or the map, and a mouse button starts a drag, as in Flood:
// 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_H)
kind = (Heuristic)((kind + 1) % 5);
else if (event.key.key == SDLK_D) diagonals = !diagonals;
else if (event.key.key == SDLK_W) heavy = !heavy;
else if (event.key.key == SDLK_T) tieBreak = !tieBreak;
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 walls. 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, H steps the heuristic on by one, and % 5 wraps it from octile back to none. The cast turns the int back into a Heuristic, since adding to an enum gives an int. The mouse works as in Flood, but the left button always paints walls, since there's no swamp.
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, as in Flood.
int hover = cellAt(mx, my);
if (hover >= 0)
{
bool free = hover != start && hover != goal;
if (drag == PAINT && free) tiles[hover] = WALL;
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, afresh every frame.
Search s = aStar(tiles, start, goal, kind, diagonals,
heavy ? HEAVY : 10, tieBreak);
std::vector<int> path;
if (s.found) path = pathTo(s.came, start, goal);The search runs every frame, with the weight in tenths: 18 with W on, and 10 without. If it found the goal, Flood's pathTo follows the came links back from it.
Drawing
After the skeleton clears the screen, every cell is drawn:
// Each cell: walls in stone, explored cells blue, and cells still
// waiting, reached but not explored, teal.
for (int cell = 0; cell < COLS * ROWS; ++cell)
{
if (tiles[cell] == WALL) fillCell(renderer, cell, STONE);
else if (s.closed[cell]) fillCell(renderer, cell, EXPLORED);
else if (s.g[cell] != INT_MAX) fillCell(renderer, cell, WAITING);
}A cell that's closed was explored. A cell that isn't closed, but has a g, was reached and is still waiting in the queue: the search's frontier when it stopped. Then come the path and the two ends:
// The path, then the start and the goal on top.
for (int cell : path) fillCell(renderer, cell, AMBER);
fillCell(renderer, start, GREEN);
fillCell(renderer, goal, RED);Last come the readout and the controls:
// The readout: the search and its path, then the settings.
std::string result = "no path";
if (s.found)
result = "a path of " + std::to_string(path.size() - 1) +
" steps, costing " + fmt2(s.g[goal] / 100.0f);
drawText(renderer, font,
"A*, heuristic " + std::string(HEURISTIC_NAMES[kind]) + ": " +
std::to_string(s.explored) + " cells explored, " + result,
12, 8, TEXT);
drawText(renderer, font,
std::string("diagonals ") + (diagonals ? "on" : "off") +
" weight " + (heavy ? "1.8" : "1") + " ties " +
(tieBreak ? "to the one further along" : "by cell number"),
12, 26, GREY);
drawText(renderer, font,
"[H] heuristic [D] diagonals [W] weight [T] ties "
"[C] clear [R] reset", 12, WINDOW_HEIGHT - 46, GREY);
drawText(renderer, font,
"[Drag] walls [Right-drag] erase drag the green or red "
"cell [Esc] quit", 12, WINDOW_HEIGHT - 26, GREY);In the preceding code, the path's cost is the goal's g, divided by 100 for the readout. So 3,388 shows as 33.88. The first line gives the heuristic, the cells explored and the path, and the second gives the settings.
Trying It Out
Run the demo. It starts with octile and diagonal steps. The next image shows it.
A* explored 219 cells, and found the best path, 28 steps costing 33.88. Heading straight for the goal, it ran into the cup, and filled it before the cells around the outside looked cheap enough. The teal ring is what was still waiting when the goal came out. Then try it, step by step:
- Take the heuristic away. Press H, which wraps round from octile to none. The search is now Dijkstra's, and explores 821 cells, nearly all of the map, for the same path.
- Use Manhattan with diagonals. Press H once more. Manhattan overestimates diagonal steps, and the search goes over the top of the cup: 31 steps, costing 36.46, where the best is 33.88.
- Try Euclidean and Chebyshev. Press H twice. Both find the best path, exploring 256 and 351 cells. Press H again for octile.
- Weight it. Press W. A* explores 193 cells, and the path costs 34.72, 2.5% more than the best. Press W again.
- Turn diagonals off. Press D. Every path now steps straight, and the best costs 42.00. Press H twice, for Manhattan, now the right heuristic: 278 cells explored. Press T to turn tie-breaking off, and it explores 301.
- Close the cup. Paint a wall across the cup's mouth, down the column where its two sides end. The search can no longer wander into the cup. With the settings from step 5, it explores 205 cells instead of 301, for the same path.
The next image shows step 1.
The explored cells fill nearly the whole map, in every direction alike, and the path is the same as A*'s. The next image shows step 2.
The Manhattan estimate counts each diagonal step as 200, where it costs 142. So routes that need many diagonal steps look dearer than they are, and the search settles for the route over the top, which looked cheaper. It's 2.58 dearer than the best, and nothing on the screen says so, except the readout's cost.
FAQ
Q) Should costs be whole numbers or floats?
A) Either works, but whole numbers are simpler to trust. Equal costs are exactly equal, so ties are real ties, and tie-breaking works as intended. With floats, two routes of the same cost, added up in different orders, can differ in their last bit. If you use whole numbers for diagonals, round the diagonal's cost up, as 142 is, so that the straight-line distance never claims more than the moves could manage.
Q) What if there's no path?
A) Then A* explores every cell it can reach before its queue runs dry, which costs as much as Dijkstra's search. If unreachable goals are common, such as clicks on an island, flood the map once into regions, and give each cell its region's number. Two cells in different regions have no path, which a single comparison shows, before any search.
Q) Is A* always better than Dijkstra's search?
A) For one path from one place to one goal, yes. But Dijkstra's search finds the cost from the start to every cell, and A* only to the goal. When many things need paths to the same place, such as monsters chasing the player, one search from the place serves them all, as Chapter 22's FAQ explained.
Exercises
The first three exercises need only a pencil. The others change A-Star Explorer.
- f by hand (paper). On Figure 23.1's grid, what's the f of the cell just below the goal, with the Manhattan heuristic, if it's reached around the bottom of the wall? Why is it never explored?
- Consistent (paper). A straight step costs 100 and a diagonal one 142. Check that octile is consistent for a diagonal step from a cell (3, 2) away from the goal to one (2, 1) away. Then show that Manhattan isn't, for the same step.
- The bound (paper). With a weight of 1.5, what's the dearest path that weighted A* could return, when the best costs 40? Why can't a weighted search promise the best path?
- Smoothing (code). After
pathTo, smooth the path as Smoothing describes, testing the line of sight by sampling the line between two cells' centers every quarter of a cell. Draw the smoothed path as lines over the amber cells, and add its length to the readout. - Swamp (code). Bring back Flood's swamp, costing 500 to step into. Which heuristics are still admissible, and why does the octile estimate stay right, as long as it counts every cell as ground?
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)
A* is how game characters get around, and watching one walk its path makes the search come alive. With an AI's help, you can turn A-Star Explorer into a small scene, with a character that walks wherever you click. 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 or WALL), stored row by row in a std::vector, and these functions: aStar(tiles, start, goal, kind, diagonals, weight, tieBreak), which returns a Search with g, came and closed vectors and a found flag, and pathTo(came, start, goal), which returns the path as a std::vector of cell numbers from start to goal. Please add a character, a circle, that stands on a cell. When I click a cell, run aStar from the character's cell to it, with the octile heuristic and diagonal steps, and make the character walk the path at 4 cells a second, moving smoothly between cell centers with lerp. If I paint a wall onto its path while it walks, search again from the cell it's walking toward. Explain why the search starts from that cell, rather than from where the character is."
That prompt describes your functions, so the AI builds on them, rather than writing a search of its own. It asks for movement between cell centers, with Chapter 8's lerp, which is how most games walk a grid path. And it asks for a new search when the map changes, which is a real game's problem, with the reason checked against the chapter.
Then smooth the path before the character walks it, and watch it cut across open ground. Then add a second character, and decide what should happen when their paths cross.
Summary
Dijkstra's search spreads evenly, so it explores as far from the goal as toward it. A* adds a heuristic h, an estimate of the cost to the goal, and takes the waiting cell with the least f = g + h, the estimated cost of the whole route. It tests for the goal when the goal comes out of the queue, so that nothing waiting can beat it. When h is admissible, never overestimating, A* finds the best path, since some cell on the best path always comes out before a worse route to the goal. When h is also consistent, never dropping by more than a step costs, a cell's g is final when it's closed, so A* never has to look at it again. The heuristic should match the moves: Manhattan for steps in four directions, octile for eight with diagonals costing the square root of 2, Chebyshev for eight that cost the same. Euclidean is admissible for any of them, but lower. Over 300 random maps with diagonal steps, octile explored a fifth of Dijkstra's cells. Manhattan, which overestimates there, returned longer paths on 127 of them. Breaking ties toward the larger g shortens the search, and weighting h trades a longer path, at most the weight times the best, for a much smaller search. Smoothing straightens a grid path by skipping to the furthest cell in sight, and A* works on any graph, such as a navigation mesh. Part 6 turns from moving through a world to drawing one, starting with textures in Chapter 24.