How can I efficiently implement a bitmask larger than 64-bits for component existence checks?

Question

In my ECS implementation, I use bit-wise operations (as described and illustrated in this thread) to tell an entity what type of components it currently consists of. So my Entity class has the following member:

unsigned long m_CompMask;

The different component types are then defined as an enum, whose member values are all power of two:

enum ComponentType
{
    COMP_TYPE_UNKNOWN                   = 0,
    COMP_TYPE_PERSON                    = 1,
    COMP_TYPE_RENDERABLE                = 2,
    COMP_TYPE_MOVEABLE                  = 4,
    [...]
};

Each time a new component is added to my entity instance, I do the following bit operation to update the mask (where newType is a member of the enum mentioned above):

m_CompMask |= newType;

This approach enables me to efficiently check if a certain entity instance has a certain component (and hence might be relevant for a specific system), like so:

return (m_CompMask & type);

The limiting factor in this approach however is the m_CompMask variable since it won't be able to handle more than 64 component types (if I increase it to unsigned long long).

I don't expect to be needing more than that in my current project, but nonetheless I'd like to hear some ideas regarding alternatives that allow more than 64 types (as big games certainly need to) while still maintaining the ease and efficiently of those bit-wise operations as much as possible? Any ideas how this is handled in "proper big" projects?

Answer 1

To add to the other answers here, you can use something like in the following code to have a bit set of arbitrary length that grows on demand. This method even lets you do a simple form of compression; if your most common components have the lowest ID values, the majority of your entities will use a small amount of bitset memory to track their components, but ones that use rarer components will still operate properly.

/// <summary>
/// A resizable collection of bits.
/// </summary>
public class BitSet {
    const int BitSize = (sizeof(uint) * 8) - 1;
    const int ByteSize = 5;  // log_2(BitSize + 1)

    uint[] bits;

    /// <summary>
    /// Initializes a new instance of the <see cref="BitSet"/> class.
    /// </summary>
    public BitSet () {
        bits = new uint[1];
    }

    /// <summary>
    /// Determines whether the given bit is set.
    /// </summary>
    /// <param name="index">The index of the bit to check.</param>
    /// <returns><c>true</c> if the bit is set; otherwise, <c>false</c>.</returns>
    public bool IsSet (int index) {
        int b = index >> ByteSize;
        if (b >= bits.Length)
            return false;

        return (bits[b] & (1 << (index & BitSize))) != 0;
    }

    /// <summary>
    /// Sets the bit at the given index.
    /// </summary>
    /// <param name="index">The bit to set.</param>
    public void SetBit (int index) {
        int b = index >> ByteSize;
        if (b >= bits.Length)
            Array.Resize(ref bits, b + 1);

        bits[b] |= 1u << (index & BitSize);
    }

    /// <summary>
    /// Clears the bit at the given index.
    /// </summary>
    /// <param name="index">The bit to clear.</param>
    public void ClearBit (int index) {
        int b = index >> ByteSize;
        if (b >= bits.Length)
            return;

        bits[b] &= ~(1u << (index & BitSize));
    }

    /// <summary>
    /// Sets all bits.
    /// </summary>
    public void SetAll () {
        int count = bits.Length;
        for (int i = 0; i < count; i++)
            bits[i] = 0xffffffff;
    }

    /// <summary>
    /// Clears all bits.
    /// </summary>
    public void ClearAll () {
        Array.Clear(bits, 0, bits.Length);
    }

    /// <summary>
    /// Determines whether all of the bits in this instance are also set in the given bitset.
    /// </summary>
    /// <param name="other">The bitset to check.</param>
    /// <returns><c>true</c> if all of the bits in this instance are set in <paramref name="other"/>; otherwise, <c>false</c>.</returns>
    public bool IsSubsetOf (BitSet other) {
        if (other == null)
            throw new ArgumentNullException("other");

        var otherBits = other.bits;
        int count = Math.Min(bits.Length, otherBits.Length);
        for (int i = 0; i < count; i++) {
            uint bit = bits[i];
            if ((bit & otherBits[i]) != bit)
                return false;
        }

        // handle extra bits on our side that might just be all zero
        int extra = bits.Length - count;
        for (int i = count; i < extra; i++) {
            if (bits[i] != 0)
                return false;
        }

        return true;
    }
}

Likely to be completely robust you'd want to implement some of the framework interfaces such as IEquatable and IComparable and override a few operators, GetHashCode, etc.

Answer 2

Maybe you could use a C-style bitfield and just add new fields as needed.

struct ComponentIds {   
    bool person     : 1;
    bool renderable : 1; 
    bool movable    : 1;
    bool ai         : 1;
    // and so on...
};

class GameObject {
public:

