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:

statechange2

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):

statechange

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.

statechange2

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:

circlebuf

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.

UndoRedo_a UndoRedo_b

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.

UndoRedo_c UndoRedo_d

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.

UndoRedo_e UndoRedo_f

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.

UndoRedo_g UndoRedo_h

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.

This entry was posted in Development. Bookmark the permalink.

6 Responses to How to design simple undo/redo functionality?

  1. Tim Fennis says:

    Interesting stuff. I’ve implemented similar systems but never used a circle buffer. Your approach seems the most efficient implementation for the ‘states’ approach. I really like reading these articles about the KaM development. Keep em’ coming and keep up the good work.

    <3

    • Krom says:

      Thanks for feedback Tim!

      There are many optimizations to this approach, I just wanted to explain the core mechanics behind it. Glad you liked it. Even with such naive wasteful approach there are no lags in KaMs map editor 🙂

  2. Fingrapyro says:

    That sounds interesting. Could it be solved to create snapshots, like in Photoshop :-).
    As such there would be states to go back to independent of whether you are over your undo limit, the one that can’t afford it(not enough RAM), simply won’t use it.
    Also, as you explained it is simple to solve it with unit added, or taken off the map, so would it be difficult to create something like a yes\no question at the beginning of each history state, regarding whether this is a total copy or a action memory? I understand it would be difficult to use action memory in more advanced actions, but as you said, adding units is simple to undo, as such there would be no 0.5 sec of lag in between unit or building adding to the map, since only the action was recorded. When the action is too complex, no problem, total copy…

    • Krom says:

      As of now, undo/redo are only applied to terrain editing where reverting actions is not as easy as with house accidentally moved. We don’t have plans on more complicated script actions (e.g. undoing AI attack settings change) as that falls into quite a different bin.

      There are some lightweight terrain edits (e.g. 1 tile being rotated), but so far we chose a simpler approach just to get going. If we have real reports about lags we can optimize it, but so far the lag is unnoticeable even on XXL maps.

  3. sompylasar says:

    Did you think of combination of the states and actions approach? The first undo item is a full snapshot, simple edits get an action/inverse pair, more complex actions get full snapshots.

    • Krom says:

      I have thought about that. There are many possible optimizations, but none of them is worth considering until we have reports of undo/redo being slow. At the moment even XXL maps undo happens instantly. There’s no need in optimizing something that is not a bottleneck 😉

Leave a Reply

Your email address will not be published.

*