How We Implement Undo

Undo is one of the most important functions in any editor. It's one of those quintessential things that makes working with a computer qualitatively different from working with traditional tools. Sometimes when I'm sketching with pen and paper, I'll impulsively think "hmm, that last line is a bit off, time for ctrl-z!" And then I get a jolt, look down, and remember there is no undo for real life. (I actually do this with ctrl-f too. I'll open up a book to find a quote and my first thought is "where's the search bar."). Undo is essential, but in the past I've found it easy to put off. There's always some cooler feature that will actually do something. Eventually, of course, it becomes apparent that none of those cool features will in fact be usable without undo, but by that time adding undo is a huge headache.

With the Overgrowth editors, I wrote the undo/redo framework at the beginning, and this has helped a lot. I'm not, by any means, an expert on this subject, but I still wanted to share our method for doing this, since I've found it pretty straightforward and easy to work with.

Two Types of Undo

First, let's look at how other programs implement undo. Little Big Planet (LBP) is a great example of a brute force method to implementing undo (and isn't it nice how all our examples can be about LBP :) ... okay, I'll admit it, we were playing LBP again last night :( ). LBP's undo feature simply rewinds every movement on the screen. It looks just like a video played in reverse. This gives the user complete analog control over the exact moment in time he or she wants to go back to. Unfortunately, as a user, this isn't usually what I want. I have an idea of what actions I want undone, not how many seconds I want to erase. The LBP system is good for gameplay video capture and for games like Braid that rely on time reversal. But effective editors need a more filtered history.

The big alternative to the 'rewind' method is what I'll call the 'semantic record' method: only important events are recorded and these events are packaged into discrete semantic actions. This method is everywhere. In Photoshop, for example, you don't rewind a painted line, you undo the entire 'paint line' action. This is what the Overgrowth editors use.

Command Patterns

The basic requirement for any action history is that each recorded action must be able to run both forward and backward. Sometimes this concept is formalized into the notion of a Command Pattern, which, in the present context, is a command structure that bundles a forward running Execute() version of some routine with a reverse running UnExecute() version of the routine. In the Overgrowth map editor, we have just six of these underlying command patterns: ADD/REMOVE, SELECT/DESELECT, GROUP/UNGROUP, TRANSLATE, SCALE, and ROTATE. Out of these, we build all the user-level controls, such as copy, paste, load, group rotate, and clone. Paste, for example, is just recorded as an ADD command that happens to act on objects in the copy buffer.

The full action history is simply represented as a list of commands with a pointer to the user's present location in the history. Undo() calls UnExecute() on the pointed to command and then moves the pointer back one step; Redo() moves the pointer forward one step and then calls Execute() on the newly pointed to item. As is usual, the redo side of the list is cleared whenever any new actions are recorded.

The undo/redo list. Blue boxes represent actions that can be undone. Yellow boxes represent actions that can be redone.

Reversing Commands

Figuring out how to play commands in reverse can be a bit tricky. What has worked for me is to record each command with some packaged data, which fully describes both the starting state and the ending state of the associated action. Then, Execute() applies the ending state and UnExecute() applies the starting state. For example, each TRANSLATE command comes packaged with a starting_pos and ending_pos. To undo a TRANSLATE, we simply reset the object's position to starting_pos.

As an alternative to recording starting and ending state, we could instead record a forward and reverse transition function. Execute() would call the forward transition function and UnExecute() would call the reverse transition function. This method would be more memory efficient when multiple obects are translated at once. Rather than having to remember a starting_pos for each object, we would just have to remember a single transition vector. Unfortunately, in gaining memory we lose speed -- applying transition functions is usually slower than just resetting to a recorded state. Sometimes the memory is more important, other times the speed. Luckily for us, for the action history, usually both are negligible, so we implement each command pattern according to which method is easiest and most intuitive. With transformations, recording and reapplying state has proven cleaner.

Pseudocode for the TRANSLATE command record.

Packaging Commands

Complicated commands require some further data structures. When a user moves multiple objects at once, semantically it makes sense to record this as just one action. In such a case, we bind all the individual TRANSLATE commands into a single event in the undo/redo list. When this event is undone, UnExecute() is called on each individual TRANSLATE, setting each affected object back to its starting_pos.

Actions that affect multiple objects at once are bundled in the history list.

Sometimes history management improves from even more bundling. For example, holding alt and transforming an object clones the object as it is being transformed. This is recorded as an ADD followed by a TRANSLATE, SCALE, or ROTATE. Here, undo should pop back both the transformation command and the ADD command. To facilitate this, command patterns can be chained with neighboring commands in the undo/redo list. When chained, these commands with be undone or redone as a unit.

When multiple commands make up a single semantic action, these commands are chained together in the history list.

Memory Management

One last tricky bit with undo is memory management. When an object is deleted, there's always the possibility that it will be brought back with an undo. One simple way to avoid costly and confusing recreation of objects (and the accompanying invalid pointer mess) is to never actually free the memory of an object as long as it remains in the undo/redo list. Instead, the object should just be unlinked from the active structures. The necessary information for relinking should be stored in the deletion record. (Edit: I previously suggested simply flagging these objects as deleted, but after reflecting on the comments, I think a flagging method is too hackish. Also, to be accurate, the Overgrowth editors primarily rely on unlinking and relinking.) If the object leaves the undo/redo list (e.g. when the redo part gets scrapped), only then should its memory actually be freed. Technically, these delayed frees might waste some memory, but for the purposes of the Overgrowth editors, I've found it sufficient.

What do you guys think of these methods for handling undo/redo? Do you know any other tricks of the trade, alternative paradigms, or convenient formalisms?