How should I traverse entities and components for their per-frame updates?

Question

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?

Answer 1

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.