Many turn-based games include an undo button to let players reverse mistakes they make during play. This feature becomes especially relevant for mobile game development where the touch may have clumsy touch recognition. Rather than rely on a system where you ask the user “are you sure you want to do this task?” for every action they take, it is much more efficient to let them make mistakes and have the option of easily reversing their action. In this tutorial, we’ll look at how to implement this using the Command Pattern, using the example of a tic-tac-toe game.
Note: Although this tutorial is written using Java, you should be able to use the same techniques and concepts in almost any game development environment. (It’s not restricted to tic-tac-toe games, either!)
Final Result Preview
The final result of this tutorial is a tic-tac-toe game that offers the capability to perform unlimited undo and redo operations.
Can’t load the applet? Watch the gameplay video on YouTube:
You can also run the demo on the command line using TicTacToeMain as the main class to execute from. After extracting the source run the following commands:
javac *.java java TicTacToeMain
Step 1: Create a Basic Implementation of Tic-Tac-Toe
For this tutorial, you are going to consider an implementation of tic-tac-toe. Although the game is extremely trivial, the concepts provided in this tutorial can apply to much more complex games.
The following download (which is different from the final source download) contains the basic code for a tic-tac-toe game model that does not contain an undo or redo feature. It will be your job to follow this tutorial and add these features. Download the base TicTacToeModel.java.
You should take note, in particular, of the following methods:
public void placeX(int row, int col) { assert(playerXTurn); assert(spaces[row][col] == 0); spaces[row][col] = 1; playerXTurn = false; } public void placeO(int row, int col) { assert(!playerXTurn); assert(spaces[row][col] == 0); spaces[row][col] = 2; playerXTurn = true; } These methods are the only methods for this game that change the state of the game grid. They will be what you will change.
If you’re not a Java developer, you’ll probably still be able to understand the code. It’s copied here if you just want to refer to it:
/** The game logic for a Tic-Tac-Toe game. This model does not have * an associated User Interface: it is just the game logic. * * The game is represented by a simple 3x3 integer array. A value of * 0 means the space is empty, 1 means it is an X, 2 means it is an O. * * @author aarnott * */ public class TicTacToeModel { //True if it is the X player’s turn, false if it is the O player’s turn private boolean playerXTurn; //The set of spaces on the game grid private int[][] spaces; /** Initialize a new game model. In the traditional Tic-Tac-Toe * game, X goes first. * */ public TicTacToeModel() { spaces = new int[3][3]; playerXTurn = true; } /** Returns true if it is the X player's turn. * * @return */ public boolean isPlayerXTurn() { return playerXTurn; } /** Returns true if it is the O player's turn. * * @return */ public boolean isPlayerOTurn() { return !playerXTurn; } /** Places an X on a space specified by the row and column * parameters. * * Preconditions: * -> It must be the X player's turn * -> The space must be empty * * @param row The row to place the X on * @param col The column to place the X on */ public void placeX(int row, int col) { assert(playerXTurn); assert(spaces[row][col] == 0); spaces[row][col] = 1; playerXTurn = false; } /** Places an O on a space specified by the row and column * parameters. * * Preconditions: * -> It must be the O player's turn * -> The space must be empty * * @param row The row to place the O on * @param col The column to place the O on */ public void placeO(int row, int col) { assert(!playerXTurn); assert(spaces[row][col] == 0); spaces[row][col] = 2; playerXTurn = true; } /** Returns true if a space on the grid is empty (no Xs or Os) * * @param row * @param col * @return */ public boolean isSpaceEmpty(int row, int col) { return (spaces[row][col] == 0); } /** Returns true if a space on the grid is an X. * * @param row * @param col * @return */ public boolean isSpaceX(int row, int col) { return (spaces[row][col] == 1); } /** Returns true if a space on the grid is an O. * * @param row * @param col * @return */ public boolean isSpaceO(int row, int col) { return (spaces[row][col] == 2); } /** Returns true if the X player won the game. That is, if the * X player has completed a line of three Xs. * * @return */ public boolean hasPlayerXWon() { //Check rows if(spaces[0][0] == 1 && spaces[0][1] == 1 && spaces[0][2] == 1) return true; if(spaces[1][0] == 1 && spaces[1][1] == 1 && spaces[1][2] == 1) return true; if(spaces[2][0] == 1 && spaces[2][1] == 1 && spaces[2][2] == 1) return true; //Check columns if(spaces[0][0] == 1 && spaces[1][0] == 1 && spaces[2][0] == 1) return true; if(spaces[0][1] == 1 && spaces[1][1] == 1 && spaces[2][1] == 1) return true; if(spaces[0][2] == 1 && spaces[1][2] == 1 && spaces[2][2] == 1) return true; //Check diagonals if(spaces[0][0] == 1 && spaces[1][1] == 1 && spaces[2][2] == 1) return true; if(spaces[0][2] == 1 && spaces[1][1] == 1 && spaces[2][0] == 1) return true; //Otherwise, there is no line return false; } /** Returns true if the O player won the game. That is, if the * O player has completed a line of three Os. * * @return */ public boolean hasPlayerOWon() { //Check rows if(spaces[0][0] == 2 && spaces[0][1] == 2 && spaces[0][2] == 2) return true; if(spaces[1][0] == 2 && spaces[1][1] == 2 && spaces[1][2] == 2) return true; if(spaces[2][0] == 2 && spaces[2][1] == 2 && spaces[2][2] == 2) return true; //Check columns if(spaces[0][0] == 2 && spaces[1][0] == 2 && spaces[2][0] == 2) return true; if(spaces[0][1] == 2 && spaces[1][1] == 2 && spaces[2][1] == 2) return true; if(spaces[0][2] == 2 && spaces[1][2] == 2 && spaces[2][2] == 2) return true; //Check diagonals if(spaces[0][0] == 2 && spaces[1][1] == 2 && spaces[2][2] == 2) return true; if(spaces[0][2] == 2 && spaces[1][1] == 2 && spaces[2][0] == 2) return true; //Otherwise, there is no line return false; } /** Returns true if all the spaces are filled or one of the players has * won the game. * * @return */ public boolean isGameOver() { if(hasPlayerXWon() || hasPlayerOWon()) return true; //Check if all the spaces are filled. If one isn’t the game isn’t over for(int row = 0; row < 3; row++) { for(int col = 0; col < 3; col++) { if(spaces[row][col] == 0) return false; } } //Otherwise, it is a “cat’s game” return true; } } Step 2: Understand the Command Pattern
The Command pattern is a design pattern that is commonly used with user interfaces to separate the actions performed by buttons, menus, or other widgets from the user interface code definitions for these objects. This concept of separating action code can be used to track every change that happens to the state of a game, and you can use this information to reverse the changes.
The most basic version of the Command pattern is the following interface:
public interface Command { public void execute(); } Any action that is taken by the program that changes the state of the game – such as placing an X in a specific space – will implement the Command interface. When the action is taken, the execute() method is called.
Now, you likely noticed that this interface does not offer the ability to undo actions; all it does is take the game from one state to another. The following improvement will allow implementing actions to offer undo capability.
public interface Command { public void execute(); public void undo(); } The goal when implementing a Command will be to have the undo() method reverse every action taken by the execute method. As a consequence, the execute() method will also be able to provide the capability to redo an action.
That’s the basic idea. It’ll become clearer as we implement specific Commands for this game.
Step 3: Create a Command Manager
To add an undo feature, you will create an CommandManager class. The CommandManager is responsible for tracking, executing, and undoing Command implementations.
(Recall that the Command interface provides the methods to make changes from one state of a program to another and also reverse it.)
public class CommandManager { private Command lastCommand; public CommandManager() {} public void executeCommand(Command c) { c.execute(); lastCommand = c; } ... } To execute a Command, the CommandManager is passed a Command instance, and it will execute the Command and then store the most recently executed Command for later reference.
Adding the undo feature to the CommandManager simply requires telling it to undo the most recent Command that executed.
public boolean isUndoAvailable() { return lastCommand != null; } public void undo() { assert(lastCommand != null); lastCommand.undo(); lastCommand = null; } This code is all that is required to have a functional CommandManager. In order for it to function properly, you will need to create some implementations of the Command interface.
Step 4: Create Implementations of the Command Interface
The goal of the Command pattern for this tutorial is to move any code that changes the state of the tic-tac-toe game into a Command instance. Namely, the code in the methods placeX() and placeO() are what you will be changing.
Inside the TicTacToeModel class, add two new inner classes called PlaceXCommand and PlaceOCommand, respectively, which each implement the Command interface.
public class TicTacToeModel { ... private class PlaceXCommand implements Command { public void execute() { ... } public void undo() { ... } } private class PlaceOCommand implements Command { public void execute() { ... } public void undo() { ... } } } The job of a Command implementation is to store a state and have logic to either transition to a new state resulting from the execution of the Command or to transition back to the initial state before the Command was executed. There are two straightforward ways of achieving this task.
- Store the entire previous state and next state. Set the game’s current state to the next state when
execute()is called and set the game’s current state to the stored previous state whenundo()is called. - Store only the information that changes between states. Change only this stored information when
execute()orundo()is called.
//Option 1: Storing the previous and next states private class PlaceXCommand implements Command { private TicTacToeModel model; // private int[][] previousGridState; private boolean previousTurnState; private int[][] nextGridState; private boolean nextTurnState; // private PlaceXCommand (TicTacToeModel model, int row, int col) { this.model = model; // previousTurnState = model.playerXTurn; //Copy the entire grid for both states previousGridState = new int[3][3]; nextGridState = new int[3][3]; for(int i = 0; i < 3; i++) { for(int j = 0; j < 3; j++) { //This is allowed because this class is an inner //class. Otherwise, the model would need to //provide array access somehow. previousGridState[i][j] = m.spaces[i][j]; nextGridState[i][j] = m.spaces[i][j]; } } //Figure out the next state by applying the placeX logic nextGridState[row][col] = 1; nextTurnState = false; } // public void execute() { model.spaces = nextGridState; model.playerXTurn = nextTurnState; } // public void undo() { model.spaces = previousGridState; model.playerXTurn = previousTurnState; } } The first option is a bit wasteful, but that does not mean it is bad design. The code is straightforward and unless the state information is extremely large the amount of waste won’t be something to worry about.
You will see that, in the case of this tutorial, the second option is better, but this approach won’t always be the best for every program. More often than not, however, the second option will be the way to go.
//Option 2: Storing only the changes between states private class PlaceXCommand implements Command { private TicTacToeModel model; private int previousValue; private boolean previousTurn; private int row; private int col; // private PlaceXCommand(TicTacToeModel model, int row, int col) { this.model = model; this.row = row; this.col = col; //Copy the previous value from the grid this.previousValue = model.spaces[row][col]; this.previousTurn = model.playerXTurn; } // public void execute() { model.spaces[row][col] = 1; model.playerXTurn = false; } // public void undo() { model.spaces[row][col] = previousValue; model.playerXTurn = previousTurn; } } The second option only stores the changes that happen, rather than the entire state. In the case of tic-tac-toe, it is more efficient and not notably more complex to use this option.
The PlaceOCommand inner class is written in a similar way – have a go at writing it yourself!
Step 5: Put Everything Together
In order to make use of your Command implementations, PlaceXCommand and PlaceOCommand, you will need to modify the TicTacToeModel class. The class must make use of a CommandManager and it must use Command instances instead of applying actions directly.
public class TicTacToeModel { private CommandManager commandManager; // ... // public TicTacToeModel() { ... // commandManager = new CommandManager(); } // ... // public void placeX(int row, int col) { assert(playerXTurn); assert(spaces[row][col] == 0); commandManager.executeCommand(new PlaceXCommand(this, row, col)); } // public void placeO(int row, int col) { assert(!playerXTurn); assert(spaces[row][col] == 0); commandManager.executeCommand(new PlaceOCommand(this, row, col)); } // ... } The TicTacToeModel class will work exactly as it did before your changes now, but you can also expose the undo feature. Add an undo() method to the model and also add a check method canUndo for the user interface to use at some point.
public class TicTacToeModel { // ... // public boolean canUndo() { return commandManager.isUndoAvailable(); } // public void undo() { commandManager.undo(); } } You now have a completely functional tic-tac-toe game model that supports undo!
Step 6: Take it Further
With a few small modifications to the CommandManager, you can add support for redo operations as well as an unlimited number of undos and redos.
The concept behind a redo feature is pretty much the same as an undo feature. In addition to storing the last Command executed, you also store the last Command that was undone. You store that Command when an undo is called and clear it when a Command is executed.
public class CommandManager { private Command lastCommandUndone; ... public void executeCommand(Command c) { c.execute(); lastCommand = c; lastCommandUndone = null; } public void undo() { assert(lastCommand != null); lastCommand.undo(); lastCommandUndone = lastCommand; lastCommand = null; } public boolean isRedoAvailable() { return lastCommandUndone != null; } public void redo() { assert(lastCommandUndone != null); lastCommandUndone.execute(); lastCommand = lastCommandUndone; lastCommandUndone = null; } } Adding in multiple undos and redos is a matter of storing a stack of undoable and redoable actions. When a new action is executed it is added to the undo stack and the redo stack is cleared. When an action is undone, it is added to the redo stack and removed from the undo stack. When an action is redone, it is removed from the redo stack and added to the undo stack.
The above image shows an example of the stacks in action. The redo stack has two items from commands that have already been undone. When new commands, PlaceX(0,0) and PlaceO(0,1), are executed, the redo stack is cleared and they are added to the undo stack. When a PlaceO(0,1) is undone, it is removed from the top of the undo stack and placed on the redo stack.
Here’s how that looks in code:
public class CommandManager { private Stack<Command> undos = new Stack<Command>(); private Stack<Command> redos = new Stack<Command>(); public void executeCommand(Command c) { c.execute(); undos.push(c); redos.clear(); } public boolean isUndoAvailable() { return !undos.empty(); } public void undo() { assert(!undos.empty()); Command command = undos.pop(); command.undo(); redos.push(command); } public boolean isRedoAvailable() { return !redos.empty(); } public void redo() { assert(!redos.empty()); Command command = redos.pop(); command.execute(); undos.push(command); } } Now you have a tic-tac-toe game model that can undo actions all the way back to the beginning of the game and redo them again.
If you’d like to see how this all fits together, grab the final source download, which contains the completed code from this tutorial.
Conclusion
You may have noticed that the final CommandManager you wrote will work for any Command implementations. This means that you can code up a CommandManager in your favorite language, create some instances of the Command interface, and have a full system prepared for undo/redo. The undo feature can be a great way to allow users to explore your game and make mistakes without feeling committed to bad decisions.
Thanks for taking interest in this tutorial!
As some further food for thought, consider the following: the Command pattern along with the CommandManager allow you to track every state change during the execution of your game. If you save this information, you can create replays of the execution of the program.
Entradas
No hay comentarios:
Publicar un comentario