Pandemonium

August 5, 2008

At Your Command

Filed under: Games Development,Tools and Software Development — bittermanandy @ 11:11 pm

Previously I wrote at some length about tips and tricks you can use to ease your game development. The focus for these articles was code-facing techniques to help you identify and diagnose bugs, and easily provide data about the current state of whichever facet of the game world you’re currently interested in. Code is only half of what makes a game – less than half, really, and a smaller proportion the bigger the game gets; most of what makes a modern game is art, design, and music content – and when it comes to generating content, you need good tools. Today I would like to talk about a feature of your game editor tools that you really shouldn’t try to live without: infinite undo and redo. Once again, I’ll provide an implementation from the Kensei library, at the end.

I won’t lie to you; there’s rather more work involved in setting up undo and redo than in, say, using Kensei.Dev.GetOption(), but I can guarantee it’s worth the effort, even if you’re in a team of one (can you imagine using Visual Studio without being able to hit Ctrl-Z to undo?) but especially if you’re in a team of many (particularly arty, creative, temperamental types, who are liable to hit you over the head with a shovel shouting “UNDO THIS, ASSHOLE!” if their tools are awkward to use – and understandably so). In fact, it’s fair to say that “tools programmer” is now a full time position at most modern games companies; you may not have time to work full-time on tools if you’re doing this for a hobby, but the ability to undo and redo is a feature that is sure to save you time in the long run.

I first read about how to implement infinite undo/redo in the so-called Gang of Four book, which came as something of a relief as until that point there had been nothing in it of any use whatsoever beyond stating the obvious. Gamma et. al. designate this the “Command Pattern”, because at its core lies the concept of encapsulating user commands as objects; to me, that’s not a great name as you can encapsulate user commands as objects and still not have infinite undo and redo. Nevertheless, to avoid confusion I will be using the established terminology in this article and accompanying code.

Let’s imagine your game has an Editor mode (or perhaps you have a separate Editor tool; it’s not important). Let’s further imagine that one of the key variables in your game is the Health of your Player. Taking the line of least resistance, you provide a mechanism (menu option? Dialog box? Command prompt? Property Grid or Reflection? Keyboard shortcut? All of the above, each calling the same function?) for the user to edit the starting value:

    LevelData.Player.Health = userInput;

Pretty straightforward. Until, that is, one day while using your Editor, you decide the player’s health is too low, so you use your Editor to increase it to 250, but then you have second thoughts, and can’t remember if it used to be 210 or 220. The first step in the solution, as noted above, is to encapsulate user input as an object:

    abstract public class ICommand

    {

        abstract public void Execute();

    }

 

    class SetPlayerHealth : ICommand

    {

        public int newHealth;

 

        public SetPlayerHealth( int health )

        {

            newHealth = health;

        }

 

        public override void Execute()

        {

            LevelData.Player.Health = newHealth;

        }

    }

 

    // … Loads of other code …

 

    ICommand cmd = new SetPlayerHealth( newHealth ); 

    cmd.Execute();

A few points to note here: firstly, throughout, I’m using public variables only to keep things simple. Secondly, you can probably guess already that you have to be very careful with the accessibility of your interface; if the code elsewhere can also set LevelData.Player.Health directly, it will be too easy for the code to change it without using a SetPlayerHealth object. Thirdly, you may still wish to wrap the command object behind a function so the external call remains the same. Fourthly, “Execute” is the term used by the GoF, so I use the same term here; I guess they thought “Do” wasn’t pretentious enough.

We’ve not really changed very much yet though. The trick is that, instead of calling Execute ourselves, we push it onto a stack owned by the Editor, and it’s the stack that is responsible for calling Execute:

    public class CommandStack

    {

        public Stack<ICommand> commands = new Stack<ICommand>();

 

        public void AddCommand( ICommand command )

        {

            command.Execute();

            commands.Push( command );

        }

    }

Now that we have a stack, any time the user hits Ctrl-Z we can take the last command off the top of the stack, reverse its effects (ie. undo it), and do that as many times as we like until we get all the way back to where we started, if we want to. (The stack can grow as large as the memory in our PC, hence, “infinite” undo/redo). Of course, we’ve not yet defined how to reverse a command, which we will do now:

    abstract public class ICommand

    {

        abstract public void Execute();

        abstract public void Unexecute();

    }

 

    class SetPlayerHealth : ICommand

    {

        public int newHealth;

        public int oldHealth;

 

        public SetPlayerHealth( int health )

        {

            // Store old state before changing it to the requested new state

            oldHealth = LevelData.Player.Health;

            newHealth = health;

        }

 

        public override void Execute()

        {

            // Set the new state

            LevelData.Player.Health = newHealth;

        }

 

        public override void Unexecute()

        {

            // Restore the old state

            LevelData.Player.Health = oldHealth;

        }

    }

 

    public class CommandStack

    {

        public Stack<ICommand> commands = new Stack<ICommand>();

 

        public void AddCommand( ICommand command )       

        {

            command.Execute();

            commands.Push( command );

        }

 

        public void Undo()

        {

            ICommand command = commands.Pop();

            command.Unexecute();           

        }

    }

