PVG
39. Undo Redo
[[programvideogames]]## Why Use Commands?
Undo/Redo Support
- Each command stores how to do and undo itself
- Command history tracks sequence of operations
- Can move backward and forward through history
Operation Validation
- Commands validated before execution
- Failed validations aren't added to history
- Predictable state updates
Command History Management
history: [Cmd1] [Cmd2] [Cmd3] [Cmd4]
^ Current
// undo
history: [Cmd1] [Cmd2] [Cmd3] -Cmd4-
^ Current
// undo
history: [Cmd1] [Cmd2] -Cmd3- -Cmd4-
^ Current
// new cmd
history: [Cmd1] [Cmd2] [Cmd3]
^ Current
Since we need to keep these commands in memory and we have no up-front knowledge about the size, we will implement a custom allocator.
This custom allocator won't ever be cleared - the idea as that in release mode the editor functionality will be removed or disabled.
The Code
The Data
First, let's create the fields required:
import "core:log"
import "core:mem"
import "core:mem/virtual"
Editor_State :: struct {
// ...
cmd_arena: virtual.Arena,
cmd_allocator: mem.Allocator,
command_history: [dynamic]Cmd_Entry,
undo_count: int,
spike_orientation: Direction,
}
We're going to use the arena to store all the dynamically allocated data for our commands.
We're also going to change how spike placement is handled. I thought automating it would be cool, but it turned out to be lackluster. There are edge-cases that can't be resolved. So, I tried this system, where we bind a key (F) to change the orientation of the spike tool. In my opinion this feels better and it's less code.
The Types
We'll need some new types for commands.
Cmd :: union {
Cmd_Tiles_Insert,
Cmd_Tiles_Remove,
Cmd_Spikes_Insert,
Cmd_Spikes_Remove,
}
Cmd_Tiles_Insert :: struct {
coords: []Vec2i,
spikes_removed: []Spike,
}
Cmd_Tiles_Remove :: struct {
coords: []Vec2i,
spikes_removed: []Spike,
}
Cmd_Spikes_Insert :: struct {
spikes: []Spike,
tiles_removed: []Vec2i,
}
Cmd_Spikes_Remove :: struct {
spikes: []Spike,
tiles_removed: []Vec2i,
}
Cmd_Entry :: struct {
forward: Cmd,
inverse: Cmd,
}
The reason we are storing individual coordinates when we insert or remove tiles rather than begin, end: Vec2i is, when we undo the command - we need to know which tiles were previously empty or filled.
It may seem confusing to have spikes_removed on the Cmd_Tiles_Remove command since removing tiles doesn't remove spikes!
However, when we construct our commands, we need to construct the inverse operation. That is, the command, if played, that would bring us back to the previous state. You'll see how that work when we implement the procedures.
Spike commands have a similar field - tiles_removed.
As you can see our command entries (what we store) Cmd_Entry hold both a forward and inverse version. We can "play" the command forward to redo, and the inverse to undo.
The Flow
Before we get into the implementation, let's outline the flow of this system.
I designed it to be expanded with ease and simple to understand.
- Construct the Command
- Query the current state of the level
- Construct a command IF conditions allow
- Execute the Command
- Either
forwardorinverseused to change level state
- Either
- Record the Command
- Add the
Cmd_Entryto history
- Add the
All of these steps have been encapsulated into their own procedures. If the construct step fails, nothing will be executed nor stored in history.
The Implementation
Let's go in order of the flow. First up is construct.
editor_command_construct :: proc(cmd_type: typeid) -> (cmd: Cmd_Entry, ok: bool) {
switch cmd_type {
case Cmd_Tiles_Insert:
area_coords := coords_from_area(es.area_begin, es.area_end)
// No tiles inside level bounds
if len(area_coords) == 0 {
return
}
spikes := spikes_from_area(es.area_begin, es.area_end, gs.level)
forward := Cmd_Tiles_Insert {
coords = area_coords,
spikes_removed = spikes,
}
air := make([dynamic]Vec2i)
for coords in area_coords {
if !is_tile_at(coords, gs.level) {
append(&air, coords)
}
}
inverse := Cmd_Tiles_Remove {
coords = air[:],
spikes_removed = spikes,
}
return {forward, inverse}, true
case Cmd_Tiles_Remove:
area_coords := coords_from_area(es.area_begin, es.area_end)
forward := Cmd_Tiles_Remove {
coords = area_coords,
}
solid := make([dynamic]Vec2i)
for coords in area_coords {
if is_tile_at(coords, gs.level) {
append(&solid, coords)
}
}
// No tiles removed
if len(solid) == 0 {
return
}
spikes := spikes_from_area(es.area_begin, es.area_end, gs.level)
inverse := Cmd_Tiles_Insert {
coords = solid[:],
spikes_removed = spikes,
}
return {forward, inverse}, true
case Cmd_Spikes_Insert:
rect := rect_from_coords_any_orientation(es.area_begin, es.area_end)
rect = rect_pos_add(rect, -gs.level.pos)
overlap := rl.GetCollisionRec(rect, rect_from_pos_size(0, gs.level.size))
// Outside level, do nothing
if overlap != rect {
return
}
// Overlapping other spikes, do nothing
for spike in gs.level.spikes {
if rl.CheckCollisionRecs(spike.collider, rect) {
return
}
}
spike := Spike {
collider = rect,
facing = es.spike_orientation,
}
switch spike.facing {
case .Up:
spike.collider.y += SPIKE_DIFF
spike.collider.height = SPIKE_DEPTH
case .Right:
spike.collider.width = SPIKE_DEPTH
case .Down:
spike.collider.height = SPIKE_DEPTH
case .Left:
spike.collider.width = SPIKE_DEPTH
spike.collider.x += SPIKE_DIFF
}
area_coords := coords_from_area(es.area_begin, es.area_end)
tiles_removed := make([dynamic]Vec2i)
for coords in area_coords {
if is_tile_at(coords, gs.level) {
append(&tiles_removed, coords)
}
}
spikes := make([]Spike, 1)
spikes[0] = spike
forward := Cmd_Spikes_Insert {
spikes = spikes,
tiles_removed = tiles_removed[:],
}
inverse := Cmd_Spikes_Remove {
spikes = spikes,
tiles_removed = tiles_removed[:],
}
return {forward, inverse}, true
case Cmd_Spikes_Remove:
spikes := spikes_from_area(es.area_begin, es.area_end, gs.level)
if len(spikes) == 0 do return
forward := Cmd_Spikes_Remove {
spikes = spikes,
}
inverse := Cmd_Spikes_Insert {
spikes = spikes,
}
return {forward, inverse}, true
}
panic("Should not reach this location, check switch statement")
}
This procedure is the most complex of the three. It uses the current state of the editor, data from the level and the command type to construct a valid Cmd_Entry. If any conditions are failed, the idea is to return false on the ok return value.
This ok will then be used to see if we should move to the next step, execution:
editor_command_execute :: proc(cmd: Cmd) {
switch v in cmd {
case Cmd_Tiles_Insert:
for coords in v.coords {
editor_tile_insert(coords, gs.level)
}
for spike in v.spikes_removed {
editor_spike_remove(spike, gs.level)
}
case Cmd_Tiles_Remove:
for coords in v.coords {
editor_tile_remove(coords, gs.level)
}
for spike in v.spikes_removed {
editor_spike_insert(spike, gs.level)
}
case Cmd_Spikes_Insert:
for spike in v.spikes {
editor_spike_insert(spike, gs.level)
}
for coords in v.tiles_removed {
editor_tile_remove(coords, gs.level)
}
case Cmd_Spikes_Remove:
for spike in v.spikes {
editor_spike_remove(spike, gs.level)
}
for coords in v.tiles_removed {
editor_tile_insert(coords, gs.level)
}
}
}
This is quite straightforward, though may still take some mental energy to visualise the changes. Especially with inverse commands.
Next up is the smallest of the three, though will need a bit of explanation, recording:
editor_command_record :: proc(cmd: Cmd) {
next_index := len(es.command_history) - es.undo_count
resize(&es.command_history, next_index + 1)
es.command_history[next_index] = cmd
es.undo_count = 0
}
I think this is better illustrated with an image. The gist is that we resize the array when recording commands. This overwrites the previous history.
![[Drawing 2025-01-04 15.19.23.excalidraw]]
Finally, I opted to wrap these all in a helper to dispatch easily:
editor_command_dispatch :: proc(cmd_type: typeid) {
if cmd, ok := editor_command_construct(cmd_type); ok {
editor_command_execute(cmd.forward)
editor_command_record(cmd)
}
}
Undo and Redo
These procedures are remarkably simple now that we have the infrastructure set up.
editor_undo :: proc() {
commands_exist := len(es.command_history) > 0
can_undo_more := len(es.command_history) != es.undo_count
if commands_exist && can_undo_more {
es.undo_count += 1
undo_cmd := es.command_history[len(es.command_history) - es.undo_count]
editor_command_execute(undo_cmd.inverse)
}
}
editor_redo :: proc() {
did_undo := es.undo_count > 0
can_redo_more := len(es.command_history) - es.undo_count >= 0
if did_undo && can_redo_more {
redo_cmd := es.command_history[len(es.command_history) - es.undo_count]
es.undo_count -= 1
editor_command_execute(redo_cmd.forward)
}
}
First we make sure we are in a state that handles undo/redo. Then, we grab the command, increment or decrement es.undo_count, and execute the forward or inverse command.
Custom Allocator
Let's create that custom allocator to store all the command data. We'll use a new init procedure:
editor_init :: proc() {
if err := virtual.arena_init_growing(&es.cmd_arena); err != nil {
log.panicf("Failed to init editor arena: %s
", err)
}
es.cmd_allocator = virtual.arena_allocator(&es.cmd_arena)
es.command_history = make([dynamic]Cmd_Entry, es.cmd_allocator)
}
We'll using Odin's built-in Growing Arena Allocator type for this. The choice was arbitrary for me, as:
- We aren't deallocating this memory
- We are not using this in performance critical loops
- It's a dev tool
On the last line, we make sure allocate the history array using this new allocator.
Next, we'll using Odin's Context system to make sure this allocator is used in our editor.
In editor_update, we want to set the current context.allocator to ours. At the end of the scope, it will be automatically re-assigned to what it was before the editor_update call.
We also now pass in the delta time from the call site.
editor_update :: proc(gs: ^Game_State, dt: f32) {
context.allocator = es.cmd_allocator
// ...
This will propagate down the call-stack to any procedure that editor_update calls. Until we get out of this procedure, the default allocator will be our new arena allocator.
Making it Work
While we are in the editor_update procedure, we'll do some house-keeping and change the code to use our new command system.
Moved the panning functionality and added the ability to pan with arrow keys.
// Scroll Camera code here
// Pan Camera
{
mouse_delta: Vec2
if rl.IsKeyDown(.LEFT) {
mouse_delta.x += 300 * dt
}
if rl.IsKeyDown(.RIGHT) {
mouse_delta.x -= 300 * dt
}
if rl.IsKeyDown(.UP) {
mouse_delta.y += 300 * dt
}
if rl.IsKeyDown(.DOWN) {
mouse_delta.y -= 300 * dt
}
if rl.IsMouseButtonDown(.MIDDLE) {
mouse_delta = rl.GetMouseDelta()
}
gs.camera.target -= mouse_delta / gs.camera.zoom
}
Just below that code, we want to add the spike orientation code I spoke about earlier:
if es.tool == .Level || es.tool == .Level_Resize {
// ...
} else {
// ...
if rl.IsKeyPressed(.F) {
es.spike_orientation += Direction(1)
if int(es.spike_orientation) > 3 {
es.spike_orientation = Direction(0)
}
}
}
And just below that, our undo and redo calls. I'm going with ctrl+z and ctrl+y:
if rl.IsKeyPressed(.Z) && (rl.IsKeyDown(.LEFT_CONTROL) || rl.IsKeyDown(.RIGHT_CONTROL)) {
editor_undo()
}
if rl.IsKeyPressed(.Y) && (rl.IsKeyDown(.LEFT_CONTROL) || rl.IsKeyDown(.RIGHT_CONTROL)) {
editor_redo()
}
Next up, we'll be changing our place and remove code in the Tiles case, which is just below:
switch es.tool {
case .None:
case .Tile:
if rl.IsMouseButtonPressed(.LEFT) || rl.IsMouseButtonPressed(.RIGHT) {
es.area_begin = coords
}
if rl.IsMouseButtonDown(.LEFT) || rl.IsMouseButtonDown(.RIGHT) {
es.area_end = coords
}
place := rl.IsMouseButtonReleased(.LEFT)
remove := rl.IsMouseButtonReleased(.RIGHT)
if place {
editor_command_dispatch(Cmd_Tiles_Insert)
} else if remove {
editor_command_dispatch(Cmd_Tiles_Remove)
}
case .Spike:
if rl.IsMouseButtonPressed(.LEFT) || rl.IsMouseButtonPressed(.RIGHT) {
es.area_begin = coords
es.area_end = coords
}
if rl.IsMouseButtonDown(.LEFT) {
switch es.spike_orientation {
case .Up, .Down:
es.area_end.x = coords.x
case .Left, .Right:
es.area_end.y = coords.y
}
} else if rl.IsMouseButtonDown(.RIGHT) {
es.area_end = coords
}
if rl.IsMouseButtonReleased(.LEFT) {
editor_command_dispatch(Cmd_Spikes_Insert)
}
if rl.IsMouseButtonReleased(.RIGHT) {
editor_command_dispatch(Cmd_Spikes_Remove)
}
Let's add the text that shows the current spike orientation as well as current undo/redo count to editor_draw:
editor_draw :: proc(gs: ^Game_State) {
// Draw Editor UI
rl.DrawTextEx(
gs.font_48,
fmt.ctprintf(
"Tool: %s
History: %d/%d
Orientation: %v
Camera.Zoom: %v
Camera.Target: %v", // changed
es.tool,
len(es.command_history) - es.undo_count, // new
len(es.command_history), // new
es.spike_orientation, // new
gs.camera.zoom,
gs.camera.target,
),
{8, 8},
24,
0,
rl.WHITE,
)
// ...
Modifications
Some of the procedures we had inconsistent naming conventions. Let's fix that whilst also fixing the bodies.
Replace editor_place_tile/spikes with the following:
editor_tile_insert :: proc(coords: Vec2i, l: ^Level) {
if !is_tile_at(coords, l) {
append(&l.tiles, Tile{pos = pos_from_coords(coords)})
recreate_colliders(l.pos, &gs.colliders, gs.falling_logs[:], l.tiles[:])
}
}
editor_tile_index :: proc(coords: Vec2i, l: ^Level) -> (index: int, ok: bool) {
for tile, i in l.tiles {
if coords_from_pos(tile.pos) == coords {
return i, true
}
}
return -1, false
}
editor_tile_remove :: proc(coords: Vec2i, l: ^Level) {
if index, ok := editor_tile_index(coords, l); ok {
ordered_remove(&l.tiles, index)
recreate_colliders(l.pos, &gs.colliders, gs.falling_logs[:], l.tiles[:])
}
}
editor_spike_insert :: proc(spike: Spike, l: ^Level) {
append(&l.spikes, spike)
}
editor_spike_index :: proc(coords: Vec2i, l: ^Level) -> (index: int, ok: bool) {
for spike, i in l.spikes {
pos := Vec2{spike.collider.x, spike.collider.y}
if coords_from_pos(pos) == coords {
return i, true
}
}
return -1, false
}
editor_spike_remove :: proc(spike: Spike, l: ^Level) {
if index, ok := slice.linear_search(l.spikes[:], spike); ok {
unordered_remove(&l.spikes, index)
}
}
We move the sorting into recreate_colliders as well as fix a bug with the tile positions, so make sure to update the procedure.
recreate_colliders :: proc(/* ... */) {
clear(colliders)
slice.sort_by(tiles, proc(a, b: Tile) -> bool {
if a.pos.y != b.pos.y do return a.pos.y < b.pos.y
return a.pos.x < b.pos.x
})
solid_tiles := make([dynamic]Rect, context.temp_allocator)
for t in tiles {
append(
&solid_tiles,
Rect{t.pos.x - world_pos.x, t.pos.y - world_pos.y, TILE_SIZE, TILE_SIZE}, // Fix: subtract world_pos from collider position
)
}
// ...
}
We can also delete a few procedures that are no longer being used:
is_area_tileddetermine_spike_facingtry_remove_tile_at
We're very close to done. We need to add two procedures that collect level state to store in our commands:
coords_from_area :: proc(begin, end: Vec2i) -> []Vec2i {
coords := make([dynamic]Vec2i)
area_min := Vec2i{min(begin.x, end.x), min(begin.y, end.y)}
area_max := Vec2i{max(begin.x, end.x), max(begin.y, end.y)}
level_min := coords_from_pos(gs.level.pos)
level_max := coords_from_pos(gs.level.pos + gs.level.size)
area_min.x = max(area_min.x, level_min.x)
area_min.y = max(area_min.y, level_min.y)
area_max.x = min(area_max.x, level_max.x - 1)
area_max.y = min(area_max.y, level_max.y - 1)
for y := area_min.y; y <= area_max.y; y += 1 {
for x := area_min.x; x <= area_max.x; x += 1 {
append(&coords, Vec2i{i32(x), i32(y)})
}
}
return coords[:]
}
spikes_from_area :: proc(p, q: Vec2i, l: ^Level) -> []Spike {
rect := rect_from_coords_any_orientation(p, q)
rect = rect_pos_add(rect, -l.pos)
spikes := make([dynamic]Spike)
for spike in l.spikes {
if rl.CheckCollisionRecs(rect, spike.collider) {
append(&spikes, spike)
}
}
return spikes[:]
}
I put these in editor.odin, but they can go anywhere you see fit.
The purpose of these two procedures is to create a copied list of tiles or spikes in a certain area. This list is then saved in our command so we can undo/redo correctly.
Finally, where we call editor_update make sure to pass in dt.
At the beginning of main, call editor_init().
That's it! We have a working command buffer for the level editor.