使用位集访问向量索引

ᴘᴀɴᴀʏɪᴏᴛɪs 发表于 Dev

ᴘᴀɴᴀʏɪᴏᴛɪs

我正在尝试编写我自己的实体组件系统的代码，并且我想要一种快速的（尽可能恒定的时间）但也要使用内存有效的方式来访问实体的组件。

使用了全局映射（std::unordered_map），该映射将每个实体映射到包含其成分的排序向量：

Key        Value
---        -----
EntityA -> Sorted vector of components 
EntityB -> Sorted vector of components
[..]    -> [..]

每个实体都有一个位集，指示该实体具有哪些组件。：

|C0 |C1 |C2 |C3 |C4 |C5
 0   0   1   0   1   1

and on the map:
Key        Value
---        -----
EntityA -> [C2,C4,C5]

随着组件的添加很少，我可以负担得起排序插入的费用，但是我绝对希望快速访问。

现在我从位集中知道C4是第二个元素集（从左侧开始计数），因此它应该在第二个矢量索引处。

我该如何将其写入将根据给定的组件类型ID返回实体组件的方法？例如。

Component* getComponent(ComponentID id){ // component id of C5 should be 6 since it occupies the 6th position of the bitset
return [..];
}

巴里

假设我们的成员是：

std::bitset<6> bits;
std::vector<Component> comps;

然后：

Component* getComponent(int id) {
    // we need to find how many bits are set for ids < id
    // first, make sure this one is set:
    if (!bits[id]) return nullptr;

    // then, let's count
    int idx = 0;
    for (int i = 0; i < id; ++i) {
        if (bits[i]) ++idx;
    }

    // now, just return the right pointer
    return &comps[idx];
}

std::bitset::test如果要进行边界检查，也可以使用而不是索引运算符。

更快的解决方案可能是这样的：

Component* getComponent(int id) {
    if (!bits[id]) return nullptr;

    // flip id and get a mask
    // if we have C0 .. C5, and we pass in 4
    // we want the mask 0x111100
    unsigned long mask = (1 << (bits.size() - id)) - 1;
    mask = ~mask;

    // apply the mask to the bitset
    // so from 0x001011, we get 0x001000
    unsigned long new_bits = bits.to_ulong() & mask;

    // count how many bits are set there
    unsigned int popcnt = __builtin_popcount(new_bits);

    // and there we have it
    return &comps[popcnt];
}

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。