How do you implement UNDO?

[doimus]

I'm trying to wrap my head around this, but I'm kind of lost.
What's the proper way of adding an undo function to an app?

I'm trying to make a simple pixel editor and undo is one of the essential functions such an app should have. But how?
I guess putting all the commands/actions into an array is given. But then what? How do you actually do stuff "in reverse"?

For example, if you paint a white pixel black and then undo it: how do you know that pixel was white before you painted it black?
Or if you draw some complex shape over multiple pixels which can all be of different values...

[doimus]

OK, reply to myself... it's amazing how ideas appear when you put the question in written form...

For this purpose (pixel bitmaps), I already have the bitmap as two dimensional array - maybe I could add third dimension that would represent undo levels? So app would basically store each undo level as separate image in memory and then revert accordingly. That is for 512x512 bitmap. Is this wasting too much memory? Array contains integers only (palette index value).

[Slydog]

I like your idea.
I wouldn't store the entire 512x512 sprite for each change, I would only store the affected size.
So, if you put one pixel on the screen, create a 1x1 sprite and remember its location.
If you draw a line spanning a 30x15 region, just create a sprite that size, and remember its location.
Limit this to a maximum level of undos.  But what do you do when you run out?  Just commit the bottom most layer to the original image and shift the others down one?

And, with a little extra programming, you can give each layer handles for the user to move or resize/scale the new sprite layer. 
Then have a 'commit' function (when saving, or on demand) that combines them all into one image.
You could also create your own file format that saves each sprite and position, so the user can continue editing his changes at a later time.

The other option is to store what was changed, so if you put a black pixel on a white background at position 10,10, remember the pixel colour (white) at 10,10 before putting the new black pixel.  When 'undoing', just reapply the remembered white pixel.  This applies to regions too, just remember the underlying region, either as a sprite, or a pixel array.  But this seems to be just the opposite of the above technique and I can't see any advantages it offers.  (Unlike the above which allows you to move and scale each edit region).

[Slydog]

One more option would be to save each image to the drive before applying each change.
If you want to 'undo', just load the previously saved image.
You could have multiple levels of undo by using multiple images, perhaps with a simple numbering scheme in the filename.

The user could see these files being created if he can view that location, which may not be desirable.
Can you write to a sandbox file?  If so, that may hide the details of what you are doing.

[fuzzy70]

I done a similar thing to what Slydog mentioned a long while back. Basically grabbed the area that was being affected as a spritegrab & added the sprite ID in an type. The ID's where created sequentiality starting at a high number like 1000 then it was just a case of removing the 1st item in the list when it hit my undo limit (which was set to 50 I think).

To undo just redraw the sprite from the list (not the last item in the list as that is the current change I made). It has the advantage that you can redo so can flick between the last changes by redrawing the last item on the list.

Although it was very very basic it did achieve what I wanted to do. And like Slydog said it can be expanded.

Lee


also using types rather than arrays makes management easier. Deleting the 1st (lowest) entry in a list is quicker than having to move each item in an array down by one unless you want an unlimited undo list

[Ian Price]

I did an undo feature in my MaxANSI ASCII drawing package a few years back in BlitzMax.

It allowed me to do 100 (more if I wanted) instant full screen undos, based on the screen data being stored in arrays. As I was using ANSI style images the screen array data was only 80x40. Obviously full screen pixel imagery will be much larger and slower than this. The program could easily be ported to GLBasic.

I used an array like this -

Code (glbasic) Select Expand


UNDO1[Undo_Number][x][y]


Basically every time an action occurs it sets a drawing flag to 1. Once the action is completed or the pen is lifted from the canvas the new screen is saved to the array and the UNDO flag updated the Undo_Number and sets the drawing flag to 0 again (to prevent the array from being updated constantly). It would continue doing this until the Undo_Number max value was reached (100) and then it would delete Undo_Number array 0 and shift the whole array set down.

When you want to UNDO, it works backwards through the array list, displaying the array as it was before the last action.

You can see it in action in the attached BlitzMax .EXE


[attachment deleted by admin]

[Kitty Hello]

my opinion: write them to a list of files if that's quick enough.
Saves program memory and is very easy/robust to do.