The rewind feature

One of the features of Millie and Molly which has got people talking is the rewind ability. This allows players to step backwards through a level to a point where they feel they made a mistake. This can be just one move but can be up to around 650 steps. There’d be no point in rewinding that far in reality as you may as well just restart the levels. So on a computer with very little memory (in modern terms) how do you go about storing that much information?

Each level is made up of an 11x8 grid. So 88 bytes are allocated for the entire map on which I run the logic for digging dirt or falling items etc. Before every move the player makes I store a copy of the layout of the level. After the player’s action this copy if effectively the rewind point for one step were I to copy it back into the main level layout. So I could do this for every step and that’s your rewind feature. However storing 88 bytes for every step of the rewind would soon eat up the memory. The final game uses 4096 bytes for the rewind buffer so storing it like that would allow for 46 rewind steps. Nice but not great and when I was developing I didn’t think I’d have so much free space to play with. I was originally working with 512 bytes which would only allow for 5 rewinds.

So I had to work out a way to reduce the amount of data to store. If you play M&M you’ll notice that not very much can actually change between each move. In fact the maximum is 9 tile changes when a player moves to the side and the whole column he vacates falls down. So when the player moves I actually compare the new layout with the previously saved one and only store the differences. A lot of the time this is only 2 changes; where the player was and where he is now.

So what is the most efficient way of storing these differences? We need to store the x and y coordinates of the difference and what type of tile it was at that stage. That’s just three bytes. So from 88 bytes for a move we can get it down to 6 for the most common change.

But there’s another saving I can make. A byte is 8 bits. As I mentioned the levels are only 8 tiles high. So the y coordinate of a tile is in the range 0 to 7. This can be fit into 3 bits of a byte. The x coordinate is between 0 and 10 which only takes 4 bits. So I can fit both the x and y coordinate into 1 byte. The second byte is still used for the tile type but also has a couple of flags for marking the end of the rewind buffer and whether Millie or Molly are there (because players can be on ladders it slightly complicates it). So now we’re down to 4 bytes for a standard rewind move. Let’s say that with the occasional falling items the average rewind length is 6 bytes this leaves us with 4096 / 6 = 682 rewind steps! More than enough for anybody. 

One final thing I added is that the rewind buffer wraps around on itself. So even if you fill up the buffer it will just start overwriting the really old data at that stage so you should be able to rewind quite a way.