Jump to content
  • Advertisement
Sign in to follow this  
DavidColson

Object interactions in a multithreaded game

This topic is 2154 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

So I have been doing research into multithreading for no reason other than curiosity and I have noticed something which I'd like to bring up. 

 

The best way to multithread any software, apparently, is data-decomposition. As in instead of putting subsystems on different threads, you break up the processing of one subsystem into multiple jobs to do concurrently, scaling to n number of threads. 

 

This is all fine and dandy, but say if you were to do this to the physics system, my logic would be to break it up so for n threads divide the number of objects by n and give each thread a group of objects to update. Then you would have a situation were conflicts would occur. Say object A collides with object B, but A and B are being updated at the same time on separate threads. Problem.

 

Another example is for updating game logic on gameObjects. What if object A is dependant on the health of object B. But again, they are being updated on different threads.

 

Now I know the simple answer is, minimize interaction and communication between objects, however this is not always going to be good enough, especially in physics, since object interaction is critical to the function of the system.

 

I have not worked on a game were objects never have to talk to each other, so how do you get around this problem when designing a multithreaded game?

Share this post


Link to post
Share on other sites
Advertisement

There are multiple things you can do.

  1. Make sure conflicts doesn't cause too much problem. In your case, the simulation could output a different result/state when singlethreaded vs multithreaded, but if the state is believable, does it really matter? If the game is networked, maybe the network will fix it anyway.
  2. Run logic without object interactions in a multithreaded way, then use a single thread to do all steps that require interactions between objects.
  3. Design your algorithms/structures so that there can't be conflicts. For example, for each object, find a new position/speed/acceleration/whatever, but don't update current position/speed/acceleration/whatever. Once all objects know their new position/speed/acceleration/whatever, run another multithreaded loop to actually update the current values.

Share this post


Link to post
Share on other sites

This is all fine and dandy, but say if you were to do this to the physics system, my logic would be to break it up so for n threads divide the number of objects by n and give each thread a group of objects to update. Then you would have a situation were conflicts would occur. Say object A collides with object B, but A and B are being updated at the same time on separate threads. Problem.

 

Another example is for updating game logic on gameObjects. What if object A is dependant on the health of object B. But again, they are being updated on different threads.

 

One option is to partition the objects more intelligently.  Physical objects in one region of the map are unable to interact in a single frame with objects in a completely different region.  Likewise, for AI, you can restrict which types of queries objects can make or which objects they can interact with.

 

However you partition your objects, a good option is to avoid making changes to any object other than "this" in a multithreaded environment.  Instead prefer messages which can be queued up and then delivered in later stages of the update pipeline.  You have to be careful with reads in this case too as you might be trying to read from an object that's in the middle of updating itself on another thread.  Ideally in this system each object has all the information it needs before you pass it off to any thread; any queries it makes are messages it sends out and then responses are handled in a subsequent update loop (usual asynchronous event programming stuff).

 

Another option is to make proxy objects which are read-only copies of their real objects.  Because they're strictly read-only they can be shared by multiple threads.  This removes the need for asyncronous queries in the previous option but can have some memory overhead; whether it's worth it depends very much on your specific game and team.

 

The fourth option is to make _all_ your objects read-only during batch jobs and to apply updates afterward, either with the messaging system or with an explicit mechanism.  One way to do this is to "double buffer" your objects: each object has its data duplicated and each frame one copy is read-only and the other is write-only, alternating between the two each frame.

Share this post


Link to post
Share on other sites

You’ve just explained why data-decomposition is not the way games are multi-threaded.

 

There are many fields in general application design and implementation you can study that cross over into game development very well.

But many that do not.  One I see most frequently is the act of treating input as an event, because that’s what it is in every kind of application…except games.

 

The most common approach to threading in games is based on sub-systems.

The game logic could be on a thread while sound, rendering, and physics could each be on other threads.

However you want to divide your threads, it is not based on data-decomposition.

 

Generally the only time that type of threading enters the world of games is when you need to load something in the background (or on any loading screen, really).

 

 

Anything you do to synchronize objects inside a physics simulation, for example, will:

  1. Lose time on partitioning.
  2. Lose time on synchronization.
  3. Fall apart some day when an object is moving too fast (or on other edge cases).
  4. Lose time signalling threads.

 

All that time lost would be better spent on a single-threaded algorithmic improvement to the physics system.

 

 

L. Spiro

Share this post


Link to post
Share on other sites

Maybe it's just me but I see something greatly overlooked in those two statements. Goal, level of abstraction. Threading is for performance. A computation like this is not performance oriented; it is also a low-level concept, while you talk about a ultra-hi-level gameplay concept. Do not mix those. The example above is a proof of concept but I recommend everyone to not try to pull a mountain out of it. Gameplay concepts like this could be scripted and there's often no control at all on scripts. It's virtual function calls... overcharged.

 

FYI, a relationship like this in my system would take no time at all (running the scripts generally take less than 2%) !

Now you'll be saying: "I'm only using those as examples". No. You're building a fictional problem.

 

Slightly different for physics. You don't do physics yourself. And as a side note, you don't give up simulation determinism.

Let me stress this: you don't do physics yourself.

Share this post


Link to post
Share on other sites

This is very interesting, I appreciate all this information. 

 

One thing I am taking out of this is that high level gameplay logic is not something that I really need to do multithreading on. I suppose were it would be most beneficial is when a certain function is called that carries out  a low level taxing process. This particular process can then be broken down into "tasks" which can be put in a queue for the thread pools to process. In my head I am imagining this to give me much more precise control over what processes are multithreaded and which not.

 

I also like this idea of removing interaction between objects until computation is complete and then sending queued messages to objects. I have learned much!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!