(This is in huge WIP status)

What is Undo/Redo

The Undo/Redo system in a game editor is a functionality that allows developers to cancel (Undo) or repeat (Redo) the last actions performed in the process of creating or editing game content.

This system typically includes:

1. Undoing the last action (Undo)
2. Repeating a previously undone action (Redo)
3. A history of actions, allowing to go back several steps

Such functionality helps developers experiment with different ideas, quickly fix mistakes, and effectively manage the game creation process.

Implementing such a system in an editor for Bevy would significantly improve the usability and productivity of developers working with this game engine.

What should Undo/Redo be like for the Bevy community

Implementing an effective Undo/Redo system for Bevy requires careful consideration of the engine's unique architecture and the needs of its community. While there are many existing implementations in other game engines and editors, it's crucial to tailor our approach to Bevy's Entity-Component-System (ECS) paradigm and the specific workflows of Bevy developers.

To design an appropriate Undo/Redo system, we need to address two key questions:

1. What actions should be undoable/redoable?
2. How will these actions be sequenced?
3. What data should these actions operate on?
4. How do we preserve the intermediate states of the data?
5. How to integrate undo/redo with ecs?

By clearly defining these aspects, we can create a system that integrates seamlessly with Bevy's architecture and provides a smooth, intuitive experience for developers.

Source of truth about game content state

In any editor, no matter what it edits, what you want to be mutating/undoing/redoing is the ultimate source of truth; you don't want the editor to be modifying data that is generated from the source of truth.

For example, a .bsn (Bevy Scene Notation) file could serve as the source of truth. The entire scene displayed in the editor might be visualized based on this file, and only changes to the .bsn file would have a real impact on the game content state. Therefore, we need to clearly identify what constitutes the source of truth for our data in a Bevy editor context.

Source of truth about game content

The main data sources that may be encountered in a Bevy editor:

Data Source	Actions that can be performed	Example
Components	adding, modifying, deleting	Transform, Sprite, Collider
Resources	adding, modifying, deleting	Editor settings, global game state
Assets	adding, modifying, deleting	Height map, textures, models, audio files
Entities	creating, destroying
Remote data	creating, modifying, deleting	Any data that is outside the ecs world. For example, a file scene in .bsn format or remote ecs world. In either case, this is data to which we do not have direct byte access within ecs world.

In my view, this is an exhaustive list of what a Bevy editor can operate on. Even if a Bevy editor manages some remote game, we're still talking about changing some components, resources, entities, assets, and files, as these are fundamental data units in the ECS paradigm. Anything that falls outside these categories is likely not ECS and is not our main focus.

What is not a data source

The following structures, inherent to ECS, cannot be a source of the true state of game content, as they are tools for changing it:

1. Events
2. Commands
3. One-shot systems

Changes in Undo/redo

