How does UNDO and REDO work?

May 31, 2020 - Github Link - 15 minute read

Click here to draw something in Pixel Paint!

Computer Games in the 90s

Bring yourself back to the youthful days of elementary school. Back to the era of vintage computer games and dial-up tones. Now that we’ve landed on the subject, think of the classic drawing applications you may have grown up with: Microsoft Paint, Kid Pix, MacPaint, the list goes on.

As our young minds scoped and sussed the insides of these applications in efforts to create the next piece of art worthy of the refrigerator wall, we made mistakes. We made many mistakes. Normal. It was not long until you, my dear reader, discovered how to undo your mistakes and apply redo brush strokes that you decided to keep. From there it was not long until you discovered the ultra-convenient hotkeys to these operations: Ctrl+Z and Ctrl+Y key commands (⌘+x and ⌘+y for Mac).

This brings us to the point of this piece, namely, how the heck does UNDO and REDO even work? This was the very question I asked myself in attempting to write Pixel Paint, a simple pixel art web app that I recently finished. The rest of this article is a high level explanation of how UNDO and REDO work on the programming level.

Trust your Intuition

The problem at hand is to write an intuitive implementation of UNDO and REDO functions in a drawing application.

Let’s say you drew this heart

and let’s say you accidentally add this blue line

but now you want to return back to this

We need a way to be able to store the pixels of the canvas at each given moment so we can go back to some previous arrangement of the pixels. Henceforth we shall refer to a set/array of all pixel colors of a canvas as a STATE of the canvas.

Pixel Paint represents canvas state as an array of 1024 pixels (since it is 32x32 pixels and 32*32=1024), each represented as a 32-bit number.

let cavasState = [0xff0000ff, 0x00ffffff, ...];

Excellent! Armed with the concept of state, let's brainstorm how to start implementing UNDO and REDO.

History States

A final piece of architecture we need before diving in any further is a place to store all the states that we want to be able to access. That final piece can be as simple as an array itself. We can call this the ARRAY OF CANVAS STATES but that doesn’t roll off the tongue. Let’s settle on calling it the HISTORY STATES array

let cavasState0 = [0xff0000ff, 0x00ffffff, ...];
let cavasState1 = [0xff0000ff, 0x00ffffff, ...];
let cavasState2 = [0xfafafaff, 0x00ffffff, ...];

let historyStates = [canvasState0, canvasState1, canvasState2, ...];

A Conversation between (Fr)enemies

Act I Scene I - An amicable dialogue between two friends.
> The Ambitious Architect A: the brainy one always coming up with new ideas.
> The Suspicious Sceptic S: the hole-poker who finds flaws and problems with ideas.

The task at hand, to brainstorm how a user’s computer actions - mouse moving, mouse clicks - will affect the canvas state and the history states array.

A: I have an idea! First we’ll initialize an array. Each time we move our cursor in the application, push that state into the array and then...

S: But wait, if we move our mouse around ad infinitum, you will continuously add states to the array and this will result in memory leaks. And what if you decided to pencil in the color blue to one same pixel over and over again? The program will continue to add states when none of the canvas colors are changing. Your idea is horrible.

A: All good points! Let’s add a cap to the number of states you can hold in an array. Let’s say, 100. And to your other point, let’s only push the state to the array only when the canvas changes.

S: Okay, okay, but how would you implement this?

A: Right! I propose that after clicking the canvas with a tool - pencil, eraser, bucket, whatever - when you release the mouse button, then the current canvas state is pushed to the history states.

S: Possible, but you still have not addressed my 2nd issue. What if I keep adding blue to the same pixel. I’m still raising the mouse up and down, but according to you each of those states would get added to the history states array. This is going to ruin your flow. You would have to press UNDO several times just to get back to the "pre-blue dot" state.

A: Ahhh, very true. So let’s implement a simple comparison check.

if lastState !== thisState:
    push to array
else:
    do nothing

S: Hmm, this is okay.

Pointers to our Canvas State

The next step is to have a way to cycle back and forth between our stored states. If we create and implement a pointer that points to the array, that should do the trick.

