Stack implementation for Undo/Redo functionality in game

Question

I'm working on a game, in which a player can move around a board/grid. It has moveLeft(), moveRight(), moveUp(), and moveDown() methods which move the player 1 space at a time around the board.

I'm trying to plan out my approach to required Undo/Redo functionality on the player movement (e.g. if player had gone one space to left, and Undo was called, player would move one space to right). I'm a student, and looking into Stacks.

However, when planning the logic out on paper before programming (I find this helps me when undertaking homework), I don't know if Stacks would be appropriate based on the following problem....

When each move method is called, a string 'Up', 'Down', 'Left', 'Right' is added to Stack 1, dependent on the method called. This tracks the players movement around the board.

If undo() is called, the string on top of Stack 1 is removed, and added to a new stack, 'Stack 2'. This is used to track 'undone' moves, so that redo() has a path to follow.

If redo() is called, the string on Stack 2 is removed, and back added to Stack 1.

This works perfectly, but only if you call Redo() for exactly the same amount of times as Undo() and directly after it.

E.g.:

1. Player makes 4 moves: (Stack 1 now has 4 strings)
2. Undo() is called once: (Stack 1 now has 3 strings, Stack 2 has 1 string)
3. Player makes 4 more moves: (Stack 1 now has 7 strings, Stack 2 still has 1 string)
4. Undo() is called once: (Stack 1 now has 6 strings, Stack 2 has 2 strings)
5. Redo() is called : (here is the problem) This can be called twice, because Stack 2 has 2 strings, but in reality the Player on the board should only be able to call Redo() once.

I've been trying to work on the logic behind this in isolation for the last 4 hrs! Any advice appreciated. Namely - based on the above, is it still possible to do what I need to do with Stacks, and I need to find a work around to the problem? Or should I abandon, because it is not possible.

Answer 1

If you don't want to use Stacks because you're unsure when to clear the undo Stack, you can do this with a List. Then, your logic can be maintained in a similar fashion:

• Keep an index of which move you are on (start at 0, increment by 1 for each new move)
• If an undo is done, decrement the index (unless you are at the beginning of the list)
• If a redo is done, increment the index (unless you are at the end of the list)
• If a new move is performed, increment the index and clear all of the moves greater than or equal to the index (thus clearing your undo/redo moves)

Then, your example is:

1. Player makes 4 moves (index is 3 and list has 4 items)
2. Undo() is called once (index is 2 and list has 4 items)
3. Player makes 4 more moves (index is 6 and list has 7 items and all undo/redo items were cleared)
4. Undo() is called once (index is 5 and list has 7 items)
5. Redo is called once (index is 6 and list has 7 items)
6. Redo is called again (rejected because no redo action available)

Answer 2

It is simple to fix. Basically, a Redo is valid only if immediate previous action was an Undo.

One solution is : When the player makes a move then empty the Stack 2 (the Undo stack, that is used to Redo).

Other Solution: Defer stack 2 clearance to later. Maintain a boolean flag that tracks if previous action was an Undo (say boolean isRecentActionUndo), that should always represent if previous action was an Undo, by setting it to true on every call to Undo() and setting it to false on every call to Move(). Check this flag in Redo().

if(isRecentActionUndo) { // perform redo } else { // clear stack 2 }

There could be other better solutions to achieve the same, to perform a valid Redo().

Answer 3

In step 3

Player makes 4 more moves: (Stack 1 now has 7 strings, Stack 2 still has 1 string) 

you must empty second stack.

Answer 4

Think of it this way.. The whole idea of undo and redo lies around the state of your application (program). The Undo means you want to go immediately previous state of your application; similarly it is the case with Redo. Yes the stack is best solution to keep your previous state saved. For an Undo you do a pop and push it to another stack. Use the other stack for redo operation. You might want to set a limit for undo and redo. How you approach to save the state of your application is up to you.