将实体与实体组件系统中的系统进行匹配的有效方法 [英] Efficient way of matching entities to systems in an entity component system
问题描述
我正在研究面向数据的实体组件系统，该组件系统在编译时就知道组件类型和系统签名.
I'm working on a data-oriented entity component system where component types and system signatures are known at compile-time.
实体是组件的集合.可以在运行时从实体中添加/删除组件.
An entity is an aggregate of components. Components can be added/removed from entities at run-time.
组件是一个小的无逻辑类.
A component is a small logic-less class.
签名是组件类型的编译时列表.如果实体包含签名所需的所有组件类型，则称该实体与签名匹配.
A signature is a compile-time list of component types. An entity is said to match a signature if it contains all component types required by the signature.
一个简短的代码示例将向您展示用户语法的外观以及预期的用法:
A short code sample will show you how the user syntax looks and what the intended usage is:
// 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操作检查实体是否与签名匹配.但是，一旦签名数量和实体数量增加，性能就会迅速下降.
I'm currently checking if entities match signatures using std::bitset operations. The performance, however, quickly degrades as soon as the number of signatures and the number of entities increase.
伪代码:
// m.forEntitiesMatching<Sig0>
// ...gets transformed into...
for(auto& e : entities)
if((e.bitset & getBitset<Sig0>()) == getBitset<Sig0>())
callUserFunction(e);
这有效，但是如果用户多次调用具有相同签名的forEntitiesMatching，则所有实体都必须再次匹配.
This works, but if the user calls forEntitiesMatching with the same signature multiple times, all entities will have to be matched again.
在对缓存友好的容器中预缓存实体可能还有更好的方法.
There may also be a better way of pre-caching entities in cache-friendly containers.
我尝试使用某种高速缓存来创建编译时映射(实现为std::tuple<std::vector<EntityIndex>, std::vector<EntityIndex>, ...>)，其中的键是签名类型(每个签名类型都有唯一的增量索引)感谢SignatureList)，并且这些值是实体索引的向量.
I've tried using some sort of cache that creates a compile-time map (implemented as std::tuple<std::vector<EntityIndex>, std::vector<EntityIndex>, ...>), where the keys are the signature types (every signature type has a unique incremental index thanks to SignatureList), and the values are vectors of entity indices.
我用以下内容填充缓存元组:
I filled the cache tuple with something like:
// 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);
});
并在每个管理员更新周期后将其清除.
And cleared it after every manager update cycle.
不幸的是，它的执行速度比我在所有测试中显示的原始"循环要慢.它还会出现一个更大的问题:如果对forEntitiesMatching的调用实际上是将某个组件删除或添加到实体，该怎么办?对于随后的forEntitiesMatching调用，必须使缓存无效并重新计算.
Unfortunately it performed more slowly than then "raw" loop shown above in all of my tests. It also would have a bigger issue: what if a call to forEntitiesMatching actually removes or adds a component to an entity? The cache would have to be invalidated and recalculated for subsequent forEntitiesMatching calls.
是否有将实体与签名匹配的更快方法?
在编译时有很多已知的信息(组件类型列表，签名类型列表等)-是否有任何辅助数据结构可以在编译时生成编译时对类位匹配"有帮助吗?
A lot of things are known at compile-time (list of component types, list of signature types, ...) - is there any auxiliary data structure that could be generated at compile-time which would help with "bitset-like" matching?
推荐答案
具有稀疏每个签名类型的整数集是理论上的最佳解决方案(就时间复杂度而言).
Having a sparse integer set per signature type is the theoretically best solution (in terms of time complexity).
稀疏整数集数据结构允许对存储的整数进行有效的连续O(N)迭代，O(1)整数的插入/删除以及O(1)查询特定整数.
The sparse integer set data structure allows efficient contiguous O(N) iteration over the stored integers, O(1) insertion/removal of integers, and O(1) querying for a specific integer.
每个签名的稀疏整数集将存储与该特定签名关联的所有实体ID.
The per-signature sparse integer set would store all entity IDs associated with that specific signature.
示例: Diana ，一个开源C和C ++ ECS库，使用了稀疏整数集来跟踪系统中的实体.每个系统都有其自己的稀疏整数集实例.
Example: Diana, an open-source C and C++ ECS library, makes use of sparse integer set to keep track of entities in systems. Every system has its own sparse integer set instance.
这篇关于将实体与实体组件系统中的系统进行匹配的有效方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