Let’s say we have 5 states in our array.


[a,b,c,d,e]
         ^

Let’s say you draw a new line on the canvas. Upon releasing the mouse button, let’s compare the canvas state now to the current canvas. If they are different, push the current state to the history states array.


[a,b,c,d,e,f]
           ^

Make sure to increment the pointer as well. Why? This way you will always be pointing to the current state, so UNDOs and REDOs will make sense.

A little Time Travel

Let’s say you want to go a few states back to, say, state c. We want to be able to go back, then be able to return to the same f state we were in before. As you are probably imagining, dear reader, this is a straightforward task.

We start by mapping a button or combination of buttons from the computer keyboard to an UNDO function. Let’s do the same with REDO.

In Pixel Paint this looks like


document.addEventListener("keydown", function(e) {
    // some code above
    // ...
    if(e.code === "KeyZ")
    {
        Undo();
    }
    if(e.code === "KeyX")
    {
        Redo();
    }
    // code below
    // ...
}
(see these lines in the project repo)

Now what good is moving a pointer if nothing is happening to the application? We want to always load the canvas state that the pointer is targeting after the pointer moves. Let’s combine these actions together.

For UNDO

For REDO

For example, if you press Z once

If you press Z again

S: Wait, wait, but what if the pointer gets to state a at index 0? Are you saying that you just keep going back outside the bounds of the array?

No no, my Suspicious Sceptic. We need to set bounds for the pointer such that

0 <= pointer <= len(historyStates)

Injection to the Middle

A: Amazing, I think we’re finished!

S: Are you sure about that? I beg to differ. What would happen, oh so brainy architect, if I wanted to go back a few states and make a tweak to the drawing? How should the application respond? And should I be able to access that f state as it was?

A: Hmmmm...

I implore you to open an application that uses UNDO and REDO: Sublime, Atom, TextEdit, Word, Paint, Logic Pro, anything. Make a few edits to the project, remember this state - let’s call it state A - then undo a few states back. Make a new funky edit to the document that you will surely remember - call it state B. Now, try to return back to state A only using REDOs and UNDOs. Can you do it?

Throughout my primitive years, - impressionable and curious - playing around with music applications and art application, I learned intuitively that no you cannot do this. I never posited a logical argument as to why. It just didn’t make sense. Let us imagine we are ignorant to any past experiences and say, what if.

Let us take the example above. Say you wanted to go back to a much older state of the drawing, before the line insertion. Let’s go back a few states.

now you draw this



Imagine it was now possible to access the first state with the blue line

According to our current logic, we press REDO a few times, incrementing the pointer and loading in the corresponding array as we go.

This, however, strikes me as strange and unintuitive. The roughly shaded frame suddenly vanishes and you are catapulted to the original red.

S: What do you propose to do about this?

A: Hmmm...

S: I don’t hear any thinking going on in there.

A: Um, um...

S: I haven’t got all day, maybe you aren’t the...

A: Stop! I have it! I don’t think it makes sense to keep those states after you insert a new one in the middle of the history states. Let’s chuck all the states right of the newly inserted state.

S: Hmm, but that is destructive. Surely you don’t want to render original-end-of-array states unrecoverable.

A: I know, I know it looks dangerous, but the point of this functionality is for it to be intuitive and familiar, no? Imagine if we continued to stay in the middle and kept adding to the drawing

[a,b,c,d,e,f]
           ^
[a,b,c,d,e,f]
     ^
[a,b,c,X,d,e,f]
       ^
[a,b,c,X,Y,d,e,f]
         ^
[a,b,c,X,Y,Z,d,e,f]
           ^

Then, I bet it would come as a huge surprise if you REDO'ed once only to find states that have nothing to do with your current drawing. Let’s just toss d, e and f away to get

[a,b,c,X,Y,Z]
           ^

S: Well...I’m at a loss for words.



Thanks for Reading!

If you have any suggestions on how I could have made this blog post clearer or more interesting, I'd love to hear back from you. Feel free to send me an email.