Sign in to follow this  
AxeGuywithanAxe

Entity Update Determinism

Recommended Posts

So I'm currently in the stage of multithreading my gameplay logic, and I seem to be stuck when it comes to maintaining Determinism. With a single threaded game loop, determinism is quite simple to maintain, even if you add a jobsystem method, as long as their is some type of "wait for job before proceeding" action, you will be able to maintain it. I am taking a more data driven approach to multithreading, in which messages are passed if any data needs to be changed, called the "data extract and update" phase , and then later on in the frame, they are executed across multiple threads to perform the updates, "data-apply" . Because there is no sequential order in which entities update, EntityA may send a message to EntityC before EntityB in frame 0, and then EntityB can send a message to EntityC before EntityA in frame 1. 

Share this post


Link to post
Share on other sites

Your update of an entity is not independent of other entities, so making it run parallel is not going to work.

 

If you know the communication structure, you may be able to exploit that, sort of progress one level in all directions every time, but you do need some form of fixed structure where within that structure, things are truly independent.

 

Failing that, thinking bigger may also work. If you have several systems that operate independent, you could run those in parallel.

 

 

Obviously, you can make it work by adding synchronization structures between the entities, but in the end, you may just get lots of cpu threads all waiting on some synchronization, and one thread running. Besides the additional work of programming it all, such a solution is also more expensive, as all the synchronisation also costs time.

Edited by Alberth

Share this post


Link to post
Share on other sites

Well I was thinking of having messages based on certain tasks, for example. Lets say you want to set an entities' position. 

In a single threaded environment, the call would be something along the lines of : 


TargetEntity->SetPosition(CVector3(0,50,0));

with the message passing system it would be like this 


struct UpdateTransformMessage
{
   CVector3 Position;
   CEntity* TargetEntity;
.....
   void Apply()
   {
     TargetEntity->SetPosition(Position);
  }

};

  //update all entities
  TargetEntity->DispatchMessage(new UpdateTransformMessage(CVector3(0,50,0));


  //after all game entities are updated , actually apply the messages 
  UpdateTransformMessage::ApplyAllMessages();


So the entity won't have it's state changed until after all objects have been updated, making the internal state of all entities during a frame thread safe... the issue comes with determining the right way to apply all of the messages

in a deterministic manner.

Share this post


Link to post
Share on other sites

I was just trying to find a better way to scale up with cores

 

The goal of trying to parallelize gameplay processing can work, but it requires an enormous amount of effort to implement and you gain almost nothing from it.

 

First and foremost, you have the problem of the minimum spec machine.  Often that is a 2-core machine.  It doesn't matter if you're really running on a 4-core, 8-core, or 24-core server-class processor, you need to respect the minimum spec machine.  While you can turn up non-essential things on those fancy processors, the core gameplay generally needs to be the same on all the machines.

 

Players completely understand if you adjust graphics, adjust particles, adjust non-interactive objects, but on the rare occasion companies alter gameplay based on hardware, players go nuts.  A smaller game called Arizona Sunshine did it two months ago, and while the game managed to get some publicity out of it, the game's ratings dropped to one star as a result.

 

 

Even if you do figure out how to provide consistent gameplay experience on varying hardware, you will have the nightmare of making all your updates work together.  It probably won't be deterministic, and it would be best to design it so it isn't deterministic, but instead to be reliable. This may mean communications between objects processed in parallel are queued as future processing, and it may mean you need to radically change from queries and commands into requests. It would mean you cannot update objects are they are now, but you will need to think either in stateless terms or as though 'now' is a locked state and the future is a request which may not be honored.

 

There are plenty of tasks that are interesting from a computer science perspective, they are mostly a waste of time if the goal is to complete a product.  It is easier and more productive to adjust those items player are expecting --- graphics settings, non-interactive particles, effects, audio, and other things that don't actually affect gameplay.  

 

About the only exception to this is networked gameplay.  If you can use the extra processing toward improving networked gameplay, players tend to be more understanding even if they don't like it.  But even then, the gameplay improvement needs to be universal.  It cannot be like the old Quake bug, where a specific processor speed lets you exploit the game for a tactical advantage.  EVERYONE gets the improvement, or NOBODY gets the improvement. 

Share this post


Link to post
Share on other sites

Thank you both, I think I was just having an issue with pre-optimization. What I'm going to do now is have 2 threads, one for the game thread, and one for a render thread, and then the other 2-4 threads will be used as worker threads. Then I will have a thread queue for each of these threads, so when the game thread is waiting for the current update job to finish, it will begin processing other jobs, and etc...

Share this post


Link to post
Share on other sites

As already told It's not a good idea for most of the game logic to enforce it to a thread pool.

I worked on racing, strategie and brawler games and the logic code was running on one core and created new jobs on specific places.

E.g. get all entities which are necessary for the next step in the logic, update input, update state machine and so on.

You can parallize code by using phases like in multicore physic.

-apply forces

-intersection handling, calculate new forces and position correction

-apply correction

The 2nd step take care of determination on multi threading by calculating the same values for each entity which is part of an intersection and do the part of the owned entity.

This is less efficient but scales better with multiple cores.

You can reduce the amount of inefficiency by do the right amount of phases and create worker tasks which take advantage of the knowledge of the current game logic.

 

I highly recommend following slides because it fits perfectly in the topic and shows how complex it can get if you want to enforce multi threading.

http://de.slideshare.net/naughty_dog/multiprocessor-game-loops-lessons-from-uncharted-2-among-thieves

Edited by TAK2004

Share this post


Link to post
Share on other sites

First and foremost, you have the problem of the minimum spec machine.  Often that is a 2-core machine

Which means that single-threaded code is running twice as slow as possible on your min-spec (and 4+ times as slow as possible on the recommended/high spec). 

The goal of trying to parallelize gameplay processing can work, but it requires an enormous amount of effort to implement and you gain almost nothing from it.

That's arguable. Porting eixsting code to be parallel does require enormous effort. Writing code that way from the start does not. What you gain is the ability to have twice as much gameplay stuff on the min spec machine...

Even if you do figure out how to provide consistent gameplay experience on varying hardware, you will have the nightmare of making all your updates work together.  It probably won't be deterministic, and it would be best to design it so it isn't deterministic, but instead to be reliable.

If adding parallelism results in your gameplay no longer being deterministic, you've done it wrong (or you've deliberately broken something in the name of some extreme optimization). There's a shitload of data-parallel operations in every game that can be exploited without affecting the behavior of the program. By default, exploiting concurrency should not alter program behavior.

 


