Implementing a time rewind (move undo) system in Pulp

Pulp
1

Here's how I built the "undo move" functionality in Blocky Balloons!

If you're not familiar with the game, here's a short overview:

Blocky Balloons is a tile-based puzzle game, and the player can press A to undo their last move (up to 30 times maximum) in case they made a mistake or want to try something else. Here's what it looks like in action:
playdate-20230215-223825
[GIF where the player pushes some rocks around a bit, then falls into a hole, then hits "undo" repeatedly until the level is back to the initial state.]

Like most Pulp games, time moves in discrete "steps". Unlike the continuous flow of a real-time action game, the state of this game only changes when the player moves up, down, left, or right. If we save those states, we can tell the game to reset to them, and "rewind" back through those snapshots.

:balloon: The Plan

We keep a list of these states, and a pointer variable keeping track of which state we're currently in. The list size can't be infinite (or else we'd run out of memory), so if we fill up the list and then need to store a new state, we overwrite the oldest entry on the list. That way, we always have the player's most recent N moves (30, in Blocky Balloon's case). The fancy term for this data structure is a "circular array", or "ring buffer". In my code I called it a "stack", since that's how I thought about it at first. A stack of game states that piles up as the player moves, and a pointer showing which state number we're currently looking at.

Early sketches from when I wasn't sure if this would even be possible.

PXL_20230222_061329446
PXL_20230222_0613294461920×2560 372 KB

More sketching. It took a few tries to reach a performant solution!

PXL_20230222_061422199
PXL_20230222_0614221991920×1440 204 KB

"State" basically means "all the important stuff we want to keep track of", like the position of the player and other tiles in the level (the rocks and holes in the above GIF). When the player starts a level, we want to store that initial state at time 0, so I call this "state T0". If the player moves to the right, then that's the game state at T1 and we store that. If they move right again, we store that as state T2. If they then press "undo", then we tell our state pointer variable to decrease by one (from 2 to 1), then we get that state (T1) and tell the game "be like this", swapping tiles and moving the player according to the data that's in state T1 so that the game is effectively reset to how it was at that time.

That's the fundamental idea, but what does that look like in Pulp?

:balloon: The Pulpscript

Pulpscript doesn't have any fancy data structures like a circular buffer. However, we can call event handlers based on variables as @shaun describes here, and write Lots & Lots of Pulpscript as @brando describes here, in order to simulate one using consistently named global variables!

Here's the dirty secret: as of Blocky Balloon's release (2/20/2023), the player script code is 6224 lines of Pulpscript, over 90% of which is event handler code that either:

  1. Stores current x/y position tile names to state Tn
  2. Tells current x/y positions to swap to the tile names stored in Tn

It actually isn't so bad once you know what code to generate, using the techniques and examples in my other post. When the player moves (in the update handler), store a new state on top and increment the pointer. When the player undos, swap back to state T-1 and decrement the pointer. If we want to store a new state and we're out of space in our buffer, wrap around to 0 and overwrite the oldest state. Likewise, if we're rewinding and the pointer goes below zero (and if we're not yet at the oldest stored state), "wrap under" to point at the top again.

:balloon: Other little things

Of course, there's some additional quirks and "Pulpisms" to work around. Fun fact, if you use goto, the player's update handler will fire. This means that on undo, when the player is sent to a different position then the update handler will fire, and if you always store a new state on every update then that new state will actually be the old state T-1 you just rewinded to and we don't want to store that. In most of these cases though, a boolean flag set from elsewhere will do the trick. Example snippet:

// this gets called from update handler
on storeNewState do
// some checking if the update is legit and we should store the new state...
// exit if this update came from an undo goto
	if undoInProgress==1 then
		log "exiting storeNewState cause undoInProgress"
		done
	end
//...
    stateStackPtr++
	if stateStackPtr==STACK_SIZE then // wrap around if at max size
		stateStackPtr = 0
	end
	//...
	
	playerStateLatest_x = event.px
	playerStateLatest_y = event.py
	call "setStateT{stateStackPtr}ToCurrent"
end

We also don't want to store new states if the player is dead, or moving into a solid wall, or if an animation is in progress... lots of little things like that. Another optimization I figured out: the game state in Blocky Balloons only ever changes along one row or column at a time, so instead of storing entire 25x15 rooms of tiles, each state snapshot is only a row/column and the X or Y axis the player moved along. When I was able to test on-device, I found that the Playdate is usually CPU-bound, so minimizing the amount of "work" done on each move makes the gameplay feel smoother. It's probably also possible to extend this system to support move "redo" as well, but I'll leave that as an exercise for the reader! :grin:

3 Likes