How should I structure my classes to allow for multithreaded simulation?

In my game, there are plots of land with buildings (houses, resource centers). Buildings like houses have tenants, rooms, add-ons, et cetera, and there are several values that have to be simulated based on all these variables.

Now, I'd like to use AndEngine for the front end stuff, and create another thread to do the simulation calculations (perhaps also later include AI in this thread). This is so that one whole thread doesn't do all the work and cause problems such as blocking. This introduces the problem of concurrency and dependency.

The currency problem is my main UI thread and the calculation thread would both need to access all the simulation objects. So I have to make them thread-safe, but I don't know how to store and structure the simulation objects to enable that.

The dependency problem is that in order to calculate values, my calculations depend on other objects' values.

What would be the best way to link up my tenant object in the building with my calculations? Hard-code it into the tenant class? What is a good way to do "store" algorithms so they are easily tweaked?

A simple lazy way would be to bung everything into a class which holds all the object, such as plots of lands (who in turn hold the buildings, et cetera). This class would also hold game state such as the technology available to the user, object pools for things such as sprites. But this is a lazy and dangerous way, correct?

Edit: I was looking at Dependency Injection, but how well does that cope with like a class that holds other objects? i.e, my plot of land, with a building, which has a tenant and a host of other values. DI looks like a pain in the bum with AndEngine as well.

• Just a quick note, there is no concern about concurrent access to data if one of the accesses is only ever read only. As long as you keep your rendering only reading the raw data to use it for rendering and Not updating the data during its processing, there is no issue. One thread updates the data, the other thread just reads it and renders it. – James Oct 6 '11 at 18:35
• Well the concurrency access is still a problem, as the user can buy a plot of land, build a building on that land and put a tenant into a house, so the main thread is creating data and can modify the data. The concurrent access isn't so much a problem, its more about its instance of sharing between the main thread and the child thread. – NiffyShibby Oct 6 '11 at 21:41
• I talk of dependency as a problem it seems people like Google guice think hiding dependency isn't a wise thing. My tenant calculations depend on the building plot, building, creating a sprite on the screen (I could have a relational relationship between a building tenant and creating a tenant sprite elsewhere) – NiffyShibby Oct 6 '11 at 21:45
• I guess my suggestion should be interpreted as making the things that are threaded off be things that are either self contained or require read-only access to data managed by another thread.. Rendering would be an example of something you could thread off as it would only need read access to the data so it can display them. – James Oct 6 '11 at 22:47
• James, even a read-only access can be a bad idea if another thread is in the middle of making changes to that object. With a complex data structure it could cause a crash, and with plain data types it could cause an inconsistent read. – Kylotan Oct 7 '11 at 10:36

Your problem is inherently serial -- you must complete an update of the simulation before you can render it. Offloading the simulation to a different thread simply means the main UI thread does nothing while the simulation thread ticks (which means it is blocked).

The commonly held "best practice" for concurrency is not to put your rendering on one thread and your simulation on another, as you are proposing. I strongly recommend against that approach, in fact. The two operations are naturally serially related, and while they can be brute forced, it's not optimal and it does not scale.

A better approach is to make parts of the update or rendering concurrent, but leave updating and rendering themselves always serial. So for example, if you have a natural boundary in your simulation (for example, if houses never affect each other in your simulation) you can shove all the houses into buckets of N houses, and spin up a bunch of threads that each process one bucket, and let those threads join before the update step is complete. This scales much better and is a much better fit for concurrent design.

You're over-thinking the rest of the issue:

Dependency injection is a red herring here: all dependency injection really means is that you pass ("inject") the dependencies of an interface to instances of that interface, typically during construction.

That means if you have a class that models a House, which needs to know things about the City that it is in, then the House constructor might look like:

public House( City containingCity ) {
m_city = containingCity; // Store in a member variable for later access
...
}


Nothing special.

Using a singleton is unnecessary (you often see it done in some of the insanely complex, over-engineered "DI frameworks" like Caliburn that are designed for "enterprise" GUI applications -- this does not make it a good solution). In fact, introducing singletons is often the antithesis of good dependency management. They also can cause serious problems with multithreaded code because they cannot usually be made thread-safe without locks -- the more locks you must acquire, the worse your problem was suited for handling in a parallel nature.

• I remember saying singletons were bad in my original post... – NiffyShibby Oct 7 '11 at 18:31
• I remember saying singletons were bad in my original post, but that was removed. I think I'm getting what you are saying. Example being, my little person is walking across a screen, as he is doing that the update thread is called, it needs to update him, but can't because the main thread is using the object, thus my other thread is blocked. Where as I should be updating between rendering. – NiffyShibby Oct 7 '11 at 18:56
• Someone has sent me a useful link. gamedev.stackexchange.com/questions/95/… – NiffyShibby Oct 10 '11 at 14:31

