Qual seria a melhor maneira de armazenar movimentos em um jogo para permitir uma reversão?

Estou desenvolvendo um jogo de tabuleiro que possui uma classe de jogo que controla o fluxo do jogo e jogadores ligados à classe de jogo. O tabuleiro é apenas uma classe visual, mas o controle dos movimentos é todo pelo jogo.
O jogador pode tentar fazer movimentos falsos que levam ao jogo dizendo ao jogador que esse tipo de movimento não é permitido (e diga a razão por trás disso). Mas, em alguns casos, o jogador pode simplesmente fazer um movimento e perceber que não é a melhor jogada, ou simplesmente clicar no tabuleiro ou apenas tentar outra abordagem.
O jogo pode ser salvo e carregado, portanto, uma abordagem pode armazenar todos os dados antes do movimento e não permitir uma reversão, mas permitir que o usuário carregue a última curva salva automaticamente. Parece uma boa abordagem, mas envolve a interação do usuário, e o redesenho do quadro pode ser entediante para o usuário. Existe uma maneira melhor de fazer esse tipo de coisa ou a arquitetura realmente importa nessa coisa?

A classe do jogo e a classe do jogador não são complicadas, portanto é uma boa ideia clonar as classes ou separar os dados do jogo das regras do jogo para uma abordagem melhor, ou o salvamento / carregamento (mesmo automático em uma reversão solicitada) está ok?

ATUALIZAÇÃO: como este jogo funciona: Possui um tabuleiro principal onde você faz jogadas (jogadas simples) e um tabuleiro de jogador que reage aos jogadas no tabuleiro principal. Ele também tem movimentos de reação de acordo com os movimentos de outros jogadores e você mesmo. Você também pode reagir quando não é a sua vez, fazendo as coisas no seu tabuleiro. Talvez eu não consiga desfazer todos os movimentos, mas gosto da ideia de desfazer / refazer flutuando em uma das respostas atuais.

Por que não armazenar o histórico de todos os movimentos realizados (assim como outros eventos não determinísticos)? Dessa forma, você sempre pode reconstruir qualquer estado do jogo.

Isso exigirá muito menos espaço de armazenamento do que o armazenamento de todos os estados do jogo, e seria bastante simples de implementar.

Construir um sistema de Desfazer é conceitualmente bastante simples. Você só precisa acompanhar as alterações. Você quer uma pilha e um tipo de objeto que descreva uma parte do estado do jogo. Sua pilha deve ser uma pilha de matrizes / listas de objetos do estado do jogo.

O truque é não registrar movimentos que as pessoas fazem . Vejo isso nas outras respostas, e isso pode ser feito, mas é muito mais complicado. Em vez disso, registre a aparência do tabuleiro de jogo antes da mudança. Por exemplo, ao mover uma peça, você fez duas alterações: A peça deixou um quadrado e a peça foi colocada em um novo quadrado. Se você criar uma matriz que mostre a aparência desses dois quadrados antes do início da movimentação, poderá desfazer a movimentação simplesmente restaurando esses dois quadrados da maneira que estavam antes da movimentação.

Ou, se o seu estado de jogo for mantido nas peças e não nos quadrados, o que você registra é a posição da peça antes que ela se mova. (E se a sua peça interagir com outras peças, como uma captura no xadrez, registre onde elas estavam antes de serem trocadas.)

Quando qualquer movimento acontece:

• Crie um novo quadro Desfazer (matriz)
• Sempre que algo mudar, se você ainda não tiver uma alteração para esse objeto no quadro Desfazer atual, adicione seu estado ao quadro Desfazer atual antes de aplicar a alteração.
• Quando a movimentação terminar, empurre o quadro Desfazer na pilha.

Quando o usuário diz Desfazer:

• coloque a parte superior da pilha e pegue um quadro Desfazer
• itere sobre cada objeto no quadro e restaure-o
• (Opcionalmente): acompanhe as alterações feitas aqui exatamente da mesma maneira que você fez ao configurar um quadro Desfazer e empurre o quadro para uma pilha. É assim que você implementa o Refazer. (Se você fizer isso, pressionar um novo quadro Desfazer também deverá limpar a pilha Refazer.)