    ComponentIds componentsUsed;
};

Since you only need boolean flags, a bitfield struct would be a lot smaller than simple bools and gives the same results and ease of use:

GameObject * go = ...
if (go->componentsUsed.ai)
{
    // has AI component
}

Answer 3

A simple example of a data structure that fills this purpose:

class LongerBitMask {

    //mask1_mask2

    long mask1
    long mask2

    public LongerBitMask() {
        mask1 = 0
        mask2 = 0
    }

    public LongerBitMask(long m1, long m2) {
        mask1 = m1
        mask2 = m2
    }

    public void OR(LongerBitMask other) {
        this.mask1 |= other.mask1
        this.mask2 |= other.mask2
    }

    public bool Match(LongerBitMask other) {
        return (this.mask1 & other.mask1) && (this.mask2 && other.mask2)
    }
}

Now, your enums can either index into a dictionary, or array of some sort. It's a bit harder to manage I suppose, but I haven't thought much about this end of things.

Perhaps just have an array of LongerBitMask that is generated automatically? Then index into it using the enum? Just make sure to only add to the end of the enums. Otherwise you'll have components that change values.

Some static code:

void CreateComponentBitMasks()
{
    LongerBitMasks[] bitMasks
    int index = 0

    bitMasks[index++] = new LongerBitMask(0, 0)

    for(int m2 = 0; m2 < 63; m2++) {
        bitMasks[index++] = new LongerBitMask(0, 1<<m2)
    }

    for(int m1 = 0; m1 < 63; m1++) {
        bitMasks[index++] = new LongerBitMask(1<<m1, 0)
    }
}

Set your components to their default enum values, 0 through 127 (don't make them power of two). Then you can retrieve your bit masks with:

bitMasks[COMP_TYPE_RENDERABLE]; //would return bit mask with values 0, 2

Now your systems will define their own LongBitMask values and compare against entities using Match.

Like a system would create its own bit mask with:

//creates a bit mask to match components that are a renderable person.
LongerBitMask thisSystemMask = new LongerBitMask()
thisSystemMask.OR(bitMasks[COMP_TYPE_RENDERABLE])
thisSystemMask.OR(bitMasks[COMP_TYPE_PERSON])

Likely something wrong in my bit shifting or other math...

Answer 4

It is indeed easily possible to use more than 64 components even in a moderate scope game.

Create you own bitset class which can hold a mask of arbitrary length.

Answer 5

I don't know how this is implemented in AAA games, but your problem seems quite simple for me. You just need to fuse together:

• Memory region holding enough bits.
• Way to manipulate given bits by index.

Here is my example code, in C++11. I hope you can translate it into whatever you are using, but if you can't, feel free to ask me. I think I saw something similiar in boost, but can't remember right now.

#include <iostream>

struct BitProxy
{
    char &ByteRef;
    char Mask;

    BitProxy& operator=(bool v)
    {
        if(v) {ByteRef |= Mask;}
        else {ByteRef &= ~Mask;}
        return *this;
    }

    operator bool() const {return ByteRef & Mask;}
};

template <unsigned NumBits, typename EnumType, typename UnderlyingType>
struct EnumSet
{
    // how much bytes we need
    static constexpr unsigned Size = (NumBits - 1) / 8 + 1;
    char Bytes[Size];

    BitProxy operator[](EnumType v)
    {
        unsigned byte_ix = unsigned(UnderlyingType(v)) / 8;
        unsigned bit_ix = unsigned(UnderlyingType(v)) & 7;
        return BitProxy {Bytes[byte_ix], char(1 << bit_ix)};
    }
};

namespace Component
{
    enum class Id : unsigned
    {
        One,
        Two,
        Three,
        c4, c5, c6, c7, c8, c9, c10,
        // this special one will tells us how much bits we need
        Last_
    };

    static constexpr Id AllIds[] =
    {
        // well...
        Id::One, Id::Two, Id::Three, Id::c4, Id::c5, Id::c6, Id::c7, Id::c8, Id::c9, Id::c10
    };

    typedef EnumSet<unsigned(Id::Last_), Id, unsigned> Set;
}

int main()
{
    Component::Set cs {};
    cs[Component::Id::Two] = true;
    cs[Component::Id::c7] = true;
    for(Component::Id id : Component::AllIds)
        std::cout << unsigned(id) << " -> " << (cs[id] ? "true":"false") << std::endl;
}

http://coliru.stacked-crooked.com/a/63904a428e95df94 Output:

0 -> false
1 -> true
2 -> false
3 -> false
4 -> false
5 -> false
6 -> true
7 -> false
8 -> false
9 -> false

Used struct insted of class for simplicity, but I advise to properly encapsulate it.