Time travel

Time travel was the very first feature I ever wanted LiSE to have. I took one look at Inform 7's Skein view and knew I needed it; why hadn't anyone done that for other types of game?

The very earliest attempts at LiSE were thin wrappers for a SQLite database holding logs of game events. To look up the present value of any given variable, it selected the value with the largest turn number that was smaller than the turn the game was on. It was uselessly slow, and I didn't expect it to be fast. Then I brought the database into memory, using Python's array library, which didn't work very well at all, frankly; but I had the good fortune to attend the International Roguelike Developer Conference of 2016, which had a panel by Jeremiah Reid that set me on the right path.

I'd been assuming you needed fast random access to the history of the game, but you don't. That's not how people use time travel. Nearly every time you time travel, you're rewinding. Jeremiah showed me that the rewinding operation is best modeled by popping from a stack, so I immediately went home and rewrote LiSE to do it that way.

Jeremiah modeled the past values of each game variable as a stack; to his model I added another stack, representing the future. It is empty when you're playing the game the normal way, but when you rewind, it lets you fast-forward to get back to the present. These two stacks are wrapped together in the WindowDict, a key-value store resembling a Python dictionary, whose keys must be well ordered. Looking up the value of the same key as the last time is practically instantaneous in a WindowDict; looking up keys near to that one is fast as well. Anything else is a gamble, but that's fine.

This approach worked fine at first, and if I was content to have a game run in the same process as its interface, I might have shipped LiSE that way. But that was impractical, because I was writing in Python, which can't run multiple operations at once within a single process--though this may not be true for much longer. So, to keep the interface responsive while LiSE was simulating the game world, I needed a way for LiSE to run in a subprocess, and give reports of changes to the world. I call the reports "deltas". It might be simpler to just copy the whole world state every turn, but this would require me to iterate over the whole world, and I don't want to do that. It's slow. So how to avoid it? Well, that turned out not to be too hard: whenever the simulation makes a change to the world, apart from keeping the change in the regular WindowDict, I also keep a copy in a big list of changes, indexed by the time of each change. A delta is just a slice of that list.

By this point, it was 2018, I'd been working on LiSE for two years, and I was itching to put together a game. So I started, and it seemed to be going fine until I made the world ten times bigger. It ran okay, actually! But when I closed the game, and reopened the same database again, it took three entire minutes before it was ready to do anything. What was taking all that time? It was keycaches--an optimization I'd introduced earlier for when, instead of looking up the value of any given variable, you're iterating over, say, the set of nodes that exist, or the set of keys that a particular node has values for. They're inconsequential for performance when you're playing the game, but when you're starting it, and it has to make a keycache for each and every entity that's ever existed in it, and the keycache needs to be updated for every time the set of entities changes, creating the keycaches in the first place took unacceptably long.

I needed a way around this, so I added keyframes, which are similar to save states in emulators. They have the whole state of the game world at any given time. This slightly changed the algorithm for looking up the present value of a variable: now you only look back through the WindowDict until you reach the time of the last keyframe, at which point you're done, and can use the value in the keyframe. Creating a keyframe from scratch is slow, but you only need to do that once, at the start of the game. After that, all further keyframes are made the same way that the user interface is updated: apply the delta since the previous keyframe.

The only missing piece was the rare case when you do have to time travel "randomly," perhaps to another branch of time altogether. There's no way to make that fast, but I was able to make it "not that slow" by taking a keyframe of the current time and the time you want to travel to, then using numpy to rapidly compare the states.

And that was the state of LiSE in April 2023, when I made this demo: