Multithreaded concurrent Game Design and Architectures

Hi, I know there's been alot of discussion on how to do multithreaded programming in jME, but I just have some specific questions that I'm hoping all you jME and threading gurus can help me with.



So as far as I see it there's been discussion of the following multithreaded jME gaming topics:



The main thing I see missing from these articles is how are you able to break game logic tasks into seperate threads when there are a lot of things in a game's model (collisions, events, animation) that need to be synchronized based on a common timer (it's partially discussed in the Multithreaded Game Scripting with Stackless Pthon). This means that there needs to be some kind of manager or synchronizer that keeps all your updates synchronized (Controllers, Script updates, game events).

The only thing I can imagine that would work is if you created a scripting framework that lets the script setup a bunch of tasks that will be executed step by step on each update (and will run in sequential order with the other "parallel" script updates, but will allow the developer and game designer the ability to design it in a clearer process oriented approach).

Does anyone have good examples of how one would design a multithreaded game, mainly focusing on the game architecutre. Basically I'm wondering from a perspective of people using jME for commercial games what work needs to be done to make jME work in a multi-threaded manner. What types of architectures are people using to put it together (resource loading, scripting frameworks, physics, etc).

I'm reading a good Java concurrency book right now, Java Concurrency In Practice. I just started it and wanted to get an idea of how concurrency would apply to jME.

Another interesting computer science topic that applies to paralllel programs is Amdahl's Law which basically states that you're only able to speed up your parallel program by 1/F where F is the fraction of your program that needs to run serially (not in parallel, or basically the synchronized sections), so for jME I believe this inherently means the OpenGL rendering context is the main serial section with parts of the resource loading and other game logic updates needing to be synchronized (or serialized, in the parallel sense not in the bytestream sense).

I'll add my two-cents here (not sure I've got much more than that to offer based on all the links you've already provided).



In the current game I'm working on I'm doing multi-threading and it's working very well.  The first thing I'm doing is changing the way the OpenGL thread is managed (via StandardGame as mentioned in the tutorial I wrote).  This creates a completely separate thread for the OpenGL updates/renders that you have to explicitly push things into the stack for (via the GameTaskQueue).  This provides a benefit of keeping the majority of your game from sticking things on the OpenGL thread that are going to cause slowdowns in the rendering that have no reason to be there.  So after I've started my StandardGame my main thread then is available to deal with other tasks such as creating all of my GameStates.  In my situation I first create my LoadingGameState and get it onto the screen, then I pass it off to the initialization of my actual GameState so it can send updates back to the LoadingGameState as it is initializing.  This keeps the graphcal thread updated, removes pauses since it's not in the OpenGL thread, and lets the client know the current loading status.  I create a separate thread for my network aspects of my game (actually multiple threads for this game) and since I'm using JGN I have complete flexibility about how I want to handle threading and an NIO architecture.



