Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
4  
Look at the memento pattern –  MichaelT 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
add comment

4 Answers

up vote 11 down vote accepted

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.

share|improve this answer
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
add comment

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.)
share|improve this answer
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
1  
@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. –  dan1111 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... –  dan1111 Mar 1 '13 at 18:16
add comment

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.

share|improve this answer
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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