检查一个位集是否包含另一个位集的所有值

Question

我正在尝试创建一个实体/组件系统，该系统自动匹配合适的实体合适的系统。我正在使用std::bitset和RTTI自动为每个组件类型分配一个位值。

系统的定义如下：MovementSystem : System<Position, Velocity>。

MovementSystem，在本例中，接受同时具有Position和Velocity组件（以及任何其他组件）的任何实体。

为了检查实体是否合适，我将系统的位集与实体的位集进行比较。

// 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

到目前为止，我的解决方案是这样的：

if(entityBitset & systemBitset) == systemBitset)) { /* entity is suitable! */ }

它似乎有效，但我在白板上涂鸦 bitsets 后发现它。这是正确的吗？还能再改进吗？（实体会在我的游戏中被创建和销毁大量时间，所以性能非常重要！）

---

如果需要（不应该），代码在这里，但几乎不可能阅读。

Answer 1

您的支票

(a & b) == b;     // check whether b is a subset of a

检查 是否b是 的子集a或等效项，是否a包含/包含b。请注意，您正在创建一个临时对象，然后创建一个 break-early operator==。

这相当于检查 和 的差值是否b为a空（注意顺序！）

(b & ~a).none(); 

这将同样快：暂时休息，然后提前休息.none()

考虑到 的界面std::bitset，这已经是您能达到的最快速度了。问题在于std::bitset它的所有按位成员 ( &、|、^和~循环遍历每个单词。早期终止操作如none()、any()、==或<, 不能与它们交织在一起。这是因为std::bitset不公开底层单词存储，因此您无法自己执行迭代。

但是，如果您要编写自己的位集类，则可以编写一个特殊用途的includes()算法来循环每个单词，&直到您提前中断为止

// 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;
}

缺少的类似算法std::bitset是intersects()有效测试(a & b) != 0。目前，您必须首先执行按位与，然后测试是否为零，而在一个循环中完成会更有效。如果有更新的话，如果它们包含和原语std::bitset那就太好了。includes()intersects()