Blender documentation (https://developer.blender.org/docs/features/core/undo/) provides a clear classification of actions that can be registered in the undo/redo system:

• Relative: A step can only be loaded if the previous (or next) one has already been loaded. In other words, the stack needs to be processed sequentially through all steps from the current (active) one until the target one is reached.
• Absolute: A step contains the whole data and can be directly loaded as its own from any point of the history.

Furthermore, we have two kinds of steps:

• Stateful: The undo step stores the state of some data, and can be loaded regardless of the direction (undo or redo).
• Differential: The undo step only stores the difference to the previous step. Furthermore, they cannot be loaded, but either applied (redo) or unapplied (undo). One key consequence of this is that with such steps, when undoing, you actually need to process (unapply) the n + 1 step, not the target n step.

In the context of game development, not all types of undo steps are equally applicable. For long-term version management in game development, version control systems such as Git or Subversion are typically used. The built-in undo/redo system in an editor is usually used for a small number of sequential rollbacks, which corresponds well with the logic of relative steps. Thus, it is proposed to implement only relative undo steps.

Naming changes

It's important to assign clear names to all user actions. This will allow for creating convenient menus, for example: "Undo Create Resource Ctrl-Z". And it will increase understanding of what is being undone in the editor.

Stateful and differential undo

Stateful approaches:

1. All data snapshot
2. Partial snapshots for only changed items
3. Just store some state to immediately move to the change

Differential approaches:

1. Reflection-based diffing
2. Patching of float arrays and buffers using diff algorithms
3. Byte diffing for serializable data
4. Any other diff algorithm

In Bevy undo/redo, support for both stateful and differential approaches is required:

1. Stateful approach is simple to implement and understand
2. Diff approach is not implementable on all data
3. Stateful approach based on cloning is faster for small data
4. Diff approach will save a lot of memory when working with large data (large textures, large scene files, 100k entities open in the editor, etc.)

Also, a useful property of the Undo system could be informing the user about unsaved actions on the data source.

Undo/redo timeline

Undo/redo timeline is an ordered sequence of data changes, along which we modify data using Undo and Redo. Timeline is not store data. It stores only changes for data.

It's important to note that Undo is not only about BSN and scenes, but also about editor settings, text fields, changes in the state of editor-specific interface elements, as well as the basis for custom in-game editors.

Obviously, for example, the timelines for editor settings and scene changes should be separate. While in the process of editing the game, we don't want to accidentally roll back an important editor setting. So the presence of multiple undo/redo timelines is definitely required.

Each Undo/redo timeline is tied to some data, which we will further refer to as timeline data. It is proposed to build the undo/redo timeline based on three principles: nested timelines, directional acyclic graph (DAG), and collapsible changes.

Nested timelines

Scene editing involves manipulations at different levels of hierarchy. We can delete or create an entire scene (top level of hierarchy), as well as modify the name of an entity in a text field (lowest level of hierarchy). At the text field level, it's convenient to use undo down to a single character. Whereas at the scene level, it's more convenient to move between the points of the start and end of name editing. That is, all small changes are nested within one large change in the higher-level timeline.

Time-continuous collapsible changes

Some changes can be prolonged and almost continuous in time. For example, moving an object using a gizmo or dragging a slider. Such changes should store in the undo/redo timeline only one change that modifies the data between the start point and end point of the changes.

DAG timeline

Multiple independent undo/redo timelines can exist simultaneously. However, these multiple timelines can be created from a single point. For example, scene viewer widget and scene editor widget should have related but different timelines. And the linking point will be the creation/opening/closing of the scene. If we undo the scene creation, the scene should be deleted, but with redo we should be able to return to the scene and its timeline at the moment of closing by the undo operation.

It is proposed to implement the Directed Acyclic Graph (DAG) for Undo/Redo timelines as follows:

1. All timelines start with a node denoting the opening/creation of data over which user actions manipulate
2. Each branch of the DAG is a separate undo/redo timeline
3. Each node is a data change
4. Each edge is a sequence of data changes
5. Nodes can have more than one outgoing edge if new timelines are created after the change
6. Only one edge can be input to a node
7. On each branch, one node is marked as the "last action performed" or hereafter "current"
8. One of the branches is marked as "in focus". All operations are applied to the timeline in focus by default

The following operations can be performed on the DAG:

1. Add data change. A new node is created. An edge is built from the current node to the new one. The new node becomes current.
3. Undo. The data change that was introduced by the current node is canceled and the previous node is marked as current. If the new node was the cause of creating new timelines, see the Data Deletion section
4. Create a timeline. A new branch of the graph is created referencing some data. The root node of the new branch becomes current in the new branch. An edge is built from the current node of the branch in focus to the root node of the new branch.
5. Redo. The data change of the next node is applied and the next node is marked as current. If the current node was the cause of creating timeline branches or deleted data of a timeline branch, then the branch, its data, and possibly the interaction window with the timeline branch data are restored.
6. Close timeline. The entire timeline is removed from the DAG and is no longer considered in undo/redo systems
7. Change focus. Another timeline becomes active for registering new changes.

Data Deletion

If an action deletes data that another timeline depends on, that line along with the data should be cached for restoration in undo. If an action closes a window that worked with a timeline, the timeline data and the timeline itself are cached so that they can be restored to undo the action.

Proposed implementation design

Two approaches to undo

1. Approach through a centralized command system:

In this approach, all changes in the game world pass through a centralized command system before being applied. For example, you can create an EditorCommand structure through which all user actions will pass.

fn system(mut commannds: EditorCommands // EditorCommands will auto register changes in undo/redo system for world
) {
  commands.spawn((Something)).id()
}

File changes

fn system(mut commands: FileCommands) { // Also will automaticly create changes in undo/redo timelines
  commands.file(path).append(new_text); 
  commands.file(path).write(replace_text);
}

Advantages:

• Full control over all changes
• Easy to track and register actions for undo/redo
• Simplifies the implementation of action cancellation, as each command can contain a method for cancellation

Disadvantages:

• Requires changes to existing code to use the command system
• Can add additional complexity to the architecture
• Potentially can reduce performance due to an additional layer of abstraction

2. Approach based on automatic change detection (Silent undo):

In this approach, the undo system automatically tracks changes in the game world without requiring explicit command calls.

Advantages:

• Does not require significant changes to existing code
• More transparent for developers using the editor
• May be easier to integrate into existing projects
• Works clearly with time-consuming commands

Disadvantages:

• More difficult to implement as it requires a reliable change detection mechanism
• May miss some changes if they are not tracked properly
• Requires a full copy of the data to build a diff between states at the moment of change detection

Both approaches have their advantages and disadvantages. The choice between them depends on the specific project requirements, existing architecture, and preferences of the development team. It is also possible to consider a hybrid approach, combining elements of both methods to achieve an optimal balance between control and ease of use.

Implementation design

(Coming soon…?)