Hello and welcome to another installment of the Blightmare development blog! I will be continuing our discussion of the Editor today by taking a look at one of those features that most people don’t notice unless it’s missing: Undo/Redo. Pretty much any application that stores and displays input from a user will need the ability to undo and redo to be useful and feel at all modern. At first thought, it may seem trivial to implement such a feature – especially because it is so pervasive. However, like most things, the complexity is in the details. Let’s take a look.
What is Undo? Simply put, it’s the opposite of “do”. While that isn’t a terribly useful definition, it does provide a clue for one way to accomplish our goal. The opposite of “do” might also be characterized as a “reverse do” or to do the inverse. For example, if you move an object left by 5 units, then moving the object right by 5 units would be one way to undo the original move. This is a way to approach the undo/redo problem by only moving forward with changes. Another possibility then is to move backwards. Moving backwards refers to a method by which the entire state of an application is stored and saved – often called a snapshot – before something is changed. Then we can undo a change by just replacing the current state with a previous state. Similarly, we can redo by keeping track of the states we were in while undoing and then we can use one of them as the current state. These two implementation strategies have very different trade-offs that we will explore next.
State Snapshots
Perhaps the most significant benefit of implementing undo using a general state snapshot mechanism is that it can often work without making significant changes to things that are already in place. One reason for this is because going forward may be significantly more difficult than going backward for certain operations. Take for example the delete operation. It’s very easy to delete something, even if there’s bookkeeping to update like acceleration structures or lookup tables – you just remove your object from them. Undoing the delete can then be quite difficult if the code was not setup to keep track of what was actually being deleted. Now we need to know the entire state of the thing that we deleted, any referenced objects that may have been implicitly deleted, any entries in utility data structures, etc. In general, there may be a lot of places that need to be updated to recreate an object and if those places do not have bidirectional links, then it may be difficult to access them during recreation. With a state snapshot, this becomes free. We simply make sure that our snapshot contains all the data that we care about and then when we roll it back to the previous version, everything is automatically back to how it was. This simplicity comes with a price of course. That price is storage. In general, we will need to keep a snapshot for every change that we want to be able to undo for as long as we want to be able to undo. This can quickly become expensive if we have a lot of state, especially if there are large assets or other resources that must be kept around by old state snapshots even though they are no longer in the active state. There are ways of mitigating the wasted space, but as you start being more careful about what state is being copied, the automatic properties of snapshot rollback become harder and harder to maintain. It’s a delicate balance.
Commands
The term often given to a discrete change is a command. For the purposes of undo/redo a command is the smallest unit of change. A command must be able to go forward (do) and backward (undo). Typically an application that uses commands will maintain a list of commands that have been done. To make a change – to do something – the application code must submit a command to this list, where it will be executed and added to the historical list. Undoing is then as simple as walking the list and executing each command’s undo functionality in order. If the commands are well behaved, then the overall state will be consistent by the time each command is being done or undone, which allows quick movement along the command list. This flexibility comes with an upfront cost to development however. Every change that a programmer wants to do must be expressed through a command, and how to undo the change must also be known. One of the major benefits of a command based system is that each command can be the minimal amount of information required to perform its task, and that information is decided on with maximum context because it’s specific to the action itself.
Blightmare implements a command based scheme in the editor to support undo and redo. This is a fairly recent addition and it was done incrementally which is another significant benefit of the command design. We have a simple Command interface:
public interface Command
{
string Describe();
void Execute();
void Undo();
Command Merge(Command other);
}
There are a few helper methods in here such as Describe which is useful when debugging or to provide the user a display of historical commands. Merge is an interesting method which allows commands to automatically combine with other commands depending on the context. For example, if you are moving an object 10 units to the right, we might generate 10 commands of “move right 1 unit”. It’s most likely that if you undo, you want the object to go all the way back instead of having to undo 10 times. This is a perfect place for merge. The first “move right” command can merge subsequent “move right” commands that are executed into itself, possibly inspecting a timestamp to see if there was a significant pause between movements, so that similar actions that are done as a group can be cleanly undone or redone.
Commands are then submitted to a central CommandManager that keeps track of the list of every Command that has been done in the current Editor session. Right now we store 500 commands in memory before forgetting any, but if that becomes too restrictive there’s plenty of room for more. The interface for our CommandManager looks like this:
public interface CommandManager {
public void Submit(Command command);
public void Undo();
public void Redo();
}
All that’s required to make an undoable action in the editor is an implementation of the Command interface which is usually not much more involved than just doing the action normally. It took about a week and a half to convert all our editor changes from direct changes into command based changes, and there’s minimal overhead to adding new commands going forward. The time saved by our designers is absolutely worth it because the faster you can iterate, the more iterations you get, and the more iterations you get, the better your quality.
That’s it for today, thanks for reading! If you like what you’re reading here, please share with your friends! Be sure to check out Blightmare on Steam and give our twitter a follow to stay up to date with the latest game updates. Stay safe out there!