Undo and Redo: Yes you have to implement it

A professional developer on the gamedev.net forums once said “if you’ve implemented Undo and Redo in your app, then you’re in the top 1% of applicants for a tools developer position”.  That’s funny to me, because I have no idea how you could possibly have a useful tool without such a fundamental element of GUI application development.  I mean…people screw up.  It’s nice for users to know that their mistake can go away with a single press of “ctrl+z”.

When I first started working on the map editor for my game JumpSwitch, I put Undo/Redo functionality in there right away.  Like I said, it’s fundamental.  The problem was, I implemented it probably the most naive way possible.  See I handled saving and loading by having my Level class dump a whole bunch of data into a LevelData class, and then serializing that to XML.  So I thought “hey, I’ll just hang onto an array of these LevelData instances and then load them up when the user wants to Undo or Redo!”  Yeah I know, dumb.  Feel free to laugh.  Worked okay when my level had under a dozen entities hanging around, but anything after that meant you were waiting 3 or more seconds.  Not exactly what I’d call a fast and responsive UI.

So….what had to be done?  I had to stop being lazy and do Undo and Redo for real.  This we got a little more sophisticated:

-Make an abstract “EditAction” class, that represents a single action taken by the user to edit the level.  Give it virtual methods for “Undo” and “Redo”
-Make a few classes that inherit from EditAction and implement Undo and Redo for a specific action (moving an object, rotating an object, adding/removing an object, changing a Property, etc.)
-MapEditorLevel class has two stacks of EditAction’s: an Undo stack and a Redo stack.  When the user performs an action, it’s pushed onto the Undo stack and the Redo stack is cleared.  When the user does an Undo, the Undo stack is popped, Undo is called on that EditAction, and the action is pushed onto the Redo stack. When the user does a Redo, the Redo stack is popped, Redo is called, and the action is pushed onto the Undo stack.

/// <summary>
    /// Represents a single action taken by the user to edit the level,
    /// and that can be Undone/Redone.
    /// </summary>
    public abstract class EditAction
    {
        protected MapEditorLevel level;

        public EditAction(MapEditorLevel level)
        {
            this.level = level;
        }

        /// <summary>
        /// Undoes the action
        /// </summary>
        public abstract void Undo();

        /// <summary>
        /// Redoes the action
        /// </summary>
        public abstract void Redo();
    }

    /// <summary>
    /// Handles undo/redo for a rotation of a GameObject
    /// </summary>
    public class RotateAction : EditAction
    {
        GameObject[] targetObjects;
        Matrix rotation;
        Matrix inverseRotation;

        public RotateAction(MapEditorLevel level, GameObject[] targetObjects, Matrix rotation)
            : base(level)
        {
            this.targetObjects = targetObjects;
            this.rotation = rotation;
            inverseRotation = Matrix.Invert(rotation);
        }

        public override void Undo()
        {
            foreach (GameObject targetObject in targetObjects)
                targetObject.PropogateRotation(ref inverseRotation);
        }

        public override void Redo()
        {
            foreach (GameObject targetObject in targetObjects)
                targetObject.PropogateRotation(ref rotation);
        }
    }

/// <summary>
    /// Handles UndoRedo for properties
    /// </summary>
    public class PropertyEditAction : EditAction
    {
        PropertyInfo property;
        object[] oldValues;
        object newValue;
        object[] propertyOwners;

        public PropertyEditAction(MapEditorLevel level, object[] propertyOwners, object[] oldValues, string propertyName)
            : base(level)
        {
            this.oldValues = oldValues;
            this.propertyOwners = propertyOwners;

            Type ownerType = propertyOwners[0].GetType();

            // Find the property
            property = ownerType.GetProperty(propertyName);

            // Get the new value
            newValue = property.GetValue(propertyOwners[0], null);
        }

        public override void  Undo()
        {
            for (int i = 0; i < propertyOwners.Length; i++)
                property.SetValue(propertyOwners[i], oldValues[i], null);
        }

        public override void Redo()
        {
            for (int i = 0; i < propertyOwners.Length; i++)
                property.SetValue(propertyOwners[i], newValue, null);
        }
    }

    // You get the idea...

Alright, looks like a solid plan.  It worked out very nicely for movement and rotation.  Movement is just translation which is a vector, so if you negate it you get the Undo.  For the rotations, it’s a matrix so you just invert it.  Piece of cake.  Adding and removing…a little more tricky since I had to also keep track of an object’s parent so I’d know where to re-add the object.  But still not too bad.  Changing properties…not so nice.  The problem is that when the user changes the value of a property with the PropertyGrid, it fires a PropertyValueChanged event that lets you know what changed, and what the old value was.  Perfect, right?  Well yes…but only for single objects.  When you have multiple objects selected in the PropertyGrid you get “null” instead of the old value.  Fantastic.  Workaround  time…

-Handle the SelectedGridItemChanged event for the PropertyGrid
-Store the current value of the selected Property for all selected objects in an array
-Handle PropertyValueChanged
-Make an array of current Property values
-Send it all off to the MapEditorLevel so it can create an appropriate EditAction and push it onto the stack

