Whenever you write a level editor or maybe a turn-based game (like chess) it would be of great help having undo and redo functionality at hand.

Based on the Game Programming Patterns book from Robert Nystrom I did like to implement an undo/redo history class. The design pattern is based on the Design Patterns book of the gang of four.

Side Note

I use this programming pattern for my test-driven development workshop, I do occasionally. If you are interested in that, just let me know in the comments below.

Implementation

Introduction

A command can be anything from move one square to shoot, cast a spell, and more. The command must encapsulate everything needed to execute and to undo his action. Every command is an own instance. The commands then get stored in a history object which I will show you in this blog post.

Command Interface

The whole thing starts with a command interface which looks like this

package mygame;

public interface Command {
    public void execute();
    public void undo();
}

The only thing you need in command is execute and undo. With that, you can even make a redo. Really?

History Execute, Undo, and Redo

I’ll show you the idea of the history implementation.

package myexample;

public History {
    public void execute(Command command) {}
    public void undo() {}
    public void redo() {}
}

To make the whole thing work you need to encapsulate everything needed to execute the command in your command object, which is of great importance.

For the implementation of the history class, I used LinkedList as it was the simplest way I found for this. Of course, you can implement as well some ring buffer structure using plain arrays, but I did not have the nerve for this.

Ok, let’s start with the basics. First of all, we need to execute the command like this

public void execute(Command command) {
    command.execute();
}

That wasn’t too hard, but to be able to undo it, we need to hold that command instance in a data structure, a linked list in my case.

    private LinkedList<Command> commands;
    public History(int size) throws InstantiationException {
        commands = new LinkedList<>();
    }

    public void execute(Command command) {
        commands.add(command);
        command.execute();
    }

    public void undo() {
        commands.removeLast().undo();
    }

Oh, wait what if I undo when the list is empty? Yes, it fails, so we need some guards to protect it.

    public void undo() {
        if (!commands.isEmpty()) {
            commands.removeLast().undo();
        }
    }

Improvments

That looks not that bad and it works already. But let’s improve it a little more. For example, does this implementation not limit the number of commands in our history, so let’s introduce a size.

    private int size;

    public History(int size) throws InstantiationException {
        if (size == 0) {
            throw new InstantiationException("0 is not a valid history size");
        }
        this.size = size;
        commands = new LinkedList<>();
    }

And now we have to improve the execute method with this size information, by dropping the first command f we hit the capacity of our history.

    public void execute(Command command) {
        if (commands.size() >= size) {
            commands.removeFirst();
        }
        commands.add(command);
        command.execute();
    }

Redo

A redo would be cool and it turns out to be very simple. We need a second linked list for book-keeping.

    private LinkedList<Command> redoCommands;
    public History(int size) throws InstantiationException {
        // ...
        redoCommands = new LinkedList<>();
    }

Then we have to store all undoed commands in that redoCommands list.

    public void undo() {
        if (!commands.isEmpty()) {
            Command command = commands.removeLast();
            redoCommands.add(command);
            command.undo();
        }
    }

Now we are prepared for the redo method

    public void redo() {
        if (!redoCommands.isEmpty()) {
            execute(redoCommands.removeLast());
        }
    }

One small problem we have to solve, what if we did undo 2 times and then call execute and after that call redo? Yeah, it will end up in redo commands which actually should be cleared. So let’s clear the redo command list on execute. This is not that easy as the redo itself calls execute to have the command book-keeping for free. The easiest way is to have an internal execute which is called by execute and redo and only execute clears the redo commands list.

    public void execute(Command command) {
        redoCommands.clear();
        internalExecute(command);
    }

    public void redo() {
        if (!redoCommands.isEmpty()) {
            internalExecute(redoCommands.removeLast());
        }
    }

    private void internalExecute(Command command) {
        if (commands.size() >= size) {
            commands.removeFirst();
        }
        commands.add(command);
        command.execute();
    }

Copy & Paste Code

And to make it a simple copy&past task to take this into your project here the things you need

package myexample;

import java.util.LinkedList;

public class History {

    private LinkedList<Command> commands;
    private LinkedList<Command> redoCommands;
    private int size;

    public History(int size) throws InstantiationException {
        if (size == 0) {
            throw new InstantiationException("0 is not a valid history size");
        }
        this.size = size;
        commands = new LinkedList<>();
        redoCommands = new LinkedList<>();
    }

    public void execute(Command command) {
        redoCommands.clear();
        internalExecute(redoCommands.removeLast());
    }

    public void redo() {
        if (!redoCommands.isEmpty()) {
            internalExecute(redoCommands.removeLast());
        }
    }

    public void internalExecute(Command command) {
        if (commands.size() >= size) {
            commands.removeFirst();
        }
        commands.add(command);
        command.execute();
    }

    public void undo() {
        if (!commands.isEmpty()) {
            Command command = commands.removeLast();
            redoCommands.add(command);
            command.undo();
        }
    }
}

That’s it, folks.

Related Books

This design pattern is based on these two books, I have both ot them, I like the game programming patterns better than the original but the orignal is almost a must have a for any programmer.