Finally, although undone currently, the AI aspects are going to be in their own thread as well so they can "think" without causing issues to the rest of the gameplay.  Forcing all threads to be lower priority than the OpenGL thread I think is also a good idea so long as you are using vsync (but even without as long as you are yielding or sleeping in the OpenGL thread it's not too bad).



The way I look at multithreading is purely simplification of tasks and keeping one task from blocking another.  Group things together in their logical places and where you need interaction between threads provide a mechanism for doing so (ex. GameTaskQueue).  There's really nothing wrong with having several threads in your game (although without good reason it can actually cause your game to run slower), it's just a problem when you have certain things that have to be done in one thread.  JNI calls are typically the only place you'll run into this problem (ex. LWJGL and ODE calls).  Much of jME hides this from you by handling it behind the scenes for you, but there are still several aspects that make direct LWJGL calls instead of sticking them in a stack to be invoked on the next update.  To my knowledge that is the same with jME-Physics as well, but I have almost no experience with version 2 of that. :wink:



Hope that was more useful than just a ramble. :o

Darkfrog that definetly helps me out in understanding the details of how to put together a multithreaded architecture.



So for the most part you create threads to improve the OpenGL's thread responsiveness, you thread off tasks such as resource loading, game state creation and setup, network IO.



You mention how you also use threads to parallelize game logic such as AI, I guess that's where I still am very fuzzy on it all. How do you synchronize all your game logic threads so they provide consistent game updates.



For example most game architectures I've seen you need to have a "game loop" where you do things as an atomic operation (The whole sequence of tasks must be run uninterrupted):


  1. Input Handling (Create events and/or take action based on user inputs)

      1a. Network Event Handling (Network events could be handled by being placed on a queue and then received at this stage).
  2. AI updates (Update AI behavior based on games internal state)
  3. Game logic update (Actors/Entities in the game update using controllers, scripts, and event handlers)
  4. Physics updates (update position of Actors/entities in the game. Collision detection)
  5. Render Frame (Execute any additional OpenGL tasks on queue, and render frame).





    I understand that you could create seperate threads for Network IO and resource loading and have the data received on those threads passed in on a synchronized Queue that could then let them be handled by the “game loop”.



    I guess I’m wondering if you could parallelize parts of the single-threaded game loop.



    It seems like you still need to provide a way to synchronize the parallel tasks in your game so that everything could be on the same “clock” in your game simulation.



    I guess I’m thinking that you would run the “game loop” single threaded, but maybe the individual steps of the game loop could be multi-threaded. For example in the physics update section, each individual entity could update in parallel, but the entire Physics Update task would wait for all the entities to finish updating. This seems like it might be going thread crazy seeing as each entity would have it’s own thread, but you could probably protect against thread overhead by detecting how many cores you are running on and provide thread pools throttled to that (2 cores 2 threads to update in parallel). Maybe I’m thinking about it to simplified, what thread pitfalls am I missing or what other methods can you provide to synchronize a games simulated internal state while trying to parallelize the individual tasks in the game?



    In the article about the multithreaded scripting framework it discusses letting individual entities run their own scripted updates in separate parallel threads but having them run non-preemptive. So what this means to me is that you could run the game logic updates for each of your game entities in parallel but you synchronize the following update to only occur when they all finish and you let the controlling thread sleep so as to provide a proper real time synchronization to your game simulation (I might be explaining this confusingly, but this is the stuff that I’m confused on as well).



    Here’s what he says in the article:

Overcoming multithreaded design pitfalls

As we said before, Stackless P*thon and tasklets can solve the scheduling overhead, memory costs and slow thread creation. Now we have a better foundation to work on, but the remaining problems like synchronization remain. We have to find ways to maintain the benefits of the multithreaded environment while removing more of these problems.

What makes the multithreading synchronization problems and race conditions serious is preemptivity. Preemptive multithreading introduces a non-determinism in the code execution that requires the programmer to cover his back while doing anything. You can be interrupted at anytime at any part of code. Preemptive multithreading might be great for interactivity on the desktop, but gives nothing to game code. It turns out that not only there is no need for it, but also it does not fit in a game environment. To make that clear we will take a closer at what a game engine does:

The game engine simulates a world different from the world the computer is running in. This other world has its own time that ticks away in discrete steps, either constant or variable. Time in the game world is frozen while the game code executes all the logic for a time step. So why would one want to preempt an actor running some calculations? There is no rush to allow another actor to run, since time does not pass! Worse, it would be wrong! Actors with more complex behaviors will progress slower in the game world, since they require more CPU cycles! The actor

Another very interesting article that discusses the design of Game Design being able to scale efficiently to multiple-core processors:



Multithreading Game Engines for Multicore Machines



It basically takes the extreme viewpoint that instead of seperating a game engine into a couple threads (game logic, physics, rendering), that you should create pools of threads that would allow it to scale to massively parallel systems (think 1024 cores haha).





Here’s a good excerpt from the article:


The basic design I

Some of the major issues with making every Actor/Entity it's own microthread (or green threads, basically non-premptive application handled threads) is that it works fine in stackless P*thon but in Java there is no easy way to skip over the C stack (definetly not cross-platforms it'd require patching of the JVM).



So I guess we'd only be left with making course grain tasks parallel ( Full Physics updates, Full game logic updates), because having 100's of threads is way to expensive to be worthwhile in a real time environment like 3D gaming.



I guess maybe the solution is to see what options there are out there for non-premptive threading in Java and see if they would provide the necessary real time performance. Even still I guess that wouldn't really allow multicore scalability because any kind of microthread system is software based and doesn't really apply to the underlying OS threading system.

