#### Archived

This topic is now archived and is closed to further replies.

# Designing an undo system

This topic is 5210 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I suppose the typical undo system is centered around a stack data structure. Depending on the data that you''re editing, you can either push the previous state onto the stack, or you can push the changes made to the data onto the stack. Then, whenever you do an undo, you simply pop off the last thing on the stack. If it is a previous state, then you simply revert back to that state. If it is a change that had been made, then you simply reverse the change.

You could probably implement a system that handles both types, previous states, and changes, since some actions can''t simply be reversed.

You''d also probably need to be able to permanently remove things that are on the bottom of the stack, in order to keep memory usage acceptable. Again, this depends on what type of information you''re pushing onto the stack, and how often.

I don''t have any links to resources, though. Sorry. But hopefully the stack suggestion will be helpful (assuming it isn''t already obvious).

##### Share on other sites
One could build a basic undo system by using functor objects and a stack.

You would have a base class for the functor objects.
And for every type of action that may need to be undone, you derive from this. These derived functor objects contain the logic to undo the action.
Every time an "undo-able" action is performed, the appropiate undo functor is created and filled with the info needed to undo that action, and finally pushed on the undo stack.

Suppose you''re building some sort of paint program
eg:

// the baseclassclass UndoFunctor{public:    virtual void Execute()=0;}:/*A undo functor for undoing a DrawLine action. It would probably contain some data members to "remember" the state of the drawing canvas before the line was drawn.something like a Rectangle class and a Bitmap class*/class UndoDrawLine : public UndoFunctor{    Rectangle affectedArea;    Bitmap backup;public:    void Execute(){        // remove the line by blitting the backup bitmap to        // the affected area    }};

I hope you got the idea.

##### Share on other sites
Stacks are a good choice, but only when they're used right. It has the potential to be memory intensive if, let's say, you decide to store each state in the stack. That would be bad.

To my knowledge, most windows applications use a memory mapped file that is always open while the application is running. This allows you to keep your undo data in a sort of customized virtual memory and it's never swapped in or out, which takes time. The stack could be used to store the handles of each location in the file where an action occurred. In my eye, using a memory mapped file with a stack of locations is the best way to go. Memory mapped files are covered in chapter seventeen of the essential Win32 book, "Programming Applications for Microsoft Windows, 4th Edition" by Jeffrey Richter.

Actually calculating the undo instructions is up to you. Depending on what and how your application does its work, you may choose to store calculation data (or de-calculation data, to reverse changes made). You may choose to keep a copy of the previous data around and incrementally store the data in your classes into the file. You might do well to integrate a record of states within each data type you have (would be VERY messy but self-contained). I can't offer much in the way of this sort of advice, but you should be able to figure out a clever way to implement it

Good luck!

_________________
:: MajorShredd ::
The glass is neither half full nor half empty;
rather, it is a combination of both, and the system is perfect.

[edited by - MajorShredd on June 2, 2004 6:35:40 PM]

##### Share on other sites
yeah, a basic undo system could work something like this:

first, you need all of your "commands" to be in some sort of common form, such as classes derived from a common base, functors or function pointers with a common signature, whatever ... I personally use interfaces like this:

class ICommand
{
public:
void Execute(void);
}

class IReversableCommand : ICommand
{
public:
void ExecuteUndo(void);
}

second, you need all of your commands to go through a central "processor" of some sort ...

so when you need to do an action, it should somehow equates to lines like:

CommandManager.PushCommand(currentCommand);

... gotta go, hope to add more later.

##### Share on other sites
Yep, a generic functor, such as boost:function, and two stacks, one for undo and another for redo build the core of the system.

Then, you make objects for each action the user can take, and when it is invoked, it puts it''s buddy undo object onto the undo stack.
When the undo action is invoked, it invokes the top object on the stack and put it''s redo buddy (the original action object) onto the redo stack.

You can check the type of the object on top of the stack, and modify it if it is the same type. e.g. Many times when you type and hit undo it undoes that last block of text, not just one character.

##### Share on other sites
thanks alot

I wasnt expecting so many replies so soon great.

##### Share on other sites
Here is an implementation of a simple undo system. Feel free to expand upon it.

http://www.randommonkeyworks.com/Programming/Undo.html

David

##### Share on other sites
Something makes me wonder why there''s not a tutorial or faq guide to undo/redo systems here on GameDev. At least, I haven''t seen any in my searches of the resources here.

_________________
:: MajorShredd ::
The glass is neither half full nor half empty;
rather, it is a combination of both, and the system is perfect.

1. 1
2. 2
Rutin
20
3. 3
4. 4
frob
15
5. 5

• 10
• 9
• 14
• 9
• 33
• ### Forum Statistics

• Total Topics
632592
• Total Posts
3007295

×