Введение
Добавьте в Sokoban на C++ полные снимки значений и безопасную отмену нескольких ходов.
Вы будете работать с небольшой терминальной игрой, где неподвижное поле отделено от движущихся объектов. Вы реализуете основные функции C++, затем поиграете и проверите их поведение.
Сохранять состояние перед допустимым ходом
На этом шаге записывайте полные предыдущие состояния, чтобы позднее отмена обращала и ходьбу, и толкание. Эта работа создаёт собственные файлы и не требует файлов из предыдущей. Начните во вкладке Terminal либо откройте Terminal > New Terminal в WebIDE.
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 после создания поле доступно только для чтения, поэтому движущийся ящик не может стереть цель. При отображении объединяются два слоя: * означает ящик на цели, а + — игрока на цели.
floor(point) сообщает, находится ли координата внутри поля и не является ли стеной. boxAt(point) возвращает индекс ящика в векторе или -1, если на клетке нет ящика. Эти вспомогательные функции, загрузка, отображение и чтение команд уже подготовлены. Вы реализуете move, won, а позднее undo в engine.cpp; сохраните engine.hpp, support.cpp, main.cpp, levels/ и sample. Можно добавлять вспомогательные функции и использовать равнозначные алгоритмы. Проверяется поведение, а не конкретное написание кода или маршрут.
Поддерживаются замкнутые прямоугольные ASCII-карты размером не менее трёх строк и трёх столбцов. На карте ровно один игрок, хотя бы один ящик и столько же целей, сколько ящиков, без наложения объектов. Обозначения: # — стена, пробел — пол, . — цель, @ — игрок, $ — ящик, + — игрок на цели, * — ящик на цели. Карта может быть неразрешимой или уже завершённой с самого начала. Подготовленный загрузчик отклоняет остальные данные; писать парсер не требуется.
move(dx, dy) принимает только (1,0), (-1,0), (0,1) или (0,-1). Любая другая пара целых должна возвращать false, не меняя состояние и историю. Допустимое действие возвращает true; недопустимое возвращает false и ничего не меняет. Порядок ящиков в векторе не влияет на занятость клеток. Позднее отмена восстановит фактическое полное состояние, сохранённое до действия, включая тогдашний порядок ящиков.
std::vector<State> history — упорядоченная коллекция полных состояний. history.push_back(state) сохраняет копию по значению: дальнейшие изменения state.player или любого элемента state.boxes не меняют эту прежнюю копию. Если сохранять только игрока, позиции сдвинутых ящиков потеряются. Неподвижное поле не копируется, потому что допустимая игра не может его изменить; завершение выводится из поля и ящиков, а не хранится отдельным флагом.
Отклонённое действие не должно занимать место в истории отмены. Сохраняйте снимок после всех ветвей отказа, но до первого изменения. Если ход запрещён из-за направления, стены, второго ящика или занятого назначения, снимок не нужен. Начальная история пуста.
Следующая проверка намеренно завершается ошибкой на начальном коде с сообщением walk records its entire before state:
bash /opt/labex-sokoban/check.sh history
Полный файл ниже добавляет по одному снимку для каждого допустимого действия; отмена пока не закончена. cat > заменяет файл, а here-document в кавычках записывает C++ буквально до закрывающей строки 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
Соберите программу с 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() удаляет использованный снимок. Обращение к 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: игра возвращается к победному полю вместе с ящиком. Второй u восстанавливает положение до победного толкания с Not solved. Третий u возвращает игрока в начальную позицию с History: 0; ещё один u безопасно сообщает No earlier move. Введите q.
./sokoban levels/warehouse.txt
Попробуйте w, s, d, d, w, нажимая Enter после каждой команды. Оба ящика займут цели. Введите u пять раз: каждый шаг восстанавливает предыдущее полное состояние, пока оба ящика и игрок не вернутся в начальные позиции. Лишняя отмена безопасно отклоняется. Другой допустимый маршрут: 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... и не меняет состояние; введите допустимую однобуквенную команду. Всегда можно ввести q, при необходимости исправить код, пересобрать программу и начать новую игру в памяти, не меняя исходные файлы уровней.
Резюме
Вы сохраняли снимки значений перед допустимыми изменениями, восстанавливали каждый движущийся объект и заново вычисляли победу после отмены. Недопустимые действия не меняют ни состояние игры, ни историю.
