Sunday, August 2, 2009

Undo/Redo System

hi, last week i implemented undo/redo system.
as you all know, editing software without undo/redo system is pretty useless.
i think undo/redo system is a must in any editing software, i think the system is very simple and easy to implement (depending on the app, but still) so i can't see any reason why not supporting it.
ok, so explained why, so now i explain (in general) how i added it to my level editor, i will explain the idea so for implementation detail just ask...
the more generic your system is (in term of managing editable objects) the more easy it become, here i describe a system with user define max size for undo/redo (because of memory issues, you don't want to consume more than needed).
you need to support few things before implementing it:
1. you have to be able to take a snapshot of current scene state, meaning, every editable object must be stored in a way that could be restored later.
2. deque container, i use deque so i could keep X oldest elements (used to limit memory used by the system), basically every container with option to add and remove from both direction will be fine.
after you support those its just a matter of identify the places you want to support undo/redo, and wrap them with Undo_Start & Undo_End or whatever name you want.
so what those functions do?
1. Undo_Start - take a snapshot of the scene and save it in undo deque, i make sure to store a flag (lets call it done) which says if i called Undo_End or not, and i checked this flag right after i entered this function. this to assure i wont try to call Undo_Start inside Undo_Start/Undo_End block (prevent nesting), the function also gets a string so i could name the operation i wrap, useful if you want your console to output text like: Undo create new box, or undo delete...
2. Undo_End - checks if i started undo op, and set the 'done' flag to true
simple enough, so now we'll see how to perform undo/redo actions:
1. Perform_Undo - pop the head from the undo deque, push it to the redo queue, and restore the snapshot you saved, i also check size limits right after pushig new element and i its greater then a max size i defined i just pop from the tail.
2. Perform_Redo - pop the head from the redo deque, push it the the undo deque, and restore the snapshot you saved, also do same limit test as in Perform_Undo

note this system could be optimized in few ways, one place to start is the snapshot function.
how exactly you do the snapshot is depends on the app, but a simple method is to duplicate all editable objects in the scene.
also note that the snapshot needs to run ONLY once, just before you modifying the scene.
practical example:
if you have 'CreateNewBox' function that you call when you click on a create new box button on main toolbar, you need to wrap this function like this:
Undo_Start("Create New Box")
if your system supporting those kind of scene changes, speed isn't an issue, but if you support dragging and manipulating object properties with the mouse (like scale/rotate/move vertices/faces) you need to do some optimizations.
that's it, pretty simple right?


Ofek Shilon said...

Naftali! always great to read your stuff. I'll be implementing undo/redo functionality myself soon, and just wanted to add my 2cents:
Seems your main focus is synchronization issues. is undo/redo such a lengthy op that you do it in a separate thread? can't you let windows messages sort out the sync issues for you?
Another thing - in our scenario, (and many others) the space complexity of holding N complete scene layouts is prohibitive. The usual design of undo/redo works around this by storing every modification as an object, that encapsulates just the deltas needed to undo/redo itself (i.e., must implement undo() and redo() ). I recently learnt this design actually has a name:

orenk2k said...

hi dude

1. the sync thing you mentioned, well... not the main prob' right now (i don't think it will because the design) the only threads i think i will use is for the build process, loading etc...

2. as i wrote, it all comes to the snapshot func, there are many ways to do it and one way is like you mentioned, you could basically inherent from some base class of undo/redo system that track the changes of the objects, this class allows the object to override few functions and let it implement its own undo/redo func, for example: if your object apply a transformation matrix, lets say move or rotate (lets call it 'the action'), so the object must implement the 'undo action' by using the inverse of that matrix... i didn't like this design, because it tend to become very hard to maintain and its not generic in a way that every object needs to implement its own undo/redo functions...
note its all depends on the app, there also few ways to do full/half snapshots, what i wrote is just a simple solution for every one to start with, but in real app or commercial one you must take care and optimize things.
some thing to think about:
when you video capturing (i'v the chance to write one, at my work...) you don't save every image by itself right? you can save deltas or whatever, you can also compress the data, you can do tons etc...
the more you work on the data to make it smaller, the more it become slower to decode, so you need to trade off speed versus memory.
its not a video capturing, but the idea is the same, we need to capture scene states instead of scene pixels ;)

i'm glad to hear you are still enjoying my posts...
thanks and bye

Ofek Shilon said...

1. i thought too that sync issues are out of place here, so i don't understand what Undo_start and Undo_End are for.
2. The video analogy actually demonstrates my point. you can *almost never* afford to store full states of real-life-size objects (be it scene or frame). Especially today, that games tend to have vast scenes, this really should be a major engine/editor design consideration.

orenk2k said...

1. implementation decision
2. not exactly
first we have a limited frames! in our prob' its scene snapshots.
second, we don't really capture fullscreen real-time frame with sound that needs a constant 25-60 fps, so if you compare the data we store in video capturing and the data we store if you take full snapshot (not that i say i'm doing that but still...) its really not an issue!
but still, its all depend on the app, if your object have 100 kb of data, its really a bad idea to take full snapshot of 100 objects! its ridiculous.