Quale sarebbe il modo migliore per memorizzare i movimenti di un gioco per consentire un rollback?

Perché non memorizzare la cronologia di tutte le mosse fatte (così come ogni altro evento non deterministico)? In questo modo puoi sempre ricostruire qualsiasi dato stato di gioco.

Questo richiederà molto meno spazio di archiviazione rispetto alla memorizzazione di tutti gli stati del gioco, e sarebbe abbastanza semplice da implementare.

Costruire un sistema di annullamento è concettualmente piuttosto semplice. Hai solo bisogno di tenere traccia delle modifiche. Avrai bisogno di una pila e di un tipo di oggetto che descriva un pezzo dello stato del gioco. Lo stack dovrebbe essere una pila di matrici / elenchi di oggetti di stato del gioco.

Il trucco è, non registrare le mosse che le persone fanno . Lo vedo nelle altre risposte, e può essere fatto, ma è molto più complicato. Invece, registra ciò che il tabellone di gioco sembrava prima la mossa è stata fatta. Ad esempio, quando sposti un pezzo, hai apportato due modifiche: il pezzo ha lasciato un quadrato e il pezzo è stato posizionato su un nuovo quadrato. Se crei una matrice che mostra come erano le due caselle prima dell'inizio della mossa, puoi annullare la mossa semplicemente ripristinando i due quadrati in base alla loro posizione precedente alla mossa.

Oppure, se il tuo stato di gioco è contenuto nei pezzi e non nei quadrati, allora ciò che registri è la posizione del pezzo prima che si muovesse. (E se il tuo pezzo interagisce con altri pezzi, come una cattura negli scacchi, registra dove erano prima questi pezzi prima che fossero cambiati.)

Quando si verifica una mossa:

• Crea una nuova cornice Annulla (array)
• Ogni volta che qualcosa cambia, se non hai ancora una modifica per quell'oggetto nel fotogramma Annulla corrente, aggiungi il suo stato al fotogramma Annulla corrente prima di applicare la modifica.
• Quando la mossa è finita, spinge il fotogramma Annulla sullo stack.

Quando l'utente dice Annulla:

• inserisci la parte superiore della pila e recupera una cornice Annulla
• scorrere su ogni oggetto nel frame e ripristinarlo
• (Facoltativamente): consente di tenere traccia delle modifiche apportate qui esattamente nello stesso modo in cui lo si è fatto durante la configurazione di un fotogramma Annulla e di spingere il riquadro su una pila. Ecco come si implementa Redo. (Se lo fai, spingendo un nuovo frame Annulla dovrebbe anche cancellare lo stack Redo.)

Un buon modo per implementare questo è incapsulare le tue mosse sotto forma di oggetti Comando. Pensa a un'interfaccia di comando con i metodi move(Position newPosition) e undo . Una classe concreta può implementare questa interfaccia in modo tale che per il metodo move , possa memorizzare la posizione corrente sulla scheda (la posizione è una classe che tiene probabilmente i valori di riga e colonna), quindi eseguire un movimento sulla riga e sulla colonna identificate di newPosition . Dopo questo, il metodo aggiungerà il comando ( this ) a uno stack globale di oggetti Command.

Ora, quando l'utente deve tornare al passaggio precedente, basta estrarre l'ultima istanza di comando dallo stack e chiamare il suo metodo undo . Ciò ti offre anche la possibilità di eseguire il rollback su tutti i passaggi necessari.

Spero che ti aiuti.

Bumping thread antico, ma il modo più semplice che ho trovato per risolvere questo problema, almeno in scenari complessi, è quello di copiare ogni cosa dannatamente prima dell'operazione dell'utente ...

... sembra uno spreco, giusto? Tranne se è davvero uno spreco, il tuo prossimo passo è quello di rendere la copia più economica in modo che le parti che non verranno modificate nel passaggio successivo non saranno copiate in profondità.

Nel mio caso lavoro spesso con gigabyte di dati, ma l'utente spesso tocca solo megabyte per un'operazione, quindi copiare tutto sarebbe normalmente estremamente costoso e ridicolmente dispendioso ... ma ho creato queste strutture dati girando attorno a superficiale copiando ciò che non cambia, e trovo questa la soluzione più semplice e apre anche molte nuove possibilità, come strutture dati permanenti immutabili, multithreading più sicuro, reti nodali che introducono qualcosa e producono qualcosa di nuovo, non distruttivo modificare, istanziare oggetti (essere in grado di copiare superficialmente, ad esempio, i loro costosi dati di mesh, ma avere il clone avere una propria posizione unica nel mondo mentre a malapena prende la memoria), ecc.

store all scene/application state in undo
perform user operation

on undo/redo:
   swap stored state with application state

Ogni progetto da allora ha seguito questo schema di base invece di dover registrare attentamente ogni piccolo cambiamento di stato e per decine di tipi diversi di dati che non si adattano a un modello omogeneo (pittura di immagini / texture, modifiche di proprietà, modifiche di mesh, variazioni di peso, cambi di scena gerarchici, cambiamenti di shader che non erano correlati alla proprietà come scambiarsi uno con l'altro, cambiamenti di busta, ecc. ecc. ecc.). Invece, se questo è troppo dispendioso in termini di memoria e tempo, allora non creiamo un sistema di annullamento più elaborato, ma cerchiamo di ottimizzare la copia in modo che le copie parziali possano essere fatte in tutte le strutture di dati più costose. Questo lo lascia come un dettaglio di ottimizzazione in cui si può avere un'implementazione di annullamento correttamente funzionante che rimarrà sempre corretta, e rimanere sempre corretti è fantastico quando, in passato, i sistemi di annullamento erano tra le parti più difficili del software per mantenere la corretta .

L'altro modo è registrare i delta (modifiche) individualmente, e in passato lo facevo, ma per software su larga scala molto complesso, era spesso molto soggetto a errori e noioso dato che era davvero facile per uno sviluppatore di plugin per dimenticare di registrare alcune modifiche nello stack di annullamento quando hanno introdotto nuovi concetti nel sistema.

Ora una cosa a prescindere dal fatto che si copi l'intero stato del gioco o delta record è di evitare i puntatori (supponendo C o C ++) quando possibile, altrimenti complicherà molto le cose. Se si utilizzano indici, tutto diventa invece più semplice, poiché gli indici non invalidi con le copie (l'intero stato dell'applicazione o parte di esso). Ad esempio con una struttura di dati del grafico, se si desidera copiarlo nella sua interezza o semplicemente registrare dei delta quando gli utenti creano nuove connessioni o interrompono le connessioni nel grafico, lo stato vorrà memorizzare i collegamenti ai vecchi nodi e si può incorrere in problemi con l'invalidazione e cose del genere. È molto più semplice se le connessioni utilizzano gli indici relativi in un array, poiché è molto più facile impedire a tali indici di invalidare i puntatori.

Manterrei una lista di annullamenti delle mosse (valide) fatte dal giocatore.
Ogni elemento dell'elenco dovrebbe contenere informazioni sufficienti per ripristinare lo stato del gioco a ciò che era appena prima della mossa. A seconda della quantità di stato di gioco esistente e del numero di passaggi di annullamento che si desidera supportare, questa potrebbe essere un'istantanea dello stato di gioco o informazioni che indicano al motore di gioco come invertire la mossa.