Should I build a multi-threaded system that handles events from a game and sorts them, independently, into different threads based on priority?

Can I build a multi-threaded system that handles events from a game and sorts them, independently, into different threads based on priority, and is it a good idea?

Here’s more info:

I am about to begin work on porting a mid-sized game from Flash/AS3 to Java so that I can continue development with multi-threading capabilities.

Here’s a small bit of background about the game:

The game contains numerous asynchronous activities, such as “world updating” (the game environment is constantly changing based on a set of natural laws and forces), procedural generation of terrain, NPCs, quests, items, etc., and on top of that, the effects of all of the player’s interactions with his environment are programmatically calculated in real time, based on a set of constantly changing “stats” and once again, natural laws and forces.

All of these things going on at once, in an asynchronous manner, seem to lend themselves to multi-threading very well.

My question is:

Can I build some kind of central engine that handles the “stacking” of all of these events as they are triggered, and dynamically sorts them out amongst the available threads, and would it be a good idea?

As an example:

Essentially, every time something happens (IE, a magic missile being generated by a spell, or a bunch of plants need to grow to their next stage), instead of just processing that task right then and adding the new object(s) to a list of managed objects, send a reference to that event to a core “event handler” that throws it into a stack of all other currently queued events, which then sorts them out and orders them according to urgency, splits them between a number of available threads for as-fast-as-possible multithreaded execution.

Ahhh concurrency in Java :-). Right, so I’m going to give some general advice here:

Model your asynch processing on a whiteboard, then get someone else to come in and challenge your assumptions, especially the assumption that you need it in the first place (it sounds like you do, but it never hurts to challenge that). There’s a whole bunch of concurrent data structures you could use to model what you’re trying to achieve, see my mention of Brian’s book to get a good practical guide on these things (in Java).
Concurrency in Java is hard – Objects are mutable by default, implicit locking is hard to get right and you often have to deal with the low-level construct that is Thread itself. If you are going to do the work in Java, then read Brian Goetz’s excellent Java Concurrency in Practice to make sure you avoid the major pitfalls. Java 7 improves things again, but there’s still some fundamental issues that make it hard (for now).
Given 2. it’s well worth looking at a framework or even another language on the JVM that abstracts away from this. Popular choices today include the Akka framework (that both Scala and Java support), GPars (Groovy) or out and out Clojure (If you like Lisp).

HTH a little!

All of these things going on at once, in an asynchronous manner, seem to lend themselves to multi-threading very well.

To me it seems like the exact opposite.

Your “world” is one gigantic bunch of mutable state, which leads to all kinds of nightmares when combined with multithreading.

The big question is: What happens when two events that are processed in parallel affect the same part of the world in contradicting ways and how do you prevent event processor code from seeing inconsistent world states? There are many subtly different variations of this question you’ll run into.

Perhaps it will turn out in the end that such cases are rare and any resulting inconsistencies tolerable, but if not, it’s going to cause massive headaches that can kill the project.

Here’s an interesting (though rather short) article about multi threaded game architectures. And here a more in-depth article that also mentions synchronization as a problem and reason why many games use a single-threaded game loop. It claims that such problems can be largely avoided by doing “non-preemptive multithreading”, but I’m not sure how that would work exactly.

Task and event-based multithreading can work really well–your ideas have similarities to my present multithreading work in native C++. You start with threads that each have their own well-defined roles to play in the application, that will collaborate with one another by posting tasks and events between them to be run.

Each thread does its own thing, and from time to time processing its own events and tasks that have been queueing up. A virtual blocking state puts waiting threads to work while they block. Every thread becomes an event processor, and having nothing to do becomes the only way you ever hard block.

Getting multithreading right is really complex as it is, but it gets much more complex with priority systems. Most events have to occur in the order posted anyway, and priorities can reorder things to cause starvation in the most unexpected places. Remember, you have to be able to debug this stuff. I just keep normal and low priority queues, and use a low-priority flag in the task to choose the queue at post(event) time. Really know that you are getting tangible from your priority system, before electing to use it.

This model scales nicely to any number of processors, because it is decentralized and allows all threads to be posting and processing events concurrently. The round trip to ping-pong a task between threads on different processors takes under 500 machine cycles, making it economical for even short tasks. Task and event execution is fast, with its data now contained within the target thread and ready to roll.

Sure, that would work. And based upon the requirements of your environment, it makes sense.

Essentially, you’re just creating a more sophisticated version of the Thread pool pattern by adding prioritized queues.

Whhyyyy? I don’t see the need for most game engines to be executing disparate async tasks left and right, and many of the commercial ones don’t.

There’s usually chunky enough homogeneous processing to parallelize and get plenty of CPU utilization without having all kinds of unrelated things going on simultaneously, and especially tasks as granular as casting a magic missile spell. Besides I can’t see that happening without potentially lots of thread synchronization of a kind that could defeat all the performance gains you hope to achieve.

I would suggest instead to think about data/state first and look for homogeneous loops you can apply over one type of game state that no other systems access at the time that system is running.

Then you can run that system in parallel, either parallelizing the loops or even running systems in parallel. For example, if only your movement and rendering systems access motion components, then there’s a sequential order where you might run movement and then rendering repeatedly in one thread (since they share the same state) but other threads that don’t deal with motion at all can be running simultaneously while that one thread is focusing on motion and rendering.

Start with the state first and seek to make it no longer shared in multiple places. State and data first, threads/tasks second. Pattern your multithreading design around the data and how it’s accessed instead of a more intuitive idea of what constitutes a unit of work. Think of it more like what chunk of data can be accessed safely by a thread at a given time.

And try to find those homogeneous loops. Instead of a task for a single magic missile spell, maybe you could have a SpellSystem which loops through all spells that need processing at a given time in a homogeneous loop. Or maybe it’s like a consumer where you use a concurrent queue and push spells to be processed by the spell system, at which point it wakes up when there are spells to pop off and process while the rest of your system gets on doing whatever other things it wants to do. That will lend itself much more readily to efficient parallel processing. Seek out those types of loopy control flows over data that no other system touches or accesses during a good chunk of time.

Try to associate a given type of data to a given system, like sounds for the SoundSystem to play (or even lower-level, what regions of memory get accessed at a given time by a given system). And of course other systems might need to directly or indirectly indicate the sounds for the sound system to play, but they can do that very cheaply at which point the SoundSystem does the heavy lifting work. That might seem like a subtle difference from, say, just arbitrarily throwing async sound playing tasks left and right, but it means you did kind of put that thought upfront into saying, “Okay, this type of data gets handled by this type of system in this specific part of the code and in this specific thread”, and that can really help make sure you can run the application across many threads efficiently without much thread contention and, more importantly, safely.

Filed under: softwareengineering - @ 10:14

Thẻ: design, java, multithreading, object-oriented

Thiết kế website giá rẻ

Danh mục

Should I build a multi-threaded system that handles events from a game and sorts them, independently, into different threads based on priority?