Using an Entity System Architecture with Task Based Parallelism

Question

Background

I have been working on creating a multithreaded game engine in my spare time and I currently trying to decide the best way to work an entity sytem into what I have already created. So far, I have used this article from Intel for a starting point for my engine. Thus far I have implemented the normal game loop using tasks, and I am now moving on to getting some of the systems and/or entity-systems incorporated. I have used something similar to Artemis in the past, but the parallelism is throwing me off.

The article from Intel seems to advocate having multiple copies of entity data, and a having changes made to each entity internally being distributed at the end of a complete update. This means that rendering will always be one frame behind, but that seems like an acceptable compromise given the performance benefits that should be gained. When it comes to an entity system like Artemis, though, having each entity being duplicated for each system means that each component will also need to be duplicated. This is doable but to me it seems like it would use up a lot of memory. The portions of the Intel document that discus this are 2.2 and 3.2.2 mainly. I have done some searching to see if I could find any good references for integrating the architectures I am going for, but I have not yet been able to turn up anything useful.

Note: I am using C++11 for this project, but I imagine most of what I am asking should be pretty language agnostic.

Possible Solution

Have a global EntityManager that is used for creating and managing Entities and EntityAttributes. Allow read access to them only during the update phase, and store all changes in a queue per thread. Once all tasks are completed the queues are combined and the changes in each are applied. This would possibly have problems with multiple writes to the same fields but I am sure there could be a priority system or timestamp to sort that out. This seems like a good approach to me because systems can be notified of changes to entities pretty naturally during the change distribution stage.

Question

I am looking for some feedback on my solution to see if it even makes sense. I won't lie and claim to be an expert on multithreading, and I am doing this largely for practice. I can forsee some complicated messes rising from my solution where multiple systems are reading/writing multiple values. The change queue I mentioned could also be hard to format in a way that any possible change could easily be communicated when I am not working with POD.

Any feedback/advice would be much appreciated! Thanks!

Links

• http://software.intel.com/en-us/articles/designing-the-framework-of-a-parallel-game-engine
• http://gamadu.com/artemis/
• http://www.gamedev.net/topic/560083-rendering-in-a-task-based-multithreaded-environment/ (not mentioned in post this post but similar solution mentioned)

Answer 1

Fork-Join

You don't need separate copies of components. Just use a fork-join model, which is (extremely poorly) mentioned in that article from Intel.

In an ECS, you effectively have a loop something like:

while in game:
  for each system:
    for each component in system:
      update component

Change this to something like:

while in game:
  for each system:
    divide components into groups
    for each group:
      start thread (
        for each component in group:
          update component
      )
    wait for all threads to finish

The tricky part is the "divide components into groups" bit. For graphics there's almost no need for shared data so it's simple (divide renderable objects evenly by number of worker threads available). For physics and AI, you want to find logical "islands" of objects that don't interact and put those together. The less interaction between components, the better.

For interaction that must exist, delayed messages work best. If object A needs to tell object B to take damage, A can just enqueue a message into a per-thread pool. When the threads are joined, the pools are all concatenated into a single pool. While not directly related to threading, see event series of articles from the BitSquid devs (in fact, read the whole blog; I don't agree with everything on there, but it is a fantastic resource).

Note that "fork-join" does not mean using fork() (which creates processes, not threads), nor does it imply that you actually must join the threads. It just means that you take a single task, parcel it out into smaller pieces to be handled by your pool of worker threads, and then wait for all the parcels to be processed.

Proxies

This approach can be used on its own or in combination with the fork-join method to make the need for strict separation less important.

You can be more friendly to interacting threads by using a simple two-layer approach. Have "authoritative" entities and "proxy" entities. Authoritative entities can only be modified from a single thread that is the clear owner of the authoritative entity. Proxies entities cannot be modified, only read. At a sync up point in the game loop, propagate all changes from authoritative entities to the corresponding proxies.

Replace "entities" with "components" as appropriate. The gist is that you need at most two copies of any object, and there are clear "sync" points in your game loop when you can copy from one to the other in most sane threaded game engine designs.

You can expand proxies to still allow (a subset of) methods/messages to be used by simply having all such things forward into a queue that is delivered to the authoritative object next frame.

Note that the proxy approach is a fantastic design to have at a higher level as it makes network support super easy.