Uma boa maneira de implementar isso é encapsular seus movimentos na forma de objetos de comando. Pense em uma interface de comando que possua os métodos move(Position newPosition)e undo. Uma classe concreta pode implementar essa interface de modo que, para o movemétodo, possa armazenar a posição atual no quadro (posição que é provavelmente uma classe que mantém os valores de linha e coluna) e, em seguida, faça um movimento para a linha e coluna identificadas por newPosition. Depois disso, o método adicionará o comando ( this) a uma pilha global de objetos de comando.

Agora, quando o usuário precisar reverter para a etapa anterior, basta exibir a última instância de Command da pilha e chamar seu undométodo. Isso também oferece a capacidade de reverter para as etapas necessárias.

Espero que ajude.

Impulsionar thread antigo, mas a maneira mais fácil que encontrei para resolver esse problema, pelo menos em cenários complexos, é apenas copiar todas as coisas antes da operação do usuário ...

... parece um desperdício, certo? Exceto se for realmente inútil, o próximo passo é tornar a cópia mais barata, para que as peças que não serão alteradas na próxima etapa não sejam copiadas em profundidade.

No meu caso, muitas vezes estou trabalhando com gigabytes de dados, mas o usuário muitas vezes toca apenas megabytes para uma operação, então copiar tudo normalmente seria extremamente caro e ridiculamente inútil ... mas configurei essas estruturas de dados girando em torno de superfícies rasas copiar o que não muda, e acho a solução mais fácil e também abre muitas novas possibilidades, como estruturas de dados persistentes imutáveis, multithreading mais seguro, redes nodais que inserem algo e produzem algo novo, edição não destrutiva, instanciação objetos (sendo capaz de copiar superficialmente, digamos, seus caros dados de malha, mas ter o clone têm sua própria posição exclusiva no mundo, enquanto apenas consomem memória), etc.

store all scene/application state in undo
perform user operation

on undo/redo:
   swap stored state with application state

Desde então, todo projeto seguiu esse padrão básico em vez de ter que registrar cuidadosamente todas as pequenas alterações de estado e para dezenas de tipos diferentes de dados que não se encaixavam em um modelo homogêneo (pintura de imagem / textura, alterações de propriedades, alterações de malha, alterações de peso, mudanças hierárquicas de cena, mudanças de shader que não estavam relacionadas à propriedade, como trocar uma pela outra, alterações de envelope, etc etc etc). Em vez disso, se for um desperdício demais em termos de memória e tempo, não criaremos um sistema mais sofisticado para desfazer, em vez disso, procuraremos otimizar a cópia para que cópias parciais possam ser feitas em todas as estruturas de dados mais caras. Isso deixa como um detalhe de otimização, no qual você pode ter uma implementação de desfazer funcionando corretamente imediatamente, que sempre permanecerá correta e sempre correta é incrível quando, no passado,

A outra maneira é registrar os deltas (alterações) individualmente, e eu costumava fazer isso no passado, mas para softwares de grande escala muito complexos, muitas vezes era muito propenso a erros e tedioso, pois era muito fácil para um desenvolvedor de plug-ins. esquecer de registrar algumas alterações na pilha de desfazer quando introduziram novos conceitos no sistema.

Agora, uma coisa, independentemente de você copiar todo o estado do jogo ou deltas de registro, é evitar apontadores (assumindo C ou C ++) quando possível, caso contrário, isso complicará bastante as coisas. Se você usar índices, tudo se tornará mais simples, pois os índices não são invalidados pelas cópias (do estado inteiro do aplicativo ou de uma parte dele). Como um exemplo com uma estrutura de dados de gráfico, se você deseja copiá-lo por inteiro ou apenas registrar deltas quando os usuários fazem novas conexões ou interrompem conexões no gráfico, o estado desejará armazenar links para os nós antigos e você poderá encontrar problemas com invalidação e coisas desse tipo. É muito mais fácil se as conexões usarem índices relativos em uma matriz, pois é muito mais fácil impedir que esses índices invalidem do que ponteiros.

Eu manteria uma lista de desfazer dos movimentos (válidos) que o jogador fez.
Cada item da lista deve conter informações suficientes para restaurar o estado do jogo ao que era antes da mudança. Dependendo da quantidade de estado do jogo que existe e do número de etapas que você deseja dar suporte, isso pode ser uma captura instantânea do estado do jogo ou informações que informam ao mecanismo do jogo como reverter a jogada.