What would be the best way to store movements on a game to allow a rollback?

Question

I'm developing a board game that has a game class that controls the game flow, and players attached to the game class. The board is just a visual class, but the control of the movements is all by the game.
The player can try to make false movements that lead to the game telling the player that this kind of movement is not allowed (and tell the reason behind it). But in some cases, the player can just make a movement and realize it's not the best move, or just miss click the board, or just want to try another approach.
The game can be saved and loaded, so an approach could be storing all the data before the movement and not allow a rollback, but allow the user to load the last autosaved turn. This looks like a nice approach, but involves user interaction, and the redrawing of the board could be tedious to the user. Is there a better way to do this kind of things or the architecture really matters on this thing?

The game class and player class are not complicate so it's cloning the classes a good idea, or separate the game data from the game rules a better approach, or the saving/loading (even automatic on an asked rollback) is ok?

UPDATE: how this game works: It has a main board where you make moves (simple moves) and a player board that react on the moves makes on the main board. It also has reaction moves according to other player moves and on yourself moves.You can also react when is not your turn, doing things on your board. Maybe I can't undo every move, but I like the undo/redo idea floating in one of the current answers.

Answer 1

Why not store the history of all moves made (as well as any other non-deterministic events)? That way you can always reconstruct any given game state.

This will take significantly less storage space than storing all of the game states, and it would be fairly simple to implement.

Answer 2

Building an Undo system is conceptually pretty simple. You just need to keep track of changes. You'll want a stack, and an object type that describes a piece of the state of the game. Your stack should be a stack of arrays/lists of game state objects.

The trick is, don't record moves that people make. I see this in the other answers, and it can be done, but it's a lot more complicated. Instead, record what the game board looked like before the move was made. For example, when you move a piece, you've made two changes: The piece left one square, and the piece was placed onto a new square. If you create an array showing what those two squares looked like before the move began, then you can Undo the move simply by restoring those two squares to the way they were before the move was made.

Or, if your game state is held in the pieces and not the squares, then what you record is the position of the piece before it moved. (And if your piece interacts with any other pieces, such as a capture in chess, record where those other pieces were before they were changed.)

When any move happens:

• Create a new Undo frame (array)
• Every time something changes, if you do not already have a change for that object in the current Undo frame, add its state to the current Undo frame before applying the change.
• When the move is over, push the Undo frame onto the stack.

When the user says Undo:

• pop the top of the stack and grab an Undo frame
• iterate over each object in the frame, and restore it
• (Optionally): Track the changes made here in exactly the same way as you did when setting up an Undo frame, and push the frame onto a stack. This is how you implement Redo. (If you do this, pushing a new Undo frame should also clear the Redo stack.)

Answer 3

One nice way to implement this is to encapsulate your moves in the form of Command objects. Think of a Command interface that has the methods move(Position newPosition) and undo. A concrete class may implement this interface such that for the move method, it can store the current position on the board (Position being a class holding the row and column values probably), and then make a movement to the row and column identified by newPosition. After this, the method will add the command (this) to a global stack of Command objects.

Now, when the user needs to roll back to the previous step, just pop the last Command instance from the stack, and call its undo method. This also provides you with the ability to roll-back to as many steps as you need.

Hope that helps.

Answer 4

Bumping ancient thread but the easiest way I've found to solve this problem, at least in complex scenarios, is to just copy every damn thing prior to the user operation...

... sounds wasteful, right? Except if it is really wasteful, then your next step is to make copying cheaper so that parts that won't be changed in the next step will not be deep copied.

In my case I'm often working with gigabytes of data but the user often only touches megabytes for an operation, so copying everything would normally be extremely expensive and ridiculously wasteful.... but I've set up these data structures revolving around shallow copying what doesn't change, and I find this the easiest solution and it also opens up a lot of new possibilities, like immutable persistent data structures, safer multithreading, nodal networks which input something and output something new, non-destructive editing, instancing objects (being able to shallow copy, say, their expensive mesh data but having the clone have its own unique position in the world while barely taking memory), etc.

store all scene/application state in undo
perform user operation

on undo/redo:
   swap stored state with application state

Every project since has followed this basic pattern instead of having to carefully record every little state change and for dozens of different types of data that didn't fit into a homogeneous model (image/texture painting, property changes, mesh changes, weight changes, hierarchical scene changes, shader changes that weren't property-related like swapping one with another, envelope changes, etc etc etc). Instead if that's too wasteful in terms of memory and time, then we don't come up with a fancier undo system, instead we seek to optimize the copying so that partial copies can be made in all the most expensive data structures. That leaves it as an optimization detail where you can have a correctly-functioning undo implementation right away that will always stay correct, and always staying correct is awesome when, in the past, undo systems were among the hardest parts of the software to keep correct.

The other way is to record the deltas (changes) individually, and I used to do that in the past, but for very complex large-scale software, it was often very error-prone and tedious since it was really easy for a plugin developer to forget recording some change in the undo stack when they introduced brand new concepts into the system.

Now one thing regardless of whether you copy the entire game state or record deltas is to avoid pointers (assuming C or C++) when possible or else it'll complexify things a lot. If you use indices, everything becomes simpler instead, since indices don't invalidate with copies (either of the entire application state or a part of it). As an example with a graph data structure, if you want to copy it in its entirety or just record deltas when users make new connections or break connections in the graph, the state will want to store links to the old nodes and you can run into issues with invalidation and things of that sort. It's much easier if the connections use relative indices into an array, since its much easier to keep those indices from invalidating than pointers.

Answer 5

I would maintain an undo-list of the (valid) moves the player made.
Each item in the list should contain enough information to restore the game state to what it was just before the move was made. Depending on the amount of game-state that there is and the number of undo-steps you want to support, this could be a snapshot of the game-state, or information that tells the game-engine how to reverse the move.