Well, I think majority of what you're still asking can be addressed by simply explaining the way I would do AI.  The most CPU intensive aspect to AI is going to be the AI's "thinking" that lets it decide what actions to take.  You can split that out into its own thread (granted that thread isn't starved) and it won't cause any problems.  Then if you have a controller that is updated in your game loop that actually implements the decisions that the AI has made (like, walk forward) then your AIs thinking process can be separated from the actual actions he's taking. From the other side if things "happen" and you need to respond the game can throw actions to an event queue that can be processed by another thread.  I do this extensively in JGN and although it can be complicated to manage it in a thread-safe manner it adds an awful lot of flexbility as you can go from one thread for everything to everything having its own thread and it doesn't matter to the system.



Split things out into their logical places and use queues to push things between them.  This keeps you from ever having to wait on another thread as well as giving you the benefit of keeping them in their logical places.

Cool, that makes sense darkfrog. Basically synchronize your threads by having a shared memory queue that will pass events back and forth.



Now how do you keep your games internal simulation state synchronized.



For example you want all your game's entities/objects run their controllers and update methods once every 1/60th of a second (so that you get a constant 60 game updates per second (UPS), no matter the rendering frame rate). Would you just run the game logic loop (including physics updating, input handling, collision detection, event handling, controller updating), all in a single thread to keep the simulation synchronized.



Or is there an easy elegant way to do threaded game logic while still maintaining a constant time simulation (I'm thinking also for some games you need to take snapshots of the games state to restore it later "Save game" so it'd be extremely difficult if the game state was not being modified atomically in one action every 1/60th of a second game time.) Also threads in java don't guarantee that each thread has equal amount of time to do its work, so there'd have to be synchronized barriers that each thread would be waiting on so that all the game entities are in a consistent state, and the next batch of update threads can then continue.



I guess my real concern is that the head-ache that multithreaded game design can be  could lead to a messy impossible to debug system that the programmer has to constantly be worried about thread safety and not developing intuitive game code.

Here’s an interesting slide from Tim Sweeney’s powerpoint (The Next Mainstream Programming Language:A Game Developer

I’m thinking I should just turn this thread into a wiki section about multithreading, listing resources(articles/tutorials), maybe I’ll do that once I get a good foundation in how to implement a complete multithreaded game architecture in jME.



Another very good article (might not be that applicable to Java, but still a good read):

Coding For Multiple Cores on Xbox 360 and Microsoft Windows



Games for Windows need to run on machines with different numbers of CPU cores. Most game machines still have only one core, although the number of two-core machines is growing rapidly. A typical game for Windows might break its workload into one thread for update and rendering, with optional worker threads for adding extra functionality. In addition, some background threads for doing file I/O and networking would probably be used. Figure 1 shows the threads, together with the main data transfer points.

Figure 1.

So what was the question again?  :stuck_out_tongue:



I'm pretty simple-minded at heart so I try to keep things as simplistic as possible.  I attempt to go for the most elegant solution that makes the most sense.  More times than not that tends to be the right way to go.  There's a lot of aspects of threading that can add as well as remove complication, such as synchronization of threads, waiting on other threads, etc. but most of my concepts of how to do things come from my own head of what seems to make sense.



Whether they are right or wrong only time will tell, but they seem to be working so far. :wink:



I think you're over-analyzing and should start putting some code together the way you think it should go and typically things will start to fall into place.  Take that approach and at least you're always learning from your mistakes.  Not to say that reading tutorials and powerpoints, and everything else isn't beneficial, but I can see you've been doing that and it seems to be time to start implementing things the way you think makes sense and then go back and analyze what worked and what didn't.

Haha sorry about the rambling.



You're right again darkfrog, I just need to start coding and see where it goes. I guess sometimes I get overwhelmed with the design of games (I figure beyond the specifics of your gameplay, alot of game design topics have already been tackled and I just want to leverage that knowledge).



My real goal with this was to be able to use the java scripting framework and develop a microthread approach to Actors/Entities in the game.



For starters though I'm going to create simple ScriptController's that will allow JME game objects to be controlled by script objects extending the Controller class.



I'll tackle the bigger threading problems when they come up, right now I need to just submerge myself in development so that I can see what the true issues are and stop focusing on all this theory.

By the way: I was able to load a scene in a separate thread but I failed to do that with a SwitchNode for distance dependant scenes. It looks like it does something that needs to run in the OpenGL thread but I could not find anything.

There is no error whatsoever - it just isn't rendered.