Serialization-Based Undo

After Blockdown’s release (Steam page), the #1 feature request from players was for undo support. While the game already supports a “restart level” feature, many modern puzzle games allow players to undo each action individually.

This presents me with an interesting challenge because Blockdown allows each puzzle script to inject arbitrary code into the game loop. In the name of simplicity, Blockdown does not use the “command” design pattern anywhere in its codebase. See my previous post for more about Blockdown scripting.

If I had to rewrite Blockdown from scratch, I might re-consider the decision to avoid a command-based architecture. However, to make my players happy, I came up with a serialization-based approach for undo that I think isn’t terrible, so I thought I’d write a quick post about it.

Dictionary-Based Compression

Since I want to implement an infinite undo stack by periodically serializing the entire game state, I’m naturally concerned about memory consumption. Supporting undo in this way can look a bit like a memory leak – every time the player makes a move, tons of data gets pushed to a stack. While researching ways to deal with this, I came across an interesting conversation in the Mercurial developers mailing list.

The conversation is about storing file deltas in Mercurial. Yann Collet, the compression guru responsible for zstd, is making a suggestion to Gregory Szorc, a Mercurial contributor and member of its steering committee:

Another potential suggestion could be to use dictionary compression in "content-only" mode.

Here is how it could work :
Presuming you have a "first original file", and you want to send a second file as delta to the first :
Compress the second file, using the first file as "dictionary".
(use ZSTD_compress_usingDict() for this scenario).

This is not a properly formatted zstd dictionary, so it triggers "content only node",
which means it has no statistics, hence no way to precompute anything.
But it can use the dictionary content for back-references.
Hence common parts should be referenced as an LZ copy operation.

This is compelling to me, because an undo stack is similar in many ways to a version control system.

It turns out this works really well. Using zstd dictionaries is so good that it makes more sense to store the entire game state in each stack entry than to store the outputs from a Myers diff algorithm. I tried measuring the memory footprint of the stack for a few different levels in the game and here are the results.

The dictionary takes up space (not included in the above table), but it’s not a per-entry cost. Blockdown creates only one zstd dictionary per top-level object by using the initial state of the game level.

So, in a sense, this type of undo stack does not store diffs between subsequent game states; rather, it stores deltas between each game state and the level’s initial state. The number of moving parts in most of Blockdown’s puzzles is quite small, so the resulting compression is quite good.

The neat thing is that you don’t really mess with diffs at all – after decompression, each entry in the undo stack is an entire state vector. This makes it possible to instantly jump to any point in the game history, without the need for applying a sequence of diffs.

The C++ Components

Blockdown’s undo architecture has three components.

• UndoSystem exposes the top-level API and contains two stacks (the “done” and “undone” stacks).

• Serializer is owned by UndoSystem and has methods for appending to internal byte buffers (similar to an output stream) and methods for reading from its internal byte buffers (similar to an input stream).

  Serializer holds a read/write buffer for each of Blockdown’s high-level game objects. This is somewhat similar to an array of std::stringstream objects, but since I’m not a fan of C++ streams, it doesn’t use them internally.

• BlobStorage is owned by Serializer and knows hows to compress data blobs using zstd dictionaries. This is what is used in lieu of a std::stringstream buffer.

This system requires all top-level game objects to expose two serialization methods:

void undo_write(Serializer& writer) const;
void undo_read(Serializer& reader);

Each object is responsible for reading and writing any state that it thinks is relevant to undo. Note that state that is constant over the lifetime of a level does not need to be serialized.

BlobStorage

The Serializer class holds a BlobStorage instance for each top-level game object. These are mappings from sha1 digests to data blobs, and they hide the process of compression and decompression. Here’s the BlobStorage API:

// Simple refcounted "database" of blobs that uses SHA1
// digests as ids, and zstd compression for storage. The
// first blob that gets inserted into the database is
// automatically used to make a zstd dictionary. This
// enables really great compression for blobs that have
// similar data.
class BlobStorage {
public:
  using Buffer = std::vector<uint8_t>;
  using Digest = std::string;
  BlobStorage(ZSTD_CCtx*, ZSTD_DCtx*);
  ~BlobStorage();

  // PUT.
  //
  // Computes the SHA1 digest for the given buffer, then
  // checks if it has already been stored. If it has not
  // been stored, compresses the buffer and stores it. If
  // it has already been stored, increments its refcount.
  Digest put(const Buffer& buffer);

