はじめに
C++ の倉庫番ゲームに、完全な値スナップショットと安全な複数手の取り消しを追加します。
固定地形と動くオブジェクトを分離した、小さな端末ゲームを扱います。中心となる C++ 関数を実装し、実際に遊んで動作を確認します。
合法な移動の前に状態を保存する
このステップでは完全な直前状態を記録し、後の取り消しで歩行と箱押しの両方を戻せるようにします。このラボは自身のファイルを初期化し、前のラボのファイルは必要ありません。Terminal タブ、または WebIDE の Terminal > New Terminal から始めてください。
cd /home/labex/project/sokoban
完成した sample は学習者のエンジンとは別です。実行して d、d、続いて u をそれぞれ Enter で入力し、完成判定、プレイヤー、箱が勝利につながる押しの前の値に戻ることを観察します。q で終了します。
./sample
自分の engine.cpp には正しい移動と完成判定がすでにありますが、履歴を記録せず、undo() は常に拒否します。内容を確認してください。
cat engine.cpp
用意された Game クラスは engine.hpp で宣言されています。Point は整数座標 x と y を保持し、x は右向き、y は下向きに増加します。State はプレイヤーと、すべての箱を含む std::vector<Point> を保持します。terrain[y][x] に含まれるのは壁 #、空白、ゴール . だけです。const により構築後の地形は読み取り専用となるため、箱が動いてもゴールは消えません。描画時には 2 つの層を重ねます。* はゴール上の箱、+ はゴール上のプレイヤーです。
floor(point) は座標が盤面内にあり、壁ではないかを返します。boxAt(point) は箱の vector 内の添字を返し、そのマスに箱がなければ -1 を返します。これらの補助関数、読み込み、描画、コマンドの読み取りは準備済みです。engine.cpp で move、won、後で undo を実装します。engine.hpp、support.cpp、main.cpp、levels/、sample は保持してください。補助関数の追加や同等のアルゴリズムの使用は可能です。検証は動作を評価し、特定の書き方や手順は要求しません。
対応するマップは、壁で囲まれた、少なくとも 3 行 3 列の長方形 ASCII 格子です。プレイヤーはちょうど 1 人、箱は 1 個以上で、ゴール数と箱数が等しく、オブジェクトは重複しません。記号は壁 #、床の空白、ゴール .、プレイヤー @、箱 $、ゴール上のプレイヤー +、ゴール上の箱 * です。解けないマップや、最初から完成しているマップも認められます。準備済みのローダーはそれ以外の入力を拒否します。パーサーを書く必要はありません。
move(dx, dy) が受け付けるのは (1,0)、(-1,0)、(0,1)、(0,-1) のみです。それ以外の整数の組は、状態と履歴を変えずに false を返す必要があります。合法な操作は true を返し、不正な操作は false を返して何も変更しません。箱の vector 内の順序はマスの占有関係には影響しません。後で実装する取り消しは、その操作の前に実際に保存した完全な状態を、その時点の箱の順序も含めて復元します。
std::vector<State> history は完全な状態を順番に保持するコレクションです。history.push_back(state) は値のコピーを保存します。後から state.player や state.boxes の要素を変更しても、先に保存したコピーは変わりません。プレイヤーだけを保存すると、押した箱の位置が失われます。合法なプレイでは固定地形を変更できないため、地形はコピーしません。完成判定は独立したフラグとして保存せず、地形と箱から導きます。
拒否した操作で取り消しの枠を使ってはいけません。スナップショットはすべての拒否分岐の後、最初の変更の前に保存します。方向、壁、2 個目の箱、または塞がった移動先によって拒否する場合、スナップショットは不要です。最初の履歴は空です。
次の検証は初期コードでは意図的に失敗し、walk records its entire before state と表示します。
bash /opt/labex-sokoban/check.sh history
次の完全なファイルでは合法な操作ごとにスナップショットを 1 つ追加します。取り消しはまだ未完成です。cat > はファイルを置き換え、引用符付きヒアドキュメントは終了行の CPP まで C++ をそのまま書き込みます。
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
C++17 とコンパイラー警告を使ってビルドします。入力を間違えた行があればその行を修正するか、ファイル全体を再度置き換えてからビルドし直してください。
g++ -std=c++17 -Wall -Wextra engine.cpp support.cpp main.cpp -o sokoban
./sokoban
d、d、d をそれぞれ Enter で入力します。履歴は歩行、ゴールへの押し、ゴールからの押しに対応して 1、2、3 と増えます。さらに d を入力すると Blocked となり、History: 3 のままです。u を入力します。次のステップで取り消しを実装するまでは No earlier move が想定され、盤面も変わりません。q を入力します。
bash /opt/labex-sokoban/check.sh history
All history checks passed は、合法な操作が実際の完全な直前値を保存し、拒否した操作は履歴を追加しなかったことを示します。取り消しが動くことはまだ意味しません。
最新のスナップショットを復元して取り除く
このステップでは取り消しを実装し、実際に複数回戻して遊びます。Terminal の /home/labex/project/sokoban で続けてください。
history.empty() はそれより前の合法な操作がないことを判定します。その場合、何も変えず false を返します。それ以外では history.back() が最新のスナップショットを指します。それを state に代入すると、値コピーによってプレイヤーとすべての箱が復元されます。コピーした後にだけ、pop_back() で使用済みのスナップショットを取り除きます。空の vector の back() にアクセスすることは不正なので、先にガードが必要です。取り消しでは新しい履歴項目を追加しません。
その他の移動処理は同じです。ファイル全体を置き換えます。
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
u を入力すると、No earlier move と表示され、初期盤面は変わりません。d、d でゲームが完成します。もう一度 d を入力すると、箱がゴールを離れ、プレイヤーの下のゴールが + として表示され、勝利状態が消えます。さらに d を試すと拒否され、履歴は 3 のままです。
ここで u を入力すると、箱も含めて勝利時の盤面に戻ります。2 回目の u で勝利につながった押しの前の状態に戻り、Not solved が表示されます。3 回目の u でプレイヤーの初期位置に戻り、History: 0 になります。もう一度 u を入力しても、安全に No earlier move と表示されます。q を入力します。
./sokoban levels/warehouse.txt
w、s、d、d、w をそれぞれ Enter で試します。2 個の箱がゴールに到達します。u を 5 回入力します。毎回、直前の完全な状態が復元され、最終的に両方の箱とプレイヤーが初期位置に戻ります。余分な取り消しは安全に拒否されます。別の合法な手順は d、d、w、s、a、a、w です。エンジンは固定された手順だけでなく、どちらも処理する必要があります。q を入力します。
bash /opt/labex-sokoban/check.sh undo
All undo checks passed は、異なる手順後の実際の直前状態の復元、空の履歴、不正な操作時の履歴保持、ゴールからの移動、勝利の取り消しを含みます。検証器は隔離したゲームで元の関数とビルド済みの sokoban 実行ファイルを使います。編集後は再ビルドし、遊ぶプログラムをソースに一致させてください。検証器はプレイ中のセッションに移動を送ったり、進行状況を書き換えたりしません。
通常のエラーからの復帰として、./sokoban levels/missing.txt のようなタイプミスは Cannot open level: ... を表示して終了します。levels/warehouse.txt でコマンドを繰り返してください。実行中のゲーム内でコマンドを間違えると、Use one command per line... を表示し、状態は変わりません。正しい 1 文字のコマンドを入力します。いつでも q で終了し、必要ならソースを修正して再ビルドし、元のレベルファイルを変えずに新しいメモリ内のゲームを開始できます。
まとめ
合法な変更前に値のスナップショットを保存し、すべての動くオブジェクトを復元し、取り消し後に勝利を再計算しました。不正な操作ではゲーム状態も履歴も変わりません。
