I'm trying to create an entity/component system that automatically matches suitable entities suitable systems. I'm using std::bitset
and RTTI
to automatically assign a bit value to every component type.
A system is defined like this: MovementSystem : System<Position, Velocity>
.
MovementSystem
, in this example, accepts any entity that has both the Position
and the Velocity
components (and any other component).
To check if an entity is suitable, I compare the system's bitset to the entity's bitset.
// Let's assume there are max 4 components
1 1 0 1 // Entity bitset
^ ^ ^
Position Velocity OtherB
1 1 0 0 // Suitable example system bitset
^ ^
Position Velocity
1 1 1 0 // Unsuitable example system bitset
^ ^ ^ // Entity does not have OtherA!
Position Velocity OtherA
So far, my solution is this one:
if(entityBitset & systemBitset) == systemBitset)) { /* entity is suitable! */ }
It seems to work, but I found it after doodling bitsets on a whiteboard. Is it correct? Can it be improved any further? (Entities will be created and destroyed an immense amount of times in my games, so performance is very important!)
Code is here if needed (shouldn't be), but it's almost impossible to read.
Member functions Tests whether all bits from bitset are set or not.
As bitset stores the same information in compressed manner the operation on bitset are faster than that of array and vector.
bitset set() function in C++ STL Parameter: The function accepts two parameters which are described below: index – this parameter specifies the position at which the bit has to be set. The parameter is an optional one.
Your check
(a & b) == b; // check whether b is a subset of a
checks whether b
is a subset of a
, or equivalent, whether a
contains/includes b
. Note that you are creating one temporary followed by the break-early operator==
.
This is equivalent to checking whether the difference of b
and a
is empty (note the order!)
(b & ~a).none();
This will be equally fast: a temporary followed by a break-early .none()
Given the interface of std::bitset
, this is as fast you can get. The problem with std::bitset
is that all its bitwise members (&
, |
, ^
and ~
loop over every word. The early termination operations like none()
, any()
, ==
or <
, cannot be intertwined with them. This is because std::bitset
does not expose the underyling word storage so you cannot perform the iteration yourself.
However, if you would write your own bitset class, you could write a special-purpose includes()
algorithm that loops over each of the words, doing the &
until you break-early
// test whether this includes other
bool YourBitSet::includes(YourBitSet const& other) const {
for (auto i = 0; i < NumWords; ++i)
if ((other.word[i] & ~(this->word[i])) != 0)
return false;
return true;
}
A similar algorithm missing from std::bitset
would be intersects()
, to efficiently test (a & b) != 0
. Currently you have to first do bitwise and, and then the test for zero, whereas that would be more efficiently done in one loop. If std::bitset
ever gets updated, it would be nice if they include includes()
and intersects()
primitives.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With