8

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.

  • 4
    Look at the memento pattern – user40980 Mar 1 '13 at 16:18
  • 1
    Just store the history of all the objects on the board every turn. – Ramhound Mar 1 '13 at 16:19
  • 2
    @Ramhound: If you do it that way, your program could easily turn into quite the... well... RAM hound. ;) – Mason Wheeler Mar 1 '13 at 17:04
  • 1
    @MasonWheeler - You don't have to keep track of the history beyond a certain point. Lots of programs store tons of data in a similar feature and don't have problems with memory. – Ramhound Mar 1 '13 at 17:17
  • Can you store the move coordinates on a stack? This is done in chess games. YMMV depending if it's a turn-based board game or a fluid movement like pong. – mike30 Mar 1 '13 at 17:38
16

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.

  • 2
    As an added bonus, at some point you can add a replay feature similar to StarCraft. – Jonathan Rich Mar 1 '13 at 17:11
  • 2
    +1 This is similar to a technique called Event Sourcing used in other contexts. – MattDavey Mar 1 '13 at 18:01
  • 1
    The comment by @MattDavey Explain this technique in a great way. I will accept this because it can be fairly easy to implement, no matter how complex the game is. – gbianchi Mar 4 '13 at 13:55
  • Event sourcing is the way to go - gets you to any point in the game – Murph Dec 10 '17 at 21:00
8

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.)
  • 4
    This is a good idea, provided the game's state takes up relatively little memory. My first real open source contribution was changing Cinelerra's undo system to the "record moves" model, because on large projects it would push megabytes of state data onto the undo stack every time I hit a key. It might not ever be an issue with a board game, but if there's any chance of the memory requirements scaling up like that, it's better to bite the bullet now. – Karl Bielefeldt Mar 1 '13 at 17:02
  • 2
    @KarlBielefeldt, I see this answer as advocating storing the changes to state only, not the entire game state at each point. The answer has lots of useful reflections on the problem, but I dislike the opening "don't record moves like the other answers say" when it really ends up advocating something very similar. – user82096 Mar 1 '13 at 17:19
  • @dan1111: I'm advocating something similar, but subtly different. When you say "record moves", that sounds like "record the changes." What I'm describing is "record what things looked like before they were changed," which makes the Undo system a lot cleaner. – Mason Wheeler Mar 1 '13 at 17:42
  • 1
    @MasonWheeler, I agree that the way you suggest implementing it is elegant. However, to me recording the states of only what changed is simply a nice way of recording the moves. I suppose it is really just an argument about semantics... – user82096 Mar 1 '13 at 18:16
  • 1
    @kuhaku No. Recording the moves that are made is making a record of what you're changing to. What I'm explaining here is that you need to make a record of what you're changing from, so that you can get back to it. – Mason Wheeler Aug 6 '16 at 14:02
2

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.

  • 2
    Command is a classic design pattern and exactly what I was going to suggest. Furthermore, I think each command should have a pointer to the player who made the move so that you can get a transcript of the entire game at the end simply by traversing the list and calling a "toString" type function for each command. For example, "Annie added a casual customer (wheat, pumpkin, turnip) and a helper (Shopper). Bill delivered to regular customer (wheat, pumpkin) for +8 cash," would be the descriptions for a couple of players turns in "At the Gates of Loyang". – John Munsch Mar 1 '13 at 18:06
  • Nice suggestion John. – Samir Hasan Mar 2 '13 at 11:40
1

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.

  • 1
    Ancient thread.. every day problem on an undo system ;). – gbianchi Dec 10 '17 at 21:51
0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.