Design Doc
Source Code
Live Builds

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.

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

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.

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:

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.

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

I would say: worth it.

→ Discussion on /r/Citybound