将实体与实体组件系统中的系统进行匹配的有效方法
我正在开发一个面向数据的实体组件系统，其中组件类型和系统签名在编译时是已知的。
实体是组件的集合。组件可以在运行时从实体中添加/删除。
组件是一个小型的无逻辑类。
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);
});并在每个管理器更新周期后将其清除。
不幸的是，在我的所有测试中，它的执行速度都比上面所示的“原始”循环慢。它还会有一个更大的问题：如果对forEntitiesMatching的调用实际上删除或添加了一个组件到一个实体，该怎么办？对于后续的forEntitiesMatching调用，必须使缓存无效并重新计算缓存。
有没有更快的方法来匹配实体和签名？
很多事情在编译时是已知的(组件类型列表，签名类型列表，...) -有没有什么可以在编译时生成的辅助数据结构，可以帮助进行“类似于位集”的匹配？
回答 5
Stack Overflow用户
发布于 2016-01-07 08:48:29
在理论上，每个签名类型都有一个sparse integer set是的最佳解决方案(就时间复杂度而言)。
稀疏整数集数据结构允许对存储的整数进行高效的连续O(N)迭代、整数的O(1)插入/删除以及特定整数的O(1)查询。
每签名稀疏整数集将存储与该特定签名相关联的所有实体ID。
示例：Diana是一个开源的C和C++ ECS库，它使用稀疏整数集来跟踪系统中的实体。每个系统都有自己的稀疏整数集实例。
Stack Overflow用户
发布于 2015-08-18 04:41:23
您是否考虑过以下解决方案？每个签名都有一个包含与该签名匹配的实体的容器。
添加或移除组件时，需要更新相应的签名容器。
现在，该函数可以简单地转到签名实体容器并为每个实体执行该函数。
Stack Overflow用户
发布于 2015-09-05 00:14:20
根据组件的添加/删除与签名匹配的比率，您可以尝试构建一种前缀树来存储对实体的引用。
树本身是静态的，只有包含实体的叶子是运行时构建的容器。
这样，在添加(或删除)组件时，您只需将实体的引用移动到正确的叶。
在搜索与签名匹配的实体时，您只需获取包含签名的叶的所有并集并迭代它们。由于这棵树(几乎)是静态的，您甚至不需要搜索这些叶子。
另一个好的地方是:你的位集可以用来表示树中的路径，所以移动实体非常容易。
如果组件的数量导致一个不切实际的数字离开，并且并不是所有的组件组合都被使用，您可以用一个哈希表替换该树，其中位集是键，值是实体引用集。
这更多的是算法上的想法，而不是具体的东西，但它似乎比迭代实体集更合理。
https://stackoverflow.com/questions/32035462
复制相似问题