8 Different Strategies for Implementing Undoable Actions

It’s good practice from a user experience point of view to have a solid way of allowing the user to experiment. The most common way to do that is to allow the user to undo and redo taken actions.

Do you need to figure out a way to add this functionality to a tool?

If so, remember that this type of functionality is expensive to change later. You might want to read on for a set of different strategies that apply in different situations.

There are two main categories of implementations. Either you store a history using state, or you store a history of commands.

Strategies 1, 2 and 3 below both work directly on the data level and store state, while strategies 4, 5 and 7 work on the logic level with stored reversible actions. Strategies 6 and 8 are combinations.

Also, there are typically two types of history modification: Linear and selective.

The standard is to use a linear approach where you can only undo actions in the exact reverse order than you first performed them. You can’t undo the second last action without first undoing the last. A selective implementation, on the other hand, would allow undoing any previous action, provided there is no conflict. This can be used to implement undo/redo functionality in a collaborative environment where clients can choose to undo only the actions they performed themselves.

1. Snapshots

From an implementation point of view, the most generally applicable strategy is simply to store copies of the state every time an edit is made. These copies are called snapshots. This works well if the changed data is small or if there’s no good way to implement any of the other strategies. It’s also commonly used in combination with other strategies as we’ll see.

When an action is undone or redone, the corresponding snapshot is loaded.

Pros

  • Easy to implement
  • Can be used for any data format or modification
  • No need for reverse logic

Cons

  • Can get a large memory overhead (but may dump data to disk)
  • Can only handle a linear history model

 

2. Diffs with Reverses

Diffs, like snapshots, work by storing data in the history but try to solve the problem of large memory overhead by only storing the things that did change. Diffs can be either recorded while applying an action, computed by the action or computed once the action is completed. In this strategy, a forward diff is stored together with a reverse diff for undoing the changes.

When an action is undone, the reverse diff is applied. When it is redone, the forward diff is applied.

Pros

  • Optimized storage

Cons

  • Depending on model format, the diff might be more or less hard to compute and apply

 

3. Snapshots + Diff Replay

This strategy combines diffs with snapshots and is a way to avoid having to store a reverse diff. Here, snapshots are used every N actions and diffs are stored in-between. When an action is undone, the last snapshot is loaded, and all the diffs before that action are applied.

When an action is undone, the last snapshot is loaded, and all the diffs before that action are applied. When an action is redone, the diff is simply re-applied.

Pros

  • Optimized storage, although how much is depending on the frequency of snapshots
  • Compared to forward and reverse diffs, this only computes and stores forward diffs

Cons

  • Depending on model format, the diff might be more or less hard to compute and apply

 

4. Undoable Commands

Here, actions are stored as commands with undo and redo implementations. All the changes are applied through code, and responsibility is given to the programmer to ensure that all state changes are properly reversed in the implementation. Undoable commands at this level may contain logic, making this potentially error-prone.

When an action is undone, the undo implementation of the command gets called. When it is redone, the do (or redo) implementation is called.

Pros

  • Generically applicable
  • Easy to implement the framework
  • Usually optimized storage

Cons

  • Hard to ensure data consistency, error-prone
  • Requires code both for applying the action and for reversing it
  • Not recommended for a non-linear history model

 

5. Recorded Primitive Reversible Commands

This strategy works by representing larger actions using small primitive commands that are trivially reversible and are recorded while the action is being applied. An action ends up being a list of primitive commands that can be applied and reversed easily. The recording encapsulates all state changes so there is no need (as there would be in the case of regular commands) to keep track of whether or not that particular item got removed from a particular array or not.

Some examples of primitive commands are SetProperty(instance, property, value) or AppendToArray(array, value).

When an action is undone, the stored primitive commands are reversed in reverse order. When it is redone, the stored primitive commands are reapplied.

Pros

  • Avoids logic errors and data corruption
  • Primitive commands can be used to reason about conflict in a selective undo model
  • Reversal of primitive commands usually trivial to implement
  • Stores only the data required, no extra information
  • No need to implement explicit undo functionality for an action

Cons

  • Requires the possibility to find a small set of primitive commands to represent all possible changes on a model
  • Actions changing many places in a model might end up with large lists of recorded commands, although such actions are usually rare

 

6. Snapshots + Command Replay

This is another way to deal with the fact that it might be hard to match up the undo implementation of commands with the action. It uses snapshots every N actions and commands are stored in-between.

When an action is undone, the last snapshot is loaded, and all commands before that action are applied. When it is redone, the command is simply applied.

Pros

  • Robust from an implementation perspective, no need for explicit undo logic

Cons

  • Requires additional storage for the snapshots

 

7. Reversible User Inputs

Depending on the application, it might also be possible to work with recording user inputs. If it is possible to compute or define the actions that the user would have to perform to manually undo an action, this might be an interesting alternative that might end up saving memory and implementation logic.

When an action is undone, the user inputs that would have been required to manually undo the action are handled. When it is redone, the user inputs are simply reapplied.

Pros

  • Potentially low storage, depending on the model
  • Captures the user’s intent and can be an interesting choice for collaborative environments

Cons

  • May need special handling for transient input (for instance, while the user is dragging a slider)
  • Might be hard to find a reverse set of inputs, depending on the type of application

 

8. Snapshots + User Input Replay

This strategy combines user input recording with snapshots.It uses snapshots every N actions and inputs are stored in-between. This removes the need to find reverse input sequences and makes using input as a strategy simpler.

When an action is undone, the latest snapshot is loaded, and all inputs before that action are reapplied. When it is redone, the inputs are simply reapplied.

Pros

  • Captures the user’s intent and can be an interesting choice for collaborative environments

Cons

  • May need special handling for transient input (for instance, while the user is dragging a slider)

 

How to Choose

So how will you choose what’s right for you?

Well, mostly it depends on your model, the data you are modifying with your undoable actions.

Is it structured data? Binary data? Text data?

What types of actions will you perform?

You should select the strategy that provides the simplest solution for you given the requirements that you have. This is something that always pays off. But make sure that in this case, you do take future requirements into account.

Do you really need a selective history model or will a classic linear history model do just fine?

Do you really need to optimize for storage or can you simply use snapshots?

I hope you found this post useful. Please share it is you did.

Do you know even more strategies for this? Leave a comment.

 

About The Author

Theresia Hansson

Theresia Hansson has worked several years as a software engineer within the game industry and on several game engines, including EA's Frostbite Engine. She is passionate about tools and workflows for creating games and loves to share her knowledge with the community.

Add a comment

*Please complete all fields correctly