Usual solution for concurrency problems is data isolation.

Isolation means that every thread has its own data, and does not touch data of other threads. This way there are no problems with concurrency... but then we have problem of communication. How can these threads work together if they don't share any data?

There are two approaches here.

First one is immutability. Immutable structures/variables are the ones that never change their state. At first, this may sound useless - how can one use a "variable" that never changes? However, we can swap these variables! Consider this example: suppose you have a Tenant class with a bunch of fields, that is required to be in some consistent state. If you change a Tenant object in thread A, and at the same time observe it from thread B, thread B may see the object in inconsistent state. However, if Tenant is immutable, thread A can't change it. Instead, it creates new Tenant object with fields set up as required, and swaps it with the old one. Swapping is just a change to one reference, which is probably atomic, and thus there's no way to observe the object in inconsistent state.

The second approach is messaging. The idea behind it is that when all data is "owned" by some thread, we can tell this thread what to do with data. Every thread in this architecture has a message queue - a list of Message objects, and a messaging pump - constantly running method that removes a message from the queue, interprets it and calls some handler method. For example, suppose you tapped on a plot of land, signaling that it needs to be bought. The UI thread can't change the Plot object directly, because it belongs to logic thread (and probably is immutable). So UI thread constructs a BuyMessage object instead, and adds it to logic thread's queue. Logic thread, when running, takes the message from the queue and calls BuyPlot(), extracting the parameters from the message object. It might send a message back, for example BuySuccessfulMessage, instructing UI thread to put up a "Now you have more land!" window on screen. Of course, access to message queue must be synchronized with lock, critical section or whatever it is called in AndEngine. But this is a single point of synchronization between threads, and threads are suspended for a very short time, so it's not a problem.

These two approaches are best used in combination. Your threads should communicate with messages, and have some immutable data "open" for other threads - for example, an immutable list of plots for UI to draw them.

Note also that "readonly" does not necessarily means immutable! Any complex data structure like a hashtable can change its internal state on read accesses, so check with documentation first.

• That sounds a neat way, I'll have to do some testing with it, it sounds quite expensive this way, I was thinking along the lines of DI with a scope of singleton, then use locks for the concurrent access. But I've never thought of doing it this way, it could possible work :D – NiffyShibby Oct 7 '11 at 12:24
• Well, that's how we do concurrency on highly-concurrent multithreaded server. Probably a little overkill for a simple game, but that's the approach I'd use myself. – Nevermind Oct 7 '11 at 14:19

Probably 99% of the computer programs written in history used just 1 thread and worked fine. I don't have any experience of the AndEngine but it's very rare to find systems that require threading, just several that could have benefited from it, given the right hardware.

Traditionally, to do simulation and GUI/rendering in one thread, you simply do a bit of the simulation, then you render, and you repeat, typically many times per second.

When someone has little experience of using multiple processes, or doesn't fully appreciate what thread 'safety' means (which is a vague term that can mean lots of different things), it's too easy to introduce many bugs into a system. So personally I would recommend taking the single-threaded approach, interleaving simulation and rendering, and saving any threading for operations that you know for sure are going to take a long time and absolutely require threads and not an event-based model.

• Andengine does the render for me, but I still feel that the calculations have to go in another thread, as the main ui thread would end up slowing down if not blocked if everything is done in one thread. – NiffyShibby Oct 7 '11 at 12:26
• Why do you feel that? Do you have calculations that are more expensive than a typical 3D game? And are you aware that most Android devices only have 1 core and therefore gain no intrinsic performance benefit from extra threads? – Kylotan Oct 7 '11 at 13:48
• No but its nice to separate out the logic and clearly define what is being done, if you keep it in the same thread, you'd have to reference the main class where this is held or do some DI with singleton scope. Which isn't so much a problem. As for core, we're seeing more dual core android devices come out, my game idea might not perform at all well on a single core device while on a dual core it could work quite well. – NiffyShibby Oct 7 '11 at 14:28
• So designing everything in 1 whole thread doesn't seem like a great idea to me, at least with threads I can separate the logic and in future not having to worry about trying to improve performance as I've designed from the start. – NiffyShibby Oct 7 '11 at 14:28
• But your problem is still inherently serial, so you'll likely block both your threads waiting for them to join anyhow, unless you have isolated the data (giving the render thread something to actually do while the logic thread ticks), and rendering a frame or so behind the simulation. The approach you are describing is not the commonly-accepted best-practice for concurrency design. – user1430 Oct 7 '11 at 15:44