Working out Replays

My current project, Protonaut, somewhat recently got a "Replay" feature. You can save your victories and share them with your friends! But how to execute the replay feature is really tricky, especially when you only have finite space and bandwidth to dish them out with.

Protonaut uses a level editor and a collection of Box2D parts - somewhat similar to Fantastic Contraption. Replays in FC are called designs, and all it is is a snapshot of the starting conditions. Since there is now way to interact with FC mid-design, you can safely let the simulation "play out" on your computer, and it will turn out the same. It's as if the fate of your contraption has been pre-determined.

I'm not able to do this obviously. You control the player character throughout, and you can change your mind halfway through playing a level - what with having a brain and free will and all.

After looking at a few options (taking a snapshot of all the objects in the level and tweening them for example), I decided to go with recording keypresses. While a replay is running, it's as if one of those automatic-piano-playing-rollers is over your keyboard. The game otherwise thinks it's you controlling it yourself!

Building the data structure was simple at first. I just wanted to get it done, and I wasn't thinking about storage requirements. Here's an example clip of the replay file:

[...] ,,1,1,0,0,0,0,0,0,,2,2,0,0,0,-1,10,0,,3,3,0,0,0,23,0,0 [...]

I used comma deliminators and the data is broken down as:

,,Array Index, Tick#, jumpstate, firestate, (other keys)...

Keystates could be At Rest (0), Just Released (-1), or Held Down (length).

There was several problems with this setup, mostly structural, but all my fault. It was possible to hold down, say, the fire button for millions of ticks - throwing huge numbers into the mix and making it a very big and clunky bit of code. To help smooth things over, I did ZIP the file - which shrunk things down nicely.

Yesterday I decided to clean things up. I realized that "just released" and "held length" could be programatically determined; If the last frame was > 0 and this frame == 0, then it means the key was down last tick.. but not this tick. -1 for release. So it was no longer necessary to store the actual keystate, but just an up/down 0/1 representation.

That means that the keystate could be summarized in a single 6-bit number, that has 64 possible combinations. From there it was easy to find a spot on the ASCII Character table that had 64 human-readable characters in a row, and just mapped the key value to that.

Then I stripped out the commas and dropped recording of null frames (where you aren't pressing any keys). Then I dropped the array indexes, because they were completely unused. Now the replay data looks like this:

...191J192Q200p201'202'203'204'205W300L...

Quite a bit shorter! All it is is "Tick#" followed by a character that represents the keypresses.

After running this through the ZIP algorythm, total space on the database was reduced to 1/20th of it's original size (using a speedrun on Tutorial #1 as a basepoint)!! I'm so very happy with this... I'm sure my database will agree with me. And my bandwidth bill.

Special thanks go out to Aubrey for helping me out with BitShifting and Ryan for writing me out a psuedocode Binary-to-String function.