Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
add comment

4 Answers

up vote 6 down vote accepted

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

  1. 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).

  2. 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).

  3. 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!

share|improve this answer
1  
+1 For mentioning Akka, which is great :-)! –  Oliver Weiler Aug 16 '12 at 15:31
    
Yes, thank you for introducing me to Akka. –  JonathonG Aug 16 '12 at 17:13
    
Mutable objects do pose a challenge but only if the design allows it to be. Good design will fight off the shared referency stuffs. Just requires everyone to be on the same page in programming. –  Rig Oct 15 '12 at 23:55
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
You're right, multi-threading my game world is one giant mess waiting to happen. What I meant when I wrote that the game seems to lend itself well to multi-threading is that there is almost nothing in the game that can't be divided into subtasks. This means it stands to gain massive performance boosts from multi-threading. You are right though, if done improperly I could see this quickly turning into a nightmare. –  JonathonG Aug 16 '12 at 15:33
    
I had already read the first article you sent me, with the different architecture maps. I was looking at the "Asynchronous function parallel model" as something that was very doable for my game. A lot of the game features such as world updating and procedural generation don't need to be perfectly synchronized. I can save each update and use the most recent completed update to render the world until the next one is available, so nothing gets changed until its new state is finalized. Perhaps this approach might reduce/negate the possibility of inconsistencies. What are your thoughts? –  JonathonG Aug 16 '12 at 15:38
    
The "non-premptive multithreading" doesn't take advantage of multiple cores. It only transitions between threads when requested. I find it most useful in the case of IO, because it allows other threads to execute while waiting, but doesn't randomly transition at other times. It simplifies the IO code without introducing the full complexity of multithreading. –  Winston Ewert Aug 16 '12 at 16:35
    
@JonathonG, the really big question I'd ask is how the CPU usage differs between the various tasks. I've seen people go to a lot of effort to introduce multithreading, but the only expensive part of the program was graphics, and they gained pretty much nothing for their effort. It does sound like you've got some things which may be expensive enough to make sense to offload onto other threads. However, some of it sounds like is too computationaly trivial to be worthwhile. –  Winston Ewert Aug 16 '12 at 16:38
    
@WinstonEwert I should have specified, my game is 2 dimensional and uses very light BLITing to render scenes and animate sprites. So far I've never managed to get rendering to use up any noticeable amount of processing power. The procedural generation is very computationally intensive, as it generates something like 1200 blocks of terrain based on all the terrain around them and applies all kinds of laws and properties in order to re-factor that terrain into something far more natural. This task by itself can bring computers to a screeching halt in Flash (single threaded). –  JonathonG Aug 16 '12 at 17:03
show 4 more comments

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.

share|improve this answer
2  
docs.oracle.com/javase/6/docs/api/java/util/concurrent/… can be created with a PriorityBlockingQueue. I think this can be used here. –  Slomo Aug 16 '12 at 14:45
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.