13 Comments

Entity Component System architecture (C#)

In this post I’ll go over how I’ve laid out the parts of my ECS framework, with some emphasis on issues related to the .Net framework. Check out some previous posts here and here.

By all means this is not meant to be authoritative. In fact, I’ll be outlining several problems I see with the way I’ve done things.

Overview

I’ll start with a few top level diagrams. First, the EntityManager:

EntityManager block diagram

EntityManager block diagram

The EntityManager contains the list of all the existing entities (which are just light wrappers over a few ids), and a ComponentManager for each type of component. So the components are stored separately from the entities, each in their own list.

A particular entity is associated with various components, like so:

The entity is composed of the 3 highlighted components.

The entity is composed of the 3 highlighted components.

The other main piece of the pie is the SystemManager:

SystemManager block diagram.

SystemManager block diagram.

The systems (e.g. RenderSystem, AnimationSystem, SoundSystem) contain the bulk of the logic. A system provides its logic by inheriting from a base class and overriding a few key methods. A system declaratively states which components it is interested in, and the base class is responsible for keeping the system’s entity list updated with all entities that have exactly the components in which the system is interested. As a result, the system can just loop through this list while doing its processing.

Memory Layout

One of the motivations for storing the components separate from the entities is that like components are usually processed together. If we store all the components of one type in a single list, then we can (theoretically) access them sequentially in memory as we process them. This results in good locality of reference. So it is mainly a performance consideration.

If, instead, the components were located in a collection off of each Entity object, then many of our operations would involve touching scattered memory. While this is certainly a valid way to go (I’ve seen several implementations like this in languages with managed memory), you won’t achieve any of the theoretical performance benefits of ECS frameworks.

In C++ you have strong control over memory allocation patterns. In C#, not so much.

Ideally, we want all the components of one type to exist in contiguous memory. The obvious way to do that in C# is to make the components value types (structs). Unfortunately this is too cumbersome – among other things, it prevents us from having a common base class or interface for components, and it is restrictive to deal with references to structs (for instance, you can’t return a struct by reference from a function).

The good news is that we can still put things in contiguous memory if the components are reference types (classes). I mentioned in a previous post that allocations made one after the other are generally allocated sequentially in memory too. I actually couldn’t find this mentioned/documented anywhere, but my testing shows it to be true (at least on my desktop computer).

Of course, the CLR is free to move things around in memory. But in my testing, my arrays of components always had each component object located adjacent to each other in memory. (Note: the CLR Profiler shows this is not true. But I believe this is because when running with the profiler enabled, the allocation logic is different).

This is all only useful if we access these components in order. Unfortunately with my current implementation, I do not.

The details

As the game runs, entities and components are frequently being added and removed. How do I manage these lists so that enumerating through them is efficient? How do I ensure adding and removing is efficient?

My current implementation has as one of its goals the efficient adding and removing of entities and components. This means that we avoid any O(n) operations (such as shifting all the components down in the array when one is removed). Add/remove operations are done in linear time.

To accomplish this, I need to keep 3 lists: The pool of entities themselves, a “compact” array of indices for lookup into the entity pool, and a reverse lookup array which I’ll call the roster.

If I allocate one entity, it would look like this:

Entity Pool [LiveId] 

LiveId [RosterIndex] 

Roster [LiveId]

EntityA 

EntityB 

1 <— NEXT FREE

-1

EntityC 

2

-1

EntityD 

3

-1

Now let’s add two more:

Entity Pool [LiveId] 

LiveId [RosterIndex] 

Roster [LiveId] 

EntityA 

EntityB 

EntityC 

EntityD 

3 <— NEXT FREE

-1

At this point, it’s worth explaining how I can enumerate through all entities. I use the LiveId list, which is indexed by RosterIndex. I simply loop from 0 to “NEXT FREE” and look up the LiveId. I then use the LiveId to index into the Entity Pool.

Now let’s remove a Entity A. The result will be this:

Entity Pool [LiveId] 

LiveId [RosterIndex] 

Roster [LiveId]

EntityA 

2

-1

EntityB 

1

EntityC 

0 <— NEXT FREE

EntityD 

3

-1

There is now a gap in the Entity Pool, but it doesn’t matter since I just enumerate through the list of LiveIds (the middle column), which never has a gap. We took the now empty spot for Entity A and swapped it with the last one in the list (and decremented NEXT FREE). The Roster[LiveId] list is just needed so we can perform the swap. It let’s us know the index in LiveId[RosterIndex] where the removed guy lives.

Now when I enumerate through the entities, I’ll encounter LiveId 2 (Entity C) and then LiveId 1 (Entity B). So you’ll note that the enumeration order is different. In fact, the more add and remove operations I perform, the more chaotic the enumeration order becomes.

I use this system (which allows for linear time add/removals, and “compact” enumerations) in 3 different places:

  1. For the list of entities in the EntityManager, as just described
  2. For the list of components in each ComponentManager
  3. For the list of entity LiveIds in each System

Just for kicks, I ran my game for a while and played a few levels. I took a look at how the items were laid out in memory for cases 1 and 2 above.

 

The global entity list on top, and the Placement component list on the bottom.

The global entity list on top, and the Placement component list on the bottom.

 

It’s maybe a bit hard to explain this image, but a perfectly sequential-in-memory order would be a smooth gradient from left to right. Instead, you can see chunks of sequential memory, and then random jumps to other places. Over time, this would become more and more randomized.

In summary, I have optimized for a fast adds and removes at the expense of potentially pool locality of reference.

A system that operates over a single type of component will be affected by this.

What about a system that operates over of two types of components (such as the RenderSystem, which needs to know about both Aspect and Placement)? Well, there is already an inherent problem there. Even if we were to somehow fix our spatial locality issue, we are simultaneously iterating over two separate lists. If one were guaranteed to be in nice enumeration order, the other would necessarily not.

So fundamentally, there are three things working against us for achieving good locality of reference:

  1. It’s possible (though not likely) that our original list won’t be contiguous in memory, and the .net garbage collector can move things around if it wants. Of course, this is not a problem in C++.
  2. My algorithm for storing Components/Entities ends up “randomizing” their order as things are added/deleted. This could get worse as time passes.
  3. The fact that most systems enumerate over multiple components means that access of at least one of those component lists will be “random”.

To sum up, I can’t honestly claim that locality of reference is a big benefit to my ECS framework with the way I have it currently implemented. Of course ECS has many other benefits.

It gets worse

I haven’t yet gone into detail about how a system enumerates through the entities it cares about. I’ll do that now.

As mentioned before, each system is automatically kept up-to-date with a compact list of entities to enumerate. It is actually just a list of LiveIds. LiveIds allow us to perform a simple array lookup to get an entity from the EntityManager (thus a LiveId is a number that is guaranteed to be unique for the lifetime of an Entity). Systems aren’t typically interested in the entities themselves though: just in their components. So a system might do something like:

 

For each entity LiveId in my compact list
   GetComponentA
   GetComponentB
   Do stuff with those components.

I need to explain another thing now. We have LiveIds for components, just like we have LiveIds for entities. The component LiveIds are quick lookups into the array in the ComponentManager for a component type. We could get away with re-using the Entity LiveIds, but then each ComponentManager would have to be large enough to hold n components, where n is the max number of entities we have. This could work with common components like Aspect and Placement (which are on most entities), but it would be a waste of space for other ones. So instead, we tailor the size of each ComponentManager to the number of components it is expected to have.

So where are these component LiveIds stored? The EntityManager has a giant array of them indexed by entity LiveId and ComponentId. ComponentId is just a fixed number that corresponds to a particular component type (e.g. Aspect = 0, Placement = 1, SoundLoop = 2, up to the number of component types we have).

So if we have 1000 entities and 20 different kinds of components, this array would be 20,000 elements.

So going back to our enumeration in the system:

For each entity LiveId in my compact list
   GetComponentA

GetComponentA involves the following:

  • index (in a non-sequential fashion) into the giant array, using [LiveId, ComponentId] to find the component LiveId
  • index (in a non-sequential fashion) into the ComponentManager’s array using that component LiveId

So that’s essentially two random accesses into arrays in order to get the component we need. Hardly ideal. Of course, a system that only cared about a single component type could directly enumerate through that type’s ComponentManager, thus incurring only a single lookup.

Thoughts

I haven’t used my ECS framework for a large enough game world yet to really know the performance implications. So it’s hard to make any conclusions about that, other than I know the implementation could definitely use some improvement.

I’d be interested to hear about other people’s implementation details, regardless of whether or not they are in native or managed code. I don’t think managed code is hurting me too much here.

 

Advertisements

13 comments on “Entity Component System architecture (C#)

  1. Again, a well written interesting article 🙂 I like the locality of reference

  2. Very intriguing.

    I like the way you group properties by components like that… then entities just encapsulate what they need.

    If someone gets carried away with the granularity of their components though they can actually make things worse by pummelling cache lines… since each type of component exists in a different memory space. (http://stackoverflow.com/questions/3928995/how-do-cache-lines-work). It’s hard to tell without measuring though.

    I take a more straight forward approach.
    I start off by prioritizing the different update processes (animation, position updates, collision data) in a frame by performance requirements.
    Then from top to bottom, for each update process (or sub process), I ask… “how can I update this data while accessing (or loading into cache) the least amount of data possible?”
    Let’s say I am updating position data, and all I need is (PositionXYZ, VelocityXYZ, ImpulseXYZ) then I would consider creating an object type that contains just that… create a pool / array of just that type and use that to process position data every frame. The ‘Position Data Manager’ (or whatever you want to call it) owns that array.

    For looping over the objects I just stick with a simple pre-allocated array coupled with a boolean array that stores “IsUsed” values.
    For quick additions and removals I use a stack object that maintains a list of free objects (their indices actually). To add an object I pop a value off the ‘free stack’ to remove an object I push onto to it.

    It would be interesting to experiment with a generic system like what you have there :).

  3. Can you talk about networking in entity component system? How do you synchronize entities (ID’s) on server and client or client/client so that they agree on what entity they are talking about, given the ID? Maybe any tips with implementing networking for entity component system?

    I suddenly realized that the component system i was using (Artemis CSharp) does not have networking taken into consideration when developing it, so i guess ill have to modify it… Do you have any opinion/experience on Artemis entity system? Writing my own system from scratch is very painful, considering I’m a single developer and i need something done fast…

    • Hi Oscar,
      I haven’t done any networked games with an entity component system, so I’m not sure I can offer much advice.
      My gut feeling, however, is that the network interactions wouldn’t really be dependent on whether an underlying entity component system was used or not (just like physics or rendering code).

      • Well there is much you can do with entity system and networking. Its very easy to split client and server logic that way. Using entity templates, i can create complex objects on players machine just by sending miniscule amount of data. I can also update any component of any entity just by sending over entity’s uniqueID, persistent componentID and De-serializing updated component data from provided network stream in place.

        I’m having problems understanding the whole roster thing. Could you provide some snippet on how its actually implemented?

        How did you get that locality gradient image? Is that some sort of home-made CLR profiler extension? 😀

      • Here’s a link to my ComponentManager class, which does the roster thing:

        https://skydrive.live.com/redir?resid=32374812F02E440E!915&authkey=!AAjB7MZrKDWi_X4

        Looking at it might be confusing because the names are different/opposite. “componentPool” is the pool of actual objects. “roster[]” is the thing you index from 0 to “partitionIndex” to get the index into the componentPool. And “inverseRoster[]” is the thing I call Roster in this article (I know it’s backwards), used for swapping stuff on remove.

        I admit, it’s very hard to grok. The idea came from this paper (A Dynamic Component Architecture for High Performance Gameplay). It probably has a much better explanation than mine:
        https://d3cw3dd2w32x2b.cloudfront.net/wp-content/uploads/2011/06/6-1-2010.pdf

        As for networking, I agree that a entity system would make a lot of things easier. I made a game with peer-to-peer networking before I knew about entity systems, and I’m sure it would have been easier/more robust if I were using an entity system, since I’d be able to hopefully re-use a bunch of the code.

        The gradient thing was just something I drew in my actual game, based on the ordering of the entity indices (after having independently confirmed that the entities were located adjacent to one another in memory in the pool).

  4. Do you have a constant amount of entities within your game world? If not how do you go about resizing your storage of components?

  5. It has been at least a year since I worked with my last ECS project, but I decided to worry about locality if and when it became an issue. I used generic dictionaries to store components by entity id, as performance for add, remove, and look-up is pretty close to O(1). The singular component manager also had id lists for each component type, stored in a HashSet for O(1) adds and removes, and also for the wonderful set operations.

    I had component retrieval methods corresponding to each of the major set operations: union, intersect, except, etc, as well as a few others. As an example, I might use:

    foreach(Component[] result in Components.GetIntersectByType(typeof(OneComponent), typeof(OtherComponent))
    {
    var one = (OneComponent)result[0];
    var other = (OtherComponent)result[1];
    var more = Components.GetOrAdd(one.Id)

    // one, other, and more processing goes here
    }

    Adding new component types and systems was a breeze.
    Components.Register();
    Systems.Register();

    I am sure it was not the most efficient way of doing things, but it was incredibly easy to navigate, quite flexible, and very predictable. It was a pleasure to use, but again, I would not doubt it if performance were to become an issue for a larger project.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Just another WordPress site

Just another WordPress.com site

The Space Quest Historian

Adventure game blogs, Let's Plays, live streams, and more

Harebrained Schemes

Developer's blog for IceFall Games

kosmonaut's blog

3d GFX and more

Halogenica

Turn up the rez!

bitsquid: development blog

Developer's blog for IceFall Games

Game Development by Sean

Developer's blog for IceFall Games

Lost Garden

Developer's blog for IceFall Games

Memories

Developer's blog for IceFall Games

Casey's Blog

Developer's blog for IceFall Games

Blog

Developer's blog for IceFall Games

Rendering Evolution

Developer's blog for IceFall Games

Simon schreibt.

Developer's blog for IceFall Games

Dev & Techno-phage

Do Computers Dream of Electric Developper?

- Woolfe -

Developer's blog for IceFall Games

Fabio Ferrara

Game Developer

Clone of Duty: Stonehenge

First Person Shooter coming soon to the XBOX 360

Low Tide Productions

Games and other artsy stuff...

BadCorporateLogo

Just another WordPress.com site

Sipty's Writing

Take a look inside the mind of a game developer.

%d bloggers like this: