The monsters of Chapter 32 are brave, but they aren't bright. A monster that notices you walks straight at you, and if a wall is in the way, it stops there and stays, pressing its nose against the stone, even when a doorway is one step to the side. Slip around a corner, and it doesn't come after you. By now you've probably learned to use that, and this chapter takes it away.
The monsters learn to find the shortest way to you, around anything, with A*, the pathfinding algorithm behind countless games. And they learn to remember. A monster that loses sight of you heads for the place where it saw you last, and picks up the chase from there. Only when it gets there, and you're nowhere to be seen, does it give up.
A more dangerous dungeon deserves a way to stop and come back later, so the game learns to save, too. Press F5, and the whole game goes into a text file, and press F9, and it comes back, just where you left it. Along the way, you'll put Chapter 15's priority queue to work, teach an unordered map to use a type of your own as its key, as Chapter 15 promised, and have the compiler check a table against its enum while the program builds. By the end of the chapter, the monsters will follow you anywhere, as in Figure 33.1.
SDL3 Projects/Rogue SDL Part 4 — the complete source for this chapter lives here, with its twenty-six files and the assets folder. The chapter carries on in your own project from Chapter 32. If you'd rather start from the book's copy of Part 3, make a copy of the Rogue SDL Part 3 folder beside it in SDL3 Projects, where it still finds the SDL3 and SDL3_ttf folders, and open the copy's .slnx file.In this chapter, we will:
- Find the shortest way from one cell to another with A*, and see why it looks at so few cells on the way
- Keep A*'s candidates in a
std::priority_queue, smallest first, and meet the other kind of heap - Teach
std::unordered_mapto use aPointas its key, by writing astd::hashfor it - Give the monsters a memory, so that they hunt you around corners, and give up when they lose you
- Check a table against its enum while the program builds, with
static_assert - Save the whole game to a text file with F5, and load it back with F9, safely
- Play, experiment, fix the most common mistakes, and try an optional AI exercise
Let's teach them to hunt.
Planning Part 4
Part 3 finished with twenty-two files. Part 4 adds four more, and changes ten. Here's what each one is for:
| File | What's new |
|---|---|
AStar.h, AStar.cpp |
New: A*, which finds the shortest path from one cell to another |
SaveLoad.h, SaveLoad.cpp |
New: saving the game to a text file, and loading it back |
Common.h |
A way to hash a Point, so that it can be a key in an unordered map |
Enemy.h, Enemy.cpp |
A memory of where the player was seen last, and what saving needs to know |
Item.h, Item.cpp |
A count of the kinds of treasure, checked against the table |
Player.h, Player.cpp |
A way to set each of the player's numbers, for loading |
HUD.cpp |
The two new keys, on the HUD |
Game.h, Game.cpp |
The monsters' hunt, and saving and loading with F5 and F9 |
The chapter has two halves, and they hardly touch. The first is about the monsters, and most of it is A*, which lives in a file of its own, knows nothing about monsters, and answers one question: what's the shortest way from here to there? The second is about saving, and most of that lives in a file of its own too, which knows how to write every part of the game down, and how to read it all back.
We'll play the game at the end of each half. First, the monsters learn to hunt, and you'll find out how much harder they are to shake off. Then the game learns to save and load, which needs a few small changes to the entities, so that everything about them can be written down and put back.
Finding the Way
Straight Toward You Isn't Enough
Part 3's monster takes one step along whichever way you're farther, across or down, and that works well enough in the open. But put a wall between you, as on the left of Figure 33.2, and the monster walks into it, and stops. What it needs is a path: a list of cells to step through, each one next to the one before, from where it is to where you are, around whatever is in the way. And not just any path, but the shortest, so that it doesn't wander.
Finding the shortest path is a search, and the simplest search spreads out from the monster evenly, like a ripple on a pond. First it looks at every cell one step away, then at every cell two steps away, and so on, until the ripple reaches the player. Every cell remembers which cell the ripple reached it from, and following those back from the player gives the path.
This is a breadth-first search, since it goes wide before it goes far, and it always finds the shortest path. Its trouble is that it has no idea where the player is. It spreads just as fast away from the player as toward them, so by the time it arrives, it has looked at almost every cell that's nearer to the monster than the player is.
A Search With a Sense of Direction
A*, said "A star," is a search with a sense of direction. It still looks at one cell at a time, and still remembers where it reached each cell from, but it chooses the next cell differently. Instead of the cell that's the fewest steps from the monster, it looks next at the one that seems most promising: the one with the smallest guess at the length of a whole path through it. A cell's guess is two numbers added together:
- the steps it took to reach the cell from the monster, which A* knows exactly, and
- the steps still to go from the cell to the player if there were no walls in the way, which is the Manhattan distance from Chapter 31.
Take a step straight toward the player, and the first number goes up by one while the second goes down by one, so the guess stays the same. Take a step the wrong way, and both go up by one, so the guess grows by 2. So A* heads straight for the player, and only when that way is blocked does it try the cells whose guesses are a little bigger. Figure 33.3 shows it at work, on the map from Figure 33.2.
The guess can be too small, when walls make the real path longer, as they do here. But it can never be too big, since no path to the player is shorter than walking straight there. That's what makes A* trustworthy. It can't overlook a shorter path, since every cell on one would have a smaller guess, and be looked at first. So the path it finds to the player is always the shortest there is.
A* was published in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael, of the Stanford Research Institute. They built it for Shakey, the first mobile robot that could reason about its own actions, which had to plan its way around the rooms it rolled through. Raphael suggested adding the steps so far to a guess at the steps to go, and Hart worked out which guesses are safe: the ones that are never too big. Nearly sixty years later, A* is still where game programmers start.
How much does the sense of direction save? In the open, a great deal. To cross forty cells of an empty room, A* looks at 41 cells, the start and one for every step, while a breadth-first search looks at 1,155.
Rogue SDL's dungeons are harder on it, since a path through them so often has to head away from where it's going before it can turn toward it. On nearly 4,000 paths between random cells of 200 levels, A* looked at 310 cells on average, and the breadth-first search at 575. Both found paths of exactly the same length, every time. A* just got there with half the work.
The Queue That Keeps Its Order
Every search keeps a list of the cells it has found but not looked at yet, which are its candidates. A breadth-first search keeps them in a plain queue, first in, first out, which is what makes its ripple even. A* needs something different. Over and over, it takes the candidate with the smallest guess, while new candidates keep arriving. That's exactly the job of Chapter 15's std::priority_queue, which hands out the biggest first, or with std::greater, the smallest.
Each candidate is a cell and its guess, kept together in a small struct. The queue compares two candidates with std::greater, which uses >, so the struct has to say what > means for a candidate: one candidate is greater than another when its guess is bigger.
A priority queue doesn't keep its candidates sorted, which would mean a lot of shuffling, with new ones arriving all the time. It keeps them in a vector, in an order called a heap. Picture the vector as a tree, as in Figure 33.4, with its first candidate at the top, the next two below that, the next four below those, and so on. The rule is that no candidate's guess is bigger than the guesses below it. So the smallest is always at the top, and adding or taking a candidate only means swapping a few of them along one branch of the tree.
Be careful with the word heap, which means two unrelated things in C++. Chapter 10's heap is memory: the place where new puts things, and where a vector keeps its elements. This chapter's heap is an arrangement: a way of ordering items in a vector so that the smallest, or the biggest, is always first. A priority queue's heap happens to sit in heap memory, as every vector's elements do, but that's a coincidence of names.
A* never looks inside the heap, or cares how it's arranged. It only ever adds a candidate, or takes the one on top, and the queue does the rest.
Remembering the Way Back
As A* reaches each cell, it writes down two things about it, in two unordered maps. The first, steps, holds the fewest steps it has found to reach the cell. The second, cameFrom, holds the cell it was reached from on that way. If A* later finds a shorter way to a cell it has already reached, it writes down the new steps and the new cell it came from, and adds the cell to the queue again, with its better guess.
When the player's cell comes out of the queue, the search is over, and the path is in cameFrom, backward. The player's cell was reached from one cell, which was reached from another, and so on, back to the monster, as Figure 33.5 shows. Following that trail from the player gives the path from the player to the monster. Turning the list around gives it in the order the monster walks it.
Points as Keys
Both maps use a Point as their key, and that's where Chapter 15's warning comes in. An unordered map finds a key by turning it into a number, its hash, and the standard library knows how to hash numbers and strings, but not a struct of yours. Ask for a std::unordered_map<Point, int> without saying how, and the build stops deep inside the standard library, with C2064, in a file called xhash.
The way to say how is std::hash. It's a class template, like Chapter 24's Grid, with a type as its blank, and the standard library comes with versions of it for numbers, strings, and more. To hash a Point, you write a version of std::hash for Point alone, which is called a specialization. It's a small struct, and all it needs is a function that takes a point and returns its number.
What should the number be? Ideally, every cell gets a different one, so that the map can go straight to a cell's entry, without sorting through others that share its number. Chapter 30 has already worked out exactly that number: the index of a cell's tile in the map's vector, y * MAP_W + x, which is different for every cell on the map. The map still checks with == that it has found the right key, and Point has had that since Chapter 32.
Since the map is a fixed size, two plain vectors, with a number for every cell, would do the same job as the unordered maps, and a little faster. The unordered maps are how A* is usually written, though, since they only hold the cells the search reaches, and they work on maps of any size, or on a map with no edges at all.
Writing A*
Hashing a Point
The hash comes first, since A* can't build without it. In Common.h, add this below #include <SDL3/SDL.h>:
#include <functional> // std::hashIn the preceding code, <functional> is the header that holds std::hash, and std::greater too. Then add the specialization below WINDOW_H, with a blank line in between:
// How to hash a Point, so that it can be a key in an unordered_map. Each
// cell gets its own number: the same number as its tile's index in the
// Map's vector
template <>
struct std::hash<Point>
{
size_t operator()(const Point& point) const
{
return point.y * MAP_W + point.x;
}
};In the preceding code, template <> says that what follows is a version of a template with all of its blanks already filled in, so there's nothing left for the compiler to fill. The next line names the template, std::hash, and the type this version is for, Point. It sits below the window's sizes because it uses MAP_W, which has to come first.
Inside, operator() is the function call operator, which lets a std::hash<Point> be called as if it were a function. The unordered map makes one, and whenever it needs a point's number, it calls it with the point, as hasher(point). A Chapter 32 lambda works in just the same way: the compiler turns it into an object with an operator(). The number is a size_t, the standard library's type for sizes and indexes, and it's the tile's index, which is different for every cell.
AStar.h
A* gets a namespace of its own, since it's a single function, with nothing to keep between one search and the next. Add a header called AStar.h, and below its #pragma once, type this:
#pragma once
#include <vector> // std::vector, for the path
#include "Common.h"
class Map;
// A*, the shortest way from one cell to another, around the walls
namespace AStar
{
std::vector<Point> findPath(const Map& map, Point from, Point to);
}In the preceding code, findPath takes the map, to know where the walls are, and two cells, and returns the path between them, as a vector of cells. It takes the map by const reference, since finding a path only reads it, and a reference only needs the forward declaration, class Map;, as in Chapter 31's FOV.h.
The path doesn't include the cell it starts from, where the monster already stands, but it does include the cell it ends at. So its first cell is the monster's next step, and its size is the number of steps to take.
The Candidates
Add a C++ file called AStar.cpp, and type its includes, and an empty namespace, which will hold three things that only A* needs:
#include "AStar.h"
#include <algorithm> // std::reverse
#include <cstdlib> // std::abs
#include <functional> // std::greater
#include <queue> // std::priority_queue
#include <unordered_map> // std::unordered_map
#include "Map.h"
namespace
{
}In the preceding code, each include has a comment saying what it's for, from std::reverse, which turns the path around at the end, to std::unordered_map. The namespace has no name, which, as in Chapter 31, keeps everything in it private to this file.
First, the candidate. Add this inside the namespace:
// A cell waiting to be looked at, and a guess at the whole length of a
// path through it: the steps it took to get there, plus the steps
// still to go, if there were no walls in the way
struct Candidate
{
Point cell;
int guess;
// So that std::greater can say which of two is farther from the
// front of the queue
bool operator>(const Candidate& other) const
{
return guess > other.guess;
}
};In the preceding code, a Candidate is a cell and its guess. Its operator> is a member function that compares this candidate with another, and it's const, since comparing changes neither of them. Only the guesses matter: the queue doesn't care which cells they are. With this, std::greater<Candidate> can compare two candidates, which is all the queue needs.
Next, the guess at the steps still to go, and the four ways to step. Add these below Candidate, with a blank line in between:
// The steps from one cell to another, if there were no walls in the
// way: across, plus down
int distance(Point a, Point b)
{
return std::abs(a.x - b.x) + std::abs(a.y - b.y);
}
// The four cells next to a cell: up, down, left, and right
constexpr Point DIRECTIONS[] = { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } };In the preceding code, distance is Chapter 31's Manhattan distance: the steps across plus the steps down, with std::abs making each of them positive. The DIRECTIONS array holds the four steps a monster can take, as changes to a cell's x and y. It's constexpr, since the four steps are known before the program runs, and it can be, since a Point is a plain struct of two ints.
Checkpoint: Click in AStar.cpp, and press Ctrl+F7 to compile it on its own. It compiles, although it doesn't do anything yet, since nothing uses the three things in the namespace.
findPath
Now the search itself. It's in three parts: getting ready, the loop that searches, and following the trail. Add the first part below the unnamed namespace, with a blank line in between:
namespace AStar
{
// The cells to step through to get from one cell to another, in order,
// not counting the first cell, but counting the last. It's empty if
// there's no way through
std::vector<Point> findPath(const Map& map, Point from, Point to)
{
// The cells still to look at, the one with the smallest guess
// first, and for every cell reached so far, the fewest steps it
// takes to get there, and the cell it's reached from
std::priority_queue<Candidate, std::vector<Candidate>,
std::greater<Candidate>> waiting;
std::unordered_map<Point, int> steps;
std::unordered_map<Point, Point> cameFrom;
waiting.push({ from, distance(from, to) });
steps[from] = 0;In the preceding code, findPath goes in the AStar namespace, as the header declared it. The queue, waiting, is Chapter 15's mouthful, with three things in its angle brackets: what it holds, candidates; what it keeps them in, a vector of candidates; and how it compares them, with std::greater, so that the smallest guess comes out first. It's split over two lines to stay readable. Then come the two unordered maps, with Point keys, which is why the hash had to come first.
The search starts with one candidate: the monster's own cell, from. It took no steps to get there, so its guess is just the distance to go, and its entry in steps is 0. Indexing an unordered map with [] adds the entry if it isn't there yet, which was Chapter 15's square-bracket trap, and here it's exactly what's wanted.
Next, the loop. Add it below steps[from] = 0;:
while (!waiting.empty())
{
Point cell = waiting.top().cell;
waiting.pop();
if (cell == to)
break;
// Reach each open neighbor in one more step, unless it's
// already been reached in as few
for (Point direction : DIRECTIONS)
{
Point next = { cell.x + direction.x, cell.y + direction.y };
if (map.isBlocked(next))
continue;
int nextSteps = steps[cell] + 1;
if (!steps.contains(next) || nextSteps < steps[next])
{
steps[next] = nextSteps;
cameFrom[next] = cell;
waiting.push({ next, nextSteps + distance(next, to) });
}
}
}In the preceding code, the loop runs until the queue is empty. Each time around, it takes the candidate with the smallest guess, with top, which reads it, and pop, which removes it, as in Chapter 15. If that candidate is the player's cell, to, the search is over, and break leaves the loop.
Otherwise, it reaches out to the cell's four neighbors, one direction at a time. A wall is skipped with continue. For any other neighbor, nextSteps is the steps to reach it through this cell: one more than the steps to this cell. If the neighbor hasn't been reached before, which contains tells, or this way is shorter than the way it was reached before, the neighbor's steps and the cell it came from are written down, and it joins the queue, with its guess.
The steps to cell are always there to read, since a cell only joins the queue after its steps are written down. A cell that joins the queue twice, once for each way it was reached, can come out twice, too, but the second time, none of its neighbors can be reached in fewer steps than before, so it changes nothing.
Last, the trail. Add this below the loop, with a blank line in between, to finish findPath and the namespace:
// Follow the trail back from the end to the start, then turn it
// around
std::vector<Point> path;
if (!cameFrom.contains(to))
return path;
for (Point cell = to; cell != from; cell = cameFrom[cell])
path.push_back(cell);
std::reverse(path.begin(), path.end());
return path;
}
}In the preceding code, if cameFrom has no entry for the player's cell, there's no trail to follow. Either there's no way through, and the queue ran out of candidates before the search reached the player's cell, or to is from, which the search starts at, and so never reaches from anywhere. Either way, the path is empty.
Otherwise, the for loop starts at the player's cell, and steps back along the trail, one cameFrom at a time, adding each cell to the path, until it gets back to from. The monster's own cell isn't added, since the monster is already standing there. Then std::reverse, from <algorithm>, turns the vector around, given its beginning and end, so that the path starts with the monster's next step.
Checkpoint: Click in AStar.cpp, and press Ctrl+F7 again. The whole of A* compiles. If the build stops in a file called xhash, go back to Common.h, and check the hash. Nothing uses A* yet, so there's nothing new to see in the game, but that's about to change.
The Hunt
A Monster's Memory
A hunting monster needs to remember two things: that it's hunting, and where it saw the player last. In Enemy.h, add these below takeDamage’s declaration, with a blank line in between:
bool isHunting() const;
Point getLastSeen() const;
void hunt(Point lastSeen);
void giveUp();In the preceding code, the first two functions answer the two questions, and the other two change the answers: hunt starts a hunt, or carries one on, with a fresh sighting, and giveUp ends it. Then add these below int hp_;:
bool hunting_ = false; // true once it has seen the player
Point lastSeen_; // where it saw the player lastIn the preceding code, a monster starts out not hunting. Its lastSeen_ starts at (0, 0), which doesn't matter, since nothing reads it until the monster is hunting, and by then it holds a real sighting.
In Enemy.cpp, add the four functions at the end of the file, below takeDamage, with a blank line in between:
bool Enemy::isHunting() const
{
return hunting_;
}
Point Enemy::getLastSeen() const
{
return lastSeen_;
}
// Starts hunting the player, or keeps on hunting, with a fresh sighting
void Enemy::hunt(Point lastSeen)
{
hunting_ = true;
lastSeen_ = lastSeen;
}
// Loses the trail, and waits where it is
void Enemy::giveUp()
{
hunting_ = false;
}In the preceding code, the first two return the members. The hunt function sets both of them, whether the monster was hunting already or not, so every sighting moves lastSeen_ to wherever the player is now. The giveUp function only clears hunting_. The monster stays where it is, and waits, until it notices the player again.
Around Every Corner
Now the monster's turn. Part 3's monsterTurn ran only for monsters that had noticed the player, and stepped straight toward them. The new one runs for every monster, every turn, since a monster that's hunting has to keep going when the player is out of sight. Figure 33.6 shows a hunt from start to finish.
The monsters will use A*, so Game.cpp needs its header. Add this below #include <string>:
#include "AStar.h"In the preceding code, AStar.h brings in findPath. Next, every monster should get a turn, and not only the ones that notice the player. Find these lines in endTurn:
for (Enemy& enemy : enemies_)
{
if (!notices(enemy))
continue;
monsterTurn(enemy);And change them to this:
for (Enemy& enemy : enemies_)
{
monsterTurn(enemy);In the preceding code, the if that skipped a monster that hadn't noticed the player is gone, since deciding what a monster does, noticing included, is now monsterTurn’s job.
Now the turn itself. Find the first lines of monsterTurn:
// A monster that has noticed the player attacks if it's next to them, and
// otherwise steps toward them
void Game::monsterTurn(Enemy& enemy)
{
Point from = enemy.getPosition();
Point to = player_.getPosition();
int dx = to.x - from.x;
int dy = to.y - from.y;
if (std::abs(dx) + std::abs(dy) == 1)And change them to this:
// A monster that sees the player hunts them. It attacks if it's next to
// them, and otherwise steps along the shortest path to where it saw them
// last, so that it can follow them around corners
void Game::monsterTurn(Enemy& enemy)
{
if (notices(enemy))
enemy.hunt(player_.getPosition());
if (!enemy.isHunting())
return;
Point from = enemy.getPosition();
Point to = player_.getPosition();
if (std::abs(to.x - from.x) + std::abs(to.y - from.y) == 1)In the preceding code, the comment says what the function does now. If the monster notices the player, it hunts them, with the player's cell as the latest sighting. A monster that isn't hunting, because it hasn't noticed the player, or has given up, has nothing to do, so its turn is over. The distances dx and dy have gone, since the only thing that still needs them is the test for being next to the player, which works them out for itself.
The attack is just as it was. The step after it changes completely. Find the lines that take the step, at the end of monsterTurn:
// One step along whichever way is farther. A wall in the way stops it
Point step = from;
if (std::abs(dx) > std::abs(dy))
step.x += dx > 0 ? 1 : -1;
else
step.y += dy > 0 ? 1 : -1;
if (!map_.isBlocked(step) && !enemyAt(step))
enemy.setPosition(step);And change them to this:
// An empty path means it's where it saw the player last, and they're
// gone, or that there's no way there. Either way, it loses the trail
std::vector<Point> path = AStar::findPath(map_, from, enemy.getLastSeen());
if (path.empty())
{
enemy.giveUp();
return;
}
// It waits, if another monster is in the way
if (!enemyAt(path[0]))
enemy.setPosition(path[0]);In the preceding code, the monster asks A* for the path from its own cell to the last place it saw the player. While it can see the player, that's where the player is, so it closes in, around anything in the way. When it can't, that's where the player was, so it follows.
If the path is empty, the monster is already standing where it saw the player last, and it can't see them now, or it would have taken a fresh sighting. So it gives up. An empty path could also mean there's no way there at all, which never happens in Rogue SDL's dungeons, since every room is joined to the rest, but giving up would be the right thing to do then, too. Otherwise, the monster takes the first step of the path, unless another monster is standing there, in which case it waits a turn. A* only knows about walls, so it happily plans a path through other monsters, and this is where the traffic is sorted out.
Checkpoint: Press F5, and find a monster. Let it see you, and then walk away, around a corner or two. It follows, and it keeps following when it's out of sight: keep walking, and it comes around the corner behind you, as in Figure 33.7. Shaking one off takes more than a corner now. You have to be out of its sight when it reaches the last place it saw you, and then it gives up, and waits there.
Saving and Loading
What Goes in a Save File
A saved game has to hold everything the game needs to carry on exactly where you left off, and nothing that it can work out again. That's less than it sounds:
- the depth;
- the player: where they stand, and their health, gold, and potions;
- every monster: its kind, where it stands, and its health;
- every item on the floor: its kind, where it lies, and its amount;
- and the map: every tile's terrain, and whether the player has explored it.
That's all. The field of view works out what's visible again, the tables already know what every kind of monster and treasure is like, and the HUD's messages and the monsters' hunts can go. A loaded monster isn't hunting, even if it was when you saved. If it can see you, though, it notices you on its first turn, which comes to the same thing.
The file is text, one thing to a line, and each line starts with a word that says what it is. That makes it easy to read back, and easy for you to read, too, as Figure 33.8 shows.
A monster's kind is an enum class, which a file can't hold as it is, so the file holds its number instead: 0 for a rat, 1 for a goblin, and 2 for an orc, from static_cast<int>, as in statsOf. Reading it back needs the opposite cast, and a check first, since a number from a file could be anything, and a kind that isn't in the table would read past its end.
The numbers in a save file only mean something while the enums keep their order. When you add a kind of monster, add it at the end of the enum, as Chapter 31 said, and old save files still load correctly. Put it anywhere else, and every kind after it gets a new number, and old saves load with the wrong monsters. And when the format itself changes, raise SAVE_VERSION, so that old files are turned away rather than misread.
Reading needs care in general. A save file is only text, and anything can happen to text: a crash halfway through writing it, a slip while editing it, a file left over from an older version of the game. So loading is all or nothing. Everything is read into new variables first, and checked as it's read, and only if the whole file is good do the game's own variables get the new values. If anything is wrong, the game carries on exactly as it was, and the HUD says the file couldn't be read.
Kinds as Numbers
Saving needs to ask a monster its kind, and loading needs to check a kind's number, and set a monster's health. In Enemy.h, add this below the closing brace of MonsterKind, with a blank line in between:
constexpr int MONSTER_KINDS = 3; // how many kinds there areIn the preceding code, MONSTER_KINDS is how many kinds of monster there are, which is one more than the biggest number a kind can have. Then add this above getStats’s declaration:
MonsterKind getKind() const;In the preceding code, getKind will return the monster's kind, for saving. Then add this below getHp’s declaration:
void setHp(int hp);In the preceding code, setHp will set the monster's health, for loading. Then, in Enemy.cpp, add getKind below the constructor, with a blank line in between:
MonsterKind Enemy::getKind() const
{
return kind_;
}In the preceding code, getKind returns kind_, which the monster has had since Chapter 32. Then add setHp below getHp, with a blank line in between:
void Enemy::setHp(int hp)
{
hp_ = hp;
}In the preceding code, setHp sets hp_. It doesn't check the number, since loading is the only thing that uses it, and a monster loaded with no health is cleared away with the rest of the dead after your next move.
Now MONSTER_KINDS has to match the enum, and the table has to have a row for every kind. Chapter 31 warned that the compiler can't catch a table that's out of step with its enum, since it has no way to know which row belongs to which kind. That's still true, but it can count them. In Enemy.cpp, add this below #include "Enemy.h":
#include <iterator> // std::sizeIn the preceding code, <iterator> brings in std::size, which Chapter 13 used to count the elements of an array. Then add this inside the namespace, below the table:
static_assert(std::size(MONSTER_STATS) == MONSTER_KINDS,
"There must be one MonsterStats for each MonsterKind");In the preceding code, a static_assert is a check that happens while the program builds, not while it runs. It takes a condition, which the compiler must be able to work out on its own, and a message. If the condition is true, it does nothing at all, and doesn't even take up space in the program. If it's false, the build stops, with the message.
Add a fourth kind of monster to the enum, and make MONSTER_KINDS 4, but forget its row, and the build stops right here, with C2338 and your message, rather than a game that reads past the end of its table. The one thing it can't check is MONSTER_KINDS itself, so when you add a kind, change that too.
The treasure gets the same treatment, since saving and loading will turn its kinds into numbers too. In Item.h, add this below the closing brace of ItemKind, with a blank line in between:
constexpr int ITEM_KINDS = 2; // how many kinds there areIn the preceding code, ITEM_KINDS counts the kinds of treasure, as MONSTER_KINDS counts the monsters. Then, in Item.cpp, add this below #include "Item.h":
#include <iterator> // std::sizeIn the preceding code, <iterator> is there for std::size again. Then add this inside the namespace, below the table:
static_assert(std::size(ITEM_STATS) == ITEM_KINDS,
"There must be one ItemStats for each ItemKind");In the preceding code, the treasure's table is checked against ITEM_KINDS, as the monsters' table is. An item already has getKind and getAmount, from Chapter 32, and loading makes each item new, with its amount, so the treasure needs nothing else.
The player's numbers need setting, too, since loading puts them all back. In Player.h, find these lines:
int getHp() const;
int getAttack() const;
int getGold() const;
int getPotions() const;And change them to this:
int getHp() const;
void setHp(int hp);
int getAttack() const;
int getGold() const;
void setGold(int gold);
int getPotions() const;
void setPotions(int potions);In the preceding code, each of the three numbers that loading puts back gets a function to set it, beside the one that gets it. The attack has no setter, since it's always PLAYER_ATTACK. In Player.cpp, add setHp below getHp, with a blank line in between:
void Player::setHp(int hp)
{
hp_ = hp;
}In the preceding code, setHp sets the player's health. Then add setGold below getGold, with a blank line in between:
void Player::setGold(int gold)
{
gold_ = gold;
}In the preceding code, setGold sets the player's gold. Then add setPotions below getPotions, with a blank line in between:
void Player::setPotions(int potions)
{
potions_ = potions;
}In the preceding code, setPotions sets the number of potions the player carries. Like the monster's setHp, none of the three check their numbers, which is the job of whoever calls them.
Checkpoint: Click in Enemy.cpp, and press Ctrl+F7, and then do the same in Item.cpp, and in Player.cpp. All three compile. If Enemy.cpp stops at the static_assert, count the rows of the table, and the kinds in the enum.
SaveLoad.h
Saving and loading get a namespace of their own, as A* did. Add a header called SaveLoad.h, and below its #pragma once, type this:
#pragma once
#include <string> // std::string, for the file's path
#include <vector> // std::vector, for the monsters and the treasure
class Enemy;
class Item;
class Map;
class Player;
// Saving the game to a text file, and loading it back
namespace SaveLoad
{
bool save(const std::string& path, const Map& map, const Player& player,
const std::vector<Enemy>& enemies,
const std::vector<Item>& items, int depth);
bool load(const std::string& path, Map& map, Player& player,
std::vector<Enemy>& enemies, std::vector<Item>& items,
int& depth);
}In the preceding code, save takes everything it writes by const reference, since writing a file changes nothing in the game. The load function takes everything it replaces by plain reference, since it changes them all, depth included, which is an int&, so that load can hand a new depth back. Both return true if they worked. The header only uses the four classes by reference, so it declares them, rather than including their headers, as MapGenerator.h did in Chapter 32.
Writing the File
Add a C++ file called SaveLoad.cpp, and type its includes, the two constants that begin every save file, and an empty namespace, for two helpers:
#include "SaveLoad.h"
#include <fstream> // std::ofstream and std::ifstream
#include "Enemy.h"
#include "Item.h"
#include "Map.h"
#include "Player.h"
// The first word of every save file, and the version of the format that
// follows it. The version goes up whenever the format changes, so that an
// old file is turned away, rather than read wrongly
const std::string SAVE_HEADER = "ROGUE_SDL_SAVE";
constexpr int SAVE_VERSION = 1;
namespace
{
}In the preceding code, <fstream> brings in the file streams from Chapter 24, and the four headers bring in the classes the header only declared. The constant SAVE_HEADER is the first word of every save file, so that load can tell a save file from any other file, and SAVE_VERSION says which version of the format follows it. This is the first.
The map's tiles are written as letters. Add this inside the namespace:
// A tile as one letter: W for wall, F for floor, and S for stairs, as
// a capital if the player has explored it
char encode(const Tile& tile)
{
switch (tile.terrain)
{
case Terrain::Floor:
return tile.explored ? 'F' : 'f';
case Terrain::StairsDown:
return tile.explored ? 'S' : 's';
default:
return tile.explored ? 'W' : 'w';
}
}In the preceding code, encode turns a tile into one letter: W for a wall, F for a floor, and S for stairs. Each is a capital if the player has explored the tile, and small if not, so one letter holds both of the tile's facts that need saving. The ternary operator picks the capital or the small letter. Then add the opposite below it, with a blank line in between:
// The tile a letter stands for. Anything but F or S is wall
Tile decode(char letter)
{
Tile tile;
tile.explored = letter >= 'A' && letter <= 'Z';
if (letter == 'F' || letter == 'f')
tile.terrain = Terrain::Floor;
else if (letter == 'S' || letter == 's')
tile.terrain = Terrain::StairsDown;
return tile;
}In the preceding code, decode starts with a new Tile, which is an unexplored wall, as the member initializers in Map.h make it. A letter from A to Z is a capital, so the tile is explored. Then F or f makes it floor, and S or s makes it stairs. Anything else stays a wall, so a letter that has been mistyped can't make a hole in the dungeon.
Next, the namespace that the header promised. Add an empty one below the unnamed namespace, with a blank line in between:
namespace SaveLoad
{
}In the preceding code, the SaveLoad namespace will hold save and load. Add the first part of save inside it:
// Writes everything the game needs to carry on later: the depth, the
// player, the monsters, the treasure, and the map. Returns false if the
// file couldn't be written
bool save(const std::string& path, const Map& map, const Player& player,
const std::vector<Enemy>& enemies,
const std::vector<Item>& items, int depth)
{
std::ofstream file(path);
file << SAVE_HEADER << " " << SAVE_VERSION << "\n";
file << "DEPTH " << depth << "\n";
Point at = player.getPosition();
file << "PLAYER " << at.x << " " << at.y << " " << player.getHp()
<< " " << player.getGold() << " " << player.getPotions() << "\n";In the preceding code, making the std::ofstream opens the file for writing, and makes it, or empties it if it's already there. Then << writes to it, as it writes to std::cout, a line at a time, each ending in "\n". The first line is the header and the version, with a space between them, then comes the depth, and then the player, with its five numbers in a row. The at variable holds the player's cell, and it gets reused next.
Next, the monsters and the treasure. Add these below the player's line, with a blank line in between:
for (const Enemy& enemy : enemies)
{
at = enemy.getPosition();
file << "MONSTER " << static_cast<int>(enemy.getKind()) << " "
<< at.x << " " << at.y << " " << enemy.getHp() << "\n";
}
for (const Item& item : items)
{
at = item.getPosition();
file << "ITEM " << static_cast<int>(item.getKind()) << " "
<< at.x << " " << at.y << " " << item.getAmount() << "\n";
}In the preceding code, every monster gets a line, and so does every item, each with its kind as a number, then its cell, then its health or its amount. The static_cast<int> is what turns a kind into its number, since an enum class won't turn into one on its own.
Last, the map. Add this below the treasure's loop, with a blank line in between, to finish save:
// The map last, a row of letters to a line
file << "MAP\n";
for (int y = 0; y < MAP_H; ++y)
{
for (int x = 0; x < MAP_W; ++x)
file << encode(map.at({ x, y }));
file << "\n";
}
// Closing the file finishes the writing, so any problem shows now
file.close();
return !file.fail();
}In the preceding code, the word MAP gets a line of its own, and then every row of the map gets a line, with a letter for each of its cells. The map goes last, after that word, so that load can read everything before it a line at a time, by the word at its start, until the word MAP says that the rows of letters are coming.
When a file stream is destroyed, it closes its file, as Chapter 24 showed, but that would be too late to find out whether the writing worked. So save closes the file itself. A write that fails, because the disk is full, say, leaves the stream failed, and fail says so, so save returns true only if nothing went wrong.
Checkpoint: Click in SaveLoad.cpp, and press Ctrl+F7. It compiles, even though load isn't written yet, since the header declares it.
Reading It Back
Now load, which reads a file back, and checks everything as it goes. Add the first part below save, with a blank line in between:
// Reads a saved game back into the game's variables. If anything in
// the file is missing or wrong, it returns false, and leaves the game
// exactly as it was
bool load(const std::string& path, Map& map, Player& player,
std::vector<Enemy>& enemies, std::vector<Item>& items,
int& depth)
{
std::ifstream file(path);
std::string word;
int version = 0;
file >> word >> version;
if (word != SAVE_HEADER || version != SAVE_VERSION)
return false;In the preceding code, making the std::ifstream opens the file for reading, just as making the std::ofstream did for writing. If there's no file, the stream is failed from the start, as Chapter 24 said, and every read from it fails. Then >> reads the first word and the number after it. If the word isn't the header, or the number isn't this version, it isn't a save file this game can read, and load returns false, having changed nothing. A missing file is caught here too, since reading from it leaves word empty.
Everything else goes into new variables first. Add these below the check, with a blank line in between:
// Read everything into new variables first
int newDepth = 1;
Player newPlayer;
std::vector<Enemy> newEnemies;
std::vector<Item> newItems;
Map newMap;In the preceding code, there's a new variable for each of the five things load replaces, each starting as a new game would have it: depth 1, a fresh player, no monsters, no treasure, and a map of unexplored wall. Nothing that happens to these can harm the game.
Next, the lines before the map. Add the start of the loop that reads them below the new variables, with a blank line in between:
// A line at a time, each starting with a word that says what it is,
// until the map
while (file >> word && word != "MAP")
{
Point at;
if (word == "DEPTH")
{
file >> newDepth;
}
else if (word == "PLAYER")
{
int hp = 0;
int gold = 0;
int potions = 0;
file >> at.x >> at.y >> hp >> gold >> potions;
newPlayer.setPosition(at);
newPlayer.setHp(hp);
newPlayer.setGold(gold);
newPlayer.setPotions(potions);
}In the preceding code, each time around, the loop reads a line's first word, and stops when there's nothing left to read, or when the word is MAP, since the map comes next. The at variable is new each time around, at (0, 0). A DEPTH line's number goes into newDepth. A PLAYER line's five numbers go into the new player, through the setters that were added for this.
Then the monsters and the treasure. Add these below the PLAYER line's closing brace:
else if (word == "MONSTER")
{
int kind = 0;
int hp = 0;
file >> kind >> at.x >> at.y >> hp;
if (kind < 0 || kind >= MONSTER_KINDS)
return false;
Enemy enemy(static_cast<MonsterKind>(kind), at);
enemy.setHp(hp);
newEnemies.push_back(enemy);
}
else if (word == "ITEM")
{
int kind = 0;
int amount = 0;
file >> kind >> at.x >> at.y >> amount;
if (kind < 0 || kind >= ITEM_KINDS)
return false;
newItems.push_back(Item(static_cast<ItemKind>(kind), at,
amount));
}In the preceding code, a MONSTER line's kind is checked before anything else: it must be at least 0, and less than MONSTER_KINDS, or load gives up, since a kind outside the table would read past its end. Only then does static_cast turn the number back into a MonsterKind, to make the monster, which gets its health from the file, and joins the new monsters. An ITEM line does the same for the treasure, with ITEM_KINDS.
Then add these below the ITEM line's closing brace, to finish the loop:
else
{
return false; // a word that has no business here
}
// A place outside the map would crash the game when it's drawn
if (!newMap.isInside(at))
return false;
}In the preceding code, any other word means the file is wrong, so load gives up. And every line that has a cell must have one that's on the map. A monster outside the map wouldn't do any harm until the game drew it, and then it would stop the game with a debug assertion, as Chapter 31's out-of-range vector did.
Now the map itself. Add this below the loop, with a blank line in between:
// The map, which must be a full MAP_W letters by MAP_H lines
for (int y = 0; y < MAP_H; ++y)
{
std::string row;
file >> row;
if (static_cast<int>(row.size()) != MAP_W)
return false;
for (int x = 0; x < MAP_W; ++x)
newMap.at({ x, y }) = decode(row[x]);
}In the preceding code, each row of the map is read as one word, since it has no spaces in it, and it must be exactly MAP_W letters long, or load gives up. That catches a file that ends partway through the map, too, since a read that finds nothing leaves row empty. Each letter is then decoded into its tile.
Everything has been read, and nothing was wrong. Add these below the map's loop, with a blank line in between, to finish load:
// The whole file was good, so now the game can have it
map = newMap;
player = newPlayer;
enemies = newEnemies;
items = newItems;
depth = newDepth;
return true;
}In the preceding code, the five new values are copied into the game's own variables, which load has by reference, and it returns true. This is the only place where the game changes, and it's only reached when the whole file has been read, and checked, which is what makes loading all or nothing.
Checkpoint: Click in SaveLoad.cpp, and press Ctrl+F7 again. The whole file compiles.
F5 and F9
Last, the game's side of it. In Game.h, add these below takeStairs’s declaration:
void saveGame();
void loadGame();In the preceding code, saveGame and loadGame are what the two keys do. Then, in Game.cpp, add this below #include "MapGenerator.h":
#include "SaveLoad.h"In the preceding code, SaveLoad.h brings in the two functions. Then add the save file's name below FONT_SIZE, with a blank line in between:
// The save file. It goes in the working directory, which is the project
// folder when the game runs from Visual Studio
const std::string SAVE_PATH = "rogue_save.txt";In the preceding code, SAVE_PATH is a relative path, like the font's, so the file goes in the working directory, which is the project folder when you run the game from Visual Studio. You'll find it beside your .cpp files, once you've saved. An installed game would save in the folder that SDL_GetPrefPath gives it, as Chapter 24 explained, but while you're making the game, the project folder is the easiest place to find the file, and read it.
Next, the keys. In handleKey, add these above case SDLK_ESCAPE::
case SDLK_F5:
saveGame();
return;
case SDLK_F9:
loadGame();
return;In the preceding code, F5 saves and F9 loads, and each ends with return, rather than break, so that neither of them is a move, and neither ends a turn. Saving and loading are outside the game's time, and a monster shouldn't get a free hit because you saved.
Then add the two functions below takeStairs, with a blank line in between:
// Saves the game, and says whether it worked. Saving doesn't take a turn
void Game::saveGame()
{
if (SaveLoad::save(SAVE_PATH, map_, player_, enemies_, items_, depth_))
hud_.addMessage("Game saved.");
else
hud_.addMessage("The game couldn't be saved.");
}
// Loads the saved game in place of this one, if there's one to load
void Game::loadGame()
{
if (!SaveLoad::load(SAVE_PATH, map_, player_, enemies_, items_, depth_))
{
hud_.addMessage("There's no saved game, or it couldn't be read.");
return;
}
FOV::compute(map_, player_.getPosition(), SIGHT_RADIUS);
hud_.addMessage("Game loaded.");
}In the preceding code, saveGame hands save everything it needs, and the HUD says whether it worked. The loadGame function does the same with load, and if it fails, the HUD says so, and the game carries on untouched. If it works, one thing is left to do: the loaded map knows what's explored, but not what's visible, since the file doesn't hold that, so the field of view is worked out again, from where the player now stands.
F5 now does two jobs, depending on which window you pressed it in. In Visual Studio, it starts the game, and in the game's window, it saves. So click in the game's window before you press F5 or F9, and if you ever want to stop the game from Visual Studio, press Shift+F5.
Last, the HUD should mention the two new keys. In HUD.cpp, find these lines in draw:
std::string help = "Arrows or WASD: move and attack H: drink a potion"
" .: take the stairs down Esc: quit";And change them to this:
std::string help = "Arrows or WASD: move and attack H: drink a potion"
" .: go down F5: save F9: load Esc: quit";In the preceding code, the stairs' key has a shorter description, to make room on the row for F5 and F9.
That's the whole of Part 4: four new files, and every change to the old ones typed.
Checkpoint: Press F5. Walk a few steps, and press F5 again, in the game's window this time, and the HUD says "Game saved." Walk somewhere else, and press F9. You're back where you were when you saved, with the same health, the same monsters, and the same map, and the HUD says "Game loaded.", as in Figure 33.9. Look in your project folder, and there's rogue_save.txt, which you can open in Visual Studio to read.
Rogue itself was stricter. Its guide warned that it deleted a save file the moment a restored game began, so that nobody could save just before a risky fight, and restore the save if they lost. Players still argue about it, and call the habit of reloading after every mistake save scumming. Rogue SDL keeps its file, so F9 works as often as you like, even after a death, once R has started a new game. How often you use it is up to you.
And to see what happens when there's nothing to load, close the game, delete rogue_save.txt, and run it again. Press F9, and the HUD says "There's no saved game, or it couldn't be read.", and the game carries on as if you'd never pressed it.
The Complete Files
Here are the fourteen files that are new or changed, in full, exactly as they are in the repository's SDL3 Projects/Rogue SDL Part 4. The other twelve, main.cpp, Entity.h, Entity.cpp, GlyphCache.h, GlyphCache.cpp, Map.h, Map.cpp, FOV.h, FOV.cpp, MapGenerator.h, MapGenerator.cpp, and HUD.h, are just as they were at the end of Chapter 32. First, Common.h:
#pragma once
#include <SDL3/SDL.h>
#include <functional> // std::hash
// A place on the map, counted in cells, not pixels
struct Point
{
int x = 0;
int y = 0;
bool operator==(const Point& other) const = default;
};
// The map is a grid of square cells, CELL_PX pixels across, MAP_W cells
// wide and MAP_H cells tall. Below it are HUD_ROWS rows of text, and the
// window is exactly the size of both: 1280 by 720 pixels
constexpr int CELL_PX = 16;
constexpr int MAP_W = 80;
constexpr int MAP_H = 40;
constexpr int HUD_ROWS = 5;
constexpr int WINDOW_W = MAP_W * CELL_PX;
constexpr int WINDOW_H = (MAP_H + HUD_ROWS) * CELL_PX;
// How to hash a Point, so that it can be a key in an unordered_map. Each
// cell gets its own number: the same number as its tile's index in the
// Map's vector
template <>
struct std::hash<Point>
{
size_t operator()(const Point& point) const
{
return point.y * MAP_W + point.x;
}
};
// How far the player can see, in cells
constexpr int SIGHT_RADIUS = 8;
// Every color in the game, in one place
namespace Palette
{
constexpr SDL_Color BACKGROUND = { 10, 10, 16, 255 };
constexpr SDL_Color WALL = { 180, 160, 110, 255 };
constexpr SDL_Color FLOOR = { 110, 110, 130, 255 };
constexpr SDL_Color PLAYER = { 255, 255, 255, 255 };
// The stairs down
constexpr SDL_Color STAIRS = { 240, 220, 80, 255 };
// The colors of things remembered, but out of sight
constexpr SDL_Color WALL_REMEMBERED = { 60, 55, 40, 255 };
constexpr SDL_Color FLOOR_REMEMBERED = { 40, 40, 55, 255 };
constexpr SDL_Color STAIRS_REMEMBERED = { 110, 100, 40, 255 };
// The HUD's text
constexpr SDL_Color TEXT = { 200, 200, 210, 255 };
constexpr SDL_Color TEXT_DIM = { 100, 100, 110, 255 };
constexpr SDL_Color TEXT_BAD = { 240, 80, 80, 255 };
// Monsters and treasure
constexpr SDL_Color RAT = { 180, 180, 100, 255 };
constexpr SDL_Color GOBLIN = { 100, 220, 100, 255 };
constexpr SDL_Color ORC = { 220, 100, 100, 255 };
constexpr SDL_Color POTION = { 220, 80, 220, 255 };
constexpr SDL_Color GOLD = { 240, 220, 80, 255 };
}In the preceding code, a Point can now be hashed, so that it can be a key in an unordered map.
Next, AStar.h:
#pragma once
#include <vector> // std::vector, for the path
#include "Common.h"
class Map;
// A*, the shortest way from one cell to another, around the walls
namespace AStar
{
std::vector<Point> findPath(const Map& map, Point from, Point to);
}In the preceding code, the AStar namespace declares findPath, the one thing A* offers.
Then AStar.cpp:
#include "AStar.h"
#include <algorithm> // std::reverse
#include <cstdlib> // std::abs
#include <functional> // std::greater
#include <queue> // std::priority_queue
#include <unordered_map> // std::unordered_map
#include "Map.h"
namespace
{
// A cell waiting to be looked at, and a guess at the whole length of a
// path through it: the steps it took to get there, plus the steps
// still to go, if there were no walls in the way
struct Candidate
{
Point cell;
int guess;
// So that std::greater can say which of two is farther from the
// front of the queue
bool operator>(const Candidate& other) const
{
return guess > other.guess;
}
};
// The steps from one cell to another, if there were no walls in the
// way: across, plus down
int distance(Point a, Point b)
{
return std::abs(a.x - b.x) + std::abs(a.y - b.y);
}
// The four cells next to a cell: up, down, left, and right
constexpr Point DIRECTIONS[] = { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } };
}
namespace AStar
{
// The cells to step through to get from one cell to another, in order,
// not counting the first cell, but counting the last. It's empty if
// there's no way through
std::vector<Point> findPath(const Map& map, Point from, Point to)
{
// The cells still to look at, the one with the smallest guess
// first, and for every cell reached so far, the fewest steps it
// takes to get there, and the cell it's reached from
std::priority_queue<Candidate, std::vector<Candidate>,
std::greater<Candidate>> waiting;
std::unordered_map<Point, int> steps;
std::unordered_map<Point, Point> cameFrom;
waiting.push({ from, distance(from, to) });
steps[from] = 0;
while (!waiting.empty())
{
Point cell = waiting.top().cell;
waiting.pop();
if (cell == to)
break;
// Reach each open neighbor in one more step, unless it's
// already been reached in as few
for (Point direction : DIRECTIONS)
{
Point next = { cell.x + direction.x, cell.y + direction.y };
if (map.isBlocked(next))
continue;
int nextSteps = steps[cell] + 1;
if (!steps.contains(next) || nextSteps < steps[next])
{
steps[next] = nextSteps;
cameFrom[next] = cell;
waiting.push({ next, nextSteps + distance(next, to) });
}
}
}
// Follow the trail back from the end to the start, then turn it
// around
std::vector<Point> path;
if (!cameFrom.contains(to))
return path;
for (Point cell = to; cell != from; cell = cameFrom[cell])
path.push_back(cell);
std::reverse(path.begin(), path.end());
return path;
}
}In the preceding code, findPath takes the candidate with the smallest guess, over and over, until it reaches its goal, and then follows the trail back.
Then Enemy.h:
#pragma once
#include "Entity.h"
// The kinds of monster, from the weakest to the strongest
enum class MonsterKind
{
Rat,
Goblin,
Orc
};
constexpr int MONSTER_KINDS = 3; // how many kinds there are
// What every monster of one kind is like
struct MonsterStats
{
const char* name;
char glyph;
SDL_Color color;
int maxHp;
int attack; // the damage it does with each hit
int sight; // how far away it can notice the player, in cells
};
const MonsterStats& statsOf(MonsterKind kind);
// A monster, of one of the kinds above
class Enemy : public Entity
{
public:
Enemy(MonsterKind kind, Point position);
MonsterKind getKind() const;
const MonsterStats& getStats() const;
int getHp() const;
void setHp(int hp);
bool isAlive() const;
void takeDamage(int amount);
bool isHunting() const;
Point getLastSeen() const;
void hunt(Point lastSeen);
void giveUp();
private:
MonsterKind kind_;
int hp_;
bool hunting_ = false; // true once it has seen the player
Point lastSeen_; // where it saw the player last
};In the preceding code, a monster knows its kind, whether it's hunting, and where it saw the player last.
Then Enemy.cpp:
#include "Enemy.h"
#include <iterator> // std::size
namespace
{
// One for each kind of monster, in the same order as the enum
constexpr MonsterStats MONSTER_STATS[] = {
{ "rat", 'r', Palette::RAT, 4, 2, 6 },
{ "goblin", 'g', Palette::GOBLIN, 8, 3, 7 },
{ "orc", 'o', Palette::ORC, 14, 5, 8 }
};
static_assert(std::size(MONSTER_STATS) == MONSTER_KINDS,
"There must be one MonsterStats for each MonsterKind");
}
const MonsterStats& statsOf(MonsterKind kind)
{
return MONSTER_STATS[static_cast<int>(kind)];
}
Enemy::Enemy(MonsterKind kind, Point position)
: Entity(position, statsOf(kind).glyph, statsOf(kind).color),
kind_(kind),
hp_(statsOf(kind).maxHp)
{
}
MonsterKind Enemy::getKind() const
{
return kind_;
}
const MonsterStats& Enemy::getStats() const
{
return statsOf(kind_);
}
int Enemy::getHp() const
{
return hp_;
}
void Enemy::setHp(int hp)
{
hp_ = hp;
}
bool Enemy::isAlive() const
{
return hp_ > 0;
}
void Enemy::takeDamage(int amount)
{
hp_ -= amount;
}
bool Enemy::isHunting() const
{
return hunting_;
}
Point Enemy::getLastSeen() const
{
return lastSeen_;
}
// Starts hunting the player, or keeps on hunting, with a fresh sighting
void Enemy::hunt(Point lastSeen)
{
hunting_ = true;
lastSeen_ = lastSeen;
}
// Loses the trail, and waits where it is
void Enemy::giveUp()
{
hunting_ = false;
}In the preceding code, the table is checked against MONSTER_KINDS as the program builds, and hunt and giveUp keep a monster's memory.
Then Item.h:
#pragma once
#include "Entity.h"
// The kinds of treasure
enum class ItemKind
{
Potion,
Gold
};
constexpr int ITEM_KINDS = 2; // how many kinds there are
// What every item of one kind is like
struct ItemStats
{
const char* name;
char glyph;
SDL_Color color;
};
const ItemStats& statsOf(ItemKind kind);
// Something lying on the floor, waiting to be picked up
class Item : public Entity
{
public:
Item(ItemKind kind, Point position, int amount = 1);
ItemKind getKind() const;
int getAmount() const;
private:
ItemKind kind_;
int amount_; // how many coins, for gold
};In the preceding code, ITEM_KINDS counts the kinds of treasure.
Then Item.cpp:
#include "Item.h"
#include <iterator> // std::size
namespace
{
// One for each kind of item, in the same order as the enum
constexpr ItemStats ITEM_STATS[] = {
{ "potion", '!', Palette::POTION },
{ "gold", '$', Palette::GOLD }
};
static_assert(std::size(ITEM_STATS) == ITEM_KINDS,
"There must be one ItemStats for each ItemKind");
}
const ItemStats& statsOf(ItemKind kind)
{
return ITEM_STATS[static_cast<int>(kind)];
}
Item::Item(ItemKind kind, Point position, int amount)
: Entity(position, statsOf(kind).glyph, statsOf(kind).color),
kind_(kind),
amount_(amount)
{
}
ItemKind Item::getKind() const
{
return kind_;
}
int Item::getAmount() const
{
return amount_;
}In the preceding code, the treasure's table is checked against ITEM_KINDS, as the monsters' is.
Then Player.h:
#pragma once
#include "Entity.h"
class Map;
constexpr int PLAYER_MAX_HP = 20; // the player's health, when it's full
constexpr int PLAYER_ATTACK = 4; // the damage the player does with a hit
constexpr int POTION_HEAL = 8; // the health a potion gives back
// You: the @
class Player : public Entity
{
public:
Player();
bool tryMove(int dx, int dy, const Map& map);
int getHp() const;
void setHp(int hp);
int getAttack() const;
int getGold() const;
void setGold(int gold);
int getPotions() const;
void setPotions(int potions);
bool isAlive() const;
void takeDamage(int amount);
void addGold(int amount);
void addPotion();
bool drinkPotion();
void reset();
private:
int hp_ = PLAYER_MAX_HP;
int gold_ = 0;
int potions_ = 0;
};In the preceding code, each of the player's numbers can now be set, as well as read.
Then Player.cpp:
#include "Player.h"
#include <algorithm> // std::min and std::max
#include "Map.h"
Player::Player()
: Entity({ 0, 0 }, '@', Palette::PLAYER)
{
}
// Steps one cell, unless the way is blocked. Returns true if the player
// moved
bool Player::tryMove(int dx, int dy, const Map& map)
{
Point next = { getPosition().x + dx, getPosition().y + dy };
if (map.isBlocked(next))
return false;
setPosition(next);
return true;
}
int Player::getHp() const
{
return hp_;
}
void Player::setHp(int hp)
{
hp_ = hp;
}
int Player::getAttack() const
{
return PLAYER_ATTACK;
}
int Player::getGold() const
{
return gold_;
}
void Player::setGold(int gold)
{
gold_ = gold;
}
int Player::getPotions() const
{
return potions_;
}
void Player::setPotions(int potions)
{
potions_ = potions;
}
bool Player::isAlive() const
{
return hp_ > 0;
}
// Never below zero, so that the HUD never shows a negative number
void Player::takeDamage(int amount)
{
hp_ = std::max(hp_ - amount, 0);
}
void Player::addGold(int amount)
{
gold_ += amount;
}
void Player::addPotion()
{
++potions_;
}
// Drinks a potion, if there's one to drink, and heals, though never past
// full health. Returns true if a potion was drunk
bool Player::drinkPotion()
{
if (potions_ == 0)
return false;
--potions_;
hp_ = std::min(hp_ + POTION_HEAL, PLAYER_MAX_HP);
return true;
}
// Everything back to how it was at the start of the game
void Player::reset()
{
hp_ = PLAYER_MAX_HP;
gold_ = 0;
potions_ = 0;
}In the preceding code, the three setters sit beside the getters they belong with.
Then SaveLoad.h:
#pragma once
#include <string> // std::string, for the file's path
#include <vector> // std::vector, for the monsters and the treasure
class Enemy;
class Item;
class Map;
class Player;
// Saving the game to a text file, and loading it back
namespace SaveLoad
{
bool save(const std::string& path, const Map& map, const Player& player,
const std::vector<Enemy>& enemies,
const std::vector<Item>& items, int depth);
bool load(const std::string& path, Map& map, Player& player,
std::vector<Enemy>& enemies, std::vector<Item>& items,
int& depth);
}In the preceding code, the SaveLoad namespace declares save and load.
Then SaveLoad.cpp:
#include "SaveLoad.h"
#include <fstream> // std::ofstream and std::ifstream
#include "Enemy.h"
#include "Item.h"
#include "Map.h"
#include "Player.h"
// The first word of every save file, and the version of the format that
// follows it. The version goes up whenever the format changes, so that an
// old file is turned away, rather than read wrongly
const std::string SAVE_HEADER = "ROGUE_SDL_SAVE";
constexpr int SAVE_VERSION = 1;
namespace
{
// A tile as one letter: W for wall, F for floor, and S for stairs, as
// a capital if the player has explored it
char encode(const Tile& tile)
{
switch (tile.terrain)
{
case Terrain::Floor:
return tile.explored ? 'F' : 'f';
case Terrain::StairsDown:
return tile.explored ? 'S' : 's';
default:
return tile.explored ? 'W' : 'w';
}
}
// The tile a letter stands for. Anything but F or S is wall
Tile decode(char letter)
{
Tile tile;
tile.explored = letter >= 'A' && letter <= 'Z';
if (letter == 'F' || letter == 'f')
tile.terrain = Terrain::Floor;
else if (letter == 'S' || letter == 's')
tile.terrain = Terrain::StairsDown;
return tile;
}
}
namespace SaveLoad
{
// Writes everything the game needs to carry on later: the depth, the
// player, the monsters, the treasure, and the map. Returns false if the
// file couldn't be written
bool save(const std::string& path, const Map& map, const Player& player,
const std::vector<Enemy>& enemies,
const std::vector<Item>& items, int depth)
{
std::ofstream file(path);
file << SAVE_HEADER << " " << SAVE_VERSION << "\n";
file << "DEPTH " << depth << "\n";
Point at = player.getPosition();
file << "PLAYER " << at.x << " " << at.y << " " << player.getHp()
<< " " << player.getGold() << " " << player.getPotions() << "\n";
for (const Enemy& enemy : enemies)
{
at = enemy.getPosition();
file << "MONSTER " << static_cast<int>(enemy.getKind()) << " "
<< at.x << " " << at.y << " " << enemy.getHp() << "\n";
}
for (const Item& item : items)
{
at = item.getPosition();
file << "ITEM " << static_cast<int>(item.getKind()) << " "
<< at.x << " " << at.y << " " << item.getAmount() << "\n";
}
// The map last, a row of letters to a line
file << "MAP\n";
for (int y = 0; y < MAP_H; ++y)
{
for (int x = 0; x < MAP_W; ++x)
file << encode(map.at({ x, y }));
file << "\n";
}
// Closing the file finishes the writing, so any problem shows now
file.close();
return !file.fail();
}
// Reads a saved game back into the game's variables. If anything in
// the file is missing or wrong, it returns false, and leaves the game
// exactly as it was
bool load(const std::string& path, Map& map, Player& player,
std::vector<Enemy>& enemies, std::vector<Item>& items,
int& depth)
{
std::ifstream file(path);
std::string word;
int version = 0;
file >> word >> version;
if (word != SAVE_HEADER || version != SAVE_VERSION)
return false;
// Read everything into new variables first
int newDepth = 1;
Player newPlayer;
std::vector<Enemy> newEnemies;
std::vector<Item> newItems;
Map newMap;
// A line at a time, each starting with a word that says what it is,
// until the map
while (file >> word && word != "MAP")
{
Point at;
if (word == "DEPTH")
{
file >> newDepth;
}
else if (word == "PLAYER")
{
int hp = 0;
int gold = 0;
int potions = 0;
file >> at.x >> at.y >> hp >> gold >> potions;
newPlayer.setPosition(at);
newPlayer.setHp(hp);
newPlayer.setGold(gold);
newPlayer.setPotions(potions);
}
else if (word == "MONSTER")
{
int kind = 0;
int hp = 0;
file >> kind >> at.x >> at.y >> hp;
if (kind < 0 || kind >= MONSTER_KINDS)
return false;
Enemy enemy(static_cast<MonsterKind>(kind), at);
enemy.setHp(hp);
newEnemies.push_back(enemy);
}
else if (word == "ITEM")
{
int kind = 0;
int amount = 0;
file >> kind >> at.x >> at.y >> amount;
if (kind < 0 || kind >= ITEM_KINDS)
return false;
newItems.push_back(Item(static_cast<ItemKind>(kind), at,
amount));
}
else
{
return false; // a word that has no business here
}
// A place outside the map would crash the game when it's drawn
if (!newMap.isInside(at))
return false;
}
// The map, which must be a full MAP_W letters by MAP_H lines
for (int y = 0; y < MAP_H; ++y)
{
std::string row;
file >> row;
if (static_cast<int>(row.size()) != MAP_W)
return false;
for (int x = 0; x < MAP_W; ++x)
newMap.at({ x, y }) = decode(row[x]);
}
// The whole file was good, so now the game can have it
map = newMap;
player = newPlayer;
enemies = newEnemies;
items = newItems;
depth = newDepth;
return true;
}
}In the preceding code, save writes the game a line at a time, and load reads it back into new variables, and only hands them over if the whole file was good.
Then HUD.cpp:
#include "HUD.h"
#include "Common.h"
#include "GlyphCache.h"
#include "Player.h"
// The first row is how things stand, and the second is the keys, so the
// messages get the rows left over
constexpr int MESSAGE_ROWS = HUD_ROWS - 2;
// Adds a message at the bottom, and drops the oldest from the top when
// there are too many to show
void HUD::addMessage(const std::string& message)
{
messages_.push_back(message);
if (messages_.size() > MESSAGE_ROWS)
messages_.pop_front();
}
void HUD::clear()
{
messages_.clear();
}
void HUD::draw(SDL_Renderer* renderer, const GlyphCache& glyphs,
const Player& player, int depth, bool gameOver) const
{
int row = MAP_H; // the first row below the map
std::string status =
"HP " + std::to_string(player.getHp()) + "/" +
std::to_string(PLAYER_MAX_HP) +
" Gold " + std::to_string(player.getGold()) +
" Potions " + std::to_string(player.getPotions()) +
" Depth " + std::to_string(depth);
glyphs.drawText(renderer, status, { 1, row }, Palette::TEXT);
// The keys, or once the player has died, what to do about it
std::string help = "Arrows or WASD: move and attack H: drink a potion"
" .: go down F5: save F9: load Esc: quit";
SDL_Color helpColor = Palette::TEXT_DIM;
if (gameOver)
{
help = "You have died. Press R to play again, or Esc to quit.";
helpColor = Palette::TEXT_BAD;
}
glyphs.drawText(renderer, help, { 1, row + 1 }, helpColor);
// The newest message is bright, and the older ones are dim
for (size_t i = 0; i < messages_.size(); ++i)
{
bool newest = i + 1 == messages_.size();
glyphs.drawText(renderer, messages_[i],
{ 1, row + 2 + static_cast<int>(i) },
newest ? Palette::TEXT : Palette::TEXT_DIM);
}
}In the preceding code, the second row has F5 and F9 with the other keys.
Then Game.h:
#pragma once
#include <SDL3/SDL.h>
#include <vector> // std::vector, for the monsters and the treasure
#include "Enemy.h"
#include "GlyphCache.h"
#include "HUD.h"
#include "Item.h"
#include "Map.h"
#include "Player.h"
// The whole game. It owns the glyphs, the map, the player, the monsters,
// the treasure, and the HUD, and runs the loop that waits for a key, acts
// on it, and draws what happened
class Game
{
public:
Game(SDL_Renderer* renderer);
bool isLoaded() const;
void run();
private:
void newGame();
void newLevel();
void handleKey(SDL_Keycode key);
void moveOrAttack(int dx, int dy);
void attack(Enemy& enemy);
void pickUp();
void drinkPotion();
void takeStairs();
void saveGame();
void loadGame();
void endTurn();
void monsterTurn(Enemy& enemy);
bool notices(const Enemy& enemy) const;
Enemy* enemyAt(Point cell);
Item* itemAt(Point cell);
void draw() const;
SDL_Renderer* renderer_;
GlyphCache glyphs_;
Map map_;
Player player_;
std::vector<Enemy> enemies_;
std::vector<Item> items_;
HUD hud_;
int depth_ = 1; // how many levels down the player is
bool gameOver_ = false; // true once the player has died
bool running_ = true;
bool dirty_ = true; // true when the window needs drawing again
};In the preceding code, the game has two more functions, one for each new key.
And last, Game.cpp:
#include "Game.h"
#include <cstdlib> // std::abs
#include <string> // std::string and std::to_string
#include "AStar.h"
#include "FOV.h"
#include "MapGenerator.h"
#include "SaveLoad.h"
// The font every character is drawn in, and its size
const std::string FONT_PATH = "assets/RobotoMono-Light.ttf";
constexpr float FONT_SIZE = 18.0f;
// The save file. It goes in the working directory, which is the project
// folder when the game runs from Visual Studio
const std::string SAVE_PATH = "rogue_save.txt";
Game::Game(SDL_Renderer* renderer)
: renderer_(renderer), glyphs_(renderer, FONT_PATH, FONT_SIZE)
{
newGame();
}
bool Game::isLoaded() const
{
return glyphs_.isLoaded();
}
// Sleeps until something happens, deals with it, and draws the window again
// if anything changed
void Game::run()
{
while (running_)
{
if (dirty_)
{
draw();
dirty_ = false;
}
SDL_Event event;
if (!SDL_WaitEvent(&event))
break;
switch (event.type)
{
case SDL_EVENT_QUIT:
running_ = false;
break;
case SDL_EVENT_WINDOW_EXPOSED:
dirty_ = true;
break;
case SDL_EVENT_KEY_DOWN:
handleKey(event.key.key);
dirty_ = true;
break;
}
}
}
// Starts again from the top, with a fresh player at depth 1
void Game::newGame()
{
depth_ = 1;
gameOver_ = false;
player_.reset();
hud_.clear();
newLevel();
hud_.addMessage("Welcome to Rogue SDL. Find the stairs down: >");
}
// Builds a new level, with its monsters and treasure, puts the player at
// its start, and looks around
void Game::newLevel()
{
enemies_.clear();
items_.clear();
MapGenerator generator(map_);
player_.setPosition(generator.generate(depth_, enemies_, items_));
FOV::compute(map_, player_.getPosition(), SIGHT_RADIUS);
}
// Every key press is one action, or none
void Game::handleKey(SDL_Keycode key)
{
// Once the player has died, only two keys do anything
if (gameOver_)
{
if (key == SDLK_R)
newGame();
else if (key == SDLK_ESCAPE)
running_ = false;
return;
}
int dx = 0;
int dy = 0;
switch (key)
{
case SDLK_UP:
case SDLK_W:
dy = -1;
break;
case SDLK_DOWN:
case SDLK_S:
dy = 1;
break;
case SDLK_LEFT:
case SDLK_A:
dx = -1;
break;
case SDLK_RIGHT:
case SDLK_D:
dx = 1;
break;
case SDLK_H:
drinkPotion();
return;
case SDLK_PERIOD:
takeStairs();
return;
case SDLK_F5:
saveGame();
return;
case SDLK_F9:
loadGame();
return;
case SDLK_ESCAPE:
running_ = false;
return;
default:
return;
}
moveOrAttack(dx, dy);
}
// Attacks the monster in the way, if there is one. Otherwise, steps, looks
// around, and picks up anything lying there. Either way, it's a turn
void Game::moveOrAttack(int dx, int dy)
{
Point next = { player_.getPosition().x + dx,
player_.getPosition().y + dy };
if (Enemy* enemy = enemyAt(next))
{
attack(*enemy);
endTurn();
return;
}
if (player_.tryMove(dx, dy, map_))
{
FOV::compute(map_, player_.getPosition(), SIGHT_RADIUS);
if (map_.at(player_.getPosition()).terrain == Terrain::StairsDown)
hud_.addMessage("There are stairs down here. Press . to go down.");
pickUp();
endTurn();
}
}
// The player hits a monster, which may die
void Game::attack(Enemy& enemy)
{
int damage = player_.getAttack();
enemy.takeDamage(damage);
std::string name = enemy.getStats().name;
if (enemy.isAlive())
{
hud_.addMessage("You hit the " + name + " for " +
std::to_string(damage) + ".");
}
else
{
hud_.addMessage("You kill the " + name + "!");
}
}
// Picks up anything lying where the player stands
void Game::pickUp()
{
Point here = player_.getPosition();
Item* item = itemAt(here);
if (!item)
return;
if (item->getKind() == ItemKind::Gold)
{
player_.addGold(item->getAmount());
hud_.addMessage("You pick up " + std::to_string(item->getAmount()) +
" gold.");
}
else
{
player_.addPotion();
hud_.addMessage("You pick up a potion. Press H to drink it.");
}
// It's the player's now, so it isn't lying on the floor anymore
std::erase_if(items_, [here](const Item& lying)
{
return lying.getPosition() == here;
});
}
// Drinking a potion takes a turn, but trying to drink one you haven't got
// doesn't
void Game::drinkPotion()
{
if (!player_.drinkPotion())
{
hud_.addMessage("You have no potions.");
return;
}
hud_.addMessage("You drink a potion, and feel better.");
endTurn();
}
// Goes down to a new level, if the player is standing on the stairs
void Game::takeStairs()
{
if (map_.at(player_.getPosition()).terrain != Terrain::StairsDown)
{
hud_.addMessage("There are no stairs here.");
return;
}
++depth_;
newLevel();
hud_.addMessage("You go down the stairs to depth " +
std::to_string(depth_) + ".");
}
// Saves the game, and says whether it worked. Saving doesn't take a turn
void Game::saveGame()
{
if (SaveLoad::save(SAVE_PATH, map_, player_, enemies_, items_, depth_))
hud_.addMessage("Game saved.");
else
hud_.addMessage("The game couldn't be saved.");
}
// Loads the saved game in place of this one, if there's one to load
void Game::loadGame()
{
if (!SaveLoad::load(SAVE_PATH, map_, player_, enemies_, items_, depth_))
{
hud_.addMessage("There's no saved game, or it couldn't be read.");
return;
}
FOV::compute(map_, player_.getPosition(), SIGHT_RADIUS);
hud_.addMessage("Game loaded.");
}
// The player has taken a turn, so now the monsters take theirs. The dead
// are cleared away first
void Game::endTurn()
{
std::erase_if(enemies_, [](const Enemy& enemy)
{
return !enemy.isAlive();
});
for (Enemy& enemy : enemies_)
{
monsterTurn(enemy);
if (!player_.isAlive())
{
gameOver_ = true;
hud_.addMessage("You die.");
return;
}
}
}
// A monster that sees the player hunts them. It attacks if it's next to
// them, and otherwise steps along the shortest path to where it saw them
// last, so that it can follow them around corners
void Game::monsterTurn(Enemy& enemy)
{
if (notices(enemy))
enemy.hunt(player_.getPosition());
if (!enemy.isHunting())
return;
Point from = enemy.getPosition();
Point to = player_.getPosition();
if (std::abs(to.x - from.x) + std::abs(to.y - from.y) == 1)
{
int damage = enemy.getStats().attack;
player_.takeDamage(damage);
hud_.addMessage("The " + std::string(enemy.getStats().name) +
" hits you for " + std::to_string(damage) + ".");
return;
}
// An empty path means it's where it saw the player last, and they're
// gone, or that there's no way there. Either way, it loses the trail
std::vector<Point> path = AStar::findPath(map_, from, enemy.getLastSeen());
if (path.empty())
{
enemy.giveUp();
return;
}
// It waits, if another monster is in the way
if (!enemyAt(path[0]))
enemy.setPosition(path[0]);
}
// A monster notices the player when it stands where the player can see it,
// and the player is within its own sight
bool Game::notices(const Enemy& enemy) const
{
Point from = enemy.getPosition();
Point to = player_.getPosition();
int dx = to.x - from.x;
int dy = to.y - from.y;
int sight = enemy.getStats().sight;
return map_.at(from).visible && dx * dx + dy * dy <= sight * sight;
}
// The monster at a cell, or nullptr if there isn't one. The pointer is
// only good until the vector of monsters next changes
Enemy* Game::enemyAt(Point cell)
{
for (Enemy& enemy : enemies_)
{
if (enemy.getPosition() == cell)
return &enemy;
}
return nullptr;
}
// The item at a cell, or nullptr if there isn't one, with the same warning
Item* Game::itemAt(Point cell)
{
for (Item& item : items_)
{
if (item.getPosition() == cell)
return &item;
}
return nullptr;
}
void Game::draw() const
{
SDL_SetRenderDrawColor(renderer_, Palette::BACKGROUND.r,
Palette::BACKGROUND.g, Palette::BACKGROUND.b, 255);
SDL_RenderClear(renderer_);
map_.draw(renderer_, glyphs_);
// Treasure, then monsters, wherever the player can see them
for (const Item& item : items_)
{
if (map_.at(item.getPosition()).visible)
item.draw(renderer_, glyphs_);
}
for (const Enemy& enemy : enemies_)
{
if (map_.at(enemy.getPosition()).visible)
enemy.draw(renderer_, glyphs_);
}
player_.draw(renderer_, glyphs_);
hud_.draw(renderer_, glyphs_, player_, depth_, gameOver_);
SDL_RenderPresent(renderer_);
}In the preceding code, every monster takes its turn, hunting with A*, and F5 and F9 save and load the game.
Playing the Game
Press F5, and go looking for trouble. The monsters are a different proposition now. A rat that sees you will follow you out of its room, along the corridors, and around every corner, and a goblin or an orc will do the same, with more to hit you with when it catches up. Figure 33.10 shows what happens when three of them see you at once.
The chase has its own rules, and they're worth knowing. A monster that's right behind you can't hit you as long as you keep walking, since every step you take puts you two cells away, and its step only closes the gap to one again. The moment you do anything else, such as drinking a potion, or you walk into a dead end, it bites. So running is a way to lead a monster somewhere, such as into a corridor, where it's the only thing that can reach you, but it isn't a way to escape it.
Save before you take the stairs, since you never know what's at the bottom. And if the dungeon gets the better of you, press R for a new game, and F9 to go back to your save, if you'd rather carry on than start again.
Understanding the Code
Follow one monster through a turn. At the end of your turn, endTurn hands every monster to monsterTurn, whether or not it has noticed you. A monster that notices you now is hunting, and its last sighting is where you stand, while one that isn't hunting does nothing at all.
A hunting monster next to you attacks. Any other asks findPath for the way to its last sighting, and takes the first step, unless another monster is in the way. And if the path is empty, because it's standing where it saw you last, and you've gone, it gives up.
Notice that the monster never needs to be told where you are while it can't see you. It works with what it knows: where it saw you last. That's what makes the hunt feel fair. You can see the same things it can, since it only notices you when you can see it too, and when you slip out of sight, it has to guess, just as you would.
Every hunting monster runs a whole search, every turn, rather than remembering its path from the turn before. That looks wasteful, but the player moves, other monsters move, and the path from last turn might not be the shortest anymore. A fresh search is always right, and it's quick. Even in a Debug build, a search for a path of up to ten steps, which is about as far as a hunting monster usually has to go, takes around three hundredths of a millisecond.
A* itself knows nothing about monsters, players, or turns. It takes a map and two cells, and returns a path. That's why it's in a file of its own, and why the AI exercise can use it for something completely different. The save file works the same way: SaveLoad knows how to write the game's pieces down, and how to read them back, and Game only decides when.
And notice how loading protects the game. The file is read into new variables, every number that could do damage is checked before it's used, and the game's own variables only change on the last few lines of load, once everything is known to be good. A file that's missing, damaged, from another version, or edited by hand can't leave the game half loaded.
Experimenting
A few of these change how A* works, and a couple change your save file. Put the code back afterward, since the next chapter carries on from this one.
- No sense of direction. In
findPath, changedistance(from, to)to0in the firstpush, andnextSteps + distance(next, to)tonextStepsin the second. The guess is now just the steps so far, so A* has become a breadth-first search. The monsters hunt exactly as well as before, since it still finds a shortest path, but it looks at about twice as many cells to do it. On paths this short, you won't notice. - Ghosts. In
findPath, changeif (map.isBlocked(next))toif (!map.isInside(next)). Now A* thinks nothing but the edge of the map is in the way, and a monster that's hunting you takes the straightest way there, through solid rock. A path is only as good as the search's idea of what's blocked. - The whole level hunts you. In
monsterTurn, put//in front ofif (notices(enemy)), so that every monster takes a fresh sighting of you every turn, wherever it is. Every monster on the level comes for you at once, each on its own shortest path. - Edit your save. Save the game, then open
rogue_save.txtin Visual Studio, with File > Open > File. Change the last number on thePLAYERline, which is your potions, to 99, save the file, and press F9 in the game. Or change aMONSTERline's first number to 2 and its last to 14, and meet a full-strength orc on the first level. - Break your save. Delete a letter from one of the map's rows, save the file, and press F9. The HUD says the file couldn't be read, and the game carries on exactly as it was. Press F5 to write a good file again.
Common Errors and Fixes
C2064: term does not evaluate to a function taking 1 arguments, in a file called xhash, with C2056: illegal expression. An unordered map with Point keys can't find a way to hash them. The specialization of std::hash is missing from Common.h, or is somewhere AStar.cpp can't see it. Add it, below WINDOW_H.
C2906: 'std::hash<Point>': explicit specialization requires 'template <>', followed by C2139 and C2079 in a file called xmemory. The template <> line above struct std::hash<Point> is missing. Without it, the compiler doesn't know that this is a version of the standard library's template. Put it back.
C2678: binary '<': no operator found which takes a left-hand operand of type 'const _Ty' (or there is no acceptable conversion), in a file called type_traits. The priority queue has lost its second and third angle-bracket arguments, so it compares candidates with <, which Candidate doesn't have, to put the biggest first. It should be std::priority_queue<Candidate, std::vector<Candidate>, std::greater<Candidate>>.
C2679: binary '<<': no operator found which takes a right-hand operand of type 'MonsterKind' (or there is no acceptable conversion), in SaveLoad.cpp. A kind is being written to the file without static_cast<int>. An enum class never turns into a number on its own, so say so.
C2338: static assertion failed: 'There must be one MonsterStats for each MonsterKind', in Enemy.cpp. A kind has been added to the enum, and MONSTER_KINDS raised to match, but the table has no row for it. Add the row, at the end of the table. If you didn't mean to add a kind, check that MONSTER_KINDS is still 3.
Right after loading, the whole map is dim, and the monsters have vanished. Take one step, and everything is back. The call to FOV::compute in loadGame is missing, so nothing is visible until the player moves. Put it back, before the message.
A monster leaps across the room in a single turn, and lands on top of you. The std::reverse at the end of findPath is missing, so the path starts at its far end, where the player is, and the monster jumps straight there, into the player's cell. Put the std::reverse back, above the last return.
Monsters stop dead the moment you step out of sight, as they did in Part 3. The old if (!notices(enemy)) and its continue are still at the top of the loop in endTurn, so a monster that can't see you never gets a turn to follow you in. Take them out.
AI Exercise (Optional)
A* doesn't care who's asking. If you'd like to put it to work for the player, here's a challenge: a key that walks you to the stairs, the way long-running roguelikes let you travel to a place you've already found. As always, it's optional.
Open your AI chatbot of choice and try a prompt like this:
"I'm writing a roguelike in C++ with SDL 3. The map is a Map of Tiles, each with a Terrain (Wall, Floor, or StairsDown) and bool explored and visible flags, and map.isBlocked(cell) is true for walls. I have A* in a namespace: std::vector<Point> AStar::findPath(const Map& map, Point from, Point to), which returns the cells to step through, not counting the first, and uses map.isBlocked to avoid walls. The monsters use findPath to hunt the player. In my Game class, handleKey(SDL_Keycode key) handles one key press, and moveOrAttack(int dx, int dy) moves the player one cell, and ends the turn, so the monsters move too. I'd like a travel key, T: each press takes the player one step along the shortest path to the stairs down, going only through cells the player has explored. If the stairs haven't been found yet, or a monster is in sight, it should do nothing but show a message. The monsters' paths must stay as they are. Show me every change, with each curly brace on its own line, and explain how the path is kept to explored cells."
Notice what the preceding prompt does. It describes findPath exactly, including what its path leaves out, so the AI can take the first step of it. Asking for each step to go through moveOrAttack means that travel costs turns, as walking does. And it says that the monsters' paths must stay as they are, which rules out the easiest wrong answer: making isBlocked treat unexplored cells as walls, which would stop the monsters from hunting you through the dark.
When the answer comes back, check it against this chapter. How does it keep the path to explored cells: by giving findPath a new parameter, a second function, or something else? Does it find the stairs by looking for StairsDown among the explored tiles only? When it checks for monsters, does it use the same visible flags as the monsters' own notices? And does a press of T that does nothing leave the monsters where they are, rather than giving them a free move?
To try it, explore until you've seen the stairs, wander off, and press T a few times. If the @ walks into the unexplored dark, or stands still while the monsters move, ask the AI why.
Summary
The monsters can find their way. A* searches outward from a monster, taking the most promising cell each time, the one with the smallest guess at a whole path's length, from a priority queue that keeps its smallest candidate on top. It remembers how it reached every cell, in unordered maps keyed by Point, which needed a std::hash of their own, and it follows the trail back to give the shortest path around anything.
The monsters use it to hunt. A monster that sees you remembers where, heads there, and keeps coming around corners and out of sight, until it reaches the last place it saw you and finds you gone. And the game can be saved with F5 and loaded with F9, in a text file that's written a line at a time, and read back all or nothing, with every number that matters checked before it's used, and static_assert making sure that every table has a row for every kind before the program even runs.
Next, in Chapter 34, the game gets louder and brighter. Every hit, kill, pickup, potion, and trip down the stairs gets a sound of its own, played with SDL's audio, and the cells flash red when blood is drawn and green when you heal, fading away in a fraction of a second.