Multithreaded City Generation

As work on version three progressed it became apparent that generating buildings would always be too expensive to do at runtime if you wanted to maintain a fast frame rate.
BuildR was very capable of generating simple buildings within milliseconds but version three had me targeting full city generation at runtime.
I had progressed well with the problem, developing a level of detail system and a simple manager to queue building generation so that we didn’t overwhelm the main thread. However, generating complex buildings would not be possible within the processing budget wanted.

The Job System

The last couple of years saw Unity unveil their job system as part of their move to data based programming. This was a very exciting development which I followed over Unite presentations and blog posts.
It would make sense to investigate what this new system could do for BuildR in solving it’s processing issue. This appeared at first to tie well into what version three was trying to achieve by extracting the data of BuildR from the Unity components and I headed into learning what the Job system has to offer…

Unhappy Marriage

Sadly, but thankfully very quickly, it was apparent that the Job System was not suited to what BuildR needed. The first problem was how the Job System would approach data. To ensure speed, it would want data bundled into similar chunks or in small simple packages. Trying to fathom how BuildR building data would fit into these constraints was overwhelming. It would require a complete rethink of how building data is stored and accessed.
The second issue was time. The Job System data had a very finite maximum lifetime and exceeding this would cause issues. I was aware that with very complex buildings, it could take a very long time to generate the geometry.
So, I decided that the Job System was not the magic bullet to solve BuildR’s runtime generation issue.

Multithreading

After my taste of the Job System though, I started to look into standard multithreading in Unity and C#. Games have not traditionally been multithreaded, so it was an area I was not highly clued up on. Unity and C# would work well together with a few caveats. C# itself is well provisioned to write this code. There are ample examples and explanations on what can be achieved and what should be avoided when writing multithreaded code. Unity isn’t written for this though. It lives on the main thread, as does it’s family of objects (gameobjects, materials, textures). Trying to do anything with these directly in threads would be a problem.
It did promise to fix the generation of even the most complex buildings. I was even thoughtful of it completely freeing the main thread of BuildR, allowing the game to run at whatever framerate it would sustain without generating buildings.
Using multithreading would also allow BuildR to generate multiple buildings in parallel too, making it even faster. I could use as many threads as I the system would give access to!

Adventures in Parallel Processing

Version three of BuildR had already been a process of splitting out the data from Unity, and this was going to pay off when I started to write multithreaded code. The buildings in BuildR were ideal candidates for multithreading to begin with. They were individual blocks of data what didn’t really touch other data points. There was also a lot of preprocessed data from Unity objects too (things like mesh data, bounds size) which would be inaccessible directly when off the main thread.
Writing the threading code involved changing the manager to deal with sending buildings off into their own threads and waiting for the procedurally generated building data to return.

Race Conditions

On of the fun things about threads was the ease with which you could produce a race condition. The bugs created by this are hellish to reproduce as it’s entirely dependant on multiple processor cores working together (or should I say against each other).
I came across one simple case when multithreading BuildR. The most central class BuildR depends on is the Dynamic Mesh class. It handles collecting the generated mesh data into a format that can then be transferred over to a Unity mesh and they were used throughout BuildR to generate every part of it. In version three, two big things has changed about how I dealt with these objects so that I could reduce garbage allocation. First, I had the internal lists for vertices and normals set to a high capacity so that they would unlikely exceed this during generation. And second, I created a static pool of them so that we would only allocate what we needed and reuse what we had.
The static pool was accessed by the threads to get a Dynamic Mesh to generate BuildR wallsections and here was where the fun began. C# allows you to lock methods that are being accessed by multiple threads. It will elegantly block other threads when one is executing it and would form a queue while this is running. I had thought this method was well covered in my initial attempt but maybe after a hundred or so buildings were procedurally generated, there would be errors popping up that suggested I had not fully locked this class down and a race condition was happening. Instances of the Dynamic Mesh class were being reset by one thread finishing while another thread had got hold of it and started generating with it. So I was seeing errors halfway through the generation process that would normally be impossible to get that far.
The solution was to completely lock down the static pool so that only a single thread could access it at once. I wanted to be a little more smart about this class, as I worried it would be a bottleneck for the generation processes, however it seems it’s simpler and safer just to keep this class in lockdown.

Lifecycle and Synchronisation

Finally, I found that I would need to solidify my threaded code to deal with a simple lifecycle. I had created a generic class for dealing with threading that would transfer to other projects (and I aim to share that very soon!).
I created an interface that defines the lifecycle of the task sent to the threading manager and a simple identification and event system to allow external classes to intercept complete executions so that the data could be synchronised with the main thread.
So far this process has removed all building generation off the game thread and into the other unused cores of the processor. The framerate at runtime is now almost unaffected by complex building generation and we have the ability to generate multiple buildings at the same time giving us further speed at generating a city.