2
\$\begingroup\$

I'm developing a game in C++, making use of the Entity-Component system.

I'm going to store a list of each component, with each component's position in the list mapping to it's entity. So, the 5th item in the list is a component for Entity 5, etc.

My inspiration came from this:

https://www.gamedev.net/resources/_/technical/game-programming/implementing-component-entity-systems-r3382

My question is what data structure is the best for this. I guess my options are an array or a vector of Components. When using either the array or the vector, is it possible to have empty elements. So, for example element 0, 1 and 4 might contain components, but positions 2 and 3 empty. I know I could achieve this with pointers to components, but is this the best way?

Advice appreciated.

Thanks, Rich.

Improve this question
\$\endgroup\$
1
  • 1
    \$\begingroup\$ The gaps between the components will tend to cause poor cache performance when iterating over a component list, and complicate your update logic with randomish branch prediction. If you iterate frequently and do random access or insertions/deletions rarely, then you might get better performance from structures that don't require these gaps (eg a sorted list, search tree, or a packed unordered array with an entity-to-index map for random access). If you describe a bit more of your typical operations, it will help narrow down which choices have suitable trade-offs. \$\endgroup\$
    – DMGregory ♦
    Apr 28, 2017 at 17:03

2 Answers 2

Reset to default
2
\$\begingroup\$

Given the constraints (unknown number of components, components can be added or removed at runtime, components have different memory footprints, components derive from the same class), the straightforward solution is:

std::vector<std::unique_ptr<IComponent>>

One could argue in favor of another container that provides constant time insertion and deletion, but I don't think that's actually necessary or even beneficial. For a small number of elements, vector insertion and removal is faster than list insertion and removal.

It can be expected that the container does not ever contain empty elements.

Improve this answer
\$\endgroup\$
0
0
\$\begingroup\$

In the game I'm making, which is not pure ECS, but something between it and common design (object oriented), I have two main types of components: 'standard' and 'extended'.

Standard are for example position, speed, health... which are common to almost all the entities and so are stored in simple arrays: there will be few gaps and can easily be iterated. Components of the same entity share the same index in the arrays and so is easy to retrieve them and create interactions.

Extended components are instead stored in arrays at the first slot available: there will be few "teleport_on_collision" entities and I can't afford to have one component at 1° slot, one at 10° and one at 23°, it would be a pain for the cache, while iterating them. So they are stored in the first free slots and each owner entity keeps in a vector (actually a linked list allocated into an array shared between all the entities) the list of extend components it has (pairs of 'type', 'slot'). Lookup is slightly slower because you have to search in this array if a component exists and in that case, get its index, its type and then get it. I'm implementing a message system to communicate between standard and extended components to avoid dependences: extended components are generally implemented after basics one which, so, can't know they existence and implementation: you just propagate messages such as "on_hit" to them and they will react on their own. I decided to use this approach because, generally, you don't fire many messages each frame, but usually you need to update each component each frame, so linear lookup into a continuous array is what you have to aim for.

I hope I've been clear, English is not my main languages.

I'm just testing this approach and I'm not sure it's the best way, but I think this text is too long to be a simple comment. (I would like to have comments and criticisms)

Improve this answer
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .