Every turn so far has been a key. That's right in a fight, where each step matters, but much of a run isn't a fight. Crossing a floor you've already seen takes dozens of key presses, and healing after a fight takes a hundred presses of the period, or more. This chapter gives the player commands that take many turns: rest until healed, travel to any cell they've seen by the shortest way, and explore a floor with a single key.
Each command plays out a step at a time, where the player can see it. It stops the moment anything new happens: a monster comes into view, the player is hurt, or something is found. The next image shows exploring, stopped by a giant white rat in the room below the first.
Two ways of finding a way meet in this chapter. Travel wants the shortest way to one cell, and finds it with A*, the best-known search in games. A* is Chapter 10's Dijkstra's algorithm with a sense of direction. Exploring wants the way to the nearest cell it hasn't seen, wherever that is, and finds it with a Dijkstra map with many goals.
Chapter 23 in the book's repository holds this chapter's finished project. The chapter carries on in your own project from Chapter 22, or from the book's Chapter 22 folder.In this chapter, we will:
- Rest with R, a turn at a time, until healed, with each turn shown as it's played
- Stop a command for anything new, and refuse to start one with a monster in view
- Find the shortest way to a cell with A*, over the floor as the player knows it, and travel there with a click
- Explore with o, walking downhill on a Dijkstra map whose goals are the edge of what the player has seen
- Travel to the stairs with >, once the player has seen them
There are five checkpoints along the way. Let's start with the plan.
Planning the Chapter
This chapter adds three files, and changes two:
| File | Status | What it's for |
|---|---|---|
src/Command.h |
New | A command that takes many turns: what it's doing, where it's going, and the turns it's taken |
src/AStar.h, src/AStar.cpp |
New | A*: the shortest way from one cell to another |
src/Game.h, src/Game.cpp |
Changed | The commands and their keys, the loop that plays them, what stops them, and the floor as the player knows it |
| The other files | Unchanged |
The next image shows how the files fit together at the end of the chapter. The command is a small struct that Game holds, and AStar stands on its own. It needs only the map, and the cost of a door from the Dijkstra map.
Most of the work is in Game.cpp, which grows by about 410 lines. Then comes AStar.cpp, with about 135. The two new headers are about 20 lines each, and Game.h gains about 35.
How a Command Runs
A command is something the game does for the player over many turns, until it's done, or something stops it. Resting is the simplest: each step is a turn of waiting, as the period is. Traveling and exploring take steps that move the player, as an arrow key does. Each step is an ordinary turn, played by the code a key would run. So the monsters move, statuses tick, and the player heals, exactly as if the keys had been pressed one at a time.
What's new is the loop. Until now, it slept until something happened, such as a key press. While a command runs, it can't, since the command's next step is due in a moment, key or no key. So the loop wakes when a step is due, takes it, and draws the screen, and the player sees each step. The next image shows the loop's three ways around.
A command stops when it's done, but also for anything the player would want to see to. Before each step, the game notes what the player knows: their health, the traps they know of, the items they've seen, and so on. After the step, it looks again. If a monster has come into view, or anything else is new, the command stops, and the log says why. A key stops it too, so the player is always the one in charge.
Resting
This part builds the machinery, with the simplest command there is. For now, a rest stops only when it's done, or for a key. The next part makes it stop for anything new.
A Command
In Solution Explorer, right-click src, choose Add > New Item, and add a Header File (.h) called Command.h. Type the whole file:
#pragma once
#include "Common.h"
// What a command that takes many turns is doing. Resting is the first
enum class CommandKind
{
Rest, // waiting until the player is healed
};
// A command that takes many turns, a step at a time, and stops for
// anything the player should see to: what it's doing, where it's going,
// if anywhere, and the turns it's taken so far
struct Command
{
CommandKind kind = CommandKind::Rest;
Point goal;
int turns = 0;
};The enum CommandKind names what a command does. Resting is the only kind for now, and traveling and exploring join it later in this chapter. A Command holds its kind, a goal, and the turns it's taken. Only traveling will use the goal, and the turns tell a rest when to give up. The goal is a Point, from Common.h, so that's the header it includes.
The Command That's Running
The game holds the command that's running, if there is one. That's a job for std::optional, as the mouse's place is: empty when no command runs. Open Game.h, and add the new header above #include "Common.h":
#include "Command.h"Add the command itself below inventoryAction_, with a blank line above it:
// The command that's running, a step at a time, if one is
std::optional<Command> command_;Resting needs a function to start it, and two to play it, a step at a time. Add rest below search's declaration:
void rest();Add the other two below setSaveAside's declaration, with a blank line above them:
// Commands that take many turns
void stepCommand();
bool restStep();The function stepCommand takes one step of whatever command is running, and restStep is that step for a rest. Traveling and exploring, later in this chapter, each get a step function of their own.
Two Numbers
A command takes a step every 30 milliseconds: quick enough that a walk across a floor takes a second or two, and slow enough to watch. Resting gives up after 300 turns, healed or not, so it never runs away with the turns. Open Game.cpp, and add both numbers below REGENERATION, with a blank line above them:
// A command that takes many turns takes a step every COMMAND_STEP_MS
// milliseconds, so the player sees it happen. Resting stops after
// REST_TURNS turns, healed or not
constexpr Uint32 COMMAND_STEP_MS = 30;
constexpr int REST_TURNS = 300;The type Uint32 is SDL's own, for a whole number that's never negative, as a wait in milliseconds never is. The help screen gets a line for the new key. In KEY_HELP, add this line below the one for . or numpad 5:
{ "R", "rest until healed, or until something happens" },The help lists the keys that pass turns first, so resting sits beside waiting, its one-turn cousin.
The Loop
The loop has slept in SDL_WaitEvent since Chapter 1. While a command runs, it has to wake up for the command's next step, every 30 milliseconds, whether anything happens or not. In run, add the time the next step is due directly above while (running_):
// When a command's next step is due, in milliseconds since SDL started
Uint64 stepDue = 0;The time is a Uint64, a whole number that's never negative, with 64 bits of room, which is what SDL's clock counts in. It starts at 0, long past, so a command's first step is due as soon as it starts. Replace the comment above SDL_Event event; with this:
// Sleep until something happens. A turn-based game has nothing to
// do while the player is thinking. But while a command runs, the
// sleep lasts only until its next step is due, so the player sees
// it happen, a step at a time. A step is due COMMAND_STEP_MS after
// the one before, however many events come in between, so moving
// the mouse doesn't hold a command upThen find these lines, below it:
if (!SDL_WaitEvent(&event))
{
SDL_Log("SDL_WaitEvent failed: %s", SDL_GetError());
break;
}
handleEvent(event);Change them to these:
Uint64 now = SDL_GetTicks();
if (command_ && now >= stepDue)
{
stepCommand();
stepDue = now + COMMAND_STEP_MS;
}
else if (command_)
{
Sint32 wait = static_cast<Sint32>(stepDue - now);
if (SDL_WaitEventTimeout(&event, wait))
{
handleEvent(event);
}
}
else if (SDL_WaitEvent(&event))
{
handleEvent(event);
}
else
{
SDL_Log("SDL_WaitEvent failed: %s", SDL_GetError());
break;
}In the preceding code, SDL_GetTicks gives the milliseconds since SDL started. With no command running, the loop sleeps in SDL_WaitEvent, as before. When one is running and its step is due, the loop takes the step and makes the next one due COMMAND_STEP_MS later. Otherwise, it waits for an event with SDL_WaitEventTimeout, which gives up when the time it's given runs out and returns false. That time is what's left until the step is due, so the loop comes around again just as the step is due, and takes it.
Taking one Uint64 from another gives a Uint64, but SDL wants the wait as a Sint32, a whole number that can be negative. The static_cast says the change is meant, and it's safe, since the step is never more than 30 milliseconds away.
Notice that an event doesn't put the step off. The mouse moving over the window sends dozens of events a second. If each one began the 30 milliseconds again, a command would stand still while the mouse moved.
A Key Stops It
A command runs until it's done, unless the player stops it, and any key will do. The key does nothing else, so a key pressed to stop a walk doesn't also take a step somewhere. In handleEvent, find these lines:
else if (event.type == SDL_EVENT_KEY_DOWN)
{
handleKey(event.key);
}Change them to these:
else if (event.type == SDL_EVENT_KEY_DOWN)
{
// A key pressed while a command runs stops it, and does nothing
// else. A key held down repeats, and its repeats are ignored
if (!command_)
{
handleKey(event.key);
}
else if (!event.key.repeat)
{
command_.reset();
redraw_ = true;
}
}A key held down sends its key-down event again and again, each a repeat, with repeat set. The repeats are ignored, so the R that starts a rest can't stop it, if it's held a moment too long. Stopping a command is reset, which empties the optional, and the screen is drawn again.
R
R rests. It's the r key, so a lowercase r rests too. In handlePlayingKey, add its check below the one for SDLK_S:
if (key.key == SDLK_R)
{
rest();
redraw_ = true;
return;
}The new key needs naming too. Replace the comment above handlePlayingKey, which names every key, with this:
// Esc opens the menu, ? shows the keys, > goes down the stairs, g picks
// up, i shows the inventory, d drops, x starts looking around, c closes a
// door, s searches, R rests, f fires the bow, t throws, z casts lightning
// by heart, and the moving keys move the playerAdd rest itself below search:
// R rests: the player waits, a turn at a time, until they're healed, or
// REST_TURNS turns have passed, or something happens. r works too
void Game::rest()
{
log_.markRead();
if (player_.hp == player_.maxHp)
{
log_.add("You're already at full health.");
return;
}
command_ = Command{ CommandKind::Rest };
}A rest at full health would end before it began. So it doesn't start, and the log says so. Otherwise command_ is given a Command, which starts it. The braces make a Command with its first member, the kind, set. Everything else is left as its default: no goal, and no turns yet.
A Step of Rest
The rest is played by stepCommand, which the loop calls whenever a step is due. Add it below springTrap:
// One step of the command that's running, which takes a turn. The command
// stops when it's done. A step can end the run, or ask the player a
// question, and that stops it too
void Game::stepCommand()
{
bool done = false;
switch (command_->kind)
{
case CommandKind::Rest:
done = restStep();
break;
}
if (state_ != GameState::Playing || done)
{
command_.reset();
}
redraw_ = true;
}The switch sends the step to the function for the command's kind, which says whether the command is done. Resting is the only kind yet, but the switch has room for the two to come. The arrow, as in command_->kind, reaches the command inside the optional, as mouse_->x reaches the mouse's place. The command stops when it's done, and also if the step has left the game in any state but Playing. Perhaps the player has died, or a step has asked a question, such as whether to step onto a trap, which is for the player to answer.
The step of rest is a turn of waiting, as the period plays it. Add restStep below stepCommand:
// A turn of rest. Returns true when the rest is over: the player is
// healed, or has rested for REST_TURNS turns
bool Game::restStep()
{
finishTurn();
++command_->turns;
if (player_.hp == player_.maxHp)
{
log_.add("You feel rested.");
return true;
}
if (command_->turns == REST_TURNS)
{
log_.add("You stop resting.");
return true;
}
return false;
}The function finishTurn plays the rest of the turn, as it does for every other key. The monsters act, statuses tick, and every tenth turn, a hurt player heals 1. Then the rest counts the turn, and stops when the player is healed or has rested for REST_TURNS turns, with a message for each. At a point every ten turns, 300 turns heal 30. So a rest nearly always ends with the player healed: only a Fighter resting from 1 health, of its 32, needs a second.
Checkpoint: To try a rest without a fight first, start the run hurt. In startAs, add player_.hp = 10; below player_.updateDefense(); for now. Press F5, with seed 42 in Command Arguments, press N for a new run, choose the Fighter with a, and press R. The turn counter in the side panel climbs, a turn every 30 milliseconds, and your health climbs a point every ten turns. Press any key while you rest: the rest stops at once. Then press R again to rest on. On turn 220, your health is full, and the log says "You feel rested."; press R once more, and it says "You're already at full health." Take the line out of startAs when you're done.
Stopping for Anything New
A rest that goes on while a monster bites the player is worse than no rest at all. This part teaches commands some caution: not to start at a bad moment, and to stop the moment anything new happens.
Not Now
Some moments are wrong for a command. With a monster in view, a rest would be over before it began, since a monster in view is just what stops a command. And a poisoned player loses health every turn, which stops one too. So a command won't start at such a moment, and the log says why. Open Game.h, and add the check directly below // Commands that take many turns:
bool canStartCommand();Whether a monster is in view is a question each step will ask as well, so it gets a function of its own. Add its declaration below restStep's:
const Monster* firstMonsterInView() const;In Game.cpp, add canStartCommand below springTrap:
// True if a command can start: there's no monster in view, and the player
// isn't poisoned, which would hurt them every turn. If not, the log says
// why
bool Game::canStartCommand()
{
const Monster* monster = firstMonsterInView();
if (monster != nullptr)
{
log_.add("Not with " + withArticle(monster->def->name) +
" in view.");
return false;
}
if (player_.poisoned > 0)
{
log_.add("Not while you're poisoned.");
return false;
}
return true;
}The monster in view is named, so the player knows what's wrong, as in "Not with a jackal in view." The article comes from Chapter 6's withArticle. The player's poisoned is the turns of poison they have left, from Chapter 14, so anything above 0 means they're poisoned.
Add firstMonsterInView below restStep:
// The first monster the player can see, if they can see one
const Monster* Game::firstMonsterInView() const
{
for (const Monster& monster : level_.monsters)
{
if (level_.map.isVisible(monster.pos.x, monster.pos.y))
{
return &monster;
}
}
return nullptr;
}A monster is in view if the player can see the cell it's on, which the map has known since Chapter 4's field of view. The function returns a pointer, which can point at nothing, nullptr, when there's no monster in view. It's a pointer to a const monster, since looking at a monster doesn't change it, and the function is const too.
Now rest asks before it starts. In rest, find this line:
command_ = Command{ CommandKind::Rest };Change it to these:
if (canStartCommand())
{
command_ = Command{ CommandKind::Rest };
}A rest that can't start leaves the log saying why, and takes no turn.
What the Player Knows
A command stops for anything new, so a step needs to know what was there before it. Before each step, the game notes what the player knows in a Watch, a struct of its own. After the step, it compares. In Game.h, add the struct directly below // Commands that take many turns:
//
// What the player knows, as a step of a command begins, so the step
// can tell what's new: the floor they're on, their health, the traps
// they know of, the secret doors still hidden, and which of the items
// they've seen
struct Watch
{
int depth = 0;
int hp = 0;
int trapsKnown = 0;
int secretDoors = 0;
std::vector<bool> itemsSeen;
};The comment line with nothing on it, //, joins the heading to the struct's own comment, so they read as one. The struct is declared inside Game, as Game::Watch, since nothing else needs it. Each number is something the player should know about if it changes: the floor's depth, their health, the traps they know of, and the secret doors still hidden. The vector holds a bool for each item on the floor, which is true if the player has seen it.
The functions that note and compare go between restStep's declaration and firstMonsterInView's:
Watch watch() const;
bool somethingNew(const Watch& before);The noting is counting. In Game.cpp, add the first part of watch below restStep:
// What the player knows of, before a step of a command
Game::Watch Game::watch() const
{
Watch now;
now.depth = level_.depth;
now.hp = player_.hp;
for (const Trap& trap : level_.traps)
{
if (trap.known)
{
++now.trapsKnown;
}
}The return type is written Game::Watch, since outside the class, C++ doesn't yet know whose Watch it is. The name is looked up in Game only from the function's own name on. Add the rest of the function below it:
for (int y = 0; y < MAP_H; ++y)
{
for (int x = 0; x < MAP_W; ++x)
{
if (level_.map.at(x, y) == Terrain::SecretDoor)
{
++now.secretDoors;
}
}
}
for (const FloorItem& floorItem : level_.items)
{
now.itemsSeen.push_back(floorItem.seen);
}
return now;
}The secret doors are counted on the map. A secret door is a cell of its own kind there, Terrain::SecretDoor, until it's found. Each item's seen is the one Chapter 12 set, the first time the item came into view.
What's New
The comparing is somethingNew. Add its first part below watch:
// True if a step of a command brought anything the player should see to:
// a monster in view, which is named, health lost, a new floor, a trap
// sprung or found, a secret door found, or an item come into view, which
// is named too. A floor's items stay in the same order while the player
// is on it, so they can be compared one by one
bool Game::somethingNew(const Watch& before)
{
const Monster* monster = firstMonsterInView();
if (monster != nullptr)
{
log_.add("You see " + withArticle(monster->def->name) + ".");
return true;
}A monster in view comes first, since it matters most. The log names it: "You see a jackal." Add the rest of the function below it:
Watch now = watch();
bool changed = now.depth != before.depth || now.hp < before.hp ||
now.trapsKnown > before.trapsKnown ||
now.secretDoors < before.secretDoors;
if (changed)
{
return true;
}
for (size_t i = 0; i < now.itemsSeen.size(); ++i)
{
if (now.itemsSeen[i] && !before.itemsSeen[i])
{
log_.add("You see " + itemName(level_.items[i].item) + ".");
return true;
}
}
return false;
}Each of these stops the command: a new floor, health lost, a trap known that wasn't, or a secret door fewer. None of them is named, since the log has told of each already, as in "A needle pricks you." Health gained doesn't count, which is just as well, since that's what a rest is for.
Then come the items. A floor keeps its items in the same order while the player is on it. Only the player adds or takes them away, by picking up, dropping, throwing and firing. Those are all keys, and a key stops a command first. So the items can be compared one by one: an item that's seen now and wasn't before is new, and it's named.
The new floor is checked first for a reason. On a new floor, the items are different ones, perhaps more of them. Comparing them with the last floor's would make no sense, or run off the end of before.itemsSeen.
The Step Watches
All that's left is for each step to use them. Replace the comment above stepCommand with this:
// One step of the command that's running, which takes a turn. The command
// stops when it's done, and as soon as anything happens that the player
// should see to. A step can end the run, or ask the player a question,
// and that stops it tooIn stepCommand, add this line directly above bool done = false;:
Watch before = watch();In stepCommand, change if (state_ != GameState::Playing || done) to if (state_ != GameState::Playing || somethingNew(before) || done).
Now a rest stops for anything new. The next image shows one stopped by a fruit bat, as at the checkpoint below.
The fruit bat came into view through the door the player had opened, and that was enough: the rest stopped before the bat could bite.
Checkpoint: Put player_.hp = 10; back in startAs for now. Press F5, with seed 42 as before, and start a new run as the Fighter. Now press j three times, to walk down to the door below you, and once more, to open it. Then rest with R. This time the rest stops before you're healed: after 66 turns, a fruit bat comes into view through the open door, and the log says "You see a fruit bat." Press R again, and the log says "Not with a fruit bat in view." The bat is coming, so fight it, then take the line out of startAs.
Travel, by A*
Travel takes the player to any cell they've seen, a step at a time, by the shortest way they know. A click on the map is all it takes. Finding that way is the job of A*, the search most games use for paths. A path is the usual name for a way from one cell to another, so the code calls its search findPath. This part builds it, in a namespace of its own, then uses it to travel.
Dijkstra's Algorithm, with a Sense of Direction
Chapter 10's Dijkstra's algorithm spreads out from its goals in every direction, a ring at a time, until every cell has its distance. That's right for a map that every monster walks down, wherever it is. For one way, from one cell to one other, much of the spreading is wasted. It's spent on cells behind the start, and on rooms the way never enters.
A* changes one thing: the order in which the queue hands cells back. Dijkstra's algorithm hands back the cell with the least cost so far. A* hands back the cell whose cost so far, plus a guess at the cost still to come, is least. Most writing on A* calls the cost so far g, the guess h, and their sum f, so A* hands back the cell with the least f = g + h.
Cells toward the goal come out sooner than cells away from it, and the search stops as soon as the goal itself comes out. The next image shows both, finding the same way on a small map.
Both find a way of seventeen steps, but A* hands back 39 cells to find it. Dijkstra's algorithm, stopping at the goal, hands back 133. On seed 42's first floor, with the whole floor known, the way from the start to the stairs takes A* 312 cells, and Dijkstra's algorithm 538, of the floor's 645. So on a real floor, A* saves less than half the work.
On floors this size, that's a saving no one would notice. Either search takes a fraction of a millisecond, so either would do for travel. A* is here because it's the standard way to find a path from one cell to another, and the search you'll meet in other games. Its saving matters on bigger maps, and where many searches run, each to a goal of its own.
A Guess That's Never Too Much
The guess has one rule: it must never be more than the cost still to come. In the usual words, the guess is the heuristic, and one that's never too much is admissible. A guess that's too little only makes A* look at more cells than it needs to. One that's too much could make it pass over a cell that the shortest way runs through, since the cell would look worse than it is. Dijkstra's algorithm is A* with a guess of 0, which is never too much, but never any help either.
Design note: A robot's way across a room. A* was made for a robot. From the mid-1960s, a team at the Stanford Research Institute built Shakey, a robot on wheels that planned its own moves. A* was how it planned its way around the things in its rooms. Peter Hart, Nils Nilsson and Bertram Raphael published it in 1968, with the proof this section leans on: a guess that's never too much always finds the shortest way. The same search now finds the ways of drivers following directions, and of characters in games.
The best guess is the cost with nothing in the way. Walking in eight directions, a diagonal step covers one cell across and one down at once. So the fewest steps from one cell to another is the longer of the two distances, across and down. Walls and doors can only make the way longer, so the guess is never too much.
Straight Where It Can
There's more than one shortest way, as a rule, often a great many. A diagonal step takes a turn, as a straight one does, so a way that zigzags is just as short as a straight one. Left alone, A* can pick a way that wanders off toward the goal's side of a room, then back to the door. That's no longer, but it looks drunk.
So a diagonal step costs a hundredth of a step more than a straight one. Of the ways with the fewest steps, the one with the fewest diagonal steps now costs least, and A* finds it. So the player walks straight where they can. It would take a hundred diagonal steps to add up to a single step, so in practice the hundredth only ever chooses between ways of the same length. The next image shows the same small map, with and without it.
Even then, there are ties, between cells that look just as good. A* tries the one nearer the goal as the crow flies first, so the way it finds makes for the goal, rather than wandering. That saves work too: on the small map, A* looks at 39 cells with the tie-break, and 50 without.
A Namespace for A*
A* needs no data of its own between searches, only the map it's given. So it's a function in a namespace, as Chapter 4's field of view is. In Solution Explorer, right-click src, choose Add > New Item, and add a Header File (.h) called AStar.h. Type the whole file:
#pragma once
#include <vector> // std::vector, for the way's cells
#include "Common.h"
#include "Map.h"
// A*: the shortest way from one cell to another, for travel
namespace AStar
{
// The cells of the shortest way from one cell to another, after the
// first and ending with the second, or none if there's no way. Only
// the ground and doors can be stepped on, and a step onto a closed
// door counts as DijkstraMap::DOOR_STEPS steps: one to open it, and
// one to step in. Of the ways with the fewest steps, it's one with the
// fewest diagonal steps, so it walks straight where it can
std::vector<Point> findPath(const Map& map, Point from, Point to);
}The way comes back as a vector of the cells to walk, in order, without the cell it starts from. An empty vector means there's no way at all. The door's cost is the Dijkstra map's, from Chapter 19, so a monster and a traveling player count a door the same way.
Now add a C++ File (.cpp) called AStar.cpp. Type the first part:
#include "AStar.h"
#include <algorithm> // std::reverse, to put the way in order
#include <cstdlib> // std::abs, for distances
#include <functional> // std::greater, to make the queue smallest first
#include <queue> // std::priority_queue, for the cells still to visit
#include <tuple> // std::tuple, for what the queue holds of a cell
#include "DijkstraMap.h"
namespace
{
// A way's cost is counted in hundredths of a step: STEP for a step, and
// DIAGONAL_EXTRA more for a diagonal one. Between ways with as many
// steps as each other, the extra picks the one with fewer diagonal
// steps. A way with a step more would need over a hundred fewer
// diagonal steps to cost less
constexpr int STEP = 100;
constexpr int DIAGONAL_EXTRA = 1;The costs are whole numbers, counted in hundredths of a step. So a step is STEP, 100, and a diagonal one 101. Whole numbers are exact, where a fraction such as 1.01 isn't quite, in a float. The unnamed namespace keeps the helpers to this file, as Data.cpp's are.
The guess comes next. Add it below DIAGONAL_EXTRA, with a blank line in between:
// The least the way from one cell to another could cost, if nothing
// were in the way: a step for each cell of the longer of the distances
// across and down, since a diagonal step covers one of each, and the
// extra for the diagonal steps that takes. A* needs a guess at the
// cost still to come that's never too much, and this is one
int leastCost(Point a, Point b)
{
int across = std::abs(a.x - b.x);
int down = std::abs(a.y - b.y);
return SDL_max(across, down) * STEP +
SDL_min(across, down) * DIAGONAL_EXTRA;
}The guess is in hundredths too: a step for each cell of the longer distance, and a hundredth for each diagonal step that takes. There's one diagonal step for each cell of the shorter distance. With nothing in the way, no way costs less, so the guess is never too much. The functions SDL_max and SDL_min give the larger and the smaller of two numbers.
Add the tie-break, and a helper for a cell's place in a vector, below it:
// How far apart two cells are as the crow flies, squared. Of two cells
// that look just as promising, the one nearer the goal this way is
// tried first, so the way found makes for the goal, rather than
// wandering among the many ways that are just as short
int crowFlies(Point a, Point b)
{
int dx = a.x - b.x;
int dy = a.y - b.y;
return dx * dx + dy * dy;
}
int indexOf(Point cell)
{
return cell.y * MAP_W + cell.x;
}
}The distance as the crow flies is left squared, since only the order matters, and squaring doesn't change which of two distances is smaller. The index of a cell is its place in a vector the size of the map, row by row, as the Dijkstra map numbers its cells.
The Search
The search begins as Dijkstra's algorithm does, with a cost for every cell, all of them out of reach to start. Add the start of findPath below the namespace, with a blank line in between:
// A* is Dijkstra's algorithm with a sense of direction. The queue hands
// back the cell whose way so far, plus the least the rest could cost, is
// the least, so the search heads for the goal, and stops when it gets
// there. Each cell remembers the cell it was reached from, and following
// those back from the goal gives the way
std::vector<Point> AStar::findPath(const Map& map, Point from, Point to)
{
std::vector<Point> path;
if (from == to || !map.isPassable(to.x, to.y))
{
return path;
}
// The cost of the cheapest way found so far to each cell, and the cell
// it came from
std::vector<int> cost(MAP_W * MAP_H, DijkstraMap::UNREACHED);
std::vector<int> cameFrom(MAP_W * MAP_H, -1);A goal the map says no one could stand on, such as a wall, has no way to it. So the search doesn't start. Each cell also remembers the cell it was reached from by its cheapest way so far, in cameFrom, or -1 for none. That's how the way is found again at the end.
The queue is the Dijkstra map's, smallest first, but each entry holds three numbers. Add it below the costs, with a blank line in between:
// Each entry is a cell's guess at the whole way's cost, its distance
// from the goal as the crow flies, and its index. std::greater puts
// the least first, comparing the guesses, and only if they're equal,
// the crow's distances
using Entry = std::tuple<int, int, int>;
std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> open;
cost[indexOf(from)] = 0;
open.push({ leastCost(from, to), crowFlies(from, to), indexOf(from) });A std::tuple holds any number of values, as a std::pair holds two. Tuples compare as pairs do: by their first values, then by their second if those are equal, and so on. So the queue hands back the least guess first, and of equal guesses, the one nearest the goal as the crow flies. The start goes in first, with its cost, 0, and its guess, the whole way's.
The queue holds the cells that have been reached but not yet handed back, known as the open set, so the code names it open. Each entry's guess, at the whole way's cost, is the cell's f: its cost so far, g, plus leastCost's guess at the rest, h.
The loop takes the cells out, one at a time. Add its start below the queue, with a blank line in between:
while (!open.empty())
{
// A structured binding gives the entry's three values names
auto [guess, crow, index] = open.top();
open.pop();
Point cell = { index % MAP_W, index / MAP_W };
if (cell == to)
{
break;
}
// A cell can be in the queue more than once, if a cheaper way to it
// was found after it joined. Only the cheapest counts
if (guess > cost[index] + leastCost(cell, to))
{
continue;
}The declaration auto [guess, crow, index] is a structured binding. It gives a name to each value of the tuple, in order, so the code can say guess, rather than std::get<0>(entry). Structured bindings work on pairs and structs too, and auto lets the compiler work out each name's type, here int for all three.
When the goal comes out of the queue, its cost is the least there is, so the search stops. A cell can come out more than once, if a cheaper way to it was found after it went in. As in Chapter 10, only the cheapest counts.
Each cell handed back offers its neighbors its own cost, plus the cost of a step. Add the step's cost below it, with a blank line in between:
for (Point step : DIRECTIONS)
{
Point next = { cell.x + step.x, cell.y + step.y };
int stepCost = STEP;
if (map.at(next.x, next.y) == Terrain::ClosedDoor)
{
stepCost = DijkstraMap::DOOR_STEPS * STEP;
}
else if (!map.isWalkable(next.x, next.y))
{
continue;
}
if (step.x != 0 && step.y != 0)
{
stepCost += DIAGONAL_EXTRA;
}A step onto the ground costs STEP, and onto a closed door, DOOR_STEPS of them. Nothing else can be stepped on. A diagonal step, with both its parts not 0, costs DIAGONAL_EXTRA more. Add the offer below it:
int nextCost = cost[index] + stepCost;
int nextIndex = indexOf(next);
if (nextCost < cost[nextIndex])
{
cost[nextIndex] = nextCost;
cameFrom[nextIndex] = index;
open.push({ nextCost + leastCost(next, to),
crowFlies(next, to), nextIndex });
}
}
}A neighbor offered a cheaper way than it had takes it, remembers where it came from, and goes into the queue with its guess at the whole way. That's Chapter 10's spread, with a guess added.
The Way Back
When the loop is over, either the goal has a cost, and so a way, or it was never reached. The way is found by following cameFrom back from the goal, which gives the cells from the goal to the start, the wrong way around. Add the end of findPath below the loop, with a blank line in between:
// No way there, or the way, followed back from the goal, then turned
// around
if (cost[indexOf(to)] == DijkstraMap::UNREACHED)
{
return path;
}
for (int index = indexOf(to); index != indexOf(from);
index = cameFrom[index])
{
path.push_back({ index % MAP_W, index / MAP_W });
}
std::reverse(path.begin(), path.end());
return path;
}The loop starts at the goal, and steps from each cell to the one it came from, until it reaches the start. The start isn't part of the way. Then std::reverse turns the vector around, so it runs from the first step to the goal. It takes two iterators, the vector's begin and end, as std::sort does. And it needs <algorithm>, which the file includes.
The Floor as the Player Knows It
A way must use only what the player knows. The floor may hold a shortcut through rooms they haven't explored, but walking it would give the floor away. So the search works on a copy of the map, with everything the player doesn't know, or would rather not walk on, made into wall. Open Game.h, and add its declaration below restStep's:
Map knownMap() const;In Game.cpp, add the start of knownMap below restStep:
// The floor as the player knows it, for finding ways across it: a cell
// they've never seen is solid, as far as they know, and so is a secret
// door, which looks like wall, and a trap they know of, which they'd
// rather go around
Map Game::knownMap() const
{
Map known = level_.map;
for (int y = 0; y < MAP_H; ++y)
{
for (int x = 0; x < MAP_W; ++x)
{
bool unseen = !level_.map.isExplored(x, y);
bool secret = level_.map.at(x, y) == Terrain::SecretDoor;
if (unseen || secret)
{
known.set(x, y, Terrain::Wall);
}
}
}The copy is a whole Map, made by copying level_.map, so set can change its cells without changing the real floor's. A cell the player has never seen is wall, as far as they know, and so is a secret door, which looks like one. Add the rest of the function below it:
for (const Trap& trap : level_.traps)
{
if (trap.known)
{
known.set(trap.pos.x, trap.pos.y, Terrain::Wall);
}
}
return known;
}Traps they know of are made wall too, since walking onto one is what they'd least want a way to do. An unknown trap stays as ground, so a way can still lead them onto one, as walking would. Because a known trap is wall, there are two reasons travel may find no way to a cell: the player knows of none, or every way they know crosses a trap. Either way, travel won't start, and says "You don't know a safe way there." The word "safe" makes that true in both cases.
Traveling
Traveling is the second kind of command. Open Command.h, and find these lines:
// What a command that takes many turns is doing. Resting is the first
enum class CommandKind
{
Rest, // waiting until the player is healed
};Change them to these:
// What a command that takes many turns is doing
enum class CommandKind
{
Rest, // waiting until the player is healed
Travel, // walking to a cell the player chose, by the shortest way
};A command that travels has a goal, the cell it's going to, which is what Command's goal is for. In Game.h, add the function that starts it below rest's declaration:
void travelTo(Point goal);Add its step below restStep's declaration:
bool travelStep();Travel uses A*, so Game.cpp needs its header. Add it above #include "CaveGen.h":
#include "AStar.h"Then add travelTo below rest:
// Starts traveling to a cell the player has seen, by the shortest way they
// know, a step at a time. A click on the map travels
void Game::travelTo(Point goal)
{
log_.markRead();
if (goal == player_.pos || !canStartCommand(CommandKind::Travel))
{
return;
}
if (AStar::findPath(knownMap(), player_.pos, goal).empty())
{
log_.add("You don't know a safe way there.");
return;
}
command_ = Command{ CommandKind::Travel, goal };
}Traveling to where the player already is does nothing. A goal with no way to it, as far as the player knows, is refused, with a message. Otherwise the command starts, made with its kind and its goal, in that order, as Command's members are declared.
The step works the way out again, every step, and takes the first. Add travelStep below restStep:
// A step of travel, along the shortest way the player knows. The way is
// worked out again at every step, since doors open and close. Returns true
// on arrival, or when there's no longer a way
bool Game::travelStep()
{
std::vector<Point> path = AStar::findPath(knownMap(), player_.pos,
command_->goal);
if (path.empty())
{
log_.add("The way there is blocked.");
return true;
}
Point next = path.front();
playerStep({ next.x - player_.pos.x, next.y - player_.pos.y });
return player_.pos == command_->goal;
}The step is the difference between the next cell and the player's, which is what the moving keys give playerStep. So a step of travel is a step as an arrow key takes it. It opens a closed door by bumping it, as Chapter 19 made it, and the next step walks through. The way is worked out again every step, since what the player knows changes as they walk: they see more of the floor, and doors open. Travel is done when the player arrives, or when there's no longer a way they know.
The step joins the switch in stepCommand. Add its case below Rest's:
case CommandKind::Travel:
done = travelStep();
break;A step of travel says when it's done, as a step of rest does, and stepCommand stops the command then.
Not While Confused
A confused player staggers, and half their steps go somewhere else. Resting doesn't care, but a walk would go astray. So a command that walks won't start while the player is confused. The check needs to know what kind of command is starting. In Game.h, change bool canStartCommand(); to bool canStartCommand(CommandKind kind);.
In Game.cpp, find these lines:
// True if a command can start: there's no monster in view, and the player
// isn't poisoned, which would hurt them every turn. If not, the log says
// why
bool Game::canStartCommand()Change them to these:
// True if a command can start: there's no monster in view, and the player
// isn't poisoned, which would hurt them every turn, or, for a command that
// walks, confused, which would send them astray. If not, the log says why
bool Game::canStartCommand(CommandKind kind)Then add the check below the one for poison, inside canStartCommand:
if (kind != CommandKind::Rest && player_.confused > 0)
{
log_.add("Not while you're confused.");
return false;
}Every kind but resting walks. So the test is for any kind that isn't Rest, which covers exploring too, when it comes later in this chapter.
Resting has to say what it is now. In rest, change if (canStartCommand()) to if (canStartCommand(CommandKind::Rest)).
A Click
A click on the map has fired at the cell clicked, while aiming, since Chapter 21. Now a click while playing travels there. In handleClick, find these lines:
// A click on the map, while aiming, fires at the cell clicked. The event
// gives its place in the window's pixels, as a mouse motion does
void Game::handleClick(SDL_Event event)
{
SDL_ConvertEventToRenderCoordinates(renderer_, &event);
bool onMap = event.button.x >= 0.0f && event.button.x < MAP_VIEW_W &&
event.button.y >= 0.0f && event.button.y < MAP_VIEW_H;
if (state_ != GameState::Targeting || !onMap ||
event.button.button != SDL_BUTTON_LEFT)
{
return;
}
lookCursor_ = view_->camera().cellAt(event.button.x, event.button.y);
fireAtCursor();
redraw_ = true;
}Change them to these:
// A click on the map: while aiming, it fires at the cell clicked, and while
// playing, the player travels there. The event gives its place in the
// window's pixels, as a mouse motion does
void Game::handleClick(SDL_Event event)
{
SDL_ConvertEventToRenderCoordinates(renderer_, &event);
bool onMap = event.button.x >= 0.0f && event.button.x < MAP_VIEW_W &&
event.button.y >= 0.0f && event.button.y < MAP_VIEW_H;
if (!onMap || event.button.button != SDL_BUTTON_LEFT)
{
return;
}
Point cell = view_->camera().cellAt(event.button.x, event.button.y);
if (state_ == GameState::Targeting)
{
lookCursor_ = cell;
fireAtCursor();
}
else if (state_ == GameState::Playing)
{
travelTo(cell);
}
redraw_ = true;
}In the preceding code, a click away from the map, or with any button but the left, does nothing, as before. The cell clicked is worked out once, and either fired at or traveled to. A click in any other state, such as the menu, does nothing. The help screen gets a line for the click. In KEY_HELP, add this line below the one for R:
{ "A click on the map", "travel there, by the shortest way" },Checkpoint: Press F5, with seed 42, and start a new run as the Fighter. Click on the room's top left corner: you walk there, five steps, a turn every 30 milliseconds. Now click on the door at the bottom of the room. You walk to it, open it with a bump, and step into the doorway. Press F1 to see the whole floor, and click on a room you've never been near: the log says "You don't know a safe way there.", since travel goes only by what you know. Hide the floor again with F1, and walk on.
Exploring
Travel goes to a cell the player chose. Exploring does the choosing. It walks to the nearest part of the floor the player hasn't seen, then the next, until there's nothing left to see, or something stops it. One key does it all, o.
The Edge of What's Been Seen
Where should exploring go? Somewhere a step would show something new. The cells the player knows they could stand on, beside a cell they've never seen, are the edge of what they know. From any of them, the next step looks into the unknown. Exploring takes every cell of the edge as a goal, and makes for whichever is nearest.
For many goals, A* has less to offer. One search could still serve them all, with the distance to the nearest goal as its guess. But the edge is often on every side of the player, and then the guess is small in every direction. A* would search about as widely as Dijkstra's algorithm does, and work out its guess for every cell it reached as well.
Chapter 10's Dijkstra map is simpler, and no slower. It starts from all its goals at once, and gives every cell its distance from the nearest. Walking downhill on it leads to the nearest part of the edge, by the shortest way, from anywhere on the floor.
That puts the two searches side by side: A* for the way to one place, and a Dijkstra map for the way to the nearest of many. The next image shows the map exploring walks down, on seed 42's first floor, as F3 would draw it.
The edge is every cell marked 0, along the dark, unseen parts of the floor. The player has just opened the first room's door, and stepped through it. Both the corridor below and the room it leads to are new, so they're full of edge. Downhill from the player is the way to the nearest of it.
The Edge
Open Game.h. Exploring needs a function to start it, and three for its steps. Add the first below travelTo's declaration:
void explore();Add the others below travelStep's declaration:
bool exploreStep();
std::vector<Point> unexploredEdge(const Map& known) const;
Point downhillFrom(Point cell, const DijkstraMap& distances) const;The edge is found by looking at every cell. In Game.cpp, add the start of unexploredEdge below travelStep:
// The edge of what the player has seen: the cells they know they could
// stand on that touch a cell they've never seen, diagonally too
std::vector<Point> Game::unexploredEdge(const Map& known) const
{
std::vector<Point> edge;
for (int y = 0; y < MAP_H; ++y)
{
for (int x = 0; x < MAP_W; ++x)
{
if (!known.isPassable(x, y))
{
continue;
}A cell is a candidate if it's passable on the map the player knows: ground, a door, or stairs they've seen, and not a known trap. Any other cell is passed over, with continue. Add the rest of the function below it:
for (Point step : DIRECTIONS)
{
int nextX = x + step.x;
int nextY = y + step.y;
bool unseen = level_.map.inBounds(nextX, nextY) &&
!level_.map.isExplored(nextX, nextY);
if (unseen)
{
edge.push_back({ x, y });
break;
}
}
}
}
return edge;
}A candidate is on the edge if any of its eight neighbors is a cell the player has never seen. As soon as one is found, break leaves the loop over the neighbors, so the cell joins the edge only once. A neighbor off the map doesn't count, since there's nothing there to see.
Downhill, for the Player
Monsters walk down Dijkstra maps with Chapter 10's stepDown. The player needs the same, with one difference.
A monster asks whether it can enter each neighbor, since the map it walks is the real floor, where another monster may be in the way. The player's map is of their own knowledge, made from knownMap. On it, a cell they can't step onto has no distance at all, so it's never downhill. Add the start of downhillFrom below unexploredEdge:
// The player's step downhill on a map of distances: to the neighbor with
// the lowest distance, if that's lower than their own cell's, or nowhere.
// It's a monster's step down (stepDown) without the question of whether
// the cell can be entered: the map is of the player's own knowledge, where
// a cell they can't step onto has no distance at all. Of neighbors as low
// as each other, a straight step wins, as it does for monsters
Point Game::downhillFrom(Point cell, const DijkstraMap& distances) const
{
Point best = cell;
int bestDistance = distances.at(cell);
bool bestIsDiagonal = false;The best cell starts as the player's own, with its distance. It also starts as a step that isn't diagonal, since it's no step at all. Add the rest of the function below it:
for (Point step : DIRECTIONS)
{
Point to = { cell.x + step.x, cell.y + step.y };
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 replaces the best cell if it's lower. Of neighbors as low as each other, a straight step beats a diagonal one, as it does for monsters. So the player walks in straight lines where they can. If no neighbor is lower, the best cell is still the player's own, which means there's nowhere downhill to go.
A Step of Exploring
The step puts the map, the edge and the walk together. Add exploreStep below travelStep, above unexploredEdge:
// A step of exploring, downhill on a Dijkstra map whose goals are the
// edge of what the player has seen, so the step is toward whichever part
// of the edge is nearest. The map is worked out again at every step, since
// each step shows more. Returns true when there's no edge left that the
// player can reach: the floor is explored, or the rest of it lies past
// traps they know of
bool Game::exploreStep()
{
Map known = knownMap();
std::vector<Point> edge = unexploredEdge(known);
DijkstraMap toEdge;
toEdge.compute(known, edge);
Point next = downhillFrom(player_.pos, toEdge);
if (next == player_.pos)
{
log_.add(edge.empty() ? "Explored."
: "Explored, as far as you can safely go.");
return true;
}
playerStep({ next.x - player_.pos.x, next.y - player_.pos.y });
return false;
}In the preceding code, the map is worked out again every step, since each step shows more of the floor and moves the edge. A closed door on the way is opened by walking into it, as travel's are.
When there's nowhere downhill, there are two reasons. With no edge at all, the floor is explored, and the log says "Explored." With an edge the player can't reach, the rest of the floor lies past traps they know of, which their map makes wall. So the log says "Explored, as far as you can safely go." Either way, exploring stops, and takes no turn.
o
Exploring is the third kind of command. In Command.h, add this line below Travel:
Explore, // walking to the nearest edge of what the player has seenIn Game.cpp, add explore below travelTo:
// o explores: the player walks, a step at a time, to the nearest edge of
// what they've seen, and on, until there's no edge left they can reach,
// or something happens
void Game::explore()
{
log_.markRead();
if (canStartCommand(CommandKind::Explore))
{
command_ = Command{ CommandKind::Explore };
}
}Add its step to the switch in stepCommand, below Travel's case:
case CommandKind::Explore:
done = exploreStep();
break;In handlePlayingKey, add the key's check below the one for SDLK_R:
if (key.key == SDLK_O)
{
explore();
redraw_ = true;
return;
}Replace the comment above handlePlayingKey with this:
// Esc opens the menu, ? shows the keys, > goes down the stairs, g picks
// up, i shows the inventory, d drops, x starts looking around, c closes a
// door, s searches, R rests, o explores, f fires the bow, t throws, z casts
// lightning by heart, and the moving keys move the playerAnd give the key a line in KEY_HELP, below the click's:
{ "o", "explore, until there's nothing left to see" },That's the third kind of command, and the last.
Items Aren't Goals
Exploring stops when an item comes into view, as every command does, so the player knows it's there. But it doesn't walk to items, and that's a choice. If every item seen were a goal, along with the edge, exploring would walk to the nearest, and stop on it. Then, with the item still lying there, the next o would find the player already on a goal, and go nowhere.
Design note: Brogue's commands, and Crawl's. Brogue has all of this chapter's commands. Its Z rests until the player is healed, for up to 300 turns, or until something happens, as R does here. With nothing to heal, it rests for 100 turns. A click travels, > travels to the stairs, and x explores, picking up the items and gold it passes. Dungeon Crawl Stone Soup explores on o, the key this chapter borrows, and its manual is frank about the trade: exploring by hand can save turns, but auto-explore usually saves real time. Both leave the player the turns that need a decision, and walk the rest.
Picking items up, as Brogue's explore does, raises questions of its own: what to do when the pack is full, or with an item the player put down on purpose. Walking to them without picking them up means remembering which items exploring has visited, and saving that with the run. It's simpler to leave the items to the player, who can travel to one with a click, and pick it up with g.
Checkpoint: Press F5, with seed 42, and start a new run as the Fighter. Press o. You walk to the door, open it, step through, and stop, with a giant white rat asleep in the room below: "You see a giant white rat." Press o again, and the log says "Not with a giant white rat in view." Kill the rat, and press o again. Exploring goes on, and stops for each new thing it finds: 18 gold pieces, and then a fruit bat, through the next door it opens. Fight the bat, and explore on. Now it stops for a scroll and a potion. A little later, it walks onto a hidden trap, as you might yourself, and a poison needle pricks you. Now o says "Not while you're poisoned.", and takes no turn, so wait the poison out with the period, then explore on, fighting what you meet.
To the Stairs
Once a floor is explored, the stairs are what's left, and the stairs are always far from where the player came in. So >, off the stairs, travels to them if the player has seen them. Then > again goes down.
Where the Stairs Are
The stairs are wherever the map has them, and the player knows where only once they've seen them. Open Game.h, and add the question below knownMap's declaration:
std::optional<Point> knownStairs() const;In Game.cpp, add knownStairs below knownMap:
// Where the stairs down are, if the player has seen them
std::optional<Point> Game::knownStairs() const
{
for (int y = 0; y < MAP_H; ++y)
{
for (int x = 0; x < MAP_W; ++x)
{
bool stairs = level_.map.at(x, y) == Terrain::StairsDown;
if (stairs && level_.map.isExplored(x, y))
{
return Point{ x, y };
}
}
}
return std::nullopt;
}The answer is a std::optional<Point>. It's empty if the player hasn't seen the stairs, and on the last floor, which has none. The cell is written as Point{ x, y }, naming its type. With the braces alone, C++ would try to make the optional itself from two numbers, which it can't.
> Travels
Now descend decides between going down and traveling. Replace the comment above descend with this:
// > on the stairs goes down to a new floor. The player keeps everything
// they have, and the floor they leave is gone. The run is saved on
// arrival. Leaving the floor's Amulet behind asks first: there's no way
// back up for it. Off the stairs, > travels to them, if the player has
// seen them, and > again goes downThen, in descend, find these lines:
if (level_.map.at(player_.pos.x, player_.pos.y) != Terrain::StairsDown)
{
log_.add("There are no stairs down here.");
return;
}
if (!confirmed && amuletStillHere())
{
confirmPurpose_ = ConfirmPurpose::Descend;
state_ = GameState::Confirming;
log_.add("Leave this floor's Amulet behind for good? (y or n)");
return;
}
arriveOnFloor("You go down the stairs");Change them to these:
if (level_.map.at(player_.pos.x, player_.pos.y) == Terrain::StairsDown)
{
if (!confirmed && amuletStillHere())
{
confirmPurpose_ = ConfirmPurpose::Descend;
state_ = GameState::Confirming;
log_.add("Leave this floor's Amulet behind for good? (y or n)");
return;
}
arriveOnFloor("You go down the stairs");
return;
}
if (level_.depth == LAST_FLOOR)
{
log_.add("There are no stairs down from the deepest floor.");
return;
}
std::optional<Point> stairs = knownStairs();
if (!stairs)
{
log_.add("You haven't found the stairs down yet.");
return;
}
travelTo(*stairs);In the preceding code, the test turns around: on the stairs, everything is as before, from the question about the Amulet to the arrival below. Off them, the last floor has no stairs to travel to, and says so. Otherwise, if the player has seen the stairs, *stairs gives the cell inside the optional. Then travelTo takes them there, with all its checks: no monster in view, no poison and no confusion.
Arriving ends the travel, on the stairs, so the player still decides when to go down. The next image shows the way > takes on seed 42's first floor, with the floor known.
Notice that the way leaves the first room straight down, through its door, rather than slanting off toward the stairs' side. That's the hundredth at work.
The comments and the help say what > does now. Replace the comment above travelTo with this:
// Starts traveling to a cell the player has seen, by the shortest way they
// know, a step at a time. A click on the map travels, and so does > when
// the player isn't on the stairsIn handlePlayingKey, replace the comment above if (typedKey(key) == SDLK_GREATER) with this:
// > goes down the stairs, or travels to them. It's Shift and the
// period on a US keyboard, so it's checked before the moving keys,
// where the period alone waitsReplace the comment above handlePlayingKey with this:
// Esc opens the menu, ? shows the keys, > goes down the stairs or travels
// to them, g picks up, i shows the inventory, d drops, x starts looking
// around, c closes a door, s searches, R rests, o explores, f fires the
// bow, t throws, z casts lightning by heart, and the moving keys move the
// playerLast, the help. In Game.cpp, change { ">", "go down the stairs" }, to { ">", "go down the stairs, or travel to them" },.
Checkpoint: Press F5, with seed 42, and start a new run as the Fighter. Press >, and the log says "You haven't found the stairs down yet." Explore with o, fighting what you meet, until you've seen the stairs, in the room at the top right of the floor. Then press > from anywhere: you travel to the stairs, and stop on them. Press > again, and you go down to floor 2.
Playing the Game
Play a few floors with the new commands, and the game finds a new rhythm. Press o, and let exploring run until something stops it. A monster: fight it, or step back out of its sight. An item: click on it to travel there, and pick it up. A trap: think about the way around.
When you're hurt and nothing's in view, R heals you in a few seconds of watching, rather than a few hundred presses of the period.
Exploring isn't careful, so watch where it goes. It walks onto traps you haven't found, as you would, and it opens every door, whatever's behind it. A closed door you'd rather leave closed is a reason to explore by hand for a while, or to travel past it with a click.
Resting is the riskiest. A wandering pack can arrive while you rest, and it stops you only once it's in view. So rest in a dead end, or behind a door, where whatever comes has one way in.
When o says "Explored.", you've seen all of the floor you know a way to, but it may still hide a secret door. A dead end, or a stretch of wall with nothing behind it, is worth a search. When you're done, > takes you to the stairs, and > again takes you down.
Understanding the Code
A command is a Command, of a kind, with a goal and a count of its turns. It's held in Game::command_, a std::optional that's empty when no command runs. While one runs, run takes a step whenever one is due, every COMMAND_STEP_MS milliseconds. Between steps, it waits for events with SDL_WaitEventTimeout, for no longer than the time left. A key stops the command, and does nothing else.
Each step is stepCommand, which sends it to restStep, travelStep or exploreStep. Before the step, watch notes what the player knows in a Watch, and after it, somethingNew compares. Any of these stops the command: a monster in view, health lost, a new floor, a trap or secret door found, or an item seen. No command starts at all while canStartCommand finds a monster in view, poison, or, for a command that walks, confusion.
Travel works out the way to its goal every step, with AStar::findPath, over knownMap, the floor as the player knows it. A* is Dijkstra's algorithm with its queue ordered by the cost so far plus leastCost, a guess that's never too much. So it heads for the goal, and stops there. Costs are in hundredths of a step, a diagonal step a hundredth dearer. So of the shortest ways, A* finds one with the fewest diagonal steps.
Exploring walks downhill, with downhillFrom, on a Dijkstra map whose goals are unexploredEdge, the known cells beside unseen ones. Off the stairs, descend travels to knownStairs.
Experimenting
Try each of these, and put each back afterward:
- Slow motion. Set
COMMAND_STEP_MSto200. Each step of a rest, a walk or exploring now waits a fifth of a second, and you can follow every one. Set it to0, and a command is over almost as soon as it starts, too fast to see. - Diagonals for free. Set
DIAGONAL_EXTRAto0. Explore seed 42 until you've seen the stairs, as at the last checkpoint. Then click on the cell where you started, in the first room, to go back there. Press >: you head off diagonally, toward the stairs' side of the room, and come back to the door, rather than walking straight down to it. It's no more steps, but it looks lost. - No look before starting. In
canStartCommand, take out the check for a monster in view. At seed 42, press o, and exploring stops in the doorway below the first room, with the rat in view. Press o again, and again. Each time, exploring starts, takes one step, and stops: "You see a giant white rat." With a monster in view, every command would be a single step.
The first shows what the timing is for: the loop's 30 milliseconds are the whole of the animation. The second shows why the hundredth is there, and the third why a command checks before it starts, as well as after each step.
Common Errors and Fixes
If the game didn't build, or doesn't behave as described, the problem is probably one of these.
C2065: 'Command': undeclared identifier, in Game.h, followed by several more. The game holds a std::optional<Command>, but Game.h doesn't include Command.h, so the compiler has never heard of a Command. Add #include "Command.h" above #include "Common.h".
C3449: the number of identifiers must match the value of 'std::tuple_size<_Ty>::value' in a structured binding of tuple-like type, in AStar.cpp. The structured binding names fewer values, or more, than the tuple holds, as in auto [guess, index] = open.top();. The size the message means is the tuple's, three: the guess, the crow's distance and the index. So the binding needs three names, in that order.
Travel jumps straight to the goal in a single turn. The way is still in the order cameFrom gives it, from the goal back to the start. So its first cell is the goal itself, and playerStep moves the player there in one go. The call to std::reverse is missing from the end of findPath.
A rest is over in a flash, all its turns at once. The line Uint64 stepDue = 0; is inside the loop. So every time around, the step is due again, and is taken at once. Move it above while (running_), so the time a step is due lasts from one time around the loop to the next.
FAQ
Q) Why does a sleeping monster stop a rest? It isn't doing anything.
A) Yet. A sleeping monster can wake at any turn, and a command can't know which, or whether it matters. The player can: a sleeping rat is no threat, and a sleeping troll is the reason to rest somewhere else. So the command stops, and lets them decide. Crawl's resting stops when a monster appears too, and Brogue's when anything happens.
Q) Why does travel work the way out again at every step, when it worked it out when it started?
A) The way can change as the player walks. They see more of the floor, which can open a shorter way. Doors they open change their cost, and the Rogue's keen eyes can find a trap on the way, which makes its cell wall. A search over a floor this size takes a fraction of a millisecond, and only one runs each step. So working it out again costs nothing anyone would notice.
Q) Couldn't travel use a Dijkstra map, and exploring use A*?
A) Travel could use a Dijkstra map, with one goal: walking downhill on it gives a shortest way, as it does for the monsters. On floors this size, that would do, since exploring builds a Dijkstra map of the whole floor at every step, and no one notices. A* is the standard way to find one path, though, and its saving matters on bigger maps, and with many searches.
Exploring could use A*, with the distance to the nearest cell of the edge as its guess. But the edge has dozens of cells, often on every side, so the guess saves little, and it costs a look at each of them. One Dijkstra map with all of them as goals is simpler, and as quick.
AI Exercise (Optional)
Brogue shows the way a click would travel. As the mouse moves over the map, the cells of the way light up, from the player to the cell under the mouse. If you'd like to add that, 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. The game draws a fixed 1600 by 900 picture, with the map in a view whose camera has cellRect(Point cell), giving the SDL_FRect a cell is drawn in. Game::hoveredCell() returns a std::optional<Point>, the map cell under the mouse, and the screen is drawn again only when it changes. A click on the map travels there: AStar::findPath(knownMap(), player_.pos, cell) returns a std::vector<Point>, the cells of the shortest way after the player's, empty if there's none. Game::drawLineOfFire() already draws a line of cells while aiming, as see-through rectangles. I'd like the cells of the way to the hovered cell drawn the same way while playing, but not while aiming or looking. Show me every change, with each curly brace on its own line, and explain it."
Notice what the preceding prompt does. It names the function that already draws a line of cells, so the answer can follow it. And it says when the screen is drawn, so the answer doesn't try to draw every frame.
When the answer comes back, check where it finds the way. Working it out in the drawing code is fine, since the screen is drawn only when something changes. But draw is const, so whatever it calls must be too, as knownMap is. And check what it draws when there's no way: an empty vector should draw nothing, not the old way, or a line through the walls.
Summary
A command takes many turns, a step at a time, and the loop wakes for each step, every 30 milliseconds, so the player sees it happen. Before each step, the game notes what the player knows, and after it, stops for anything new. R rests until healed, and a click travels by A*, Dijkstra's algorithm with a guess at the cost still to come. The o key explores down a Dijkstra map whose goals are the edge of what's been seen, and > travels to the stairs. In Chapter 24, the game gets some juice: hits flash, arrows fly across the screen, and a big blow shakes it.