  // GET.
  //
  // Checks if a buffer has been stored with the given
  // digest and decompresses it into "result".

  bool get(const Digest& digest, Buffer* result) const;

  // ACQUIRE.
  //
  // Checks if the given digest has been stored and if
  // so, increments its refcount.
  bool acquire(const Digest& digest);

  // RELEASE.
  //
  // Decrements the refcount of the given blob. If it
  // reaches zero, it is immediately freed.
  void release(const Digest& digest);

  // RESET.
  //
  // Frees all blobs and destroys the zstd dictionary.
  void reset();
};

Serializer

As stated earlier, the Serializer component is actually just an array of read/write streams. The real work of serialization is deferred to each of Blockdown’s top-level game objects. Each game object proffers read/write methods that take a Serializer as an argument.

Serializer is also the factory and manager of Snapshot objects, each of which represents an entire game state. Snapshot objects are used by UndoSystem to form stack entries.

class Serializer {
public:
  using SlotId = int;
  using SlotMask = uint32_t;

  // The Serializer is constructed by giving it
  // a fixed number of "slots", where each slot
  // corresponds to a high-level game object.
  Serializer(int num_slots);

  // Clears the compression dictionaries for all slots
  // and the backing storage for all snapshots.
  void reset();

  // Selects the slot to use in subsequent calls to
  // write_begin() and read_begin().
  void set_current_slot(SlotId id);

  // Starts a writing session for the current slot
  // and clears its output buffer.
  void write_begin();

  // Ends a writing session and invokes compression
  // on its output buffer.
  void write_end();

  // Appends a value to the output buffer. Must be
  // called between write_begin() and write_end().
  template <typename T> void write(const T& value);

  // Starts a reading session for the current slot
  // and decompresses its input buffer.
  void read_begin();

  // Ends a reading session.
  void read_end();

  // Fetches a value from the input buffer and
  // advances the input cursor.  Must be called
  // between read_begin() and read_end().
  template <typename T> T read();

  // Creation and destruction of snapshots.
  Snapshot* snapshot_create();
  void snapshot_destroy(Snapshot* snapshot);

  // Replaces the current Serializer buffers with
  // the given snapshot.
  void snapshot_apply(Snapshot* snapshot);

  // Returns which slots in the given snapshot
  // are different from the current buffers.
  SlotMask get_affected_slots(Snapshot* snapshot) const;
};

UndoSystem

Max Liani wrote an excellent post on the subject of undo, and I used this as a starting point for the UndoSystem component. Here’s the API for UndoSystem in Blockdown, and it’s fairly similar to Max’s.

class UndoSystem {
public:
  // Adds a new entry to the undo stack and
  // clears the redo stack. If collapse is
  // true, this first pops the undo stack.
  void done(bool collapse = false);

  // Applies the top of the undo stack to
  // the game and moves it to the redo stack.
  void undo();

  // The inverse of undo.
  void redo();

  // Clears all stacks and re-captures the
  // entire game state.
  void reset();

  // Gets the rough number of bytes consumed
  // by the undo and redo stacks.
  size_t footprint() const;

  // Called every tick to update game state
  // if an undo or redo operation is underway.
  void update_animation(double dt);

  // True if an undo or redo is underway.
  bool is_animating() const;
};

Here are some things to note in this API that might make it a little different from other undo systems:

1. The done() method includes an optional collapse argument. In Blockdown, done() is called every time the player makes a move in one of the four possible directions. However, sometimes the custom puzzle logic will automatically perform some action shortly after a move.

   For example, consider a tile switch that raises a drawbridge. After the drawbridge is raised, the level’s script will want to replace the top of the undo stack rather than pushing to it, so it calls done with collapse set to true.

2. Because memory consumption can be a major concern with serialization-based undo, for diagnostic purposes it was useful to add a footprint() query.

3. Blockdown’s undo system supports animation. When the player requests an undo, you can watch the game change to its historical state over the course of 250 milliseconds. On every frame, the game calls update_animation() on the undo system, passing in a time delta.

Retrospective

In retrospect, I think it would have been better to write Blockdown from the beginning with undo in mind. Even though zstd dictionaries are very cool, I think that storing individual actions in the game history might have been easier to deal with.

Even better, I wish that I had thought about an “instant replay” feature from day one, rather than an undo system, since animated undo would naturally fall out from that.

That’s all for now! If you’re interesting in trying out the game, head over to its Steam page.