next »

[BorisTheBrave]

You neglect to mention any phases that EDIT the game data (mainly the game-logic code). Clearly, that's going to be harder to paralize.

Also, you don't have massive amounts of multi threading if you have a game loop with discrete steps. You want to be working on AI for as long a period as possible because it is computationally expensive. Blocking it off while you do non-ai things is bad for performance.

But even so, games are very rarely going to break from the per-frame synchronization. Try to imagine a non-game program where this is no time at which everything "synchronizes", and they are all trying to edit the same data structures at the same time.

[Core Xii]

You neglect to mention any phases that EDIT the game data (mainly the game-logic code). Clearly, that's going to be harder to paralize.

You also neglected to mention any. Can't make an argument without providing a valid example.

Also, you don't have massive amounts of multi threading if you have a game loop with discrete steps. You want to be working on AI for as long a period as possible because it is computationally expensive. Blocking it off while you do non-ai things is bad for performance.

It's not bad for performance, just worse than your imagined 'ideal' parallelization. It's still better than no multithreading at all.

Processing the AI of every entity at once is obviously faster than sequentially one at a time. But you can't really do AI before you've done LOS, for instance. And you can't do physics before you've done AI, so I don't really see a way past this discretization.

I don't see a reason to, either. Say you've got 4 cores. There are a lot more entities than 4 that have AI in an average game. So all the threads will be working full-time anyway, regardless of how you section off the logic.

[BorisTheBrave]

I meant all game logic as an example of stuff needing to modify the data. You know, changing the position based on the current velocity, destroying objects that have been hit by bullets. Adding to the score. Physical interactions between bodies. I thought it was obvious enough to not go into detail.

Anyway, I think you might have missed my point. I'm not saying yours is a bad scheme, just that there are other schemes one might do that make multithreading hard, in order to eke a bit more out of performance, or to meet different requirements. Just because it is not hard in your app where you have little mutable shared state doesn't mean it is not hard in general.

I don't see a reason to, either. Say you've got 4 cores. There are a lot more entities than 4 that have AI in an average game. So all the threads will be working full-time anyway, regardless of how you section off the logic.

What? No. If you have discrete phases for each part of your game, and others are single-threaded and take 75% of each frame, then you are only using 4 cores for 25% of game time, and they are being underutilized the rest of the time. That's precisely why you need all your different jobs to be concurrent. Even if most of the phases are trivially paralizable, it's likely that it's the ones that aren't that quickly become the bottle neck.

Not to mention that AI isn't all that paralizable. Sure, you can write AIs that think for themselves only (like real life). But it might be better to share some calculations, such as path finding, or decision trees. Or for them to co-ordinate in actions, so they don't walk into each other, or act as if they are in platoons, etc.
Or what if you are writing chess, or an RTS? Now there aren't multiple individual AIs just a few big ones, and you must paralize inside their thought process.

[rfrank.nj]

I don't see a reason to, either. Say you've got 4 cores. There are a lot more entities than 4 that have AI in an average game. So all the threads will be working full-time anyway, regardless of how you section off the logic.

hahaha you don't make a thread for each unit that requires AI.  how many threads do you think you're going to have here?  you don't want to be creating threads constantly either.

try writing a thread pool to do some complex operation such as AI or pathfinding, then you'll realize how difficult multithreading is.

[Core Xii]

I meant all game logic as an example of stuff needing to modify the data. You know, changing the position based on the current velocity, destroying objects that have been hit by bullets. Adding to the score. Physical interactions between bodies. I thought it was obvious enough to not go into detail.

Changing the position based on the current velocity is a pretty damn trivial calculation. So is destroying objects. All you do is iterate over them once. The physics and collision detection are already parallel problems and handled in a previous phase. Adding to score? Are you serious?

Code:

score += points;

That wasn't so hard.

What? No. If you have discrete phases for each part of your game, and others are single-threaded and take 75% of each frame, then you are only using 4 cores for 25% of game time, and they are being underutilized the rest of the time.

The abovementioned tasks like destroying objects certainly do not take 75% of the game loop. It's collision detection, pathfinding, AI and rendering that take the most time.

Not to mention [...]

Some things are difficult to parallelize, yes. But it doesn't matter. You don't have to parallelize everything, that's not what multithreading is about. The point is to just parallelize enough to make up for the overhead, and you're already profiting.

hahaha you don't make a thread for each unit that requires AI.  how many threads do you think you're going to have here?  you don't want to be creating threads constantly either.

try writing a thread pool to do some complex operation such as AI or pathfinding, then you'll realize how difficult multithreading is.

I never said I was creating a thread per unit, That would be idiotic. I said I'm creating a job per unit, putting said jobs in a queue and letting the worker threads loose on them. Yes I'm using a thread pool, and it's easy.

[Guillaume]

