Parallel Block-Based Physics

For the four years I've been working on this game engine, I've been slamming my head against a brick wall: concurrency.  The question of how to process the block-based physics in parallel has been a very thorny and difficult beast to tame.  My naive approaches all centered around synchronization, trying to lock smaller areas at any given time.  These inevitably ended in deadlock, as different physics tasks fought with each other over control of overlapping regions.

On Saturday I had a small burst of inspiration that gave me the solution, which I've now tested on the Tumbler, the class that's responsible for the movement of tumbling sand blocks.

The basic idea is a fairly simple one: the Tumbler gets triggered like normal and even performs a synchronization lock on the entire world, but instead of doing the work on it's task thread, it keeps a thread pool with a number of threads matching the available processor cores on the system.  The work consists of a sorted set of block coordinates that could potentially tumble.

Each thread in the pool then attempts to gain a synchronization lock on the source of work.  As each gains the lock, it obtains a single pair of coordinates and then notifies the work queue of where it will be working, so other threads can avoid that area before releasing the synchronization lock on the work source.

The actual work is then performed.  When the work is complete and a block has either tumbled or not, the thread then seeks to synchronize on the work source again.  When it gains the synchronization lock, it unlocks the area it was working on and seeks a new piece of work, until all work has been completed.

At the moment, this works on one block at a time, requiring locking an area five blocks wide (the maximum area that can be impacted by a block tumbling, requiring additional checks and potential additions to the work queue).  It could be made more efficient by working with sequences of blocks, but is still a decent proof of concept.

The same technique can definitely be applied to the movement of fluid, where I suspect the impact will be even greater, due to the large amount of work that is done for each cell with fluid in it.

So, while I've been saying liquid paint would be coming soon, I must admit I got distracted by something very useful, so that may not make it into the next release.  The next release will include parallel block-based physics, however, which is not something to be sneezed at, when most modern systems have at least 4 processor cores.