Introdução
Adicione cópias completas de estado por valor e desfazer seguro de vários passos a um jogo Sokoban em C++.
Você trabalhará em um pequeno jogo de terminal com terreno fixo e objetos móveis separados. Implementará as funções centrais em C++ e depois jogará para conferir seu comportamento.
Salvar o estado antes de um movimento válido
Nesta etapa, registre estados anteriores completos para que desfazer possa depois reverter passos e empurrões. Este laboratório inicializa seus próprios arquivos e não precisa dos arquivos anteriores. Comece na aba Terminal ou use Terminal > New Terminal no WebIDE.
cd /home/labex/project/sokoban
O programa completo sample é separado do motor do aluno. Execute-o, digite d, d e depois u, com Enter após cada comando, e observe o estado de conclusão, o jogador e a caixa voltarem aos valores anteriores ao empurrão vencedor. Digite q para sair.
./sample
Seu engine.cpp já contém movimento e conclusão corretos, mas não registra histórico e seu undo() sempre recusa. Examine-o:
cat engine.cpp
A classe preparada Game é declarada em engine.hpp. Point guarda as coordenadas inteiras x e y: x cresce para a direita e y para baixo. State guarda o jogador e um std::vector<Point> contendo todas as caixas. terrain[y][x] contém apenas paredes #, espaços e alvos .. const torna esse terreno somente leitura após a construção, impedindo que uma caixa em movimento apague um alvo. A exibição combina as duas camadas: * indica uma caixa sobre um alvo, e +, o jogador sobre um alvo.
floor(point) informa se uma coordenada está dentro do tabuleiro e não é uma parede. boxAt(point) retorna o índice de uma caixa no vetor, ou -1 quando nenhuma caixa ocupa a casa. Esses auxiliares, o carregamento, a exibição e a leitura de comandos já estão preparados. Você implementa move, won e, mais tarde, undo em engine.cpp; preserve engine.hpp, support.cpp, main.cpp, levels/ e sample. Pode adicionar auxiliares e usar algoritmos equivalentes. A verificação avalia o comportamento, não uma escrita ou rota específica.
Os mapas aceitos são grades ASCII retangulares fechadas, com pelo menos três linhas e três colunas. Contêm exatamente um jogador, ao menos uma caixa e tantos alvos quanto caixas, sem objetos sobrepostos. Os símbolos são # parede, espaço chão, . alvo, @ jogador, $ caixa, + jogador sobre alvo e * caixa sobre alvo. Um mapa pode não ter solução ou já começar concluído. O carregador preparado recusa outras entradas; você não precisa escrever um analisador.
move(dx, dy) aceita apenas (1,0), (-1,0), (0,1) ou (0,-1). Qualquer outro par de inteiros deve retornar false sem mudar estado ou histórico. Uma ação válida retorna true; uma inválida retorna false e não muda nada. A ordem do vetor de caixas não importa para a ocupação das casas. Mais tarde, desfazer restaura o estado completo real salvo antes daquela ação, incluindo a ordem das caixas naquele momento.
std::vector<State> history é uma coleção ordenada de estados completos. history.push_back(state) armazena uma cópia por valor: mudanças posteriores em state.player ou em qualquer elemento de state.boxes não alteram aquela cópia anterior. Salvar apenas o jogador perderia as posições das caixas empurradas. O terreno fixo não é copiado porque uma partida válida não pode alterá-lo; a conclusão é deduzida do terreno e das caixas, em vez de armazenada como um indicador independente.
Uma ação recusada não deve ocupar uma entrada de desfazer. Salve a cópia depois de todos os ramos de recusa, mas antes da primeira alteração. Nenhuma cópia é útil quando direção, parede, segunda caixa ou destino bloqueado recusam o movimento. O histórico inicial está vazio.
A verificação seguinte falha intencionalmente no código inicial com walk records its entire before state:
bash /opt/labex-sokoban/check.sh history
O arquivo completo abaixo adiciona uma cópia por ação válida; desfazer ainda está incompleto. cat > substitui o arquivo; o here-document entre aspas escreve C++ literalmente até a linha final 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
Compile com C++17 e os avisos do compilador. Se houver uma linha digitada incorretamente, corrija-a ou repita a substituição completa e recompile.
g++ -std=c++17 -Wall -Wextra engine.cpp support.cpp main.cpp -o sokoban
./sokoban
Digite d, d, d, pressionando Enter após cada um. O histórico passa por 1, 2, 3: caminhar, empurrar para o alvo e empurrar para fora. Outro d mostra Blocked e mantém History: 3. Digite u: espera-se No earlier move até implementar desfazer na próxima etapa, e o tabuleiro permanece igual. Digite q.
bash /opt/labex-sokoban/check.sh history
All history checks passed significa que ações válidas salvaram seus valores anteriores reais e completos, enquanto as recusas não adicionaram entradas. Ainda não significa que desfazer funciona.
Restaurar e remover a última cópia de estado
Nesta etapa, implemente desfazer e jogue revertendo várias ações. Continue em Terminal, no diretório /home/labex/project/sokoban.
history.empty() detecta que não existe ação válida anterior. Nesse caso, retorne false sem mudar nada. Caso contrário, history.back() se refere à última cópia de estado. Atribuí-la a state restaura o jogador e todas as caixas por cópia de valor. Só depois da cópia, pop_back() remove o estado utilizado. Acessar back() em um vetor vazio é inválido; por isso a proteção vem primeiro. Desfazer não acrescenta outra entrada ao histórico.
O restante do movimento continua igual. Substitua o arquivo inteiro:
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
Digite u: No earlier move mantém o tabuleiro inicial intacto. Digite d, d: a partida é concluída. Digite d novamente: a caixa deixa o alvo, que aparece como + sob o jogador, e a vitória desaparece. Tente outro d: ele é bloqueado, e o histórico permanece em 3.
Agora digite u: a partida volta ao tabuleiro vencedor, incluindo a caixa. Um segundo u restaura a posição anterior ao empurrão vencedor, com Not solved. Um terceiro u devolve o jogador à posição inicial com History: 0; outro u informa com segurança No earlier move. Digite q.
./sokoban levels/warehouse.txt
Tente w, s, d, d, w, com Enter após cada comando. As duas caixas ocupam seus alvos. Digite u cinco vezes: cada passo restaura o estado anterior completo até devolver ambas as caixas e o jogador às posições iniciais. Uma tentativa extra de desfazer é recusada com segurança. Outra rota válida é d, d, w, s, a, a, w; o motor deve aceitar qualquer uma delas, não uma sequência fixa. Digite q.
bash /opt/labex-sokoban/check.sh undo
All undo checks passed inclui a restauração dos estados anteriores reais após rotas diferentes, histórico vazio, preservação do histórico em ações inválidas, saída de alvos e reversão da vitória. O verificador usa partidas isoladas com suas funções originais e o executável sokoban já compilado; recompile após editar para que o programa jogável corresponda ao código-fonte. Ele nunca envia movimentos à sessão em andamento nem reescreve seu progresso.
Para se recuperar de erros comuns, uma digitação como ./sokoban levels/missing.txt imprime Cannot open level: ... e encerra o programa. Repita o comando com levels/warehouse.txt. Um comando errado dentro do jogo em execução imprime Use one command per line... sem mudar o estado; digite uma ordem válida de uma letra. Você pode sempre digitar q, corrigir o código se necessário, recompilar e iniciar uma nova partida na memória sem alterar os arquivos originais dos níveis.
Resumo
Você salvou cópias de valores antes de mudanças válidas, restaurou cada objeto móvel e recalculou a vitória após desfazer. Ações inválidas deixam o estado do jogo e o histórico intactos.
