undo/redo technique

Blitz3D Forums/Blitz3D Programming/undo/redo technique

Charrua(Posted 2011) [#1]
Hi

I'm thinking a way to implement an undo/redo in a world creator

Basically a list of object with some properties, fields, entities..

I think that there are some differents aproaches like:

a) store the current state
b) store the difference
c) store the command/transformation made

an operation should delete, modify and/or create new objects

a) pro/cons: i think to much redundancy waste of memory? easiear at first?

b) related to trasformations like move, rotation and the like, storing the realtive change is an interesting one, simply add/substract the deltas... for each element (tagged?) but wich is a delta related with textures, and or if i deleted the object or created a new one?

c) probably the most efficient but i think more complicated to code, with many Select Case statement's.

Has some one a pseudo code or a simply set of rules?

Thank's in advance

Juan

Last edited 2011


Danny(Posted 2011) [#2]
I personally think that storing relative changes is probably the most efficient way, however, I also think you'll be opening a can of worms:
- You'll have to keep an entire history starting from some original state to start from. If any thing at any stage goes wrong in the partial re-construction (due to a relative undo system) then the entire system collapses.
- You will have to support a special mechanism to deal with every possible action/operation the user can do.
- You'll probably have to add support for all sorts of exceptional conditions and situations to your undo system every time you add a new feature to the one of your engines.
Thus you might end up spending nearly the same amount of time on you undo system as on your 'do' systems..

Most likely your internal database will allow you to store 'complete instances' or duplicates of your original in-world entities (incl. their properties, settings, transformation data, etc.), this was you can be sure that the content will be reliably un-do'd - regardless of your world's current feature-set. Yes that will take a couple bytes of memory but what the heck, memory is plenty and cheap these days..

When replacing an entity with a previous state, simply purge the current one (Free Entities/textures/etc,), replace it with the previous data stored in the undo system. And then your engines will simply have to re-initialise that new asset (light, mesh, animated character, terrain, whatever it is); And most likely, you have that last bit of code already.
Using this approach you can simply reserved a fixed amount of records if you like (e.g. max 20 or 50 undos).

Just my thoughts / gut feeling on the subject i.e. I've never done or researched this topic at length..

Danny

Last edited 2011


Charrua(Posted 2011) [#3]
thank's
i have benn playing with some alternatives, and put my hands to work on the subject.
I already have Cut, Copy and Paste feature so my aproach (by now) is an extension of the copy/paste feature.
Basically i have a list of "Normal copy objects" the ones you manage with Ctrl+C and Ctrl+V (tagged Normal) and many more Copy objects Tagged diferently depending on the "Undo-Level"
I copy any set of objectes that should change in one operation. When doing Undo/Redo i analize wich objects are in both (now and after or now and before depending on Undo/Redo) sets of copy objects and Keep, Delete, Paste based on the analysis.
I implemented only 5 functions: Undo, Redo, ResetUndoSystem and 2 for saving the state: SaveState and SaveNewState that are called after and before any modification.
The UndoLevel used as a tag is 0 for normal copy objects and cycle between 1 and MaxRingValue (20 by now), every time the head reaches the tail i simply delete the oldest undo info on the list.

As far as i tested is working say... 99% (better than i spect at first)

i agree that relative changes are a headhache, and no one is so simple as it can seems at first

Juan


jfk EO-11110(Posted 2011) [#4]
Bah, Undo is for the lazy people. Seriously. If I hit UNDO several times, I never know exactly what I've been undoing, esp. in a 3D world editor, where you won't see everything on the screen. More than 10 UNDO Steps won't make much sense IMHO.

Anyway, you may think about to save the entire level after every siginificant change. In theory this would be only a matter of drive space, shouldn't be a problem. It would however allow to undo/redo anything that can be saved. If your level saving routine is fast then this may work well. In my editor the level file is only a text file with a few hundred lines of text, it's saved in a couple of millisecs.

This method may be brute force and very unelegant, but at least it's bulletproof and stabile, and easily implemented (assuming your editor can load a saved level).

Bundle the user actions, eg: moving an item 15 times will save only one undoable copy, to undo moving the item. That's about what eg. Photoshop does.


Charrua(Posted 2011) [#5]
thank's

my editor is incorporating some csg routines, so, in the world should be some meshes (not blitz natives) and i'm saving eshaustive mesh info inside the file, so a world could be very little if only primitives are used or some hundreds of kilobytes if some complex meshes are inside. One aproach could be, save this meshes as .b3d and use them as if you dropped a b3d on the world (wasting a few bytes of the file like it was a primitive)...

Probably some day i take this way.

And, is true, when debuging, i put a counter to see in which undo i am, and some undo/redo seems to do nothing as you say. When adding 2 shapes, the resulting one is visible the same as before, but only in the objects list you see the difference or/and if you select/unselect the objects.

Juan


Warner(Posted 2011) [#6]
Csg routines? May I ask, how did you incorporate those? I'm writing csg routines myself. I spent months getting them to work right.


Charrua(Posted 2011) [#7]
Hi

i just want to thank you!

i'm testing your's (and other with less success)

With some good's and some unespected results.

basically i think that most fails are related with shapes that are side by side but not intercepting each other...

The easy way (sure is not the correct one) was to scale slightly: none, one A or B, or both.

i do very little modifications due to some problems working with meshes with surfaces with diferent brushes.

Now i'm coding sonme weld funtions, not to reduce the amount of vertex, the intention is to joint some vertex that result slightly moved.

if you like to see your csg (with little modifications) in action:

http://blitzbasic.com/Community/posts.php?topic=93544#1073241

thank's again and of course you will be (among others) in the credits

Juan


Warner(Posted 2011) [#8]
That's cool. It seems like a nice program. Very elaborate.