Introduction
Add complete value snapshots and safe multi-step undo to a C++ Sokoban game.
You will work on a small terminal game with fixed terrain and separate moving objects. You will implement the core C++ functions, then play the result and check its behavior.
Save the State Before a Legal Move
In this step, record complete before states so later undo can reverse both walking and pushing. This lab initializes its own files; it needs no files from the earlier lab. Start in the Terminal tab, or use Terminal > New Terminal inside WebIDE.
cd /home/labex/project/sokoban
The complete sample is separate from the learner engine. Run it, enter d, d, then u, each followed by Enter, and observe that the completion status, player, and box return to their values before the winning push. Enter q to leave.
./sample
Your own engine.cpp already contains correct movement and completion, but it does not record history and its undo() always refuses. Inspect it:
cat engine.cpp
The prepared Game class is declared in engine.hpp. Point holds integer x and y coordinates: x grows right and y grows down. State holds the player and a std::vector<Point> containing every box. terrain[y][x] contains only # walls, spaces, and . goals. const makes this terrain read-only after construction, so a moving box cannot erase a goal. Rendering combines the two layers: * means a box on a goal; + means the player on a goal.
floor(point) reports whether a coordinate is inside the board and not a wall. boxAt(point) returns a box's vector index, or -1 when no box occupies it. These helpers, loading, rendering, and command reading are prepared. You implement move, won, and later undo in engine.cpp; preserve engine.hpp, support.cpp, main.cpp, levels/, and sample. You may add helper functions and use equivalent algorithms. A check tests behavior, not a particular spelling or route.
Supported maps are enclosed rectangular ASCII grids at least three rows and columns wide. They contain exactly one player, at least one box, and the same number of goals as boxes, with no overlapping objects. Symbols are # wall, space floor, . goal, @ player, $ box, + player on goal, and * box on goal. A map can be unsolvable or already completed. The prepared loader rejects other input; you do not need to write a parser.
move(dx, dy) accepts only (1,0), (-1,0), (0,1), or (0,-1). Any other integer pair must return false without changing state or history. A legal action returns true; an illegal action returns false and changes nothing. Box vector order is not significant for occupancy. Later, undo restores the actual complete state saved before that action, including its then-current box order.
std::vector<State> history is an ordered collection of complete states. history.push_back(state) stores a value copy: later changes to state.player or any element of state.boxes do not change that earlier copy. Saving only the player would lose pushed box positions. Fixed terrain is not copied because legal play cannot change it; completion is derived from terrain and boxes rather than stored as an independent flag.
A refused action must not use an undo slot. Put the snapshot after all rejection branches but before the first mutation. There is no useful snapshot when a direction, wall, second box, or blocked destination rejects the move. The initial history is empty.
The following check intentionally fails on the starter with walk records its entire before state:
bash /opt/labex-sokoban/check.sh history
The complete file below adds one snapshot per legal action; undo remains unfinished. cat > replaces the file; the quoted here-document writes the C++ literally until the closing CPP line.
cat > engine.cpp <<'CPP'
#include "engine.hpp"
bool Game::move(int dx, int dy) {
if (!((dx == -1 && dy == 0) || (dx == 1 && dy == 0) ||
(dx == 0 && dy == -1) || (dx == 0 && dy == 1))) return false;
Point next{state.player.x + dx, state.player.y + dy};
if (!floor(next)) return false;
int box = boxAt(next);
Point beyond{next.x + dx, next.y + dy};
if (box >= 0 && (!floor(beyond) || boxAt(beyond) >= 0)) return false;
history.push_back(state);
if (box >= 0) state.boxes[box] = beyond;
state.player = next;
return true;
}
bool Game::undo() {
return false;
}
bool Game::won() const {
if (state.boxes.empty()) return false;
for (Point box : state.boxes) {
if (terrain[box.y][box.x] != '.') return false;
}
return true;
}
CPP
Compile with C++17 and compiler warnings. If a line is mistyped, correct that line or repeat the full replacement, then rebuild.
g++ -std=c++17 -Wall -Wextra engine.cpp support.cpp main.cpp -o sokoban
./sokoban
Enter d, d, d with Enter after each. History progresses through 1, 2, 3: walking, pushing onto the goal, pushing off it. Another d is Blocked and keeps History: 3. Enter u: No earlier move is expected until the next step implements undo, and the board is unchanged. Enter q.
bash /opt/labex-sokoban/check.sh history
All history checks passed means legal actions saved their real complete before values, while refusals did not add entries. It does not yet claim undo works.
Restore and Remove the Latest Snapshot
In this step, implement undo and play through several reversals. Continue in Terminal, in /home/labex/project/sokoban.
history.empty() detects that no earlier legal action exists. In that case return false without changing anything. Otherwise history.back() refers to the latest snapshot. Assigning it to state restores the player and every box through value copying. Only after copying, pop_back() removes that used snapshot. Accessing back() on an empty vector is invalid, which is why the guard comes first. Undo does not add another history entry.
The rest of movement stays the same. Replace the complete file:
cat > engine.cpp <<'CPP'
#include "engine.hpp"
bool Game::move(int dx, int dy) {
if (!((dx == -1 && dy == 0) || (dx == 1 && dy == 0) ||
(dx == 0 && dy == -1) || (dx == 0 && dy == 1))) return false;
Point next{state.player.x + dx, state.player.y + dy};
if (!floor(next)) return false;
int box = boxAt(next);
Point beyond{next.x + dx, next.y + dy};
if (box >= 0 && (!floor(beyond) || boxAt(beyond) >= 0)) return false;
history.push_back(state);
if (box >= 0) state.boxes[box] = beyond;
state.player = next;
return true;
}
bool Game::undo() {
if (history.empty()) return false;
state = history.back();
history.pop_back();
return true;
}
bool Game::won() const {
if (state.boxes.empty()) return false;
for (Point box : state.boxes) {
if (terrain[box.y][box.x] != '.') return false;
}
return true;
}
CPP
g++ -std=c++17 -Wall -Wextra engine.cpp support.cpp main.cpp -o sokoban
./sokoban
Enter u: No earlier move leaves the initial board unchanged. Enter d, d: the game is solved. Enter d again: the box leaves its goal, so the goal appears as + beneath the player and victory disappears. Try another d: it is blocked and history stays at 3.
Now enter u: the game returns to the winning board, including its box. A second u restores the position before the winning push, with Not solved. A third u returns to the original player position with History: 0; another u safely reports No earlier move. Enter q.
./sokoban levels/warehouse.txt
Try w, s, d, d, w with Enter after each. The two boxes occupy their goals. Enter u five times: every step restores the previous complete state, eventually returning both boxes and the player to the original positions. Extra undo safely refuses. Another legal route is d, d, w, s, a, a, w; the engine must support either route rather than a fixed sequence. Enter q.
bash /opt/labex-sokoban/check.sh undo
All undo checks passed includes actual before-state restoration after different routes, empty history, illegal-action history preservation, goal departure, and victory reversal. The checker uses isolated game instances for your original functions and your already built sokoban executable; rebuild after edits so the playable program matches the source. It never sends moves into a live session or rewrites your progress.
For ordinary recovery, a typo such as ./sokoban levels/missing.txt prints Cannot open level: ... and exits. Repeat the command with levels/warehouse.txt. A command typo inside the running game prints Use one command per line... and changes no state; enter a valid one-letter command. You can always enter q, fix your source if necessary, rebuild, and start a fresh in-memory game without changing the original level files.
Summary
You saved value snapshots before legal changes, restored every moving object, and derived victory again after undo. Illegal actions leave both game state and history unchanged.
