by

August 2015 Update - A week with Michael

(
Aug
09
)

I am writing this update on my phone, from a beautiful, but currently rainy, Spanish town. The last couple weeks were quite eventful - let me summarize:

First, I moved back from Russia to Germany. My wife and me will both do our masters in Munich!

Then we celebrated our wedding a second time, with my German family and friends - and with a special guest who came all the way from Australia: Michael!

Michael and me decided to spend the next week pair-programming Citybound, something that we already planned to do "some day". Now we had this opportunity and even though I was half-distracted by my day job which I took up again (gotta pay rent somehow) I would say we made a lot of meaningful progress.

We even recorded a video outside together, but due to my mistake to ignore the wind, the audio is ruined. And my rambling there is pretty incoherent anyways. That's why I'm writing this as a text post instead! Given that, I will go into a little more technical detail - even though I already hate writing on my phone. (I have to write it from my phone because I'm on holiday and I didn't bring more than my phone, because it's supposed to be holiday, right?) Anyways...

The initial plan: multithreaded Citybound

The goal we set ourselves for this week was to introduce multi-threading to Citybound, using a small part of the game that we would parallelize as a proof of concept.

We didn't exactly get there, but we got a lot of things leading there done, and covered some other topics in the process.

Moving to Electron.js

Citybound runs inside a tweaked Chrome Browser, which allows us to both ship the game as a single bundled executable and to make use of some features that are not enabled by default or completely not present in normal browsers.

For most of the development, NW.js was used as this browser container, but recently Electron.js emerged and turned out to be the better-maintained, cleaner-designed, more full-featured and more up-to-date alternative.

Moving all the code of Citybound to Electron went quite well and already paid off: we could already start using WebGL2, for example.

Hardcore IPC: Shared Memory

Modern JavaScript does offer WebWorkers as primitives for parallelization, but the way they communicate with each other or with the main thread is quite clunky: they can either share data by copying, or they have to completely give up all access to data that is handed over to another thread - these options are either too slow or too impractical, neither something that you can do repeatedly every simulation frame.

Michael had the inspiration and the bravery/foolishness to use a much lower-level way of sharing data: shared memory. This would definitely give us the required speed, but it would make us directly responsible for not getting into any concurrency issues like race conditions.

Because we are using a tweaked browser like Electron.js we can make almost arbitrary functionality available in JavaScript, in our case, there even already existed a NPM package which did just what we needed, (shared memory, using mmaped files to be precise), but only in Linux and Mac. Implementing this also for Windows should be "kinda straightforward", but as this oxymoron tells you, it is not one of the things I look forward to.

Michael played around with this NPM package and made a simple test case work, with a main thread and a worker thread, writing and reading shared memory.

How we want Citybound to be multithreaded

Now that we had the low level tools to make parallelization possible, we needed to come up with a strategy to correctly make the whole game work in a parallelized context.

Our proposed solution is quite simple: the whole city is spatially subdivided into chunks, each of which functions like a small city itself. Each chunk can be processed by a different thread. The chunks only need to communicate when an agent passes the border between two chunks: they then exchange information regarding this agent and its current trip - it is completely handed over.

This means that each chunk processes only the agents inside it - only it has write access to their underlying data. Still, every thread can read-access the information of all agents in all chunks of he city, which might be needed as reference information. In my oversimplified imagination of the whole idea this completely avoids all race conditions and everything is perfect.

Because the "surface" of each chunk is much smaller than its "volume", the number of agents crossing the border between chunks should be much lower than the number of agents that stay within one chunk. This should keep the overhead of communication between chunks fairly low.

Storing people in binary data

One problem with the shared memory that we are using is that it is just flat byte buffers - no easy way to store (potentially quite complex) high-level JavaScript objects. What I ended up working on for most of the week was writing a proxy wrapper that allows accessing this huge shared byte buffer as if it was a collection of high-level objects - making sure that in the background all information is correctly serialized to and respectively rebuilt from a very compact binary representation, using a simple data layout schema (which each entity type in the game will have).

This sounds at first like a lot of hassle for no new functionality, but only it really allows us to use shared memory in our high-level simulation and it has some pleasant side effects:

First, it gives us savegames for free, since the serialization/parsing that they would require happens all the time anyways. All that needs to be done is to dump all shared memory to disk on save and to copy a stored buffer to shared memory on load. If all nontransient game state lives in this shared memory (which I hope), then savegames are indeed easy.

Another benefit is that we might be able to port parts or all of the simulation onto another programming language, running in a different thread, but also just accessing this shared memory - and the existing JavaScript code won't even notice the difference.

Finally, I think that some WebGL related stuff might become simpler or faster by all of the simulation data already existing in raw binary form, ready to be sent to the GPU (for example for instanced/batch drawing of cars)

My progress on this I would classify with the ever-so-vague "mostly done".

A day in the life of a citizen

Thinking about the parallelizability of the simulation forced us to come up with clear architectural plans for the economy, and my existing model for that still had some holes. One such hole was how to organize a citizen agent in the code - so far I just assumed all of a citizens behavior would be contained in a simple class and that all the points where an agent can make a choice would be explicitly hardcoded.

Stated like that, that already sounds bad - Michael had the idea to instead model citizens as state machines and sketched out what the states and transitions for a normal day of a citizen would look like.

Our state machines are not state machines in the strictest sense, they are probabilistic (meaning each transition has a probability of being chosen relative to alternative transitions) and transitions can include side effects that change properties of the citizen, their family, or the whole world. The probabilities of transitions can then also depend on such external properties.

This state machine model made the whole process of defining an agent's behavior much more declarative and extensible. There turned out to be a couple important hub states where a lot of transitions lead to and go from (for example "leavehome") - which would also work really well as hook points for mods to easily extend the behavior of citizens, starting at any existing state in their day and bringing them back to an existing state.

In fact, this structure seemed to have hit the creativity sweet spot between freedom and constraint. Especially after adding a visualization of our current state/transition graph it became very easy to spot mistakes like dead end states as well as to come up with new states and transitions just by looking at the graph for long enough.

The biggest surprise was that even very complex behaviors like getting married or moving out of the parents' home could be modeled there quite easily. Even rare or obscure events, like a pyromaniac setting a couple houses on fire and then returning home happily fit into this framework as well. The possibility space for mods there is certainly inspiring!

What's next

Now we have to take all these ideas, half-implemented pieces, architecture plans and programmatic sketches and turn them into working code.

This will take some time, but we'll keep you up to date and once I've settled in enough, I definitely want you to participate in livestreams again!

Until then, I hope the perspective I laid out here gives you some food for thought and continued excitement for the wonderful game that this will become!

See you all soon!

Discussion on /r/Citybound
Support Citybound