Undo system

BlitzMax Forums/BlitzMax Programming/Undo system

_JIM	(Posted 2009) [#1]

Hi!

I've been trying to think of an implementation of an undo system that can handle undoing pretty much any operation.

So far I cam up with something like a global undo list filled with containers which in turn contain a list of fields that have modified along with their old/new value.

Type UndoContainer
	Global UndoList:TList = New TList
	
	Field Values:TList = New TList
End Type

Type UndoField
	Field OldVal:Float
	Field NewVal:Float
	Field Pointer:Float ptr
End Type

The problem here is the system above can only handle floats. Since there's no templates in BMax, I don't see an easy way of being able to handle any data type.

The other way I can think of is having a list like this:

Type UndoContainer
	Global UndoList:TList = New TList
	
	Field Values:TList = New TList
End Type

Type UndoField
	Field OldVal:Object
	Field NewVal:Object
	Field Caller:Object
End Type

And save an entire object whenever I am modifying something. Even though this works, it would be an awful waste of memory.

Anyone got any brilliant ideas for this?

Evil Roy Ferguson

(Posted 2009) [#2]

I would implement this with a variant of the command pattern and a stack. Something like:

' If you have a Stack with Push(), Top(), and Pop(), you're good to go.
' This won't compile without one.

SuperStrict

' Undo command interface
Type IUndoCommand
    Method Undo() Abstract
End Type

' Undoes setting a float. Unfortunately, the lack of generics in BlitzMax
' does mean you'll also need UndoInt, etc. as well, but at least you'll
' be able to have them all in one UndoStack now.

' To undo other things, create other subclasses of IUndoCommand and
' override the Undo method. These should hold a reference to the object
' to act on. For example, to undo RotateRightBy90,
' you might create a RotateLeftBy90 extension of IUndoCommand that would
' rotate the image left by 90. To undo calling TurnOn(), create an
' IUndoCommand that would call TurnOff().

Type UndoFloat Extends IUndoCommand
    Field _float:Float Ptr
    Field _oldValue:Float

    Method Set:UndoFloat(fl:Float Var)
        _float = Varptr fl
        _oldValue = fl
        Return Self
    End Method

    Method Undo()
        _float[0] = _oldValue
    End Method
End Type

' Holds all of the things to undo. It's just a wrapper around a stack
' that undoes things when they get popped off.
Type TUndoStack
    Field _stack:Stack = New Stack

    Method Push(x:IUndoCommand)
        _stack.Push(x)
    End Method

    Method Undo()
        Local undo:IUndoCommand = IUndoCommand(_stack.Top())
        _stack.Pop()

        undo.Undo()
    End Method
End Type

' A myfloat to test on.
Global myFloat:Float = 20

' I'm just pretending you already have a stack class available...
Local stack:TUndoStack = New TUndoStack
Local undo:IUndoCommand

' Save undo command
undo = New UndoFloat(myFloat)
stack.Push(undo)

' Set myfloat
myFloat = 672
Print myFloat

' Undo setting myfloat
stack.Undo()
Print myFloat

_JIM	(Posted 2009) [#3]

I see. I wouldn't however use a stack due to the simple fact that I might need "Redo" :)

I feared I might have to write a class for each type.

Thanks for the answer. I'll go with this one.

Otus	(Posted 2009) [#4]

You could use a Byte Ptr and a length. Then for Floats you'd actually copy four bytes and for Doubles eight. You could even copy arrays or multiple consecutive Fields if you are careful. As long as you only keep it in memory, you won't have to care about the meaning of the data or endianness.

_JIM	(Posted 2009) [#5]

Otus, that was my first idea, because I am a big fan of "stuff that applies to anything and just works", however I've hit a brick wall with strings. As unusual as they are, I still need to handle them.

Otus	(Posted 2009) [#6]

That's true, but there is a hack around that, if you use the threaded GC. :)

Just save the address of the old string instead of the actual string data. The GC recognizes the reference even if it lives as an Int or a Byte Ptr instead of a String variable, so the old string isn't deleted. You need a lot of casting, though, to make sure the correct value is stored.

You probably shouldn't rely on that behavior, though.

N	(Posted 2009) [#7]

That's true, but there is a hack around that, if you use the threaded GC. :)

I don't think this works unless you're using the BDW GC?, and that was removed if I recall correctly.

I see. I wouldn't however use a stack due to the simple fact that I might need "Redo" :)

Could just do this for redo (sort of modified eel's code - and by modified I mean the principle is probably the same, but the implementation differs):

SuperStrict

Type TFloatAction Extends TAction
    Field _float:Float Ptr
    Field _newValue:Float
    Field _oldValue:Float

    Method Init:TFloatAction(fl:Float Var, newvalue#)
        _float = Varptr fl
        _oldValue = fl
        _newValue = newvalue ' don't actually set the value of fl
        Return Self
    End Method

    Method Undo()
        _float[0] = _oldValue
    End Method
    
    Method Redo()
    	_float[0] = _newValue
	End Method
End Type

' Actions that can be done and undone
Type TAction Abstract
	Method Undo() Abstract
	Method Redo() Abstract
End Type

' Action history - You can push new history, but you can never remove history (this would be bad, unless all your TActions were deltas)
Type TActionHistory
	Field _history:TList = New TList
	Field _head:TLink = Null
	Field _current:TLink = Null
	
	' Spawns a new TActionHistory with all history up to Current
	Method Branch:TActionHistory()
		' No history?  No problem.
		If Not (_head And _current) Then Return New TActionHistory
		
		Local br:TActionHistory = New TActionHistory
		Local f:TLink = _history.FirstLink()
		If f Then
			Repeat
				br.Push(TAction(f.Value()))
				If f = _current Then Exit
				f = f.NextLink()
			Forever
		EndIf
		Return br
	End Method
	
	Method Current:TAction()
		If _current = Null Then Return Null
		Return TAction(_current.Value())
	End Method
	
	Method Push:TActionHistory(action:TAction)
		If Not _current And _head Then
			' If everything has been undone already, but there is history, clear it
			_history.Clear()
		ElseIf _head <> _current
			' If not everything has been undone, but there is history, clear any history ahead of whatever can still be undone
			While _current.NextLink()
				_current.NextLink().Remove()
			Wend
		EndIf
		
		' Make the new action the current undoable action and set the head to that
		_current = _history.AddLast(action)
		_head = _current
		
		Return Self
	End Method
	
	Method Undo%()
		' If there is no current action, nothing is undone
		If Not _current Then Return False
		' Undo the current action and set the current action to whatever is before it (may be null)
		TAction(_current.Value()).Undo()
		_current = _current.PrevLink()
		Return True
	End Method
	
	Method Redo%()
		If _current Then ' If there's already a current action
			' Check to see if this action can be applied (there is history ahead of it)
			Local t:TLink = _current.NextLink()
			' If there is no future history, the current history cannot be applied (it's what happened last)
			If Not t Then Return False
			' Otherwise, set the current history to the next appliable history
			_current = t
		ElseIf _head Then ' Otherwise, if there is history
			_current = _history.FirstLink()
			If Not _current Then Return False
		Else
			' If there is no history, nothing was done
			Return False
		EndIf
		' Apply the now-current history
		TAction(_current.Value()).Redo()
		Return True
	End Method
	
	' Sort of dry-run versions of Redo/Undo
	
	Method CanRedo%()
		Return (_current And _current.NextLink()) Or _history.FirstLink()
	End Method
	
	Method CanUndo%()
		Return _current <> Null
	End Method
End Type

Granted you seem to already know what you want to do, but I was bored and felt like writing bad code. (Warning: very likely to be bugs.)

Czar Flavius

(Posted 2009) [#8]

Yeah I think it's best to put all possible changes you can make into different kinds of "command" objects, rather than modifying things directly. Collect these in some kind of command list, which every now and again (every frame?) you empty and execute. Then to Undo, the opposite to these command objects in an undo list in reverse order. If you want a Redo, then, whenever you Undo, put the reverse again into a Redo list ;)

Zakk	(Posted 2009) [#9]

I don't think any of these strategies will undo the deletion of an object, unless I am mistaken. For that you'd need a TList or something to store deleted objects.

_Skully

(Posted 2009) [#10]

The object would have to be retained within the Undo system.

Czar Flavius

(Posted 2009) [#11]

Every frame, save a memory dump of the entire system on to the hard drive and keep an index. Then you can revert to any prior state with ease :D

Brucey

(Posted 2009) [#12]

Undo frameworks are interesting :-)

Here's an example of an undo framework working in BlitzMax (Win32, 4.5meg)
This example shows Undo and Redo in action using a command-pattern type system.

:-)

Volker

(Posted 2009) [#13]

The UAC will ask for confimation every time you do that.
If you can click 60 times per second Ok, this will work.

_JIM	(Posted 2009) [#14]

Nice example, Brucey, but 15mb (uncompressed) seems a bit too much for an undo system. (yes, i know I can use other features of qt). Currently my game editor has less than 800kb with all interface icons and images incbin-ed.

@Zakk

Type ObjectDeletionUndo

    Field _value:Object
    Field originalList:TList Ptr (does this work?)

    Method Set(list:TList Ptr, value:Object)

EndType

You get the idea. Having the ability to make a derived type from the base interface means I can pretty much do whatever I want.

Sadly, it would mean some heavy modifications to the core to enable a list of commands that execute once per frame and are saved in a global list (or multiple lists by type).

As with other features, I'll probably do this like Roy and Nillium said just to give the level designers something to work with, then work on doing it properly :)

Brucey

(Posted 2009) [#15]

...seems a bit too much for an undo system.

Indeed :-)
But it does show that a "proper" undo/redo is easily appliable to BlitzMax. I think the clickable commands-list is also a nice feature.

Hope you get it sorted out :-)

_JIM	(Posted 2009) [#16]

...it does show that a "proper" undo/redo is easily appliable to BlitzMax. I think the clickable commands-list is also a nice feature.

If I have time, I will eventually end up having something like that, because I love "proper" design :)

Muttley

(Posted 2009) [#17]

I have an open source command stack implementation you could use here: http://code.google.com/p/muttmod/downloads/list

_JIM	(Posted 2010) [#18]

Muttley, thanks!

I finally got to undo/redo on my TODO list and your mod is great. Saves a lot of work. I got support to undo the basics (place, move, delete objects) in a couple of minutes.

Muttley

(Posted 2010) [#19]

Glad you found it useful _JIM.

And, yes, it really did take me 7 months to spot this post. ;)

rs22	(Posted 2010) [#20]

I started using your module after I saw this post a week or so ago, Muttley. It's extremely useful. Thanks for creating it!

Muttley

(Posted 2010) [#21]

Cool.

It's nice to see it being used. :)