How do you handle entity life-time and entities without all components in an ECS?

Question

I'm just starting to implement my own ECS and am drawing everything down on paper to make sure I understand it all before tackling the implementation in code. However I'm getting stuck on entity-lifetime and nothing I've read really answers my question.

Just to be sure I'm not missing something, my understanding so far is:

1. Components of the same type all sit next to each other in memory
2. Entities are just an ID, which Components refer to (i.e. Components have an "owner")
3. Components all have a unique Id

Great! So for example, say I have a PositionComponent, VelocityComponent, and VisibleComponent.

struct PositionComponent {
    vector2f position;
};

struct VelocityComponent {
    vector2f velocity;
};

struct VisibleComponent {
    Image imageToRender;
};

Great. Now let's say I have two types of Entity:

1. EntityA has a position, velocity, and visible components
2. EntityB has a position and velocity component, but is not visible

(let's hypothetically say that the Image in the visible component is the actual image data because every entity is super unique or something)

Say I have an PhysicsSystem which wants to iterate over all the Position and Velocity components and update the Position. This works, because every entity I've created has both of these components.

And so we're using EntityID as an index into the component arrays, we can easily know we're accessing the correct ones.

But then if there was a RenderSystem that wants to iterate over all the Position and Visible Components, the problem is that the EntityId can no longer be an index into the arrays, because not every Entity has every component.

So; the way I've thought to address this is by having an "Entity to Index Map" for each component. Basically, this EntityID has a PositionComponent in index 232 of the array.

But because of this, now any system that needs two or more Components to act, will lose out on all the benefits of an ECS, right?

I dismissed giving all components arrays empty space to keep them all "in sync", but that means I could have a lot of wasted data, which only gets worse the more different components I create.

There's then the problem of lifetime. If EntityID 232 is killed, I ideally would shift all the components in these arrays down to fill the gap, which again means I can't use EntityId as an index into the arrays.

A solution I thought of here was to re-use EntityIDs when they're no longer needed, maybe by using a 16bits of a 32-bit ID as the actual array index, and the other 16-bits as some sort of random guid to keep it clear that it's a new entity (and not the old one who's EntityID is being reused). This means I don't need to shift the data around, and wouldn't need to keep a map from ID to Index; but it doesn't solve the problem where not all entities have all components, so none of the arrays can ever be assumed to be "in sync".

So in summary my questions are: 1. How does a System in an ECS handle iterating over two separate components, when it's not guaranteed both component arrays will have the same entities components in the same indices? 2. Is it more beneficial to keep the data compact, or keep the arrays in sync?

Answer 1

One way this can be solved is with the notion of Archetype.

An Archetype is the set of components a particular entity needs. So in your example you have two archetypes: (position, velocity, visible) and (position, velocity).

For each archetype, you store an array of each component it needs, densely packed, representing all entities of that one archetype.

So here you have one trio of arrays for one archetype, and a separate pair of arrays for the second archetype.

Your entity ID can be a combination of high bits that indicate its archetype, and low bits that represent its index in that archetype's arrays.

Since each archetype stores entities that use every component of the archetype, you don't have to contend with mismatched or gappy collections.

A system then acts by iterating over all the archetypes that match its component needs, and churning through their arrays of its components of interest. You'll typically have lots of entities of each archetype, so you still get good cache coherency this way, taking a miss only when you switch to a different archetype.

To contend with destruction, a solution I've seen is to...

• Defer any destruction of entities to the end of an update frame, so it doesn't interfere with fast iteration the rest of the time.

• Handle deletion by swapping to and deleting from the end of the collection, so that the active entities stay densely packed.

• Forbid any script from holding onto an entity index/pointer longer than one frame. Instead, entites that need cross references have a stable long-term ID stored separately. Scripts can hold this stable ID, and when they need to actually look up a component, ask to translate it into the correct index/pointer to use this frame, then discard and re-request next frame (when it might have moved to a different spot).

  Updating the mapping of this stable ID to an index can be done lazily by memoized search (if you expect to delete often and reference rarely), or proactively by book-keeping during swaps (if you expect to reference often)