The only application of multithreading in games is if we code a dining simulation where the player plays a philosopher. 

[Average Software]

I never said I was creating a thread per unit, That would be idiotic. I said I'm creating a job per unit, putting said jobs in a queue and letting the worker threads loose on them. Yes I'm using a thread pool, and it's easy.

Just curious, but are you familiar with the use of the volatile keyword in relation to parallel programming?  If not, the compiler's optimizer could tear your program to tiny shreds.

[BorisTheBrave]

Changing the position based on the current velocity is a pretty damn trivial calculation. So is destroying objects. All you do is iterate over them once. The physics and collision detection are already parallel problems and handled in a previous phase. Adding to score? Are you serious?

Code:

score += points;

That wasn't so hard.

These are not easy things to do at the same time. score+=points obviously breaks if two threads try to do it at the same time. And the score might be effectively edited from anywhere in the business logic of the game, so don't go telling me to just do those calculations one at a time, like you've been answering half my points. The solution is simple - a mutex around the score -  but that's already a new concept you've had to learn.

The other examples get even worse. Again, writing a parallel loop over all objects to update their positions is not so hard (though again, you have to learn it somewhere first), but show me one which copes nicely with deleting stuff while you iterate over it. Moving objects is horrible as you must update your broadphase concurrently (see later). 

The abovementioned tasks like destroying objects certainly do not take 75% of the game loop. It's collision detection, pathfinding, AI and rendering that take the most time.

Collision detection requires a broadphase, a structure for efficiently storing the positions and sizes of all objects, and determining which overlap. You can easily write a parallel collision detector that doesn't use one, but there's no point, as the single threaded app using a broadphase would blow it out the water for most circumstances.
Similarly pathfinding. It's easy to "find the shortest path from A to B" in such a way that I can do several at once. It's not so easy to share calculations to actually take advantage of the fact you are doing many similar queries, though the same single threaded code is frequently obvious. Shared mutable data!

I think I already mentioned some problems with AI. On top of that, complex AIs are hard to write - compounding that with multithreading is just no fun (but as AI depends on pathfinding, so I guess you have to if you want any pathfinding gains).

Rendering, I got no complaint with.

Some things are difficult to parallelize, yes. But it doesn't matter. You don't have to parallelize everything, that's not what multithreading is about. The point is to just parallelize enough to make up for the overhead, and you're already profiting.

So you're saying multithreading is easy, as long as you don't use too much of it? Well, I can agree there. There's not much point just making up for the overhead, though, as then it hasn't paid you back for your time doing it. And that includes time debugging. I expect serious performance gains over a single threaded app, or I wouldn't bother. Don't forget Amdahl's law - it's certainly the bits you've failed to multithread that give you the bottle neck, even if it's a relatively trivial bit of code.

And I neglected to mention debugging before. Once something goes wrong, (which is does more frequently with multi-threading than without), it's as hard as hell to track down. Bugs are invariably intermittent, and frequently disappear when you get out a debugger. Many leave you with corrupt data structures. Most compilers are no help at all in pointing out forgotten mutexes, or (C++ excepted) assumptions of constness. I haven't even had time to go into the fun that is deadlocks, or the mysterious optimizations taken on non "volatile" variables.

For the record, I've been talking about (CPU) performance so much, even though I don't really believe it's all that important for most games nowadays, as otherwise i cannot see much point in multithreading at all for games (except an extra thread or two for UI responsiveness).


TL;DR:
Multhreading involves new concepts, and tricky bugs. It is hard to get the most out of.

[Core Xii]

score+=points obviously breaks if two threads try to do it at the same time. And the score might be effectively edited from anywhere in the business logic of the game, so don't go telling me to just do those calculations one at a time, like you've been answering half my points.

Why would you delegate something as trivial as adding scores for a thread pool? I don't understand why you seem to think every damn thing has to be parallel. Being multithreaded doesn't mean everything has to be.

Same with the rest of your post. Physics isn't threaded. Instance deletion isn't threaded. I admit I don't know much about collision detection so you're probably right there.

On top of that, complex AIs are hard to write - compounding that with multithreading is just no fun

I disagree. It's tons of fun. I wouldn't be doing it otherwise

it's certainly the bits you've failed to multithread that give you the bottle neck, even if it's a relatively trivial bit of code.

I don't mind. There's always a bottleneck. As I'm making it wider with multithreading, I'm fine.

[...] debugging [...]

I've never used a debugger and probably never will; I'll cross that bridge when I come to it. But you're certainly not discouraging me from multithreading with that.

I expect serious performance gains over a single threaded app, or I wouldn't bother.

I bother multithreading no matter how small the gain, if only to leave that door open in the future. Threading is nigh impossible to tack on a finished project after you've already written it single-threaded.

[increpare]

Same with the rest of your post. Physics isn't threaded.

