One of the new features in Wind-up Knight 2 is checkpoints. They work the way you expect: if you die after passing a checkpoint you will restart at the checkpoint location with the game world restored to its previous state. This sort of system is easy to implement if you plan for it from the beginning of development, but it can be tricky to retrofit to an existing game engine because entities tend to change their state subtly as the game is played. What animation frame was the character on when the checkpoint was hit? What was his velocity? His collision contacts? If you didn’t plan on saving this sort of state when you wrote your entity behaviors, adding it in later could represent a pretty major code change.
We didn’t have checkpoints in the original Wind-up Knight, and when we decided to add them for the sequel I realized we were looking at a potentially massive change to the codebase. Our requirements for checkpoints were as follows:
- Flexible. Need to be able to serialize all the entities in levels we already built.
- Instant. No hitching when saving the checkpoint, and restarting after a death should be instantaneous.
- Repeatable. We only store one checkpoint at a time, but a level can have any number of checkpoints in them.
- Efficient. We can’t use too much runtime memory.
At first, my main concern was Flexibility. We have a lot of entities that change their state in a lot of different ways. Coins that are collected. Enemies that animate, attack, and turn around. Rocks that fall only once. Gates that open and close. I wanted to make a system that would deal with all of those things without having to make code modifications to each.
My first attempt was to use C# reflection. I figured that if I walked the object tree and recorded all of the public fields and properties, I could restore those values on checkpoint reset and be 90% done. Turns out that this isn’t so hard to do in C#, and I was able to knock out a prototype in a couple of hours. But immediately there were problems: the number of fields to serialize was so large that there was a visible framerate hitch, and properties on many Unity objects have side-effects when set (e.g. rigidbody asserts if you try to write to velocity while isKinematic is true), making deserialization difficult. I also noticed that most of the data getting serialized was not really information needed for a checkpoint restore. Most fields never change.
This lead me to try the opposite extreme. I would serialize only specific objects, and only a few parameters of those objects, and anything that wasn’t sufficiently covered would require custom code. For this second attempt I decided only to record the following information:
- Object transform
- Whether or not the object was destroyed since the last checkpoint
That’s it. Any other state would have to be dealt with on a per-script basis. I figured that this method would get me about half way there and then I’d spend a lot of time modifying entity code to deal with state storage and loads. Sort of a lame solution, I thought, but one that probably would meet all of the requirements above.
I implemented this in three parts:
- CheckpointRegistry, a singleton that maintains a record of all objects that are tracked for checkpointing.
- CheckpointAware, a script that marks an object (and all of its children) for tracking, and
- CheckpointBehavior, a child of MonoBehaviour that adds two virtual methods for dealing with checkpoint saves and loads.
CheckpointRegistry contains a HashSet of objects that have been marked for tracking. When a new object is registered, all of its children are automatically registered as well, and top-level objects are called when save or restore events occur. The Registry also provides methods for destroying objects; CheckpointRegistry.Destroy() makes an object inactive and adds it to another set, to be reactivated on the next checkpoint restore or actually deleted on the next checkpoint save.
The real work occurs in CheckpointAware. This script, which is dropped on any object that should save its state when a checkpoint is hit, records the transforms of itself and all of its children. CheckpointAware adds its object to the CheckpointRegistry when it is allocated, and waits to be told to save or restore its state. When a call from the Registry comes in, CheckpointAware reads or writes all of the transforms in its subgraph and calls the appropriate method on any CheckpointBehaviors therein.
To sum up the algorithm: CheckpointAware stores position, scale, and rotation of subsets of the hierarchy. CheckpointRegistry stores references to all of the objects in all of those subsets, and manages object destruction from within those subsets. A checkpoint is saved by calling CheckpointRegistry.SetCheckpoint(), which calls a similar method on each CheckpointAware instance. CheckpointAware records the transform of itself and its children to a simple struct and calls CheckpointBehavior.SaveState() on any children with CheckpointBehavior-derived components. Restoring the checkpoint is the same, but reversed: CheckpointAware walks its list of stored transforms and writes the cached values back into them, and then calls CheckpointBehavior.RestoreState() on any children that need it. Whew.
In any given Wind-up Knight level there are thousands of objects that need to be serialized for checkpoints. Fortunately this method is very fast; there’s no visible hitch on saving or restoring the state, even on fairly low-end devices. It’s also pretty efficient, as only the minimum amount of data required to restore a checkpoint is saved. So there’s two of our four requirements right off the bat. It’s also easy to manage multiple checkpoints with this system, so we can mark off Repeatable as well.
Which leaves us with one last requirement: Flexibility. The weakness of this approach is that it’s only storing positional and lifetime information; nothing about entity state is recorded by default. I thought it was only going to get me half way. But once I had it up and running, I found that it is almost a complete solution. For Wind-up Knight, storing position and lifetime alone proved to be about 90% of the final solution.
I did end up having to go through a bit of entity code to save and restore internal variables. But even that turned out to be simple; most objects just need to record an int or a bool, and can cache them right in the script instance. I spent a day converting existing scripts to CheckpointBehaviors and adding SaveState() and RestoreState() implementations, usually only three or four lines of code each, and then I was done.
Retrofitting a mass of existing code to perform new tricks isn’t fun (even when it’s simple and easy), but the payoff was worth it. Now dying in Wind-up Knight 2 (which happens a lot) hardly slows you down; you’re sent back a bit and get to try again without missing a beat. It’s a huge improvement in the general flow of the game compared to its predecessor (which required a full scene reload on every death–ugh). The architecture of this checkpoint system occupies a nice middle ground between general purpose serialization and script-specific logic, and I’m glad (and a little surprised) that the design worked out so well.
Oh, and if you’re one of the hardcore group of folks that wants to play the game without checkpoints, never fear: you can turn them off.