How do you filter entities in an Entitiy Component System?

Question

I am currently writing my own ECS in C++ and I am using std::bitset.

I register a component at compile time and give it an ID.

Position has ID 1
Direction has ID 2
..

vector<bitset<numberOfComponents>> 

And so on. The problem with this approach is the more components I register the bigger my bitset for every entity will get.

If I overshoot my goal a bit and say that I will have 1000 components and 5000 entities.

A std::bitset<1000> is 128 bytes big of my machine and for 5000 entities that is 640kbytes of overhead. To be fair that is actually not that big considering that many machines have 8 gigs of ram.

But I am wondering how you guys are doing it? How do you filter your entities? Are you also using something like a component mask?

Update based on congusbongus answer:

vector<DrawComponent> c1;
vector<MoveComponent> c2;

vector<Entity> draw = {1, 2, 8, 42,128}
vector<Entity> move = {8,128};

I assume that is how you think it works right? Two questions:

1.) How do you make vector<Entity> draw = {1, 2, 8, 42,128} contiguous in memory? If the id is just the index into a vector there will be a lot of "holes".

2.) Because there is no filter, how do you then associate entities together? If you have system System<Draw,Move>, you need the Draw and Move component and because of

vector<Entity> draw = {1, 2, 8, 42,128}
vector<Entity> move = {8,128}; 

if you just iterate over both of them it doesn't work. because move[0] = 8, and draw[0] = 1.

I mean if you draw something you actually need the draw and move component because u need to draw at a specific position.

Answer 1

In a "pure" ECS, your entities consist of just a unique ID, which shared among its components. For example you may have these entities:

• Entity ID 123, it is drawn and moved
• Entity ID 234, which is only drawn

Thus you'll have the following component collections:

• Drawn components: <123, 234>
• Moved components: <123>

There is no need to filter in this scheme; you might have a rendering system that draws all the "drawn" components, and a physics system that moves all the "moved" components.

Answer 2

I suppose that you're really asking now, post-edit, how you can use the entity ID's as indices into your component vectors without there being gaps in the component vectors. The simple answer is that you can't. You really want an associative container for your components, like an std::map or std::unordered_map, but barring that, if you insist on storing your components contiguously, you just need to let your components know what entities they are associated with:

// use as a base class for your components
class Component{
    Entity ent_id;
}

Then, in your "System<DrawComponent, MoveComponent>", you loop through EITHER your vector of DrawComponents or your vector of MoveComponents, and use the ent_id from those components to find the corresponding component from the other component vector that you're not looping through by using something like std::upper_bound.

An alternative to a Component base class containing the Entity ID would be to use an associative vector class, like Łukasz Czerwiński's AssocVector or Loki's. These guarantee memory contiguity while allowing you to retrieve your components by a key.

Answer 3

1. component types

I am using component bit mask as well and the mask size is only 64 now, maybe too small, but I don't think it would grow to 1000 in any case, that's too much for the types of components.

The point of ECS is that you can create unlimited types of "entity" with provided components, so with N types of components you can have a maximum of (CN1 + CN2 + ... + CNN) types of entities, and that's really many.

The entity has a component bit mask to identify which types of component it has. Like bitset<64> componentTypes, and the value could be 1100... which indicates the entity contains type 0 and 1 of components.

2. contiguous memory

I think the contiguous memory is focused on components not on entities, i.e.

vector<DrawComponent> c1;
vector<MoveComponent> c2;

should be contiguous, and that's guaranteed by vector.

The entity ID is not the index of component vector, if you want to get certain component of your entity, you have to find it sequentially in the vector, so I keep the component vector sorted by entity id.

3. system

System<Draw,Move> wants to filter all entities who have at least Draw and Move component, so the system itself should have a mask (bitset) (same size as entity's bit mask) as well.

The system also has a list of entity (or entity id) which records the filtered entites. (in your case, that's the vector<Entity> draw)(so this list should belong to a system)

When an entity add a component, the entity updates its component bit mask, and then try to match the masks with all systems; when a match occurs, that system register the entity onto its list, then the filtering is done.

On the next system's update, the system check the list, get the first entity id, then get the components from c1, c2 by this id, update those components, then move to the next entity id and repeat.