Several modern physics libraries do run in their own threads (or on the gpu even).

I bother multithreading no matter how small the gain, if only to leave that door open in the future.

So why not try and introduce object deletion into your threaded code?  Ditto for physics?  Why not make the program as concurrent as possible and try and cut out your critical section code altogether?  Performance gains from this could be quite high indeed potentially.

[Robotacon]

I've tried a couple of different multi-threaded setups and so far I've never had any visible problems but the last couple of posts really makes me worried that I'm not doing it right.

Currently I've got one extra thread that handles all multi-player traffic from the server and one that takes care of all enemy AI but it's either one or the other that will be used depending on if you play solo or online. These threads are the only ones updating the other players and/or enemies.

I don't think I could run the physics engine in it's own thread because my game in a 2D platformer and I want it to be pixel perfect so the game loop needs to call both the update routine (that process input and data constructed in the network thread or the AI thread) and the drawing routines which is basically the rest of the game logic.

[BorisTheBrave]

Robotacon: The moment you have two threads updating the same value, you are in trouble. But if each thread affects different game objects, and neither is editing shared stuff (such as the structure listing all elements in the game), then you should be fine, which sounds like it is the case. But you do need to take the time to verify that fact, and make sure the assumption stays true as you refactor your code.

I picked score as an example as lots of things require changing the score. I wouldn't put it alone in a thread pool, but if my game logic is threaded, locks on the score is a necessary consequence. Making one thing multi-threaded frequently contaminates other areas of your code like that.

Commercial physics engines are indeed multi-threaded to varying extents. I still have nightmares about adapting the Box2D physics engine I work on to multiple threads. Even though the first step, with the biggest gain, is the easiest.

But you seem happy giving up on threading the moment it looks hard, and declaring the amount you've done as the perfect quantity. Thus, I am obsessive, to even consider what it would take to multi-thread the other parts, pointing out how hard it would be.

[John Nesky]

Are there people who actually want Box2D to be threaded?

I would vote against that, if for no other reason than it raises the barrier to entry to using it.

[Robotacon]

BorisTheBrave: I looked through my code and the only parameters that I change in different threads are game object states (running,crawling,kneeling etc). It appears to work out alright but I will definitely keep an eye on those values and add mutex locks where it is needed. I think the reason I've been lucky so far is that object states only affect movement in a secondary way and that the only thing shared between threads is intended behavior and not actual positions or velocity or values of any other kind.

I guess I'm still a happy programmer then

[BorisTheBrave]

John Nesky: Box2D C++ has many extraneous features. Like fixed point arithmetic for the Gameboy DS. Compile flags means that average users aren't bothered by them, nor does it increase the base dependencies of the library. Also, I won't actually do this, as I don't have any direct control over the C++ version any more, I just think about how much could be done.
But yes, there are people who'd like it to be threaded. Box2D can eat up CPU cycles as much as any other physics engine. I was prompted into thought after someone posted saying they'd adapted the java library to solve separate islands of bodies concurrently (thus the API is still single threaded, it's just faster).

[TeaAndBiscuits]

Threads eh? Easy until they go wrong. Not that you'd know cos it tends to be something else that breaks and not always obviously related to threading.

ANYWAY!

I'm a happy programmer
I have water propagating nicely in my 2D platformer. Ever played the Bullfrog classic Flood?http://www.youtube.com/watch?v=2Rch3gfrPOo
I now have my own version... though it is SLOW as hell. Guess I should optimise it a bit... 

-T&B

[LemonScented]

Super-happy programmer

I just got realistic interactions between fluids and dynamic rigid bodies working in my game. It's taken me 10 months to get a realistic, stable, fluid sim running at a decent framerate, and proper solid body interaction is the icing on the cake which will allow me to build all of the cool machines which will provide the gameplay. To say that I'm pleased about (by far) the longest R&D period I've ever encountered coming to an end so I can go full steam ahead with actually building a game around it is an understatement.

I'm just going to throw up some more smilies in here:  :D

[Kekskiller]

[powly]

Inspired by the OpenGL text tutorial in the tutorials section I just rewrote my old text system (well, I didn't follow the tutorial but went by my old lazy foo' -type method) and now it supports every single ASCII character instead of a small, fixed table of my own AND I finally put in a feature my old BASIC system had: at loadtime the system automatically detects glyph widths so I can have differently sized letters and it won't look odd <3 (A bit embarrassed to admit my laziness though, it took me months to just pick this up. there was always something cooler I wanted to work on :<)

As a slight downside, now a friend of mine is probably going to beat me up if I don't put some output into one of our programs : D

Quick edit: I just threw in the fancy text("int: %d, float: %f", int, float) -stuff. Oh, the ease of printing variables from now on..

[Zaknafein]

Catmull-Rom splines that can be edited for camera movement and orientation during cutscenes makes me a happy programmer.