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.

I am implementing a simple entity/component-based engine in C++ and am unsure about the best way to store references to entities/components and what the best way to traverse them each game step would be.

My current thoughts are to:

  • Store a reference to the parent entity of each entity in the game.
  • Instantiate the game engine with a root entity (e.g. a Scene entity).
  • Traverse all entities in the game starting from the root entity and call the update method.

My entity interface is such that each entity in the game will have an update method which will call the update method for each of the entities components:

class Entity
{
public:
    virtual void update();
};

However I don't think a tree traversal would be the most optimal solution - would it be better to store references to every entity in the game in a flat data structure and loop this every game step?

share|improve this question

1 Answer 1

up vote 8 down vote accepted

Storing components within the entity objects, and then doing a "for each entity, for each component, update" loop is a fairly straightforward and obvious solution. It's also not very good for cache coherency and creates problems for concurrent update scheduling.

Consider an outboard storage approach, where component instances are stored in large homogeneous lists within the subsystem that is responsible for them. For example, physics components all live in what is effectively a big std::vector<PhysicsComponent> within the physics simulation object.

In this system, entities only store IDs (possibly simple integers) or some other similar form of reference to components that comprise the entity. In fact, it's possible (and in some cases beneficial) to take this to the Nth degree and eschew an entity object altogether, binding components together only implicitly by storing an entity ID number.

To update components, you simply update the owning system (that is, physicsSimulator.Update(deltaTime) or similar). This update traverses each component in order and does whatever updating is needed. This is much more cache-friendly, and affords you a much coarser organization of update dependencies. This allows you to more easily reason about which systems have dependencies on the updated data from other systems and order their relative updates accordingly. It allow allows you to easily process updates for entire batches of components in parallel if you know the two relevant systems do not need to directly interact in the same frame.


Storing the entities themselves in a large tree is also not something I think you should do unless you have a really compelling need for it. It sounds like you are conflating the idea of a scene graph with the idea of your entity system: thus the assumption that every entity has a parent that ultimately leads back to a "root" entity.

This is probably a bad idea for the very same reason that (most) scene graph implementations are a bad idea: you end up with a very deep tree, the leafs of which constantly need reshuffling based on new parents or due to lifetime goods (good scene graphs tends not to be particularly deep, and do not try to include "every" object at an extremely granular level). Plus, this design will force you to find physical parents for entities that don't logically need them just because your system says everybody must be parented to the root.

A flat list of entities is a more common, and generally better, solution. I would go with that until can demonstrate a very compelling need to organize them otherwise.

share|improve this answer
    
Thank you for the detailed response Josh, I really like this approach. Would the idea be to pass a reference of a owning system (e.g. physicsSimulator) in the constructor of an entity and store the ID in the entity this way? –  Alex May 15 at 16:22
1  
I wouldn't do it that way, that means every time you add a new system you have to add a constructor parameter. Instead, I'd implement an observer-pattern-like approach where systems can subscribe to an event generated by the entity factory that tells them "a new entity has been created with this parameters, you may create a corresponding component for this entity if anything about it interests you." The process is discussed in more detail in the link I provided at the top of the answer. –  Josh Petrie May 15 at 16:25
    
Many thanks Josh! –  Alex May 15 at 16:31
    
Just wanted to expand or share my thoughts: I wouldn't put the arrays (or vectors) storing the component data inside the managers (systems). I'm more partial to putting all the components in a centralized location and letting the various systems iterate through the components that way. I guess it just makes it easier for, say, the rendering system to inspect the transformation that the physics system actually works with. –  Boreal May 15 at 19:59

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.