Wie kann ich eine Bitmaske, die größer als 64 Bit ist, effizient für die Überprüfung der Komponentenexistenz implementieren?

In meiner ECS-Implementierung verwende ich bitweise Operationen (wie in diesem Thread beschrieben und dargestellt ), um einer Entität mitzuteilen, aus welcher Art von Komponenten sie derzeit besteht. Meine EntityKlasse hat also folgendes Mitglied:

unsigned long m_CompMask;

Die verschiedenen Komponententypen werden dann als definiert enum, deren Elementwerte alle Zweierpotenzen sind:

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

Jedes Mal, wenn eine neue Komponente zu meiner Entitätsinstanz hinzugefügt wird, führe ich die folgende Bitoperation aus, um die Maske zu aktualisieren (wobei newType Mitglied der enumoben genannten ist):

m_CompMask |= newType;

Mit diesem Ansatz kann ich effizient prüfen, ob eine bestimmte Entitätsinstanz eine bestimmte Komponente enthält (und daher für ein bestimmtes System relevant sein kann), z.

return (m_CompMask & type);

Der begrenzende Faktor bei diesem Ansatz ist jedoch die m_CompMaskVariable, da sie nicht mehr als 64 Komponententypen verarbeiten kann (wenn ich sie auf erhöhe unsigned long long).

Ich erwarte nicht, dass ich in meinem aktuellen Projekt mehr als das brauche, aber ich würde trotzdem gerne einige Ideen zu Alternativen hören, die mehr als 64 Typen zulassen (wie es große Spiele sicherlich müssen) und gleichzeitig die Leichtigkeit und Effizienz von beibehalten diese bitweisen Operationen so viel wie möglich? Irgendwelche Ideen, wie dies in "richtigen großen" Projekten gehandhabt wird ?

Um die anderen Antworten hier zu ergänzen, können Sie so etwas wie den folgenden Code verwenden, um einen Bit-Satz beliebiger Länge zu erhalten, der bei Bedarf wächst. Mit dieser Methode können Sie sogar eine einfache Form der Komprimierung durchführen. Wenn Ihre am häufigsten verwendeten Komponenten die niedrigsten ID-Werte aufweisen, verwendet die Mehrheit Ihrer Entitäten eine kleine Menge Bitset-Speicher, um ihre Komponenten zu verfolgen. Diejenigen, die seltenere Komponenten verwenden, funktionieren jedoch weiterhin ordnungsgemäß.

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

Wahrscheinlich vollständig robust, möchten Sie einige der Framework-Schnittstellen wie IEquatable und IComparable implementieren und einige Operatoren, GetHashCode usw. überschreiben.

Vielleicht könnten Sie ein Bitfeld im C-Stil verwenden und nach Bedarf neue Felder hinzufügen.

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

class GameObject {
public:

    ComponentIds componentsUsed;
};

Da Sie nur boolesche Flags benötigen, ist eine Bitfeldstruktur viel kleiner als einfache Bools und bietet dieselben Ergebnisse und Benutzerfreundlichkeit:

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

Ein einfaches Beispiel für eine Datenstruktur, die diesen Zweck erfüllt:

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)
    }
}

Jetzt können Ihre Aufzählungen entweder in ein Wörterbuch oder in ein Array indizieren. Ich nehme an, es ist etwas schwieriger zu handhaben, aber ich habe nicht viel über dieses Ende der Dinge nachgedacht.

Vielleicht wird nur ein Array davon LongerBitMaskautomatisch generiert? Dann mit der Aufzählung hinein indizieren? Stellen Sie einfach sicher, dass Sie nur am Ende der Aufzählungen hinzufügen. Andernfalls haben Sie Komponenten, die Werte ändern.

Einige statische Codes:

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)
    }
}

Stellen Sie Ihre Komponenten auf ihre Standard-Enum-Werte 0 bis 127 ein (machen Sie sie nicht zu zweit). Dann können Sie Ihre Bitmasken abrufen mit:

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

Jetzt definieren Ihre Systeme ihre eigenen LongBitMaskWerte und vergleichen sie mit Entitäten Match.

Als würde ein System seine eigene Bitmaske erstellen mit:

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

Wahrscheinlich stimmt etwas nicht mit meiner Bitverschiebung oder anderen Berechnungen ...

Es ist in der Tat leicht möglich, mehr als 64 Komponenten zu verwenden, selbst in einem Spiel mit mittlerem Umfang.

Erstellen Sie eine eigene Bitset-Klasse, die eine Maske beliebiger Länge enthalten kann.

Ich weiß nicht, wie dies in AAA-Spielen implementiert ist, aber Ihr Problem scheint mir recht einfach zu sein. Sie müssen nur miteinander verschmelzen:

• Speicherbereich mit genügend Bits.
• Möglichkeit, bestimmte Bits nach Index zu manipulieren.

Hier ist mein Beispielcode in C ++ 11. Ich hoffe, Sie können es in alles übersetzen, was Sie verwenden, aber wenn Sie nicht können, können Sie mich gerne fragen. Ich glaube, ich habe etwas Ähnliches im Boost gesehen, kann mich aber momentan nicht erinnern.

#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 Ausgabe:

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

Verwendete der Einfachheit halber die Struktur der Klasse, aber ich empfehle, sie richtig zu kapseln.