Programming an Undo

Hi, I didn't know where to put this as its more of a general design concept, and although I am using Blitz3D, I wanted to hear from some of the Max people too.

I am building a little editor for my game, and I wanted to have an 'undo' feature. I thought I would ask as I can imagine that writing an 'undo' would be much harder after the code is complete.

How I think its done is that for every 'create' function there should also be an 'undo'. So for example, Light_CreateLight() and Light_UndoLight(). This 'undo' function would be similer to the delete/destroy, but any global or variable changes outside of the create function would have to have thier original values saved in the 'create' and restored in the 'undo'.

Then there would have to be a list of undos so it knew which order to go back in?

Advice from anyone who has done an undo feature in an editor, or knows how to go about it is most welcome.

Thanks.

After each change is made, save it to a temp file.

Save an "undo state" for each object before a change is made to it. Then revert to this state when the undo level is changed.

How would you go about creating a history tree of states for an undo?

I can understand the concepts as to how you tackle undo, but when it comes to coding it, I've no idea on how to program the source in a manner that's friendly for reversing actions in a manner that's quick and efficient.

Are there some pseudo-code barebone examples out there?

Here is what I did. It was a pain in the ass.

Global undocontext:TUndoContext=New TUndoContext
undocontext.MaxUndoStates=Int(AppSetting("undolevels","40"))

Rem
Function CleanEntities()
	For Local entity:TEntity=EachIn CurrentWorld().entities
		If entity.userdata
			If Not ObjectSelectable(entity)
				Local kill=1
				For Local o:TObjectState=EachIn TMap(entity.userdata).Values()
					If o.exists
						kill=0
						Exit
					EndIf
				Next
				If kill
					entity.Destroy()
					AppLog "Freeing Entity."
				EndIf
			EndIf
		EndIf
	Next
End Function
EndRem

Type TObjectState
	Field entity:TEntity
	Field mat:TMat4
	Field keys:TMap
	Field path$
	Field exists=1
	
	Method Free()
		Local objectstate:TObjectState
		If entity
			If Not ObjectSelectable(entity)
				If entity.userdata
					Local kill=1
					For objectstate=EachIn TMap(entity.userdata).Values()
						If objectstate<>Self
							If objectstate.exists
								kill=0
								Exit
							EndIf
						EndIf
					Next
					If kill
						entity.userdata=Null
						entity.Destroy()
						'AppLog "Freeing entity..."
					EndIf
				EndIf
			EndIf
		EndIf
		If entity.userdata TMap(entity.userdata).remove(entity)'remove(Self)
		entity=Null
		exists=0
	EndMethod
	
	Method Restore()
		If exists
			entity.Show()
			entity.setmatrix(mat)
			entity.keys=keys
			UpdateEntityKeys(entity)
			MakeObjectSelectable(entity)
			If terrain
				If Int(entity.getkey("aligntoterrain"))
					entity.aligntoterrain(terrain)
				EndIf
			EndIf
			If TBody(entity) TBody(entity).reset()
		Else
			entity.Hide()
			DeselectObject(entity)
			MakeObjectUnselectable(entity)
		EndIf
	End Method
	
	Function Create:TObjectState(o:Object,context:TUndoContext)
		Local entity:TEntity=TEntity(o)
		Local objectstate:TObjectState
		objectstate=New TObjectState
		objectstate.entity=entity
		objectstate.mat=entity.mat.Copy()
		objectstate.keys=entity.keys.copy()
		objectstate.exists=1
		If entity.userdata=Null entity.userdata=New TMap
		TMap(entity.userdata).insert(objectstate,objectstate)
		undocontext.current.objectstates.insert(entity,objectstate)
		Return objectstate
	EndFunction
	
EndType

Type TUndoContext
	Field undostates:TList=New TList
	Field current:TUndoState
	Field MaxUndoStates:Int=0
	
	Method New()
		Init()
	EndMethod

	Method Init()
		current=New TUndoState
		current.link=undostates.AddFirst(current)
	End Method
		
	Method CreateState()
		Local entity:TEntity
		Local link:TLink
		If current
			link=current.link.nextlink()
			While link
				TUndoState(link.Value()).free()
				link=current.link.nextlink()
			Wend
		EndIf	
		current=New TUndoState
		current.link=undostates.AddLast(current)
		For entity=EachIn SelectedObjects()
			TObjectState.Create(entity,Self)
		Next
		If MaxUndoStates>0
			While undostates.Count()>MaxUndoStates
				link=undostates.FirstLink()
				TUndoState(link.Value()).free()
			Wend
		EndIf
		EnableGadget Menu_Undo
		EnableGadgetItem Toolbar,TOOLBARBUTTON_UNDO
		UpdateWindowMenu MainWindow
	EndMethod
	
	Method UndoAvailable:Int()
		If current.link.prevlink() Return 1
	EndMethod
	
	Method RedoAvailable:Int()
		If current.link.nextlink() Return 1	
	EndMethod
	
	Method RollBack()
		Local entity:TEntity
		Local objectstate:TObjectState
		If current=Null Return
		If current.link.prevlink() current=TUndoState(current.link.prevlink().value())
		If current
			For objectstate=EachIn current.objectstates.values()
				objectstate.restore()
			Next
		EndIf
	EndMethod
	
	Method RollForward()
		Local objectstate:TObjectState
		If current=Null Return
		If current.link.nextlink() current=TUndoState(current.link.nextlink().value())
		If current
			For objectstate=EachIn current.objectstates.values()
				objectstate.restore()
			Next
		EndIf
	EndMethod
	
	Method Clear()
		For Local undostate:TUndoState=EachIn undostates
			undostate.free()
		Next
		Init()
		DisableGadgetItem Toolbar,TOOLBARBUTTON_UNDO
		DisableGadgetItem Toolbar,TOOLBARBUTTON_REDO
		DisableGadget Menu_Undo
		DisableGadget Menu_Redo
		UpdateWindowMenu MainWindow
	EndMethod
	
EndType

Type TUndoState
	Field link:TLink
	Field objectstates:TMap=New TMap
	
	Method free()
		'applog "Freeing state"
		Local objectstate:TObjectState
		For objectstate=EachIn objectstates.values()
			objectstate.free()
		Next
		objectstates.Clear()
		If link link.Remove()
		link=Null
	EndMethod
	
EndType

Use the Command pattern.

Can I use these methods in Blitz3D? Without looking at them quite deeply they seem to both rely on OOP techniques.