Erase And Rewind

As I continue work on the level editor for the game I decided that adding an undo/redo system would be pretty handy. Because such a system will end up being quite tightly integrated into the editor code it makes sense to add it sooner rather than later - so that's what I'll be doing in this post

Implementing an undo systems in an editors is a programming problem that has been solved many times. The solutions usually fall into one of two categories:

1. Memorising the state of the system after each change. Undo can be done by restoring the previously recorded state. This one is pretty simple to implement (if you can save/load your state then you can do memorisation) but it's quite an inelegant and inefficient way to solve the problem
2. Using the Command Pattern. This one is a little harder to implement but is more elegant and has a number of nice benefits (that I will talk about below..)

The Command Pattern

To implement the Command Pattern you wrap each editor action into a command object that implements do() and undo() functions. The do() function is called when the user triggers the action and then the object is put on a stack of "done" commands. If the user later decides to undo the action then you run then undo() function, pop the command from the "done" stack and push it onto a "redo" stack. To redo that action again, pop in from "redo", run do() and push it back onto "done". The undo and redo stacks can be as long as you like and with modern computing resources they are usually unbounded, which means that users can undo and redo every action they carry out. Older readers may remember the days when our undo stack were limited to a few dozen commands or, even worse, just one... *shudder*

What work each commands do() and undo() functions perform depends on the command itself. A pseudo-code example for a command to move an object from one position to another might look like this:

Pretty straightforward? In this example, you can see that I pass in object_id and new_position as arguments to the command. And once you've wrapped your head around this one, see if you can think about how to write other commands such as "select object" or "delete object".

There are loads of tutorials on how to write an undo/redo system using the Command Pattern, but most of them stop at a basic implementation. There are a couple of small extensions to the pattern that I have implemented to make it nicer for the user (folding) and easier to program (exploiting state management)

Folding

Folding is the process of collapsing similar commands. For example, if you make many small movements to an object's position then having to undo them all (one at a time) can be annoying. With folding you take all similar commands and collapse them down into one. Instead of having a hundred Move commands on your undo stack, with each one moving the same object a small amount, you collapse them into a single Move command.

Folding can be done automatically by comparing the command type and arguments: if commands are the same then they can be folded. In the Move example shown above, a test for "foldability" would be:

You can see how the fold() function works internally by simply copying the state from the previous command. I would then remove the old command from the top of the stack and push this one on instead.

In my implementation I also limit "foldability" based on time since last command, using a cut-off of one second. This means that if you move an object, stop, then move it again, that won't all be folded into a single command - there will be a break at the point you paused. This works well in practice as a user often moves an object to a few positions, stopping to consider each one before settling on a final position. When the user undoes the action, they generally want to see these intermediate stages as distinct undo points. You'll notice this sort of folding being done in, for instance, text editing packages, where quickly typing a large piece of text is folded into one undo-able action, but slowly typing it, maybe one sentence at a time, will result in multiple undo-able actions.

As well as folding commands, I also make sure that I ignore commands that don't change any state at all. For example, if I select the same object twice in a row then the second command does not even need to be considered for execution. I check for this with a shouldDo() function that simple compares the previous and new states of the command, and drops it if they are the same.

State

The commands I've been talking about here are all basically just manipulating state. What if, instead of writing one function to do() and another to undo() I just wrote one applyState() function and passed it the appropriate state - either "old state" or "new state"? That's exactly what I do in my implementation. It makes the code easier as I only have to write one function for each command. It also makes folding easier to check for as I can write a generic function to compare the states of two commands rather than having to write a different check for each different command type.

Implementation

Here's the base Command object:

..and here's the real implementation of the move Command that I discussed earlier:

You can see that I pass the new and old states as objects, and the applyState() function as an anonymous function rather than defining these as members of the class. I do this so that I can be absolutely sure that the command has captured all of the state required in the config, newState and previousState objects.

The rest of the code can be found in the editorCommands.js file.

Other Changes

I also added a couple of other bits of code to support the undo/redo functionality. The biggest change was to alter the Object Manager's add() function to allow you to optionally pass in the id of the object that you adding. When you first create an object the manager creates a unique id for it. If you later delete and then un-delete that object, you need it to be created with the same id - not a new one. If you don't, then the object is recreated with a different id any subsequent commands in the undo stack that reference it by id (like select or move) would fail.

Wrapping Up

I implemented an undo/redo system based on the command pattern. I'm not totally happy with the implementation - it doesn't feel perfect yet. That's ok though - I can revisit it later if I find a good way to improve it. In the mean time, it's more than good enough to work, and I'm more than happy with how it operates from a user's persepective.

The code is here and the editor can be `played' online here. To control the editor, use the mouse to select and move objects, delete key to delete an object, CTRL+Z and CTRL+Y to undo and redo and SPACE to start and stop the game running. Note that you can edit while the game is playing.

Coming Up Next

This is the 20th instalment in my series on creating Bullet Hell Survive. I thought it might be nice to take stock in the next post and look at both how far the game has come, and how far it still has to go. Maybe I'll also take a stab at deciding what to work on for the next few posts. As always, your comments on progress and thoughts and guidance on where I should go next are always welcome.