Replay Seeking

All features have their little complications, but some are really hard won. If you don’t plan for something so demanding from the start you inevitably have to do some refactoring, and then even with a good code design there will be many loose ends to tie up. So it was with seeking within a replay – the ability to skip forward or backward within a recorded game. Until now you could watch the replay from start to finish, with only the ability to slow down or speed up time. This is achieved by feeding recorded game commands into the game engine, initialised with the exact same world state as the original game. In order to allow seeking I had to either play the game at unlimited speed to that point (potentially extremely slow), implement a key frame system to restore a state within the game at various times, or a combination of the two, much like a video file. For starters I’ve recorded key frames, and restore the closest one to the desired seek time.

First I had to refactor the way projectile parameters were stored. Previously every node stored their own projectile parameters – such as how much damage it applies – even nodes that were not actually projectiles but part of structures. It made no sense to do it that way, it just grew out of a poor decision made years ago. All that information is now stored in a list of projectile types. Each weapon specifies which projectile type it uses. This lightened the load for the serialisation required for the replay seeking. It also allows projectile types to be easily re-used, improving the modification system. It’s now possible to make the machine gun fire cannon projectiles with a single line change in a Lua script, for example.

Next I had to work out a way of serialising a great deal more data than I was to date. Because it’s a deterministic game engine, every variable that can affect the future of the simulation must be restored exactly. I thought about this for a while, and settled on the following. Complex data and simple data are separated in each serialised class: node, link, device, and weapon. The complex data can’t simply be written and read out. It primarily includes pointers, but also std string objects, texture ids, etc. Anything that requires some special work to restore. The simple data can be dumped in bulk and then read into the newly created object. The simple data area is marked with a specially named variable and continues to the end of the object in memory.

With that more or less working, I had to record these key frames at roughly equal intervals during the game. I decided to insert them directly into the replay file rather than in separate files, which makes it easier for people to distribute replays. It does also bloat the replay file, but this can be tuned by adjusting the rate at which the key frames are made – plus storage space is cheap these days. I have not serialised projectiles so far, as they contain a fair bit of complex state. With the design of the game at the moment, there are abundant periods where there are no projectiles flying, so the replay system just waits until such a moment arrives to write the key frame. The same goes for delayed splash damage which causes devices to explode in a chain reaction. During replay playback these key frames are skipped, it’s only when the user wants to seek to a certain time that they are used.

Of course the hardest part was restoring the key frames and continuing the game in exactly the same state from that point in the replay. All of the timers in the different classes, which I had considered simple data, needed to have their time keepers fixed up, and their current times explicitly written and restored. I kept it in the simple data area though because the timeout variable had to be serialised. The resources of each team needed to be serialised separately, and various individual variables the physics manager maintained. Every node and device, and subsequent ones, all needed to receive exactly the same numerical ids since the commands in the replay refer to them explicitly. A bug in an existing debugging system became evident due to the larger size of the replay key frame message inserted into the command stream.

The state of the pseudo random number generator used for the physics needed to be dumped and restored and I am unhappy about the 2508 bytes that this takes up each key frame. I will be looking for a better solution to this; perhaps resetting the seed to something predictable when every key frame is created.

Finally there was a slight discrepancy in a physics manager variable that meant that if a command was issued in the same physics frame as the key frame was made, it was applied in the wrong frame when it was played back from that key frame. That variable was changed just after the key frame was made, so it had to be read from the command the new value was contained in. With this fix I could seek around a complex game replay without any desyncs; all the checksums of the replay matched the original game. What a sweet thing to experience!

There are a few loose ends to fix up yet. In the process of developing this feature the effect system started to wig out, creating fire effects from devices that were not firing. In debug mode the game would break with a message about heap corruption. It was difficult to understand what was going on, so I just disabled all effects and will have to go back to work it out. There was also a memory reallocation issue when the replay got too big for the buffer it was in – I worked around that by creating a huge buffer. To complete the feature I need to add a timeline bar with a marker to the current position. I’d also like to analyse the game to place icons indicating battles and periods of construction, like Age of Empires II does in its post-game statistics screen. In the long run I may fast forward the game in the background to allow precise seeking, but that is a low priority for now.

The next biggest hurdle may be to serialise the Lua script states – efficiently. At the moment the seeking will only work for games that don’t have a mission script, and don’t have AI enabled (which is implemented in Lua).

For a prior game I worked on for Ratbag Games, I implemented a system to cut replays and export movies into an avi file. A simple version of that would be nice for this game too. The immediate use for the seeking feature is to allow Nick to create a promotional video for the game, and I’m sure players will want to create their own.

Sometimes I can get obsessed with completing a particular feature, or problems within it. When it’s a large problem the rest of my life tends to get neglected. Lets hope there are not too many big features like this left in the project, or my sleep and other projects will continue to suffer.

Update 1: Thanks to Andrew I have replaced the random number generator with one which requires only 4 bytes of state, and fixed a bug in my normal distribution function.

Update 2: I’ve re-enabled the effects and am happy to find the mysterious corruption did not reappear. It may have been caused by a bug now fixed.

Update 3: Reallocation of the replay buffer in memory has been fixed. The buffer starts at 1MB, and is then incremented in 1MB blocks. These values may be changed in the constants configuration script. I also had to fix a bug caused by a pointer held to a location in the buffer used to write the size of the key frame. If the key frame caused a reallocation, the buffer is potentially moved and the pointer is no longer valid. An offset from the start of the buffer instead does the trick.