将实体与实体组件系统中的系统匹配的有效方法
Efficient way of matching entities to systems in an entity component system
我正在开发面向数据的实体组件系统，其中组件类型和系统签名在编译时已知。
实体是组件的集合。组件可以 added/removed 来自 运行 时间的实体。
一个组件是一个小型的无逻辑class.
A signature 是组件类型的编译时列表。如果实体包含签名所需的所有组件类型，则称该实体与签名匹配。
一个简短的代码示例将向您展示用户语法的外观和预期用途：
// User-defined component types.
struct Comp0 : ecs::Component { /*...*/ };
struct Comp1 : ecs::Component { /*...*/ };
struct Comp2 : ecs::Component { /*...*/ };
struct Comp3 : ecs::Component { /*...*/ };
// User-defined system signatures.
using Sig0 = ecs::Requires<Comp0>;
using Sig1 = ecs::Requires<Comp1, Comp3>;
using Sig2 = ecs::Requires<Comp1, Comp2, Comp3>;
// Store all components in a compile-time type list.
using MyComps = ecs::ComponentList
<
Comp0, Comp1, Comp2, Comp3
>;
// Store all signatures in a compile-time type list.
using MySigs = ecs::SignatureList
<
Sig0, Sig1, Sig2
>;
// Final type of the entity manager.
using MyManager = ecs::Manager<MyComps, MySigs>;
void example()
{
MyManager m;
// Create an entity and add components to it at runtime.
auto e0 = m.createEntity();
m.add<Comp0>(e0);
m.add<Comp1>(e0);
m.add<Comp3>(e0);
// Matches.
assert(m.matches<Sig0>(e0));
// Matches.
assert(m.matches<Sig1>(e0));
// Doesn't match. (`Comp2` missing)
assert(!m.matches<Sig2>(e0));
// Do something with all entities matching `Sig0`.
m.forEntitiesMatching<Sig0>([](/*...*/){/*...*/});
}
我目前正在使用 std::bitset 操作检查实体是否匹配签名。然而，一旦签名数量和实体数量增加，性能就会迅速下降。
伪代码：
// m.forEntitiesMatching<Sig0>
// ...gets transformed into...
for(auto& e : entities)
if((e.bitset & getBitset<Sig0>()) == getBitset<Sig0>())
callUserFunction(e);
这可行，但如果用户多次使用相同的签名调用 forEntitiesMatching，则必须再次匹配所有实体。
在缓存友好的容器中预缓存实体可能还有更好的方法。
我试过使用某种缓存来创建 编译时映射（实现为 std::tuple<std::vector<EntityIndex>, std::vector<EntityIndex>, ...>），其中键是签名类型（每个由于 SignatureList)，签名类型具有唯一的增量索引），并且值是实体索引的向量。
我用类似的东西填充了缓存元组：
// Compile-time list iterations a-la `boost::hana`.
forEveryType<SignatureList>([](auto t)
{
using Type = decltype(t)::Type;
for(auto entityIndex : entities)
if(matchesSignature<Type>(e))
std::get<idx<Type>()>(cache).emplace_back(e);
});
并在每个管理器更新周期后清除它。
不幸的是，在我的所有测试中，它的执行速度比上面显示的 "raw" 循环慢。它还会有一个 更大的问题 ：如果对 forEntitiesMatching 的调用实际上删除了一个组件或向实体添加了一个组件怎么办？必须使缓存失效并为后续 forEntitiesMatching 调用重新计算。
有没有更快的方法将实体与签名匹配？
编译时知道很多东西（组件类型列表，签名类型列表，...） - 是否有任何辅助可以在编译时生成的数据结构，这将有助于 "bitset-like" 匹配？
关于伪代码：
for(auto& e : entities)
for(const auto& s : signatures)
if((e.bitset & s.bitset) == s.bitset)
callUserFunction(e);
我不确定你为什么需要内循环。
如果您在函数中有请求的签名，那么您可以获得该签名的位集，而无需遍历所有签名。
template <typename T>
void forEntitiesMatching(const std::function<void(Entity& e)>& fun)
{
for(auto& e : entities)
if((e.bitset & T::get_bitset()) == T::get_bitset())
fun(e);
}
您是否考虑过以下解决方案？
每个签名都会有一个与该签名匹配的实体容器。
添加或删除组件时需要更新相关的签名容器。
现在函数可以简单地转到签名实体容器并为每个实体执行函数。
根据add/remove组件与签名匹配的比例，您可以尝试构建一种前缀树存储对实体的引用。
树本身是静态的，只有包含实体的叶子才是运行时构建的容器。
这样在添加（或删除）组件时，只需将实体的引用移动到正确的叶子即可。
在搜索与签名匹配的实体时，您只需获取包含签名的所有叶子的并集并迭代它们。由于树（几乎）是静态的，您甚至不需要搜索这些叶子。
另一个好点：您可以使用 bitset 表示树中的路径，因此移动实体非常容易。
如果组件的数量导致了不切实际的叶子数量，并且没有使用所有组件的组合，您可以用哈希表替换树，其中位集是键，值是实体引用集。
这比具体的东西更多的是算法思想，但它似乎比遍历实体集更合理。
受@Marwan Burelle 想法影响的另一个选项。
每个组件将包含一个已排序的容器，其中包含具有该组件的实体。
在查找与签名匹配的实体时，您需要遍历实体的组件容器。
添加或删除是 O(nlogn)，因为它需要排序。但您只需要 add/remove 它 to/from 一个包含更少物品的容器。
迭代项目有点重，因为它是组件数量和每个组件中实体数量的一个因素。
你还有一个乘法元素，但是元素的数量又变小了。
我写了一个简化版作为POC。
编辑：我以前的版本有一些错误，现在希望它们已修复。
// Example program
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <vector>
#include <functional>
#include <memory>
#include <chrono>
struct ComponentBase
{
};
struct Entity
{
Entity(std::string&& name, uint id)
: _id(id),
_name(name)
{
}
uint _id;
std::string _name;
std::map<uint, std::shared_ptr<ComponentBase>> _components;
};
template <uint ID>
struct Component : public ComponentBase
{
static const uint _id;
static std::map<uint, Entity*> _entities;
};
template <uint ID>
std::map<uint, Entity*> Component<ID>::_entities;
template <uint ID>
const uint Component<ID>::_id = ID;
using Comp0 = Component<0>;
using Comp1 = Component<1>;
using Comp2 = Component<2>;
using Comp3 = Component<3>;
template <typename ...TComponents>
struct Enumerator
{
};
template <typename TComponent>
struct Enumerator<TComponent>
{
std::map<uint, Entity*>::iterator it;
Enumerator()
{
it = TComponent::_entities.begin();
}
bool AllMoveTo(Entity& entity)
{
while (HasNext() && Current()->_id < entity._id)
{
MoveNext();
}
if (!Current())
return false;
return Current()->_id == entity._id;
}
bool HasNext() const
{
auto it_next = it;
++it_next;
bool has_next = it_next != TComponent::_entities.end();
return has_next;
}
void MoveNext()
{
++it;
}
Entity* Current() const
{
return it != TComponent::_entities.end() ? it->second : nullptr;
}
};
template <typename TComponent, typename ...TComponents>
struct Enumerator<TComponent, TComponents...>
{
std::map<uint, Entity*>::iterator it;
Enumerator<TComponents...> rest;
Enumerator()
{
it = TComponent::_entities.begin();
}
bool AllMoveTo(Entity& entity)
{
if (!rest.AllMoveTo(entity))
return false;
while (HasNext() && Current()->_id < entity._id)
{
MoveNext();
}
if (!Current())
return false;
return Current()->_id == entity._id;
}
bool HasNext() const
{
auto it_next = it;
++it_next;
bool has_next = it_next != TComponent::_entities.end();
return has_next;
}
void MoveNext()
{
++it;
}
Entity* Current() const
{
return it != TComponent::_entities.end() ? it->second : nullptr;
}
};
template <typename ...TComponents>
struct Requires
{
};
template <typename TComponent>
struct Requires<TComponent>
{
static void run_on_matching_entries(const std::function<void(Entity&)>& fun)
{
for (Enumerator<TComponent> enumerator; enumerator.Current(); enumerator.MoveNext())
{
if (!enumerator.AllMoveTo(*enumerator.Current()))
continue;
fun(*enumerator.Current());
}
}
};
template <typename TComponent, typename ...TComponents>
struct Requires<TComponent, TComponents...>
{
static void run_on_matching_entries(const std::function<void(Entity&)>& fun)
{
for (Enumerator<TComponent, TComponents...> enumerator; enumerator.Current(); enumerator.MoveNext())
{
if (!enumerator.AllMoveTo(*enumerator.Current()))
continue;
fun(*enumerator.Current());
}
}
};
using Sig0 = Requires<Comp0>;
using Sig1 = Requires<Comp1, Comp3>;
using Sig2 = Requires<Comp1, Comp2, Comp3>;
struct Manager
{
uint _next_entity_id;
Manager()
{
_next_entity_id = 0;
}
Entity createEntity()
{
uint id = _next_entity_id++;
return Entity("entity " + std::to_string(id), id);
};
template <typename Component>
void add(Entity& e)
{
e._components[Component::_id] = std::make_shared<Component>();
Component::_entities.emplace(e._id, &e);
}
template <typename Component>
void remove(Entity& e)
{
e._components.erase(Component::_id);
Component::_entities.erase(e._id);
}
template <typename Signature>
void for_entities_with_signature(const std::function<void(Entity&)>& fun)
{
Signature::run_on_matching_entries(fun);
}
};
int main()
{
Manager m;
uint item_count = 100000;
std::vector<Entity> entities;
for (size_t item = 0; item < item_count; ++item)
{
entities.push_back(m.createEntity());
}
for (size_t item = 0; item < item_count; ++item)
{
//if (rand() % 2 == 0)
m.add<Comp0>(entities[item]);
//if (rand() % 2 == 0)
m.add<Comp1>(entities[item]);
//if (rand() % 2 == 0)
m.add<Comp2>(entities[item]);
//if (rand() % 2 == 0)
m.add<Comp3>(entities[item]);
}
size_t sig0_count = 0;
size_t sig1_count = 0;
size_t sig2_count = 0;
auto start = std::chrono::system_clock::now();
m.for_entities_with_signature<Sig0>([&](Entity& e) { ++sig0_count; });
m.for_entities_with_signature<Sig1>([&](Entity& e) { ++sig1_count; });
m.for_entities_with_signature<Sig2>([&](Entity& e) { ++sig2_count; });
auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now() - start);
std::cout << "first run took " << duration.count() << " milliseconds: " << sig0_count << " " << sig1_count << " " << sig2_count << std::endl;
for (size_t item = 0; item < item_count; ++item)
{
if (rand() % 2 == 0)
m.remove<Comp0>(entities[item]);
if (rand() % 2 == 0)
m.remove<Comp1>(entities[item]);
if (rand() % 2 == 0)
m.remove<Comp2>(entities[item]);
if (rand() % 2 == 0)
m.remove<Comp3>(entities[item]);
}
sig0_count = sig1_count = sig2_count = 0;
start = std::chrono::system_clock::now();
m.for_entities_with_signature<Sig0>([&](Entity& e) { ++sig0_count; });
m.for_entities_with_signature<Sig1>([&](Entity& e) { ++sig1_count; });
m.for_entities_with_signature<Sig2>([&](Entity& e) { ++sig2_count; });
duration = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now() - start);
std::cout << "second run took " << duration.count() << " milliseconds: " << sig0_count << " " << sig1_count << " " << sig2_count << std::endl;
}
每个签名类型 sparse integer set 是理论上 最佳解决方案（就时间复杂度而言）。
稀疏整数集数据结构允许对存储的整数、O(1)insertion/removal整数和O(1) 查询特定整数。
per-signature稀疏整数集将存储与该特定签名关联的所有实体 ID。
示例：Diana，一个 open-source C 和 C++ ECS 库，利用 稀疏整数集 来跟踪系统中的实体。每个系统都有自己的稀疏整数集实例。
对于匹配，您是否一次一位地检查每个组件类型？您应该能够通过检查签名的所有组件是否在针对位掩码的一条指令中可用来遍历实体。
例如，我们可以使用：
const uint64_t signature = 0xD; // 0b1101
...检查组件 0、1 和 3 是否存在。
for(const auto& ent: entities)
{
if (ent.components & signature)
// the entity has components 0, 1, and 3.
}
如果您的实体连续存储在数组中，那应该会非常快。就性能而言，一次检查 3 种组件类型还是 50 种组件类型并不重要。我不会为我的 ECS 使用这种类型的代表，但绝对不会花很长时间，即使你有一百万个实体。这应该在眨眼之间完成。
查看哪些实体提供一组给定的组件同时存储最少的状态，这几乎是最快的实用方法——我不使用此代表的唯一原因是因为我的 ECS 围绕插件架构人们在运行时通过插件和脚本注册新的组件类型和系统，所以我无法有效地预测会有多少组件类型的上限。如果我有一个像您这样的编译时系统，旨在提前预测所有这些东西，那么我绝对认为这是可行的方法。只是不要一次检查一位。
使用上述解决方案，您应该能够轻松每秒处理数百次一百万个组件。有些人应用 CPU 图像过滤器处理每秒多次乘以许多像素的处理速度，并且这些过滤器比单个 bitwise and 和每次迭代的单个分支有更多的工作要做。
我什至不会费心缓存这个超级便宜的顺序循环，除非你有一些系统只想处理，比如说，一百万个实体中的十几个。但是到那时，您可能会缓存那些罕见的情况，在这些情况下，一个系统几乎不处理系统本地的任何实体，而不是尝试集中缓存。只需确保感兴趣的系统可以发现实体何时添加到系统或从系统中删除，以便它们可以使本地缓存无效。
此外，您不一定需要为这些签名进行花哨的元编程。归根结底，您并没有真正使用模板元编程来保存任何东西，因为它无法避免循环遍历实体以检查某些内容，因为实体列表仅在运行时已知。理论上没有什么值得在编译时优化掉的东西。你可以这样做：
static const uint64_t motion_id = 1 << 0;
static const uint64_t sprite_id = 1 << 1;
static const uint64_t sound_id = 1 << 2;
static const uint64_t particle_id = 1 << 3;
...
// Signature to check for entities with motion, sprite, and
// particle components.
static const uint64_t sig = motion_id | sprite_id | particle_id;
如果您使用实体相关位来指示实体具有哪些组件，我建议为您的系统可以处理的组件类型总数设置一个上限（例如：64 可能很多，128 是一大堆）这样您就可以一次性检查这些组件是否符合位掩码。
[...] what if a call to forEntitiesMatching actually removes or adds a
component to an entity?
如果，比方说，你有一个每帧都有 adding/removing 个组件的系统，那么我一开始就懒得去缓存了。上面的版本应该能够超快地循环实体。
按顺序遍历所有实体的最坏情况是，如果您有一个系统，比方说，它只会处理这些实体中的 3%。如果你的引擎设计有这样的系统，那就有点尴尬了，但你可能只是在组件 added/removed 时通知他们他们特别感兴趣的时候他们可以使他们的实体缓存无效然后下次重新缓存系统开始运行。希望您没有系统 adding/removing 组件，每一帧的类型都是 3% 的少数组件。但是，如果您确实遇到了最坏的情况，最好根本不要理会缓存。缓存是没有用的，它只会在每一帧都被丢弃，并且试图以一种奇特的方式更新它可能不会给你带来太多好处。
例如，处理 50% 或更多实体的其他系统可能甚至不应该去缓存，因为间接级别可能不值得仅仅按顺序遍历所有实体并做一个非常便宜的事情bitwise and 超过每一个。
我正在开发面向数据的实体组件系统，其中组件类型和系统签名在编译时已知。
实体是组件的集合。组件可以 added/removed 来自 运行 时间的实体。
一个组件是一个小型的无逻辑class.
A signature 是组件类型的编译时列表。如果实体包含签名所需的所有组件类型，则称该实体与签名匹配。
一个简短的代码示例将向您展示用户语法的外观和预期用途：
// User-defined component types.
struct Comp0 : ecs::Component { /*...*/ };
struct Comp1 : ecs::Component { /*...*/ };
struct Comp2 : ecs::Component { /*...*/ };
struct Comp3 : ecs::Component { /*...*/ };
// User-defined system signatures.
using Sig0 = ecs::Requires<Comp0>;
using Sig1 = ecs::Requires<Comp1, Comp3>;
using Sig2 = ecs::Requires<Comp1, Comp2, Comp3>;
// Store all components in a compile-time type list.
using MyComps = ecs::ComponentList
<
Comp0, Comp1, Comp2, Comp3
>;
// Store all signatures in a compile-time type list.
using MySigs = ecs::SignatureList
<
Sig0, Sig1, Sig2
>;
// Final type of the entity manager.
using MyManager = ecs::Manager<MyComps, MySigs>;
void example()
{
MyManager m;
// Create an entity and add components to it at runtime.
auto e0 = m.createEntity();
m.add<Comp0>(e0);
m.add<Comp1>(e0);
m.add<Comp3>(e0);
// Matches.
assert(m.matches<Sig0>(e0));
// Matches.
assert(m.matches<Sig1>(e0));
// Doesn't match. (`Comp2` missing)
assert(!m.matches<Sig2>(e0));
// Do something with all entities matching `Sig0`.
m.forEntitiesMatching<Sig0>([](/*...*/){/*...*/});
}
我目前正在使用 std::bitset 操作检查实体是否匹配签名。然而，一旦签名数量和实体数量增加，性能就会迅速下降。
伪代码：
// m.forEntitiesMatching<Sig0>
// ...gets transformed into...
for(auto& e : entities)
if((e.bitset & getBitset<Sig0>()) == getBitset<Sig0>())
callUserFunction(e);
这可行，但如果用户多次使用相同的签名调用 forEntitiesMatching，则必须再次匹配所有实体。
在缓存友好的容器中预缓存实体可能还有更好的方法。
我试过使用某种缓存来创建 编译时映射（实现为 std::tuple<std::vector<EntityIndex>, std::vector<EntityIndex>, ...>），其中键是签名类型（每个由于 SignatureList)，签名类型具有唯一的增量索引），并且值是实体索引的向量。
我用类似的东西填充了缓存元组：
// Compile-time list iterations a-la `boost::hana`.
forEveryType<SignatureList>([](auto t)
{
using Type = decltype(t)::Type;
for(auto entityIndex : entities)
if(matchesSignature<Type>(e))
std::get<idx<Type>()>(cache).emplace_back(e);
});
并在每个管理器更新周期后清除它。
不幸的是，在我的所有测试中，它的执行速度比上面显示的 "raw" 循环慢。它还会有一个 更大的问题 ：如果对 forEntitiesMatching 的调用实际上删除了一个组件或向实体添加了一个组件怎么办？必须使缓存失效并为后续 forEntitiesMatching 调用重新计算。
有没有更快的方法将实体与签名匹配？
编译时知道很多东西（组件类型列表，签名类型列表，...） - 是否有任何辅助可以在编译时生成的数据结构，这将有助于 "bitset-like" 匹配？
关于伪代码：
for(auto& e : entities)
for(const auto& s : signatures)
if((e.bitset & s.bitset) == s.bitset)
callUserFunction(e);
我不确定你为什么需要内循环。
如果您在函数中有请求的签名，那么您可以获得该签名的位集，而无需遍历所有签名。
template <typename T>
void forEntitiesMatching(const std::function<void(Entity& e)>& fun)
{
for(auto& e : entities)
if((e.bitset & T::get_bitset()) == T::get_bitset())
fun(e);
}
您是否考虑过以下解决方案？ 每个签名都会有一个与该签名匹配的实体容器。
添加或删除组件时需要更新相关的签名容器。
现在函数可以简单地转到签名实体容器并为每个实体执行函数。
根据add/remove组件与签名匹配的比例，您可以尝试构建一种前缀树存储对实体的引用。
树本身是静态的，只有包含实体的叶子才是运行时构建的容器。
这样在添加（或删除）组件时，只需将实体的引用移动到正确的叶子即可。
在搜索与签名匹配的实体时，您只需获取包含签名的所有叶子的并集并迭代它们。由于树（几乎）是静态的，您甚至不需要搜索这些叶子。
另一个好点：您可以使用 bitset 表示树中的路径，因此移动实体非常容易。
如果组件的数量导致了不切实际的叶子数量，并且没有使用所有组件的组合，您可以用哈希表替换树，其中位集是键，值是实体引用集。
这比具体的东西更多的是算法思想，但它似乎比遍历实体集更合理。
受@Marwan Burelle 想法影响的另一个选项。
每个组件将包含一个已排序的容器，其中包含具有该组件的实体。
在查找与签名匹配的实体时，您需要遍历实体的组件容器。
添加或删除是 O(nlogn)，因为它需要排序。但您只需要 add/remove 它 to/from 一个包含更少物品的容器。
迭代项目有点重，因为它是组件数量和每个组件中实体数量的一个因素。 你还有一个乘法元素，但是元素的数量又变小了。
我写了一个简化版作为POC。
编辑：我以前的版本有一些错误，现在希望它们已修复。
// Example program
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <vector>
#include <functional>
#include <memory>
#include <chrono>
struct ComponentBase
{
};
struct Entity
{
Entity(std::string&& name, uint id)
: _id(id),
_name(name)
{
}
uint _id;
std::string _name;
std::map<uint, std::shared_ptr<ComponentBase>> _components;
};
template <uint ID>
struct Component : public ComponentBase
{
static const uint _id;
static std::map<uint, Entity*> _entities;
};
template <uint ID>
std::map<uint, Entity*> Component<ID>::_entities;
template <uint ID>
const uint Component<ID>::_id = ID;
using Comp0 = Component<0>;
using Comp1 = Component<1>;
using Comp2 = Component<2>;
using Comp3 = Component<3>;
template <typename ...TComponents>
struct Enumerator
{
};
template <typename TComponent>
struct Enumerator<TComponent>
{
std::map<uint, Entity*>::iterator it;
Enumerator()
{
it = TComponent::_entities.begin();
}
bool AllMoveTo(Entity& entity)
{
while (HasNext() && Current()->_id < entity._id)
{
MoveNext();
}
if (!Current())
return false;
return Current()->_id == entity._id;
}
bool HasNext() const
{
auto it_next = it;
++it_next;
bool has_next = it_next != TComponent::_entities.end();
return has_next;
}
void MoveNext()
{
++it;
}
Entity* Current() const
{
return it != TComponent::_entities.end() ? it->second : nullptr;
}
};
template <typename TComponent, typename ...TComponents>
struct Enumerator<TComponent, TComponents...>
{
std::map<uint, Entity*>::iterator it;
Enumerator<TComponents...> rest;
Enumerator()
{
it = TComponent::_entities.begin();
}
bool AllMoveTo(Entity& entity)
{
if (!rest.AllMoveTo(entity))
return false;
while (HasNext() && Current()->_id < entity._id)
{
MoveNext();
}
if (!Current())
return false;
return Current()->_id == entity._id;
}
bool HasNext() const
{
auto it_next = it;
++it_next;
bool has_next = it_next != TComponent::_entities.end();
return has_next;
}
void MoveNext()
{
++it;
}
Entity* Current() const
{
return it != TComponent::_entities.end() ? it->second : nullptr;
}
};
template <typename ...TComponents>
struct Requires
{
};
template <typename TComponent>
struct Requires<TComponent>
{
static void run_on_matching_entries(const std::function<void(Entity&)>& fun)
{
for (Enumerator<TComponent> enumerator; enumerator.Current(); enumerator.MoveNext())
{
if (!enumerator.AllMoveTo(*enumerator.Current()))
continue;
fun(*enumerator.Current());
}
}
};
template <typename TComponent, typename ...TComponents>
struct Requires<TComponent, TComponents...>
{
static void run_on_matching_entries(const std::function<void(Entity&)>& fun)
{
for (Enumerator<TComponent, TComponents...> enumerator; enumerator.Current(); enumerator.MoveNext())
{
if (!enumerator.AllMoveTo(*enumerator.Current()))
continue;
fun(*enumerator.Current());
}
}
};
using Sig0 = Requires<Comp0>;
using Sig1 = Requires<Comp1, Comp3>;
using Sig2 = Requires<Comp1, Comp2, Comp3>;
struct Manager
{
uint _next_entity_id;
Manager()
{
_next_entity_id = 0;
}
Entity createEntity()
{
uint id = _next_entity_id++;
return Entity("entity " + std::to_string(id), id);
};
template <typename Component>
void add(Entity& e)
{
e._components[Component::_id] = std::make_shared<Component>();
Component::_entities.emplace(e._id, &e);
}
template <typename Component>
void remove(Entity& e)
{
e._components.erase(Component::_id);
Component::_entities.erase(e._id);
}
template <typename Signature>
void for_entities_with_signature(const std::function<void(Entity&)>& fun)
{
Signature::run_on_matching_entries(fun);
}
};
int main()
{
Manager m;
uint item_count = 100000;
std::vector<Entity> entities;
for (size_t item = 0; item < item_count; ++item)
{
entities.push_back(m.createEntity());
}
for (size_t item = 0; item < item_count; ++item)
{
//if (rand() % 2 == 0)
m.add<Comp0>(entities[item]);
//if (rand() % 2 == 0)
m.add<Comp1>(entities[item]);
//if (rand() % 2 == 0)
m.add<Comp2>(entities[item]);
//if (rand() % 2 == 0)
m.add<Comp3>(entities[item]);
}
size_t sig0_count = 0;
size_t sig1_count = 0;
size_t sig2_count = 0;
auto start = std::chrono::system_clock::now();
m.for_entities_with_signature<Sig0>([&](Entity& e) { ++sig0_count; });
m.for_entities_with_signature<Sig1>([&](Entity& e) { ++sig1_count; });
m.for_entities_with_signature<Sig2>([&](Entity& e) { ++sig2_count; });
auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now() - start);
std::cout << "first run took " << duration.count() << " milliseconds: " << sig0_count << " " << sig1_count << " " << sig2_count << std::endl;
for (size_t item = 0; item < item_count; ++item)
{
if (rand() % 2 == 0)
m.remove<Comp0>(entities[item]);
if (rand() % 2 == 0)
m.remove<Comp1>(entities[item]);
if (rand() % 2 == 0)
m.remove<Comp2>(entities[item]);
if (rand() % 2 == 0)
m.remove<Comp3>(entities[item]);
}
sig0_count = sig1_count = sig2_count = 0;
start = std::chrono::system_clock::now();
m.for_entities_with_signature<Sig0>([&](Entity& e) { ++sig0_count; });
m.for_entities_with_signature<Sig1>([&](Entity& e) { ++sig1_count; });
m.for_entities_with_signature<Sig2>([&](Entity& e) { ++sig2_count; });
duration = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now() - start);
std::cout << "second run took " << duration.count() << " milliseconds: " << sig0_count << " " << sig1_count << " " << sig2_count << std::endl;
}
每个签名类型 sparse integer set 是理论上 最佳解决方案（就时间复杂度而言）。
稀疏整数集数据结构允许对存储的整数、O(1)insertion/removal整数和O(1) 查询特定整数。
per-signature稀疏整数集将存储与该特定签名关联的所有实体 ID。
示例：Diana，一个 open-source C 和 C++ ECS 库，利用 稀疏整数集 来跟踪系统中的实体。每个系统都有自己的稀疏整数集实例。
对于匹配，您是否一次一位地检查每个组件类型？您应该能够通过检查签名的所有组件是否在针对位掩码的一条指令中可用来遍历实体。
例如，我们可以使用：
const uint64_t signature = 0xD; // 0b1101
...检查组件 0、1 和 3 是否存在。
for(const auto& ent: entities)
{
if (ent.components & signature)
// the entity has components 0, 1, and 3.
}
如果您的实体连续存储在数组中，那应该会非常快。就性能而言，一次检查 3 种组件类型还是 50 种组件类型并不重要。我不会为我的 ECS 使用这种类型的代表，但绝对不会花很长时间，即使你有一百万个实体。这应该在眨眼之间完成。
查看哪些实体提供一组给定的组件同时存储最少的状态，这几乎是最快的实用方法——我不使用此代表的唯一原因是因为我的 ECS 围绕插件架构人们在运行时通过插件和脚本注册新的组件类型和系统，所以我无法有效地预测会有多少组件类型的上限。如果我有一个像您这样的编译时系统，旨在提前预测所有这些东西，那么我绝对认为这是可行的方法。只是不要一次检查一位。
使用上述解决方案，您应该能够轻松每秒处理数百次一百万个组件。有些人应用 CPU 图像过滤器处理每秒多次乘以许多像素的处理速度，并且这些过滤器比单个 bitwise and 和每次迭代的单个分支有更多的工作要做。
我什至不会费心缓存这个超级便宜的顺序循环，除非你有一些系统只想处理，比如说，一百万个实体中的十几个。但是到那时，您可能会缓存那些罕见的情况，在这些情况下，一个系统几乎不处理系统本地的任何实体，而不是尝试集中缓存。只需确保感兴趣的系统可以发现实体何时添加到系统或从系统中删除，以便它们可以使本地缓存无效。
此外，您不一定需要为这些签名进行花哨的元编程。归根结底，您并没有真正使用模板元编程来保存任何东西，因为它无法避免循环遍历实体以检查某些内容，因为实体列表仅在运行时已知。理论上没有什么值得在编译时优化掉的东西。你可以这样做：
static const uint64_t motion_id = 1 << 0;
static const uint64_t sprite_id = 1 << 1;
static const uint64_t sound_id = 1 << 2;
static const uint64_t particle_id = 1 << 3;
...
// Signature to check for entities with motion, sprite, and
// particle components.
static const uint64_t sig = motion_id | sprite_id | particle_id;
如果您使用实体相关位来指示实体具有哪些组件，我建议为您的系统可以处理的组件类型总数设置一个上限（例如：64 可能很多，128 是一大堆）这样您就可以一次性检查这些组件是否符合位掩码。
[...] what if a call to forEntitiesMatching actually removes or adds a component to an entity?
如果，比方说，你有一个每帧都有 adding/removing 个组件的系统，那么我一开始就懒得去缓存了。上面的版本应该能够超快地循环实体。
按顺序遍历所有实体的最坏情况是，如果您有一个系统，比方说，它只会处理这些实体中的 3%。如果你的引擎设计有这样的系统，那就有点尴尬了，但你可能只是在组件 added/removed 时通知他们他们特别感兴趣的时候他们可以使他们的实体缓存无效然后下次重新缓存系统开始运行。希望您没有系统 adding/removing 组件，每一帧的类型都是 3% 的少数组件。但是，如果您确实遇到了最坏的情况，最好根本不要理会缓存。缓存是没有用的，它只会在每一帧都被丢弃，并且试图以一种奇特的方式更新它可能不会给你带来太多好处。
例如，处理 50% 或更多实体的其他系统可能甚至不应该去缓存，因为间接级别可能不值得仅仅按顺序遍历所有实体并做一个非常便宜的事情bitwise and 超过每一个。