Introduction
Add complete value snapshots and safe multi-step undo to a C++ Sokoban game.
This independent workspace already has legal movement and actual goal completion. You will play that baseline, use WebIDE to locate the safe before-state snapshot point, and implement undo without rewriting the correct movement logic. Compile and play each improvement in Terminal.
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.
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
Now observe your own program, which is a different executable from sample. Its engine.cpp already contains correct movement and completion, but it does not record history and its undo() always refuses. Compile that unchanged starter:
g++ -std=c++17 -Wall -Wextra engine.cpp support.cpp main.cpp -o sokoban
./sokoban
Enter d, d, each followed by Enter. The box reaches its goal and the program reports Solved!, but history stays at 0. Enter u: No earlier move leaves the same winning board in place. Enter q and press Enter to return to the shell. You are adding history and undo to working movement, rather than building that movement again.
Switch to WebIDE. Choose File > Open Folder..., enter /home/labex/project/sokoban, and click OK. Use Explorer to click engine.hpp, then engine.cpp and support.cpp. To find a name within an open file, focus its source text before pressing Ctrl+F on Windows/Linux or Command+F on macOS, enter the name, then Escape to close Find. Reading these prepared files is different from changing them. Preserve the correct move and won implementations while locating the history change.
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. In this lab, preserve the correct movement and completion logic in engine.cpp, add history at the legal-move boundary, and implement undo. Keep engine.hpp, support.cpp, main.cpp, levels/, and sample unchanged. 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.
Before adding a statement, identify every branch that returns false in move, then find the first assignment that changes either a box or the player. Where could one complete before value be saved so that a blocked push uses no slot and a successful push can restore both objects? What would go wrong if the copy were made after the box assignment?
A refused action must not use an undo slot. The snapshot belongs 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. Saving after the first assignment would preserve a partly changed state instead of the real before state. The initial history is empty. Return to Terminal for the initial check.
The following check intentionally fails on the starter with walk records its entire before state:
bash /opt/labex-sokoban/check.sh history
Switch to WebIDE and find Game::move in engine.cpp. Locate the final refusal for an obstructed beyond square. Immediately after that refusal, before the line that can assign state.boxes[box], insert exactly one snapshot statement:
history.push_back(state);
Check the surrounding control flow: every return false is above your insertion, and both the box assignment and player assignment are below it. Keep all existing movement and won lines, and leave undo unfinished. Use File > Save for engine.cpp and wait until its unsaved-change marker has gone, even if Auto Save is enabled. To recover an accidental local edit, focus the source text, use Ctrl+Z on Windows/Linux or Command+Z on macOS, inspect the restored text and save again. Close a saved file with its tab's x if needed, then reopen it from Explorer. These editor actions do not restart the game or reinstall this independent workspace. Switch to the Terminal tab at the shell prompt.
Compile with C++17 and compiler warnings. If a line is mistyped, the first compiler error gives a file and line, for example engine.cpp:7:.... Open that file in WebIDE, use focused Find to locate the method, and read the editor line numbers to reach the reported line. Repair only the relevant local text and nearby punctuation/braces, use File > Save, wait until saved, then rebuild. A failed build does not prove an older executable contains the new snapshot.
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.
Before editing, predict the first undo after pushing off the goal: which complete state should become current, and how many history entries should remain? Restoring the latest snapshot first returns the winning player and box positions; removing that used snapshot then leaves the earlier history available.
Switch to WebIDE. Find Game::undo in engine.cpp. Drag to highlight only its explanatory comment and return false; between that method's braces; check that neither outer brace nor another method is selected. Write this body, keeping the method signature, braces and all move/won code unchanged:
if (history.empty()) return false;
state = history.back();
history.pop_back();
return true;
Read it in execution order: refuse empty history; restore the complete value while it still exists; remove only that used value. Keep the snapshot insertion from the previous step. Save engine.cpp and switch to Terminal; enter q first if a game is still running.
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.
