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

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?

• I'd be surprised if even big games used more than 64 different component types. This might be language specific as well, but I guess it'll depend on the strategy. – MichaelHouse Mar 11 '14 at 21:13
• Use two 64-bit longs and the bitwise AND twice :) ! – user9790 Mar 11 '14 at 21:24
• Please write return m_CompMask & type; :-) – bogglez Mar 11 '14 at 21:25
• @bogglez That indeed is even better. Edited and changed in my project. Thanks! – Philip Allgaier Mar 11 '14 at 21:40
• @Byte56 This slide deck from "Dungeon Siege" (2002: Windows, OS X) talks about 150+ components (gamedevs.org/uploads/data-driven-game-object-system.pdf) and so does this slide deck from the game "Prototyp" (2009: 360, PS3, Windows) (gdcvault.com/play/1911/Theory-and-Practice-of-the) – Philip Allgaier Mar 11 '14 at 21:48

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.

• I like this better than my answer. – MichaelHouse Mar 12 '14 at 4:00
• I'm confused. We're all writing C#... so why aren't we just using something like the BitSet or BitArray? – Vaughan Hilts Mar 12 '14 at 4:50
• @VaughanHilts C# has a BitArray class and a BitVector32 structure. The former cannot be resized after initialization; the latter is fixed at 32 bits and so useless for this situation. – MikeP Mar 12 '14 at 5:51

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
}


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

class LongerBitMask {

}

public LongerBitMask(long m1, long m2) {
}

}

}
}


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()
{
int index = 0

for(int m2 = 0; m2 < 63; m2++) {
}

for(int m1 = 0; m1 < 63; m1++) {
}
}


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.


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

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.

• An example would make this a great answer. (and maybe some commentary on performance impact). – MichaelHouse Mar 11 '14 at 21:35
• The one in our use is not made by me so I cannot post code. It is not trivially small either, over 200 lines of code. – karmington Mar 11 '14 at 21:39
• Any example will do. – MichaelHouse Mar 11 '14 at 21:40
• "m_activeComponentMask.setBit(typeId);" There's an initializer, functions like setBit and isBitSet, and operator overloads for all the binary operators. The class was not inlined so I assume it's overhead was negligible. – karmington Mar 11 '14 at 21:50
• Dungeon Siege had 169 (21 C++ components, 148 script ones) PDF – elFarto Mar 11 '14 at 21:51

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;

BitProxy& operator=(bool v)
{
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;
}

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.