Einführung
Ergänze ein C++-Sokoban-Spiel um vollständige Wertkopien und sicheres Rückgängigmachen mehrerer Züge.
Du arbeitest an einem kleinen Terminalspiel mit festem Gelände und getrennten beweglichen Objekten. Du implementierst die zentralen C++-Funktionen und spielst anschließend, um ihr Verhalten zu prüfen.
Den Zustand vor einem erlaubten Zug speichern
In diesem Schritt zeichnest du vollständige vorherige Zustände auf, damit Rückgängig später sowohl Gehen als auch Schieben umkehren kann. Dieses Lab richtet seine eigenen Dateien ein und benötigt keine Dateien aus dem vorherigen Lab. Beginne im Tab Terminal oder nutze Terminal > New Terminal in WebIDE.
cd /home/labex/project/sokoban
Das vollständige Programm sample ist vom Spielkern der Lernenden getrennt. Starte es, gib d, d und dann u ein, jeweils mit Enter, und beobachte, wie Lösungsstatus, Spieler und Kiste zu ihren Werten vor dem siegreichen Schieben zurückkehren. Gib q zum Beenden ein.
./sample
Deine Datei engine.cpp enthält bereits korrekte Bewegung und Lösungsprüfung, zeichnet aber keinen Verlauf auf, und undo() lehnt immer ab. Sieh sie dir an:
cat engine.cpp
Die vorbereitete Klasse Game ist in engine.hpp deklariert. Point enthält die ganzzahligen Koordinaten x und y: x wächst nach rechts, y nach unten. State enthält den Spieler und einen std::vector<Point> mit allen Kisten. terrain[y][x] enthält nur Wände #, Leerzeichen und Ziele .. Durch const ist dieses Gelände nach der Konstruktion schreibgeschützt; eine bewegte Kiste kann daher kein Ziel löschen. Die Darstellung kombiniert beide Ebenen: * bedeutet Kiste auf einem Ziel, + Spieler auf einem Ziel.
floor(point) meldet, ob eine Koordinate innerhalb des Spielfelds liegt und keine Wand ist. boxAt(point) liefert den Vektorindex einer Kiste oder -1, wenn dort keine steht. Diese Hilfsfunktionen sowie Laden, Darstellung und Befehlseingabe sind vorbereitet. Du implementierst move, won und später undo in engine.cpp; erhalte engine.hpp, support.cpp, main.cpp, levels/ und sample. Du darfst Hilfsfunktionen hinzufügen und gleichwertige Algorithmen verwenden. Die Prüfung bewertet Verhalten, keine bestimmte Schreibweise oder Zugfolge.
Unterstützte Karten sind umschlossene rechteckige ASCII-Raster mit mindestens drei Zeilen und drei Spalten. Sie enthalten genau einen Spieler, mindestens eine Kiste und genauso viele Ziele wie Kisten, ohne überlappende Objekte. Die Zeichen sind # für Wand, Leerzeichen für Boden, . für Ziel, @ für Spieler, $ für Kiste, + für Spieler auf Ziel und * für Kiste auf Ziel. Eine Karte darf unlösbar oder bereits zu Beginn gelöst sein. Der vorbereitete Lader lehnt andere Eingaben ab; du musst keinen Parser schreiben.
move(dx, dy) akzeptiert nur (1,0), (-1,0), (0,1) oder (0,-1). Jedes andere Ganzzahlpaar muss false zurückgeben, ohne Zustand oder Verlauf zu ändern. Eine erlaubte Aktion liefert true; eine unerlaubte liefert false und ändert nichts. Für die Feldbelegung ist die Reihenfolge im Kistenvektor unerheblich. Später stellt Rückgängig den tatsächlich vor der Aktion gespeicherten vollständigen Zustand wieder her, einschließlich der damaligen Kistenreihenfolge.
std::vector<State> history ist eine geordnete Sammlung vollständiger Zustände. history.push_back(state) speichert eine Wertkopie: Spätere Änderungen an state.player oder einem Element von state.boxes verändern diese frühere Kopie nicht. Würde nur der Spieler gespeichert, gingen die Positionen geschobener Kisten verloren. Das feste Gelände wird nicht kopiert, weil erlaubtes Spielen es nicht ändern kann; der Lösungsstatus wird aus Gelände und Kisten abgeleitet, statt als eigenes Merkmal gespeichert zu werden.
Eine abgelehnte Aktion darf keinen Rückgängig-Eintrag verbrauchen. Speichere den Schnappschuss nach allen Ablehnungszweigen, aber vor der ersten Änderung. Wird der Zug wegen Richtung, Wand, zweiter Kiste oder blockiertem Ziel abgelehnt, ist kein Schnappschuss sinnvoll. Der anfängliche Verlauf ist leer.
Die folgende Prüfung schlägt beim Ausgangscode absichtlich mit walk records its entire before state fehl:
bash /opt/labex-sokoban/check.sh history
Die folgende vollständige Datei ergänzt für jede erlaubte Aktion einen Schnappschuss; Rückgängig bleibt unfertig. cat > ersetzt die Datei; das Here-Document in Anführungszeichen schreibt C++ wörtlich bis zur Abschlusszeile CPP.
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
Kompiliere mit C++17 und Compilerwarnungen. Ist eine Zeile falsch eingegeben, korrigiere sie oder wiederhole das vollständige Ersetzen und baue erneut.
g++ -std=c++17 -Wall -Wextra engine.cpp support.cpp main.cpp -o sokoban
./sokoban
Gib d, d, d ein und drücke jeweils Enter. Der Verlauf durchläuft 1, 2, 3: gehen, auf das Ziel schieben, vom Ziel schieben. Ein weiteres d zeigt Blocked und lässt History: 3 bestehen. Gib u ein: Bis zur Implementierung im nächsten Schritt ist No earlier move zu erwarten, und das Spielfeld bleibt unverändert. Gib q ein.
bash /opt/labex-sokoban/check.sh history
All history checks passed bedeutet, dass erlaubte Aktionen ihre tatsächlichen vollständigen vorherigen Werte gespeichert haben und Ablehnungen keine Einträge hinzufügten. Es bedeutet noch nicht, dass Rückgängig funktioniert.
Den letzten Schnappschuss wiederherstellen und entfernen
In diesem Schritt implementierst du Rückgängig und spielst mit mehreren Rücknahmen. Arbeite weiter in Terminal, im Verzeichnis /home/labex/project/sokoban.
history.empty() erkennt, dass keine frühere erlaubte Aktion vorliegt. Gib dann false zurück, ohne etwas zu verändern. Andernfalls bezeichnet history.back() den letzten Schnappschuss. Seine Zuweisung an state stellt durch Wertkopieren den Spieler und alle Kisten wieder her. Erst nach dem Kopieren entfernt pop_back() den benutzten Schnappschuss. Der Zugriff auf back() bei einem leeren Vektor ist ungültig; deshalb muss die Schutzbedingung zuerst kommen. Rückgängig fügt keinen weiteren Verlaufseintrag hinzu.
Die übrige Bewegung bleibt gleich. Ersetze die vollständige Datei:
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
Gib u ein: No earlier move lässt das anfängliche Spielfeld unverändert. Gib d, d ein: Das Spiel ist gelöst. Gib erneut d ein: Die Kiste verlässt ihr Ziel, das unter dem Spieler als + erscheint, und der Sieg verschwindet. Versuche ein weiteres d: Es wird blockiert und der Verlauf bleibt bei 3.
Gib nun u ein: Das Spiel kehrt einschließlich der Kiste zum gewonnenen Spielfeld zurück. Ein zweites u stellt die Position vor dem siegreichen Schieben mit Not solved wieder her. Ein drittes u bringt den Spieler mit History: 0 zur Ausgangsposition zurück; ein weiteres u meldet sicher No earlier move. Gib q ein.
./sokoban levels/warehouse.txt
Probiere w, s, d, d, w, jeweils mit Enter. Beide Kisten erreichen ihre Ziele. Gib fünfmal u ein: Jeder Schritt stellt den vorherigen vollständigen Zustand wieder her, bis beide Kisten und der Spieler an ihren Ausgangspositionen stehen. Weitere Rücknahmen werden sicher abgelehnt. Eine andere erlaubte Folge ist d, d, w, s, a, a, w; der Spielkern muss beide Folgen unterstützen, nicht nur eine feste Sequenz. Gib q ein.
bash /opt/labex-sokoban/check.sh undo
All undo checks passed umfasst die Wiederherstellung tatsächlicher vorheriger Zustände nach verschiedenen Zugfolgen, leeren Verlauf, unveränderten Verlauf bei unerlaubten Aktionen, das Verlassen von Zielen und die Rücknahme eines Siegs. Die Prüfung verwendet isolierte Spiele für deine unveränderten Funktionen und die bereits gebaute ausführbare Datei sokoban; baue nach Änderungen neu, damit das spielbare Programm zum Quelltext passt. Sie sendet keine Züge in eine laufende Sitzung und überschreibt keinen Fortschritt.
Bei gewöhnlichen Fehlern gibt etwa ein Tippfehler wie ./sokoban levels/missing.txt die Meldung Cannot open level: ... aus und beendet das Programm. Wiederhole den Befehl mit levels/warehouse.txt. Ein Tippfehler im laufenden Spiel zeigt Use one command per line... und ändert keinen Zustand; gib einen gültigen Befehl aus einem Buchstaben ein. Du kannst jederzeit q eingeben, bei Bedarf den Quelltext korrigieren, neu bauen und ein neues Spiel im Speicher starten, ohne die ursprünglichen Leveldateien zu ändern.
Zusammenfassung
Du hast vor erlaubten Änderungen Wertkopien als Schnappschüsse gespeichert, jedes bewegliche Objekt wiederhergestellt und den Sieg nach Rückgängig neu abgeleitet. Unerlaubte Aktionen verändern weder Spielzustand noch Verlauf.
