Thoughts on runtime Undo/Redo

Development Programming & Scripting C++
1

We need a Undo/Redo system for our software at runtime. We already have something in place following the Command Design Pattern. We have a basic UndoRedoItem that the manager works with. Inheriting from it, it is possible to create what ever undo redo functionality you need.

One problem is: Everything you want to do needs its custom item. Looking at UndoRedo system tutorials online, they are only utter ■■■■. Like pushing a int to a glogal array<int>.
(Cause the item is responsible for what is going to happen, we also wrapped those items into an action that can be transmitted for multiplayer (No Undo/Redo in multiplayer, but execute needs to happen)).

But having an actual program with lots of different data and different possible transactions, that does not work out nicely.

Another problem: runtime created objects. Making an undo might undo something for an object that does not exist anymore (no tutorial/blog entry handles that problem).

Having a look at Unreals Editor UndoRedo-System (ITransaction/FTransaction/UTransactor/UTransBuffer), Unreal serializes entire UObjects into the buffer and updates the Editor interface after Undo/Redo.
Doing a Undo/Redo at editor time can sometimes take up to 1second depending on the size of the blueprint. Which introduces a nother problem: We are developing for VR, so we have 11ms per frame, maybe 1ms at max for Undo/Redo operation.

We also want to release for standalone VR (Oculus Quest), where we face the problem of reduced memory and thus want to keep the items as small as possible.

Best thing I can think of is: stay with the Command Design Pattern:

  • Items only contain the data they need -> Small memory footprint
  • Do only what needs to be done (no overhead) -> Fast execution

Still facing the problem with deleted runtime created objects that are referenced in the UndoRedo buffer.

And also problems like a slider in an interface: the slider influences a value and we want to save that value to the buffer. But when do you save it? the slider updates the value continually and saving to the buffer every time the value changed is overkill. Basically you only want to save the value after the player released the slider. That again requires the user to assign to the event of slider got released for every slider (head spinning just thinking about the upcomming bug mess). And interface interaction also breaks the principle of the UndoRedo item executes the action.

Any thoughts on that?

2

You should take some time and watch this talk the NetherRealms guys did on the networking for MK11 / Injustice 2 : 8 Frames in 16ms: Rollback Networking in Mortal Kombat and Injustice 2 - YouTube

They run their game 7 times each frame, rewinding to the latest input packet and replaying. They do this by:

1.) Making the game incredibly deterministic (from particles, to animations, etc).
2.) Serializing objects every frame (runtime created objects are simply initialized to a default “empty” state and only cleaned up if they aren’t reinitialized after some time).

You could apply those same concepts to your Undo/Redo.

3

There’s a few things that you can do for an undo/redo.

1- Keep track of the entire set of relevant state, and have a method to restore that state exactly.

2- Keep track of all changes to the state, and replay that from the beginning to the point in the state where you need to be.

3- Keep track of all changes to the state, and have an “opposite” change method – ie if a state action is to remove an object, the opposite of it would be to create that object. When the user wants to undo a change, then play the opposite action.

1 is probably the easiest to implement, but probably takes the most memory. Speed will be determined by how quickly you can completely restore the state from a snapshot.

2 is probably the second easiest to implement, takes the least amount of memory. Speed will be ultimately based on how quickly you can tear down the state and restore it by replaying to the desired point. Number of actions in the stack will have a significant effect on speed.

3 is probably the most difficult to implement, takes a similar amount of memory, but will most likely perform the fastest. You may have issues with reconnecting, for example, deleted then recreated objects, to where they may have previously been connected to.

There may be other ideas that I’m not familiar with.

4

Thank you both for the replays.
Neither do we have the memory nor the power (Oculus Quest) for serializing entire objects. Also we do have to much data to keep a backup of a application state.

We try to go with only incremental changes to what is happening. Which requires the programmer/scripter to push every relevant change to the history. This might introduce many bugs if data is not submitted, though keep us performant.

I came up with a function that is able to serialize any property from blueprint which will ease the process.



    UFUNCTION(BlueprintCallable, Category = "UndoRedo", CustomThunk, meta = (CustomStructureParam = "myProperty"))
    static void SerializeProperty(UObject* properyOwner, UProperty* myProperty, FUndoRedoPropertyCallback onUndo, FUndoRedoPropertyCallback onRedo)
    {
        check(0); // This function should never get called. @see execSerializeProperty
        return;
    }

DECLARE_FUNCTION(execSerializeProperty);

DEFINE_FUNCTION(execSerializeProperty)
{
    P_GET_OBJECT(UObject, propertyOwner);
    Stack.Step(Stack.Object, NULL);
    UProperty* myProperty = Stack.MostRecentProperty;
    check(myProperty);
    P_GET_PROPERTY(UDelegateProperty, onUndo);
    P_GET_PROPERTY(UDelegateProperty, onRedo);
    P_FINISH;

    P_NATIVE_BEGIN;

    uint8* valuePtr = myProperty->ContainerPtrToValuePtr<uint8>(propertyOwner);
    TArray<uint8> binaries;
    FMemoryWriter ar(binaries);
    property->SerializeItem(ar, valuePtr);
    ar.Flush();

    P_NATIVE_END;
}