سؤال

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.

هل كانت مفيدة؟

المحلول

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.

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى StackOverflow
scroll top