Stripped of all irrelevant detail that’s all there is to it. But we don’t need to stop there; there is some very low-hanging fruit that we can pluck to improve this feature yet further.

The most obvious next step is to support redo as well as undo. Very simply, this requires adding a second stack (redoCommands) to our CommandStack. Every time we pop a command off the main stack, after calling Unexecute, we push it onto the redo stack; and to redo, we simply pop off the redo stack, Execute it, and push it onto the main stack. If a new command is added, we empty the redo stack, as you can’t redo something when you’ve done something different since undoing it. If that doesn’t make sense, draw yourself a diagram, think about how Undo/Redo works in Visual Studio, and it should all become clear.

Speaking of Visual Studio – if you type in “abcdef” then hit Ctrl-Z, it will delete the whole string rather than leave you with “abcde”. Evidently, the “add text” command behind the scenes in Visual Studio isn’t limited to single characters. Instead, with the first key press, “add text: a” is added to the command stack, then when the second key is pressed, rather than adding a new command, the top command is modified to represent “add text: ab”. I’m not sure if there is an official term for this; I call it “merging” commands. It’s not too hard to implement, but the code I provide in a moment shows how anyway.

I’ll not go into detail on some of these other features, though again the supplied code implements them; but it would be nice to tie the Command Stack to the Editor’s Save system, so we can provide a “Save changes before closing?” dialog box when the user clicks “Exit” or similar. This is simply a case of recording the size of the stack every time the Editor saves the data file, and if we Do, Undo or Redo away from that size, mark the command stack as dirty. Additionally, some commands are too complex or destructive for us to be able to Undo them. In that case, we’ll need to warn the user (this part is left up to the calling code) then, once the command is executed, clear the undo and redo stacks – they will no longer be valid.

You can download Kensei.CommandStack here. You are, as always, free to do anything you like with it, including use it or not use it, as long as you don’t blame me if something goes wrong. Or, you can use the techniques I’ve discussed to come up with something different – perhaps even something better. Please tell me about it if you do.

I would just like to mention some final caveats:

  • This is an all-or-nothing system. If some parts of your Editor implement the Command Pattern and other parts do not, bad things will happen. At best, you will confuse your user. At worst, you may leave your data files in an invalid state with no way to recover from the damage.
  • Execute() and Unexecute() must be exact opposites of one another with no side effects. An Undo system that does something other than actually Undoing is no use at all. This is an ideal situation for unit tests; I recommend that you do as I say, not as I do, as Kensei.CommandStack doesn’t come with a unit test suite. Sorry.
  • It may be tempting to say, “aha! To Unexecute, I simply need to restore the game world state to what it was before I Executed. So if I just store the whole world state in my command objects, that will be all I need to be able to Unexecute!” Don’t be tempted. It’s not unreasonable for game world data to approach 5MB in a simple game; in a more complex game, it can be 100MB or more. (Compare that to the 20 bytes or so required for SetPlayerHealth, above). Just ten “Executes” later, with each storing the whole game state, and you’ve used 1GB of memory in your CommandStack. Even if you don’t run out completely, Windows will eventually start swapping memory with the hard disk and your tool will be unusably slow. Not an improvement. Store the changes (deltas) only, and change only what you need to, to Execute and Unexecute.

I hope this article has helped. I’d love to hear your comments if it did, or, even more so if it didn’t. I wrote at the beginning that there is more work in this than the “naive” way of writing an Editor, and that is true. But I hope you can see that it is not that much more work, and given how simple it is to understand, implementing infinite Undo/Redo in your tools is well worth the effort.

“In the midst of this our mortal life, I found me in a gloomy wood, astray.” – Dante

