Home
Blogs
Forums
News
Portfolios
Projects
Tutorials
25 users logged in
New? Learn about game development.
Before posting, review our community guidelines.
Follow Us
Chat in the GameDev.net Discord!
Mastodon
Back to General and Gameplay Programming

[C#] List for generic undo redo and Mementos

Started by
12 comments, last by Spa8nky 12 years, 7 months ago
Currently I can undo and redo voxels/tiles using the following Interface and IMemento based classes:



public interface IMemento<T>
{
IMemento<T> Restore(T target);
}


abstract class TileMemento : IMemento<Tile[]>
{
public abstract IMemento<Tile[]> Restore(Tile[] target);
}

class AddTileMemento : TileMemento
{
private int index;

public AddTileMemento(int index)
{
this.index = index;
}

public override IMemento<Tile[]> Restore(Tile[] target)
{
Tile removed = target[index];

IMemento<Tile[]> inverse = new RemoveTileMemento(index, removed);

target[index] = null;

return inverse;
}
}

class RemoveTileMemento : TileMemento
{
private int index;
private Tile removed;

public RemoveTileMemento(int index, Tile removed)
{
this.index = index;
this.removed = removed;
}

public override IMemento<Tile[]> Restore(Tile[] target)
{
IMemento<Tile[]> inverse = new AddTileMemento(index);

target[index] = removed;

return inverse;
}
}


These classes are added to an undo/redo history class:



public class UndoRedoHistory<T>
{
/// <summary>
/// The subject that this undo redo history is about
/// </summary>
protected T subject;

...


which is accessed with the 'Ctrl'+'Z' and 'Ctrl'+'Y' commands:



// [Redo]
if (isControlDown && hid.IsKeyHit(PlayerIndex.One, Microsoft.Xna.Framework.Input.Keys.Y))
{
if (level.UndoRedoHistory.CanRedo)
{
level.UndoRedoHistory.Redo();
}
}

// [Undo]
if (isControlDown && hid.IsKeyHit(PlayerIndex.One, Microsoft.Xna.Framework.Input.Keys.Z))
{
if (level.UndoRedoHistory.CanUndo)
{
level.UndoRedoHistory.Undo();
}
}


The problem is that the UndoRedoHistory class can only store one type for T for each instance.

If I would like to search an UndoRedoHistory that involves other types of objects and their mementos other than just 'Tile' but in order of action, how would I go about such a process?

So for example the UndoRedoHistory could contain:

TileMemento // Add tile action
LightMemento // Changed light intensity action
EntityMemento // Removed an entity
Advertisement
Well rather than storing commands to be acted on object store commands that have objects bound. So instead of having a Restore(T target) member, just have a Restore() member and store the target as part of the concrete object.

[color="#1C2837"]Well rather than storing commands to be acted on object store commands that have objects bound. So instead of having a Restore(T target) member, just have a Restore() member and store the target as part of the concrete object.
[color="#1c2837"][/quote]

[color="#1c2837"]I'm a little confused by that.

[color="#1c2837"]If I just have Restore for the IMemento:

[color="#1c2837"]
public interface IMemento<T>
{
IMemento<T> Restore();
}


[color="#1c2837"]then I can't store a global list of IMementos that can be done/undone despite the different object types they refer to, as the T would need to refer to a single object type.
Don't parameterize the interface. Store a base interface type.
Could you please give an example? I'm not sure how that would work with the UndoRedoHistory class:



[Serializable]
public class UndoRedoHistory<T>
{
/// <summary>
/// The subject that this undo redo history is about
/// </summary>
protected T subject;

private const int DEFAULT_CAPACITY = 100;

private bool supportRedo = true;
private bool inUndoRedo = false;

[NonSerialized]
private CompoundMemento<T> tempMemento = null;

/// <summary>
/// Undo stack with capacity
/// </summary>
protected RoundStack<IMemento<T>> undoStack;

/// <summary>
/// Redo stack with capacity
/// </summary>
protected RoundStack<IMemento<T>> redoStack;

/// <summary>
/// Creates <see cref="UndoRedoHistory<T>"/> with default capacity.
/// </summary>
/// <param name="subject"></param>
public UndoRedoHistory(T subject)
: this(subject, DEFAULT_CAPACITY)
{
}

/// <summary>
/// Creates <see cref="UndoRedoHistory<T>"/> with given capacity.
/// </summary>
/// <param name="subject"></param>
/// <param name="capacity"></param>
public UndoRedoHistory(T subject, int capacity)
{
this.subject = subject;
undoStack = new RoundStack<IMemento<T>>(capacity);
redoStack = new RoundStack<IMemento<T>>(capacity);
}

/// <summary>
/// Gets a value indicating if the history is in the process of undoing or redoing.
/// </summary>
/// <remarks>
/// This property is extremely useful to prevent undesired "Do" being executed.
/// That could occur in the following scenario:
/// event X causees a Do action and certain Undo / Redo action causes event X,
/// i.e. Undo / Redo causes a Do action, which will render history in a incorrect state.
/// So whenever <see cref="Do(IMemento<T>)"/> is called, the status of <see cref="InUndoRedo"/>
/// should aways be checked first. Example:
/// <code>
/// void SomeEventHandler()
/// {
/// if(!history.InUndoRedo)
/// history.Do(...);
/// }
/// </code>
/// </remarks>
public bool InUndoRedo
{
get { return inUndoRedo; }
}

/// <summary>
/// Gets number of undo actions available
/// </summary>
public int UndoCount
{
get { return undoStack.Count; }
}

/// <summary>
/// Gets number of redo actions available
/// </summary>
public int RedoCount
{
get { return redoStack.Count; }
}

/// <summary>
/// Gets or sets whether the history supports redo.
/// </summary>
public bool SupportRedo
{
get { return supportRedo; }
set { supportRedo = value; }
}

/// <summary>
/// Begins a complex memento for grouping.
/// </summary>
/// <exception cref="InvalidOperationException">
/// Thrown if previous grouping wasn't ended. See <see cref="EndCompoundDo"/>.
/// </exception>
/// <seealso cref="EndCompoundDo()"/>
public void BeginCompoundDo()
{
if (tempMemento != null)
{
throw new InvalidOperationException("BeginCompoundDo cannot be called again until EndCompoundDo has been successfully called.");
}

tempMemento = new CompoundMemento<T>();
}

/// <summary>
/// Ends grouping by pushing the complext memento created by <see cref="BeginCompoundDo"/> into the undo stack.
/// </summary>
/// <remarks>
/// For details on how <i>grouping</i> works, see <see cref="BeginCompoundDo"/>.
/// </remarks>
/// <exception cref="InvalidOperationException">
/// Thrown if grouping wasn't started. See <see cref="BeginCompoundDo"/>.
/// </exception>/// <seealso cref="BeginCompoundDo()"/>
public void EndCompoundDo()
{
if (tempMemento == null)
{
throw new InvalidOperationException("BeginCompoundDo must be called successfully before EndCompoundDo can be called.");
}

_Do(tempMemento);
tempMemento = null;
}

/// <summary>
/// Pushes an memento into the undo stack, any time the state of <see cref="subject"/> changes.
/// </summary>
/// <param name="m"></param>
/// <remarks>
/// This method MUST be properly involked by programmers right before (preferably) or right after
/// the state of <see cref="subject"/> is changed.
/// Whenever <see cref="Do(IMemento&lt;T&gt;)"/> is called, the status of <see cref="InUndoRedo"/>
/// should aways be checked first. See details at <see cref="InUndoRedo"/>.
/// This method causes redo stack to be cleared.
/// </remarks>
/// <seealso cref="InUndoRedo"/>
/// <seealso cref="Undo()"/>
/// <seealso cref="Redo()"/>
public void Do(IMemento<T> m)
{
if (inUndoRedo)
{
throw new InvalidOperationException("Invoking Do within an undo/redo action.");
}

if (tempMemento == null)
{
_Do(m);
}
else
{
tempMemento.Add(m);
}
}

/// <summary>
/// Internal <b>DO</b> action with no error checking
/// </summary>
/// <param name="m"></param>
private void _Do(IMemento<T> m)
{
redoStack.Clear();
undoStack.Push(m);
}

/// <summary>
/// Restores the subject to the previous state on the undo stack, and stores the state before undoing to redo stack.
/// Method <see cref="CanUndo()"/> can be called before calling this method.
/// </summary>
/// <seealso cref="Redo()"/>
public void Undo()
{
if (tempMemento != null)
{
throw new InvalidOperationException("The complex memento wasn't commited.");
}

inUndoRedo = true;
IMemento<T> top = undoStack.Pop();
redoStack.Push(top.Restore(subject));
inUndoRedo = false;
}

/// <summary>
/// Restores the subject to the next state on the redo stack, and stores the state before redoing to undo stack.
/// Method <see cref="CanRedo()"/> can be called before calling this method.
/// </summary>
/// <seealso cref="Undo()"/>
public void Redo()
{
if (tempMemento != null)
{
throw new InvalidOperationException("The complex memento wasn't commited.");
}

inUndoRedo = true;
IMemento<T> top = redoStack.Pop();
undoStack.Push(top.Restore(subject));
inUndoRedo = false;
}

/// <summary>
/// Checks if there are any stored state available on the undo stack.
/// </summary>
public bool CanUndo
{
get { return (undoStack.Count != 0); }
}

/// <summary>
/// Checks if there are any stored state available on the redo stack.
/// </summary>
public bool CanRedo
{
get { return (redoStack.Count != 0); }
}

/// <summary>
/// Clear the entire undo and redo stacks.
/// </summary>
public void Clear()
{
undoStack.Clear();
redoStack.Clear();
}

/// <summary>
/// Gets, without removing, the top memento on the undo stack.
/// </summary>
/// <returns></returns>
public IMemento<T> PeekUndo()
{
return undoStack.Count > 0 ? undoStack.Peek() : null;
}

/// <summary>
/// Gets, without removing, the top memento on the redo stack.
/// </summary>
/// <returns></returns>
public IMemento<T> PeekRedo()
{
return redoStack.Count > 0 ? redoStack.Peek() : null;
}
}
What SiCrane means is that make your undo/redo class object oblivious. Don't store the tile handle, but rather do something like this (below code doesn't use templates):



class BaseClass {};

class Tile : public BaseClass {}

class UndoCommand
{
//used for create/undo operations to know which type of object to instantiate
UINT iObjectType;
//use std::map or a custom storage holder to store the basic arguments needed to re-create an object if needed. Store only the minimum amount of information required here.
ArgList pList;
//a handle to the object; you can use this for caching (eg when you remove the object from the active list in your app, but don't deallocate it to speed up undo/redo operations
//by simply copying the object pointer to the undo stack; you can also use this for simple operations that do not affect memory operations, eg when translating, rotating or scaling
//an object (or changing one of its parameters) to speed things up a lot)
BaseClass* objHandle;
//something basic like UNDO_DELETE, UNDO_CREATE_ UNDO_TRANSLATE, UNDO_MODIFYPROPERTY, etc
UINT iCommand;
}
Your interface should not be generic and each memento target bundled in the memento.

With that change the UndoRedo class also does not require to be a generic and can handle any memento from anywhere for any instance.


public interface IMemento
{
IMemento Restore();
}



class AddTileMemento : IMemento
{
private int index;
Tile[] target;
public AddTileMemento(Tile[] target, int index)
{
this.target = target;
this.index = index;
}

public override IMemento Restore()
{
Tile removed = target[index];

IMemento inverse = new RemoveTileMemento(target, index, removed);

target[index] = null;

return inverse;
}
}


class RemoveTileMemento : IMemento
{
private int index;
private Tile removed;
Tile[] target;
public RemoveTileMemento(Tile[] target, int index, Tile removed)
{
this.target = target;
this.index = index;
this.removed = removed;
}

public override IMemento Restore()
{
IMemento inverse = new AddTileMemento(target, index);

target[index] = removed;

return inverse;
}
}
Thanks Gorg. When thinking of a C# implementation I came up with something similar but I wasn't sure if this is what SiCrane and irreversible were getting at.

Things that made me think I was doing it wrong:



UINT iObjectType;
UINT iCommand;


These could be implemented as enums.

What would happen if I was translating more than one tile?

I could store the indices for each tile and recreate them or I would have to create a copy of the array each time it changed so the previous indices could be restored, but that would no doubt consume a lot of memory.

I'm not sure how this translates to C# either:




//a handle to the object; you can use this for caching (eg when you remove the object from the active list in your app, but don't deallocate it to speed up undo/redo operations
//by simply copying the object pointer to the undo stack; you can also use this for simple operations that do not affect memory operations, eg when translating, rotating or scaling
//an object (or changing one of its parameters) to speed things up a lot)
BaseClass* objHandle;

These could be implemented as enums.


How you store these is up to you - you can use enums, define lists, strings or whatnot.



What would happen if I was translating more than one tile?



One way would be to store selection as an undo action and undo the moving as group undo of two user actions: (1) deselect range->select range (if the last action the user did was to deselect the range), (2) move tiles. The main thing you have to decide on is how undo commands are automatically grouped (normally you'll want a group to end when the user commits a change, such as removing/creating/translating/scaling/rotating and object and store all other commands (select/deselect/move caret for text controls etc) as soft commands that are always executed as a group until a real command is encountered. In this case the translation itself is stored as a translation action with zero additional information. However, instead of the regular selection.pos += moveAmount you implement its inverse selection.pos -= moveAmount.


I'm not sure how this translates to C# either:



Sorry, I can't help you with C# :(. The undo mechanism, however, remains the same no matter what language you implement it in.
Command Pattern.

Instead of modifying state directly, all actions are applied by creating commands. Each of these derives from base interface:interface Command {
void perform();
void undo();
};

Let's say you want to draw a tile:
class SetTileCommand : Command {
void perform() {
oldColor = map.get(x, y);
map.set(x, y, newColor);
}
void undo() {
map.set(x, y, oldColor);
}
Map map;
private Color oldColor;
private Color newColor;
private int x;
private int y;
};


It should be obvious how undo now becomes merely a list of these commands. To undo, call unto() on them as far as needed.


Such approach tends to be better for coarse-grained actions, but a few thousand actions should not be a big deal.

For fancy and advanced undo, you would introduce coalescing - if several actions of same type are applied consecutively, you can merge them into a single super action. A generic solution might involve reflection or you could just manually code it. Something like:class GroupedSetTileAction {

...
List<int> x;
List<int> y;
List<int> oldColor;
List<int> newColor;
...
};

Then, when applying an action, if it's the same type as previous, you append to previous action, otherwise you create a new command.

This topic is closed to new replies.

Advertisement

Popular Topics

aigan
The promise of freedom in story games Game Design and Theory
Nosey
Ideas for a new genre (anonimous) Game Design and Theory
KielanT
DirectX 12 Renderer Graphics and GPU Programming
MrK45
Inheriting from application registered class AngelCode
The Luke
How can i make an event system? Engines and Middleware
Advertisement

Recommended Tutorials

Myopic Rhino
Tile-Based Games FAQ version 1.2 General and Gameplay Programming
Myopic Rhino
Large Animal Games Interviews
Myopic Rhino
The Physics of Racing, Part 14: Why Smoothness? Math and Physics
Myopic Rhino
Linux Game Development Part 1 General and Gameplay Programming
Myopic Rhino
Introversion Software Interviews

Reticulating splines

About GameDev.net
Community Guidelines
Terms of Service
Privacy Policy
Contact Us
Copyright (c) 1999-2024 GameDev.net, LLC
Back to Top