So I'm currently in the stage of multithreading my gameplay logic, and I seem to be stuck when it comes to maintaining Determinism. With a single threaded game loop, determinism is quite simple to maintain, even if you add a jobsystem method, as long as their is some type of "wait for job before proceeding" action, you will be able to maintain it. I am taking a more data driven approach to multithreading, in which messages are passed if any data needs to be changed, called the "data extract and update" phase , and then later on in the frame, they are executed across multiple threads to perform the updates, "data-apply" . Because there is no sequential order in which entities update, EntityA may send a message to EntityC before EntityB in frame 0, and then EntityB can send a message to EntityC before EntityA in frame 1.
Look up the "actor model". This idea of serial entities communicating concurrently was coined in the 70's :) It's not a very good model, so I'd advocate you do something else, but...
 
In that model, they do some hand waving and invent an arbitrator that controls messaging order.
 
If your problem is that message ordering can introduce non-determinism then you can create an arbitration system as so:
Break each frame into cycles of message processing.
Within a cycle, collect all the messages that are in the message queue, group them by destination entity address, then stable-sort them by source entity address. Have a thread-pool execute the groups of messages (the group belonging to a single entity will run on a single thread). This preserves any ordering messages sent serially (if a single thread sends messages A and B to the same destination entity, A will always execute before B because you used a stable sort), and produces a deterministic order for any multi-threaded message sending (if entity #1 and entity #2 both send messages to entity #3, then entity #1's messages will be processed by it first, because you sorted them by source entity address).
During a cycle, entities will generate new messages. Do not send these directly to the destination entities -- instead push them into a queue, which will be grouped/sorted by the arbitrator at the end of the cycle.
A tangential benefit of this message queuing is that now, sending a message can actually be a wait-free operation -- give each thread in the pool it's own message queue, and then new messages can be written to it without the need for any synchronization primitives! At the end of a cycle, the arbitrator can merge the queues of all threads together.
 
Now you can have fairly typical looking object-style entities, which can arbitrarily communicate with each other via message passing, will scale their processing over any number of threads (up to the number of active entities), and everything maintains determinism.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this