Okay, so this works. Only problem left with that is that when you set the value of a Property through PropertyInfo.SetValue, the PropertyGrid doesn’t reflect the changes.  Still haven’t figured out a workaround for that one…

So in the end it was a little messy, but not that bad.  It only took me a single evening in fact.  Certainly nothing worthy of that frightening 99% statistic, IMO.   Besides…if you don’t implement it, it’s going to be first thing your designers and artists complain to you about anyway. 😛

2 thoughts on “Undo and Redo: Yes you have to implement it

  1. hehe, i think that comment regarding the top 1% of tool devs sounds a lot like i said it (because no-one actually implements it – and it’s the bain of my life). Nice article btw, it’s surprising how many people still overlook the basics of undo/redo, it can be relatively straightforward – but it can quickly become quite hacky and laborious to maintain.

    My next question then, is how would your system work with app level scripting? How will your method be applied to custom user scripts (to create game objects, modify all objects of a similar type etc) in a way that enables undo/redo to work for custom user tools? Think about that for a minute before continuing ….

    There are a few ways you can approach it, but logically extending your approach will leave you with an approach fairly similar to maya’s. Ultimately all commands in maya are represented with an MPxCommand object, which performs the undo/redo actions.

    With maya’s way of doing this, you’d start by modifying your EditAction class to contain a list of sub actions. Your Edit Action class can now represent a script call (where each unique command has it’s own EditAction class), and the undo/redo steps actually becomes a hierarchy of undo/redo actions rather than a single step. e.g.

    proc foo()
    {
    createBox();
    }

    proc bar()
    {
    setValue(“someObject.translate”,1,2,3);
    foo();
    }

    so bar() will store 2 sub actions, setValue() and foo(). foo() will store the subaction createBox().

    (It might be worth pointing you at some docs for MPxCommand at this point: http://caad.arch.ethz.ch/info/maya/manual/DevKit/PlugInsAPI/classDoc/MPxCommand.html )

    – doIt builds up an internal list of what the command is going to do
    – redoIt performs those actions and nothing else.
    – undoIt simply performs the inverse of those actions.

    It’s important to note that doIt() will always call redoIt() after it’s built up the internal list. That way you save on code duplication. It’s then worth noting that every single user action (be it clicking on a button, moving an object with a mouse, opening a file etc) has to be executed as a script command. This basically simplifies all of the undo/redo for the whole app into a single command interface.

    Maya does have a fairly nice class that aims to try to wrap up a lot of the common undo/redo actions (see: http://caad.arch.ethz.ch/info/maya/manual/DevKit/PlugInsAPI/classDoc/MDagModifier.html ). The only problem is that quite often, that class just isn’t good enough, and so you have to do all of that manually. which sucks. a lot.

    A bigger problem with this technique is that you end up having to implement an awful lot of boilerplate code for a lot of commands, eg…

    http://caad.arch.ethz.ch/info/maya/manual/Commands/index.html

    and whilst it works…. it quickly becomes a royal PITA to maintain, with a hell of a lot of bugs thrown in for comedy value.

    I have seen a couple of clever ways to automate the whole undo/redo process, which are a dream to work with. Unfortunately i can’t comment on those due to NDA’s, but it might give you something to think about😉

    Rob.

  2. Indeed…I didn’t have to create too many more EditAction derivatives before I realized how much of a pain the system was to extend and maintain. It really doesn’t help that I keep making big changes to the map editor…unfortunately it’s the first (3D) editor I’ve ever made and without experience behind me I just keep running into problems that seem obvious in hindsight. But I’m learning I suppose.🙂

    That Maya API stuff is really interesting. Like you said…on one hand it works since the basic underlying system is generic, but after a while it all just explodes into this huge monster. I have enough trouble keeping my EditAction’s from glitching…I can’t imagine trying to maintain the amount of commands they have available.

    When I first starting implementing the system I have right now, I had a few visions in my head of a system where the user/map boundary was designed in such a way that any modifying of the map was just a generic transaction that could be easily understood by the Undo/Redo system without having to write specific code to handle it. What I’m doing with the PropertyGrid is actually sorta in that direction…I do a lot of custom stuff with the PropertyGrid control and (for the most part) my Undo/Redo stuff works for that without me having to do anything special. I figure if you planned out right, you could probably extend that somehow (probably using a lot of Attributes for metadata) to make an automatic (or mostly automatic) system…at least for a managed app, anyway. I’d love to refactor what I have into something that would make this work…but unfortunately I’ve got a thousand other things to do for the project and almost zero free time to do them. In fact I wish I had more time to devote to tool development in general…I really enjoy it but at the moment I have to keep bouncing back and forth to different areas and subsystems.

    Anyway, thank you so much for comments! It’s nice to discuss these things with someone…it’s not a popular topic on the forums I’m afraid. I also greatly appreciate the insights you’ve offered…especially the ones that aren’t NDA’ed. 😛

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s