How to design simple undo/redo functionality?

When working with a map editor undo and redo are one of the most useful tools. They allow to correct sudden mistakes and revert wrong decisions. But how hard is it to design a proper undo/redo solution? Let’s see inside:

The process of editing the map can be represented as a timeline. At each given moment the map rests in a certain state. Between each two states there’s a certain change that brought one state to another. In mapmaking that means that map rests in states between mapmakers edits (changes):

When we need an undo/redo solution we basically need a way to travel back in time to revert previous states. There are two major methods for undo/redo here. First one is to store snapshots of the states, so that the matter of undoing something is just taking an old state from the memory. Second approach is to store only the actions that made the change between the states and be able to apply them in reverse. Knowing current state and action that lead to it, we can revert that action and get an earlier state.

States method keeps snapshots of maps whole state between changes. Pros are that having a list of such snapshots / checkpoints you can easily pick one and revert to it without any worries. The method is very simple to implement, you just need a buffer large enough to hold the copies of relevant data. Downside is the sheer amount of memory required for all these copies. Even the tiniest change, a single tile rotation requires a whole map copy. This is especially wasteful when we are dealing with extra-large 256 x 256 tiles maps.

Actions method records only the actions and their inverses instead. Upside is the efficiency – only the relevant info is being stored, the map size does not matters. If we rotate one tile only that rotation info is stored. However there are downsides: the method imposes extra complications with making a reverse action to each normal action. It may be simple with an object added (the opposite would be to remove it), but it quickly gets out of hand when you want to invert a brushstroke or a “magic water” action. E.g. you will need to invent containers versatile enough to store all the water tile rotations changed. This method is also more prone to implementation errors since it requires a whole lot of code for actions manager, actions data holders and stuff.

Since we don’t have tight RAM limits and snapshot approach proved itself trustworthy with KaM Editor we can start with it. Later on, if it becomes a bottleneck we can upgrade it, there are some simple and effective optimizations in line. After all, we don’t want to over-engineer ahead of time, otherwise we get a ton of bugs and a feature delayed by months.

For snapshot method we need one essential part – an array that allows to add new buffers that hold map states endlessly while keeping the whole undo length constant (e.g. 32 steps). The answer is the circle buffer. It is called circle because it has no start and no end, it is endless in both directions, it just keeps on overlapping itself. Each time the current position gets incremented and approaches buffers “end” it gets silently set to 0 and each time it is decremented and reaches 0 it gets set to the “last” index. Concept can be pictured like so:

When any change is being made we record a new checkpoint. Since the states are quite lengthy in time ( it may be seconds or minutes between mapmakers action) we face a decision – when to take the states snapshot? We can take the snapshots right before the changes or the moment after them.

Why do we choose to record the state after the change? Because recording big map may take a noticeable amount of time and it would feel laggy. Imagine each time mapmaker wanted to apply a brushstroke the map editor would halt for 0.5sec while he kept on moving the cursor and then when the snapshot was taken, the change suddenly took effect. Taking snapshot after cursor is released imposes much less of a pause.

Number of Undo steps has no hard limit and can be anything ranging from 1 to 1000. The difference between is only the number of buffer items allocated. If we don’t do any optimizations, each one is as big as terrain that is being edited multiplied by tile data we store. Quick example: one snapshot of 256 x 256 map roughly takes ~330kb. Storing 1 undo step is kind of silly and 1000 would take up a lot of RAM (330 mb), so we better pick something reasonable in between (or let the mapmaker choose through options).

Now that we have dealt with the method and its implementation details it is time to run a simulation. For this example lets take a circle buffer of 5 elements. Grey items are empty, pink item is the copy of the current state, yellow items are copies of earlier states.

Initially the buffer is empty (A) but as soon as the map is loaded into the map editor we memorize the first state and place it into 0 element (B). This will be our first snapshot.

As the map editing goes changes are applied, e.g. terrain type changes, elevation or objects placement (C). When there’s more changes than the buffer length older states get replaced with the new ones (D). The item in front of the current state is always marked empty to indicate the end of the chain.

When Undo is pressed we return one step back and copy buffer state over to the map (E). Now our current state is in the middle of the recorded states and we can go back (undo) and forward (redo). If we keep on undoing changes we keep on reverting the map to the earlier states and at some point we reach the undo buffer limit (F). We can not undo any further, because earlier changes got overwritten.

Redo acts the same as undo, we can go forward through recorded states (G). What happens when we are in the middle of the buffer states and apply new changes? The new state gets copied to the buffer as usual and the next block is marked empty (H), so we can not redo to it any more.

End of example.

Final piece is the circle array implementation in code. It is stored like an ordinary array, but accessing its next and previous elements is done with a bit of a trick:

var UndoArray: array of [0..MAX_UNDO-1] of UndoBuffer;

//Wherever we access an element it is always within array, 
//wrapped to the other side if needed
PrevElement := (CurElement - 1 + MAX_UNDO) mod MAX_UNDO;
NextElement := (CurElement + 1) mod MAX_UNDO;

And that’s how it works, one more feature that will be implemented in future KaM Remake version explained in devblog 🙂

If you have any question – feel free to ask in comments.