7 Comments »

  1. I always felt it would be damn cool to store all game world variables in such a fashion that would enable undoing/redoing. But as you mentioned, it’s almost impossible to store all variable, as it would be very inefficient. But I’m still thinking of something similar, that could be helpful for example in RPG games.

    Such system could store only that game variables which have impact on quests/NPC reactions and stuff, and are modified by quest system/dialogues etc. Then during playing(testing) one is able to undo some action(s) he did to the previous state, and test different paths.

    Another option I find useful, is to save command stack along with the file. Normally, after you save and load, you can’t undo, with this you’ll be able. I think it could be nice.

    Comment by scypior — August 6, 2008 @ 11:25 am | Reply

  2. Excellent article, I have a system very similar to this implemented. However there is one issue that I have not found an entirely graceful solution for.

    Most of the editing in my editor is done via PropertyGrids; not particularly pretty, but allow adding of new actors/triggers with new properties without having to modify the UI. Since PropertyGrids directly modify the properties of an object, there doesn’t seem to be a clean solution to allowing undo for these edits. The only solution I have come up with is adding a command to the list from within the property setter.

    Any suggestions?

    Comment by toris — August 7, 2008 @ 10:07 am | Reply

  3. Interesting you should ask, as I’d been planning on using PropertyGrids on Pandemonium and had been musing over how they could be combined with Undo/Redo.

    One solution might well be for each Property to issue its own undoable Command, as you’ve done. Seems like a bit of a pain though.

    Another – and this would very much depend how you have structured your Editor – would be for your property grid not to work on the actual in-game object, but a separate data structure that gets copied to one side. So, in your Editor, when you select your Actor, it copies the Actor.InitialValues structure to a new object, and opens that up in a PropertyGrid. You make all the changes you want in your PropertyGrid, then click an OK button – and at this stage, an undoable Command is issued to change the Actor.InitialValues object.

    That’s just a thought at the moment, I’ve not actually tried it. You can probably get a more concrete example from Visual Studio – play around with the Windows Forms editor for a while, which uses a PropertyGrid for each control, and see what happens when you Undo/Redo. You may be able to work out how the VS team did it.

    Comment by bittermanandy — August 7, 2008 @ 12:26 pm | Reply

  4. Hi. First of all, great articles. I really found them helpful especially because I’m writing game editor at the moment too. When it comes to game developement most people seem to concentrate on describing shiny graphic effects, so your blog is very refreshing. ;)

    Regarding PropertyGrids, I think other solution could be to hook to PropertyValueChanged event and record selected object, PropertyDescriptor and old value. All this information is given in event parameters. This method could record changes to individual properties and doesn’t require any specific actions from user. You could also subclass PropertyGrid and make some UndoPropertyGrid which would do that automatically. I didn’t try it yet, but at first glance I don’t see any big problems with this approach.

    Comment by Luke — August 7, 2008 @ 10:16 pm | Reply

  5. Ah, events… an even better idea. PropertyGrids are something I’ve barely looked at so far but the solution you suggest seems an excellent one. All the flexibility and much less work than hooking up commands to each individual property.

    As for shiny effects, yeah… I’m very aware that there’s people out there that know a lot more about them than me! So I’m deliberately pitching this blog in a different direction, ie. talking about how to get actually stuff done.

    Comment by bittermanandy — August 7, 2008 @ 10:47 pm | Reply

  6. The approach suggested by Luke works pretty well, until you start expanding objects and editing properties. Coming from a C++ background, and not generally touching the Windows APIs, I can’t find a way around it at present.

    Basically, when hooking into the PropertyValueChanged event, there doesn’t appear to be a way to get the object actually being edited. Say you’re editing an Item object, which has a Vector2 for it’s position in the world. If you edit the position without expanding it it all works fine, the PropertyDescriptor is associated with a property that belongs to the PropertyGrid’s SelectedObject. However, if you expand that Vector2 so that the X and Y properties of the vector are shown in the PropertyGrid then proceed to edit one of these, you get a problem. The PropertyDescriptor no longer belongs to the SelectedObject, it belongs to the Vector2. And I cannot appear to find any way of getting the correct object.

    Comment by toris — August 9, 2008 @ 4:32 pm | Reply

  7. It looked too good to be that easy. ;) When expanded property is inside reference type you can get object from e.ChangedItem.Parent.Value. But the real problems exist for value types nested in another value type (like aforementioned float inside Vector2). You can’t get reference to the Vector2 because e.ChangedItem.Parent.Value returns only boxed copy of the vector.

    After some experiments I ended up with following code (hope it won’t look too bad in the comment field):

    class PropertyCommand : ICommand {
    public PropertyCommand(object selectedObject,
    GridItem item, object oldValue)
    {
    if (item.Parent.GridItemType == GridItemType.Category) {
    // If parent is category this is property belongs to SelectedObject
    instance = selectedObject;
    descriptor = item.PropertyDescriptor;
    this.oldValue = oldValue;
    }
    else {
    // Else find first item in hierarchy which isn’t value type
    object currentItem;
    bool found = false;

    // Go up in hierarchy until it’s nested property
    for ( ; item.Parent.GridItemType == GridItemType.Property;
    item = item.Parent) {
    // If parent is reference type we’re done
    if (!item.Parent.Value.GetType().IsValueType) {
    found = true;
    break;
    }
    else {
    currentItem = item.Parent.Value;
    item.PropertyDescriptor.SetValue(currentItem, oldValue);
    oldValue = currentItem;
    }
    }

    instance = (found) ? item.Parent.Value : selectedObject;
    descriptor = item.PropertyDescriptor;
    this.oldValue = oldValue;
    }
    }

    public void Unexecute() {
    descriptor.SetValue(instance, oldValue);
    }

    private object instance = null;
    private PropertyDescriptor descriptor = null;
    private object oldValue = null;

    }

    After a couple of tests it seems to work.

    Comment by Luke — August 10, 2008 @ 6:02 pm | Reply


RSS feed for comments on this post. TrackBack URI

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

The Rubric Theme. Create a free website or blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: