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

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

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
    // ...
}

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

• decrement the pointer
• load state to pointer into the application

For REDO

• increment the pointer
• load state to pointer into the application

For example, if you press Z once

• decrement the pointer; load state e into the canvas

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

If you press Z again

• decrement the pointer; load state d into the canvas

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

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

0 <= pointer <= len(historyStates)

Injection to the Middle

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.

[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]
           ^

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

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.