Background: A Tale of Two Worlds

Note: I'm working on a mindblowing, super secret update. I don't know how long it will take so I will bridge the time in between with a series of more abstract posts, covering some of my current thoughts!

This blog post is about a new approach to capture and update the state of the ingame world in Citybound and what it makes possible.

The naive approach to state handling

In the old Javascript prototype of Citybound, all of the game state was stored in memory in a pretty straightforward fashion:

Each game object existed once, in its current state.

To update the whole simulation, I would go over each object and update it individually.

This had three big problems:

When I want to write a savegame, I have to wait until the current simulation step finishes to end up with a constistent view of the world in the save game.

When I update car A, I don't know if car B, which is in front of it, was already updated in this simulation step or not.

• This leads to for example a wrong estimate of available breaking distance (because you're essentially comparing the future with the past).
• In this case it's not that horrible (it just causes weird jittering), but for other interactions between game objects it might even lead to inversions of causality.

Once I update a game object, there is no way to see the previous version of it anymore.

• For example, if it's payday and I apply the incomes of all the members of a household to its wealth, I can't find out in a following simulation sub-step, by how much the wealth of the household increased in this timestep - because I overwrote the old value to compare to.

The worst: if I tried to parallelize the simulation and I'm updating car A in one thread and car B in another, car A might try to get some information about B that is currently being overwritten by the other thread (imagine trying to read a number on a blackboard that someone is currently changing) - and you will end up with garbage information about B.

• In the best case this leads to wrong behaviour.
• In the common case this just crashes the game.
• The only way to solve this would be to introduce so called synchronization locks, but they bring a significant overhead with them (imagine the blackboard guy always having to put up a sign "wait a sec, I'm rewriting the number" and you having to wait until he removes the sign again).

Introducing the "double buffer"

In the world of computer graphics there exists the concept of double buffering, maybe you've already seen a setting called like this in a game's graphics settings.

Double buffering is the solution to the problem that your graphics card draws to the screen pixel by pixel, but you only want to see whole, finished pictures (else you get a visible "tear" between the old and new pictures).

Note: This is exactly equivalent to the first problem stated above, that in a savegame you only want to see a finished simulation step, even though the simulation updates the world one object at a time.

So double buffering works like this: you introduce a second ("double") buffer to hold a picture for the screen, and then you always display one of them on the screen, while letting the graphics card draw (pixel by pixel) onto the other screen. When it's done, you simply swap the roles of the two buffers, showing the recently finished picture that's in the second buffer and starting to draw the next picture into the now hidden first buffer.

What if we apply the same concept to our simulation? What are the two buffers in our case?

In our case this means that we always have exactly two representations of the game world: the past and the future.

Very nicely following intuition, the following properties hold:

• Updating the world means: determining the future based on the past.
• After one simulation step ("time passes") the future becomes your new past and you start determining an even newer future (this is exactly the swapping of buffer roles).
• Inside one simulation step, the past cannot be changed and you know for sure that it is correct and consistent, even when you determine the future in a parallelized fashion.

This truly makes parallelization possible.

Even better, this brings the following surprising advantages:

You can at any point in time create a savegame out of the past and even start saving it in parallel to the current simulation step.

It makes it much easier to test the simulation in a "does this actually lead to that" way.

For programmers: the simulation update looks much more functional on all levels - instead of willy-nilly mutating the current simulation state, you explicitly map an immutable past to a future in an almost declarative way.

If there is a bug in the game, where a correct past state results in an invalid future state or even a game crash, you can at least save the past state (as an emergency measure). Then you reload the game in this state and try fixing it until it doesn't crash and produces the correct future state.

• This means that even if someone else finds a game-crashing bug, they can just send me their emergency-auto-savegame and I can debug exactly this case of wrong behaviour that they discovered.
• That means that I can write the game with a "let it crash" mentality, where I don't try desperately to keep the game running even under invalid circumstances, trying to sweep them under the rug.
• This makes a lot of code much simpler and leads to earlier discovery of bugs - while still keeping your most valuable savegame! (ideally)

The only drawback: you need exactly twice as much memory.

I would say: worth it.