Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

After reading a few documentation about entity-component system, i decided to implement mine. So far, I have a World class which contains the entities and the system manager(systems), Entity class which contains the components as a std::map, and a few systems. I am holding entities as a std::vector in World. No problem so far. What confuses me is the iteration of entities, i can't have a crystal clear mind on that, so i still can't implement that part. Should every system hold a local list of entities which they are interested in ? Or should I just iterate through the entities in the World class and create a nested loop to iterate through systems and check if the entity has the components the system is interested in ? I mean :

for (entity x : listofentities) {
   for (system y : listofsystems) {
       if ((x.componentBitmask & y.bitmask) == y.bitmask)
             y.update(x, deltatime)
       }
 }

but I think a bitmask system will kinda block flexibility in case of embedding a scripting language. Or having local lists for each system will increase memory usage for classes. I am terribly confused.

share|improve this question
    
Why do you expect the bitmask approach to hamper script bindings? As an aside, use references (const, if possible) in the for-each loops to avoid copying entities and systems. –  Benjamin Kloster Jul 19 '13 at 12:25
    
using a bitmask for example an int, will hold only 32 different components. I am not implying there will be more than 32 components but what if i have ? i will have to create another int or 64bit int, it won't be dynamic. –  deniz Jul 19 '13 at 12:44
    
You could use std::bitset or std::vector<bool>, depending on whether or not you want it to be run-time dynamic. –  Benjamin Kloster Jul 19 '13 at 15:03
add comment

3 Answers

up vote 4 down vote accepted

Having local lists for each system will increase memory usage for classes.

It's a traditional space-time tradeoff.

While iterating through all the entities and checking their signatures is straight to code, it may become inefficient as your number of systems grow - imagine a specialized system (let it be input) that looks for its probably single entity of interest amongst thousands of unrelated entities.

That said, this approach may still be good enough depending on your goals.

Although, if you're worried about speed, there are of course another solutions to consider.

Should every system hold a local list of entities which they are interested in?

Exactly. This is a standard approach that should give you decent performance and is reasonably easy to implement. The memory overhead is negliglible in my opinion - we're talking about storing pointers.

Now how to maintain these "lists of interest" may not be that obvious. As for data container, std::vector<entity*> targets inside system's class is perfectly enough. Now what I do is this:

  • Entity is empty on creation and does not belong to any system.
  • Whenever I add a component to an entity:

    • obtain its current bit signature,
    • map component's size to world's pool of adequate chunk size (personally I use boost::pool) and allocate the component there
    • obtain entity's new bit signature (which is just "current bit signature" plus the new component)
    • iterate through all the world's systems and if there's a system whose signature doesn't match the entity's current signature and does match the new signature, it becomes obvious we should push_back the pointer to our entity there.

          for(auto sys = owner_world.systems.begin(); sys != owner_world.systems.end(); ++sys)
                  if((*sys)->components_signature.matches(new_signature) && !(*sys)->components_signature.matches(old_signature)) 
                          (*sys)->add(this);
      

Removing an entity is entirely analogous, with the only difference that we remove if a system matches with our current signature (which means that the entity was there) and doesn't match with the new signature (which means the entity should no longer be there).

Now you may be considering usage of std::list because removing from vector is O(n), not mentioning that you would have to shift big chunk of data every time you remove from the middle. Actually, you don't have to - since we don't care about processing order on this level we can just call std::remove and live with the fact that on every deletion we only have to perform O(n) search for our to-be-removed entity.

std::list would give you O(1) remove but on the other side you have a bit of additional memory overhead. Also remember that most of the time you will be processing entities and not removing them - and this surely is done faster using std::vector.

If you are very performance critical, you can consider even another data accessing pattern, but either way you maintain some kind of "lists of interest". Remember though that if you keep your Entity System API abstracted enough it shouldn't be a problem to improve systems' entity processing methods if your framerate drops because of them - so for now, choose the method that is easiest for you to code - only then profile and improve if needed.

share|improve this answer
    
Thanks for the answer, that was a great one. –  deniz Jul 23 '13 at 8:41
add comment

There's an approach that is worth considering where each system owns the components associated with itself and the entities only refer to them. Basically, your (simplified) Entity class looks like this:

class Entity {
  std::map<ComponentType, Component*> components;
};

When you have say a RigidBody component attached to an Entity, you request it from your Physics system. The system creates the component and lets the entity keep a pointer to it. Your system then looks like:

class PhysicsSystem {
  std::vector<RigidBodyComponent> rigidBodyComponents;
};

Now, this might look a little counter intuitive at first but the advantage lies in the way component entity systems update their state. Often, you'll iterate through your systems and request they update the associated components

for(auto it = systems.begin(); it != systems.end(); ++it) {
  it->update();
}

The strength of having all components owned by the system in contiguous memory is that when your system iterates over every component and updates it, it basically only has to do

for(auto it = rigidBodyComponents.begin(); it != rigidBodyComponents.end(); ++it) {
  it->update();
}

It doesn't have to iterate over all entities that potentially don't have a component they need to update and it also has a potential for very good cache performance because the components will all be stored contiguously. This is one, if not the greatest advantage of this method. You'll often have hundreds and thousands of components at a given time, might as well try and be as performant as possible.

At that point your World only loops through the systems and calls update on them without needing to iterate entities as well. It's (imho) better design because then the responsibilities of systems are a lot clearer.

Of course, there are a myriad of such designs so you have to carefully evaluate the needs of your game and choose the most appropriate but as we can see here it's sometimes the little design details that can make a difference.

share|improve this answer
    
good answer, thanks. but components don't have functions (like update()), only data. and the system processes that data. so according to your example, i should add a virtual update for the component class and a pointer of entity for each component, am i right ? –  deniz Jul 19 '13 at 15:14
    
@deniz It all depends on your design. If your components don't have any methods but only data, the system can still iterate over them and perform the necessary actions. As for linking back to entities, yes you could store a pointer to the owner entity in the component itself or have your system maintain a map between component handles and entities. Typically though, you want your components to be as self-contained as possible. A component that doesn't know at all about it's parent entity is ideal. If you need communication in that direction, prefer events and the like. –  pwny Jul 19 '13 at 15:18
    
If you say it will be better for efficiency, i will use your pattern. –  deniz Jul 19 '13 at 17:20
    
@deniz Make sure you actually profile your code early and often to identify what works and doesn't for your particular engin :) –  pwny Jul 19 '13 at 17:27
    
okay :) i will do kinda stress test –  deniz Jul 19 '13 at 17:46
show 1 more comment

In my opinion, a good architecture is to create a components layer in the entities, and separate the management of each system in this components layer. For example, the logic system has some logic components that affects to their entity, and store the common attributes that are shared to all the components in the entity.

After that, if you want to manage the each system's objects in different points, or in a particular order, it is better to create a list of active components in each system. All the lists of pointers that you can create and manage in the systems are less than one loaded resource.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.