Combined Undo Actions

Recently I quickly described how I implemented complex undo-actions in a game I developed. That game is a Sokoban clone, which I implemented in the Mini Micro neo-retro fantasy computer.

TLDR: the challenge of executing multiple small undo-actions was solved by combining many anonymous functions into a bigger one, finally pushing the latter into an undo-stack.

A first approach

A first naive approach could be like this:

• When the user makes a move
• Push the opposite move on a stack
• When the user wishes an "undo"
• Pop the stack and perform the popped operation

This works "good enough" as long as we are just moving the worker. But it fails as soon as box-pushing is involved. For the reason alone that the approach above completely ignores boxes.

Boxes and directions

In addition to failing to consider boxes, the approach above fails to capture another additional detail: worker facing-directions. That is: the worker (in my implementation) does not always "look" in a fixed direction. Rather he turns left, right, up, down depending on where he's trying to go or push.

So now we have two more aspects which should be "undone" when undoing a step:

• Box position (if this changed due to a push)
• Worker turning to a new direction

As we see a single user-event (wanting to go "left" one step) can result in many things happening:

• The worker turning to a new direction
• The worker changing position
• A box changing position

Box state

If we think possible outcomes of an action further, another very important change can happen:

• A box changing its "state"

Remember, the goal of Sokoban is to "place" boxes in special "target" or "goal" tiles. A level is solved when all boxes are placed in such tiles.

So a box can change from "unplaced" to "placed". And vice-versa (from "placed" to "unplaced", this is often temporarily needed for tactical reasons before the level is solved completely).

To recap, this would be the a complete list of things that can happen in a user "turn":

• The worker turning to a new direction
• The worker changing position
• A box changing position
• A box changing state

Complex undo actions

Intuitively, using an "undo" stack makes sense. But what would we push onto it, so that we can properly undo an user "turn"?

Let's say a user "turn" results in these steps:

1. Turn worker to the "left"
2. Move worker (from [3,2]) to [2,2]
3. Change box position (from [2,2]) to [1,2]

Would I want to push in the stack what happened and then figure out the opposite action? Or push the opposite action to begin with? I opted for the latter.

So I would push this, in this order:

1. Change box position (from [1,2]) to [2,2]
2. Move worker (from [2,2]) to [3,2]
3. Turn worker to the "right"

For example, here is the implementation of moving an element (worker or box) and registering the opposite "undo" action:

LevelSprite.moveTo = function(position)

  // Only do this if sprite already placed and the new
  // position is different than the current one.
  if self.position and self.position != position then

    previousPosition = obj.position
    previousX = obj.x
    previousY = obj.y

    // Register corresponding "undo" action ...
    // (Capture "self" so that it's "fixed" when executing)
    obj = self
    undoAction = function()
      obj.position = previousPosition
      obj.x = previousX
      obj.y = previousY
    end function
    // Note the function reference
    Actions.queue @undoAction

  end if
end function

But I needed a way to "group" actions, so that when the user wants to undo his last keystroke all of the three are popped from the stack and executed. But not more! (the stack could well have previous undo-actions pushed into it).

Enter transactions

I solved the problem by grouping actions belonging to a "turn" and pushing them as-one into the undo-stack.

That is, my undo-stack always has ONE entry per turn. Those three entries shown in the previous section are grouped into one and pushed into the stack.

When the user wants to perform an undo, the composite action is popped and executed.

But how do I group the smaller actions into a bigger one to begin with?

I solved this by simulating "transactions".

When the user presses a direction key, thus issuing a game event, a transaction is started in the "undo manager".

The different parts of the code that change game-state are responsible of pushing their "undo actions" into a temporary (transaction) stack. For example the part that moves a box due to a push is responsible for registering the opposite move.

When all game-state changing logic is executed, the transaction is "closed". Then the undo-manager groups all registered "undo actions" and makes one bigger single action, which is pushed in the undo-stack.

In terms of code, it looks like this:

WorkerSprite.move = function(direction)
  Actions.beginTransaction

  self.rotateInDirection direction
  nextPosition = self.nextPositionInDirection(direction)

  objectAtNextPosition = LEVEL.getLevelObjectAt(nextPosition)
  objectAtNextPosition.move direction

  if LEVEL.hasFreeTileAt(nextPosition) then
    super.move direction
  end if

  Actions.endTransaction
end function

The relevant parts are the beginTransaction and endTransaction in the move method. The rest is the normal logic for a movement in a Sokoban level.

Functions

What are those undo-actions really?

The actions, small and combined, are anonymous functions.

After that, pressing undo is just a matter or popping the stack, and executing the top-most function (which returns the game state to one step before).

For example in one transaction all of this could happen:

• Worker changes direction to the right
• Worker advances one position
• A box is pushed in direction "right"
• A box changes its "placed" state from "unplaced" to "placed" (green)

All of this would require ONE undo-action which:

• Moves the worker one step to the left
• Moves the box one step to the left
• Rotates the worker to whichever direction it was facing before
• Sets the box to "unplaced"

And how to combine many function-references into one that calls them all? Something like this:

fn = function()
  for qa in queuedActions
    qa()
  end for
end function
// Register composite action
self.actions.push @fn 

This takes place within endTransaction. A new anonymous function that executes other anonymous functions stored in a list. Then pushed to a stack, ready to be retrieved and executed later.

Going into more detail would blow up the length of this blog post. Readers so inclined can take a look directly at the source code. Questions are welcome.

Conclusion

Undo-actions were modeled using anonymous small functions which would restore the game-state to a previous step.

By using a "transaction" per user turn / action all relevant game-state changes could be registered and combined.

The small anonymous functions were then combined into a bigger one, and pushed into the undo-stack. This makes the latter execution of an undo step trivial.

Happy coding!