A new undo system

I’m more than sure that someone, somewhere already had this idea ages ago and patented it, which is ridiculous frankly, considering that it’s actually pretty easy to come up with (*I* came up with it, and it wasn’t a stroke of genius, just a typical “why don’t they just do it this way?”).

In fact, anyone with at least a limited knowledge of data structures could have come up with this idea pretty easily. Nevertheless, here it is, in all it’s mundane glory:

Our undo systems work in a linear manner, and so do the “previous” and “next” buttons in our internet browsers, letting us undo and redo things, go back and forth. The thing is, if you can go back, then you can change a previous decision you made, that’s the fundamental reason why we have undo systems, but then if we change the past, the present completely disappears.

We lose information.

And I want to keep that information, even at the cost of having a really large file size. It’s okay, I have more than a hundred GigaBytes of free space, I can afford it. And so can you. Nowdays the cost of the gygabyte is way below the dollar, don’t you think we can afford a few megabytes more on each document or photoshop image?

Right. Now, the simplified version of *my* idea goes like this: Our normal Undo Systems work like a linked list. One event next to the other, but what I’m proposing here is a tree structure. Don’t like how the picture you were drawing in Gimp ended up? Go back a few steps and do something different, which instead of erasing data, creates a new branch in the history tree.

That’s how it works, at least with things like browser history management and document modifications. You’ll have a new window dedicated to this history tree, showing a bunch of nodes in a tree structure that can be copied, pasted, moved, erased, and so on. You’ll be in charge of how much data you want to store, because you’ll be able to see how much information you are creating.

Now, for image editing software this thing gets more interesting. Instead of saving “states” of our image (saving a complete version of the image in every node of the tree), we save the actions made on each node. The image you get when selecting a node is the result of applying all of the nodes before him. So, let’s say you draw a cat with the pencil tool, then you apply a few filters here and there, then draw the background and so on. After all that hard work, you suddenly realize that you’ll have to do the whole process again but with the drawing of a dog. Now, with the system I’m proposing this would be extremely simple. Just go to the initial node where you have a blank canvas, draw the picture of the dog (creating a new history branch) and then copy all the nodes applied to the cat and paste them on the branch of the dog. There, all set.

As a bonus, you could also modify any node without having to create a new branch. So if you didn’t need the cat, just go back and modify that specific node for a drawing of a dog.

I’m particularly interested in the visualization of this system. After all, if we work with nodes for each action wouldn’t the tree look horrible? I mean, we tend to work in a linear way until we are not happy with the drawing or made a mistake, so the tree would always have really narrow sections filled with nodes with a single child each.

How can we fix that? Well, there are two concepts I think are fundamental for the tree to be easy to work with.

First is the use of a linked list structure inside each tree node. Wait, what? Simple! Each node instead of having a single action will have a list of actions. That way, the tree will never have nodes with only one child. As long as you don’t go back to any previous action and create a new branch, you’ll always be working in the same node. Your actions will be stored in the only one node that exists. Then, when something goes wrong, select a previous action in the node and create a new branch. This will take all of the actions that came after the one you selected and sent them to a new node, a child node of the node you were in. Then, another child is created, this time completely blank.

I wasn’t planning on having to draw something to explain the idea, but I think this particular part needs a visual aid:

See? Its way easier to explain using drawing than with words. For me at least.
See? It's way easier to explain the system by using drawings instead of words.

That was one of the two concepts I said I’d use to make the trees easier to use. What’s the other concept then? Minimizing. Having a plus or minus sign next to each node tells us if we are seeing the whole tree or if some of it’s parts were hidden away by the user. Except instead of having the traditional system used by the files explorer, this time around we have two of these signs on each node. The lower symbol is used for showing or hidding all of it’s children, and the upper one is used for hiding or showing all of it’s fathers.

This concept is not as straightforward and fleshed out as all the others, so I can’t really say if it should work this way. But it certainly is a concept that needs to be there if we are talking about a professional system. I mean, you have to have at least one way to hide parts of the tree that are just eating up screen space. They may be really important, but you are not concentrated on that part of the tree right now, so why should you have to look at the whole tree instead of just that part?


Now, why the flying f*ck am I talking about undo systems?

Because I’m tired of having to use the regular undo system. I’m freaking tired of being able to undo only the last thing I did. I’m tired of not being able to revert the 457965 changes I just made. I have the space, why does the program refuse to use it?

Videogames? Remember those?

Ah? …. of course! Everything has to do with videogames! I have to say that I didn’t really think about it much, but this same system could be applied to a mode of play. Something aking to the timeline mode I designed for that DS platformer game.

Mmmhhh… at the very least it’s food for thought.

Why are you blogging about this idea instead of patenting it and becoming filthy rich?

Because I detest patents. Simple as that. It’s like I’ve said at the beginning of this post: anyone with some knowledge of data structures could have come up with this idea. If I did patent it I would feel like I was patenting the freaking wheel.

Besides, I’m (probably) never going to implement this thing. I’d have to have a normal undo system for the modifications done to the tree undo system. It’s simple on the surface but the complexity behind it is something I don’t want to touch, not even with a ten foot stick. And even without considering that, it’s an auxiliary system, it’s not a tool in and off itself, I’d need to build my own image editing program just to justify the cool undo system.


Perhaps I could pitch it to the GIMP developers. We’ll see.

One thought on “A new undo system

  1. Novack

    Wow, this is good. Potentially, a mess, but with a rock solid design, could be awesome.

    Eventually, it could redesigned to commit each node to version control systems.

    One observation:
    As a bonus, you could also modify any node without having to create a new branch. So if you didn’t need the cat, just go back and modify that specific node for a drawing of a dog.

    There I think is the flaw of the majority of the time travel movies: if you go back 10 steps, and change something, you are conceptually creating a new branch, so I will intuitively try to do that in the system, even if that means to duplicate a bunch of information (cheap dollar and such). Later on, if the design allows for safe reuse of nodes among different branches, cool; if not, you are still conceptually transparent.

    Really good idea.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s