decs - 一个简洁的C++ ECS实现方案
decs - 一个简洁的C++ ECS实现方案
Author: fangshen
1. 简介
decs是目前Github上开源的一个ECS实现(DECS源码地址), 对比复杂度较高的entt, 以及稍微简单一点的entityx, decs的实现非常简洁, 没有过多的像Event等的高阶功能, 也没有Sparsed Table的处理, 但ECS的基础部分实现得比较扎实, 所以用来熟悉ECS机制本身, 或者用来做进一步的定制, 这种复杂度是刚刚好的, 本文也主要对DECS的实现进行解析.
2. Archetype based ECS内存布局
decs是跟U3D的Archetype based ECS实现思路基本一致的一版ECS实现, 它的主要特点是将包含的Compnent数量和类型相同的Entity当成一类Archetype, 并将它们在Chunk中存储在一起.
首先是Archetype本身的元数据的组织:
以一个包含A,B,C 三个Component的Entity为例说明, 通过相关的编译期模板推导, 我们可以很方便的拿到每个Component类型的Meta信息, Meta信息主要是图上的这些, 然后有这些信息后可以进一步的组织Chunk内的数据结构, Chunk在内存中的视图如下:
通过上图我们也容易看出, 对比面向对象的AData[0], B Data[0], C Data[0], AData[1], BData[1], CData[1]顺序存储的方式(Array of structure), 一个Archetype的内存组织有效模拟了DOD(Data Oriented Design)中的SoA数据结构(Structure of array), 这种方式对目前的底层硬件架构更友好, 性能更高. 在Archetype based这种数据存储模式下, 不管我们是对 ComponentA 做遍历, 或者同时遍历处理ComponentA, B, C, 发生cache miss的情况都比面向对象的写法大大降低, SoA的数据组织方式能够有效提高cache命中, 从而提升程序的实际运行效率. 服务器其实更多情况还是某一System对单个Component做遍历处理, 始终是一个比较优的情况. DOD相关的内容比较多, 本文侧重分析decs本身的实现, 所以DOD相关的背景知识就不详细展开了, 有需要的可以自行阅读相关的设计院资料.
下面我们结合实际代码来看一下decs的具体实现.
3. 基础功能部分
3.1 hash函数: hash_64_fnv1a
主要用于将类型T(此处都是Component)转换为64位无符号整数. 主要代码:
struct MetatypeHash {
size_t name_hash{ 0 };
size_t matcher_hash{ 0 };
bool operator==(const MetatypeHash& other)const {
return name_hash == other.name_hash;
}
template<typename T>
static constexpr const char* name_detail() {
#if RSTUDIO_CORE_PLATFORM == RSTUDIO_CORE_PLATFORM_LINUX
return __PRETTY_FUNCTION__;
#else
return __FUNCSIG__;
#endif
}
template<typename T>
static constexpr size_t hash() {
static_assert(!std::is_reference_v<T>, "dont send references to hash");
static_assert(!std::is_const_v<T>, "dont send const to hash");
return hash_fnv1a(name_detail<T>());
}
};注意hash()用到的辅助函数, 编译期函数 name_detail()利用 PRETTY_FUNCTION 宏生成标识类型T的唯一字符串, 再将此字符串hash, 得到全局唯一(忽略Hash碰撞)的64位ID.
4. Metatype部分
4.1 Metatype类
namespace ecs
{
struct Metatype {
using ConstructorFn = void(void*);
using DestructorFn = void(void*);
MetatypeHash hash;
const char* name{ "none" };
ConstructorFn* constructor;
DestructorFn* destructor;
uint16_t size{ 0 };
uint16_t align{ 0 };
bool is_empty() const { return align == 0; };
template<typename T>
static constexpr MetatypeHash build_hash();
template<typename T>
static constexpr Metatype build();
};
//has stable pointers, use name_hash for it
static robin_hood::unordered_node_map<uint64_t, Metatype> metatype_cache;
}Metatype类完成对Component的反射支持, 很薄的一层实现了, 需要注意的是EntityId本身也是当成一个Component来处理的, 这样World上提供的for_each也可以很好的覆盖EntityId类型.
Metatype对象主要提供以下特性:
4.1.1 ConstructorFn* constructor;
构造函数支持(无参数, 所以后续可以直接对接Ponder的相关特性, 提供更好的支持)
4.1.2 DestructorFn* destructor;
析构函数支持(同上, 可以用Ponder功能整体替换).
4.1.3 MetatypeHash hash;
利用基础部分提供的对类型T的hash函数完成Component的hash值生成, 注意decs使用的是constexpr的处理方式, 对类型T的hash生成都是编译期来完成的, 无运行时开销.
4.1.4 size 和 align
记录Component的align值和size.
4.1.5 static robin_hood::unordered_node_map metatype_cache;
记录所有Metatype的静态变量, 一般我们需要获取某Component类型的Metatype的时候, 先利用MetatypeHash的编译期hash()函数获取到64位的key值后, 再通过robin_hood的hash map来取得对应的Metatype.
PS: 一开始理解错robin_hood hash map的使用场合了, 看描述我以为是Component的实际数据由它存储, 还想了一下线性存储的hash map内存不够的时候Component的重新创建desc内部是怎么处理的, 后面发现想多了, robin hood的hash map实现仅用于存储Metatype, 实际上对Metatype的访问并不是一个高频操作(正常一次foreach对相关Component访问一次就足够了), 所以此处其实此处选择比较多, 不一定需要使用robin hood的hash map实现.
5. Archetype部分
5.1 Archetype内存布局
decs没有使用额外的内存分配器, 而是自己实现的, 这也跟ECS本身一般使用SoA数据布局方式, 同类型Component存储在连续的内存上, 这样对于特定类型的Component来说, 内存分配的实现和策略都是比较简单的, 下面我们来看下decs的实现:
namespace ecs
{
struct DataChunkHeader {
//pointer to the signature for this block
struct ChunkComponentList* componentList;
struct Archetype* ownerArchetype{ nullptr };
struct DataChunk* prev{ nullptr };
struct DataChunk* next{ nullptr };
//max index that has an entity
int16_t last{ 0 };
};
struct alignas(64) DataChunk {
byte storage[BLOCK_MEMORY_16K - sizeof(DataChunkHeader)];
DataChunkHeader header;
};
static_assert(sizeof(DataChunk) == BLOCK_MEMORY_16K, "chunk size isnt 16kb");
}DataChunk类的storage成员直接负责数据的存储, 通过额外的header形成一个DataChunk的链表, 这样当单个Chunk到达上限的时候, 可以新分配一个新的DataChunk来完成对后续更多物体的处理(理论上单个DataChunk上存储的量级和总的DataChunk数不在一个数量级, 多个DataChunk的存在对性能拖慢的影响极其有限).
5.2 Archetype对象
namespace ecs
{
struct ChunkComponentList {
struct CmpPair {
const Metatype* type;
MetatypeHash hash;
uint32_t chunkOffset;
};
int16_t chunkCapacity;
std::vector<CmpPair> components;
};
struct Archetype {
ChunkComponentList* componentList;
struct ECSWorld* ownerWorld;
size_t componentHash;
int full_chunks;
//full chunks allways on the start of the array
std::vector<DataChunk*> chunks;
};
}ChunkComponentList 负责对Archetype中存储的Component的信息进行描述, 主要是一个chunk中能容纳的对应Archtype类型的Entity的总数, 每个Component的metatype指针, hash, offset这些信息, 这样我们结合这些信息, 就可以很好的完成对某个DataChunk块中存储的数据按Component方式进行访问了. decs内部对Component的访问是通过一个额外的辅助设施ComonentArray来完成的(编译期设施), ComponentArray的实现如下:
template<typename T>
struct ComponentArray {
ComponentArray() = default;
ComponentArray(void* pointer, DataChunk* owner) {
data = (T*)pointer;
chunkOwner = owner;
}
const T& operator[](size_t index) const {
return data[index];
}
T& operator[](size_t index) {
return data[index];
}
bool valid()const {
return data != nullptr;
}
T* begin() {
return data;
}
T* end() {
return data + chunkOwner->header.last;
}
int16_t size() {
return chunkOwner->header.last;
}
T* data{ nullptr };
DataChunk* chunkOwner{ nullptr };
};其实就是通过pointer带入component的offset, 我们之前也给出了Chunk的布局图, 多种Component会存储在一个Chunk内, 相同的Component连续存储, 所以已知Chunk和对应Component类型的情况下, 我们可以很方便的对其进行访问.
另外与Archetype相关的最重要的函数是find_or_create_archetype(), 在已知一组Component Metatype的情况下, 我们需要获取或创建正确的Archetype并返回:
inline Archetype* find_or_create_archetype(World* world, const Metatype** types, size_t count) {
const Metatype* temporalMetatypeArray[32];
assert(count < 32);
const Metatype** typelist;
if (false) {//!is_sorted(types, count)) {
for (int i = 0; i < count; i++) {
temporalMetatypeArray[i] = types[i];
}
sort_metatypes(temporalMetatypeArray, count);
typelist = temporalMetatypeArray;
}
else {
typelist = types;
}
const uint64_t matcher = build_signature(typelist, count);
//try in the hashmap
auto iter = world->archetype_signature_map.find(matcher);
if (iter != world->archetype_signature_map.end()) {
auto& archvec = iter->second;//world->archetype_signature_map[matcher];
for (int i = 0; i < archvec.size(); i++) {
auto componentList = archvec[i]->componentList;
int ccount = componentList->components.size();
if (ccount == count) {
for (int j = 0; j < ccount; j++) {
if (componentList->components[j].type != typelist[j])
{
//mismatch, inmediately continue
goto contA;
}
}
//everything matched. Found. Return inmediately
return archvec[i];
}
contA:;
}
}
//not found, create a new one
Archetype* newArch = new Archetype();
newArch->full_chunks = 0;
newArch->componentList = build_component_list(typelist, count);
newArch->componentHash = matcher;
newArch->ownerWorld = world;
world->archetypes.push_back(newArch);
world->archetypeSignatures.push_back(matcher);
world->archetype_signature_map[matcher].push_back(newArch);
//we want archs to allways have 1 chunk at least, create initial
create_chunk_for_archetype(newArch);
return newArch;
}回忆篇头的两幅图, 在已知Metatype的情况下, 计算各Component的Offset, 以及当前Archetype能够容纳的Entity总数, 整体还是一个很自然的过程, 同时我们也看到创建好的Archetype对象会被注册到关联的World上, 另外新建Archetype的时候也会至少为其添加一个DataChunk. 最后默认的行为可能对于建立一个Entity空对象再逐步添加Component的创建方式不太友好, 需要注意一下.
6. Entity & World
6.1 Entity相关的对象
struct EntityID {
uint32_t index;
uint32_t generation;
};decs中的Entity对象其实是间接存在的, 这也跟SoA的组织方式有直接关系, SoA化数据后, 单个Entity的数据其实是被分散存储在Chunk中的, 所以Entity对象在decs中其实弱化了, 外部更多是通过上面贴出的EntityID对某一Entity数据进行操作和访问的.
另外World内部还有一个隐含的Entity的关联对象, EntityStorage, 定义如下:
struct EntityStorage {
DataChunk* chunk;
uint32_t generation;
uint16_t chunkIndex;
};根据成员和结构体名称也容易看出EntityStorage用于定义某个Entity存储的Chunk和在Chunk中的索引, 以及分代Index(对应Entity被复用一次该计数加1).
6.2 World
World是decs的操作入口, 对Entity的增加删除操作, 以及对Entity上的Component的增删操作, 以及对所有Component的遍历操作, 都是透过ECSWorld来完成的, 我们通过一个ECSWorld来完成对一组ECS数据的管理维护操作. 举例来说, 如下图所示:
为了更好的完成关卡的ECS化和关卡内的Role(活动物体, Npc, 怪, 人等)的ECS化, 我们如上图所示组织代码, 并如下面代码所示:
ecs::World mRoleECSWorld;
ecs::World mLevelECSWorld;分别建立容纳Role实体的World, 以及容纳Level实体的World, 这样对于Level和Role的操作就能比较好的隔离到两个独立的World中, 相关的Component与System也能更好的如上面图中工种所示归属到level和role目录下, level和role的目录下也可以进一步按照功能模块对不同的component和system做适当的组织.
我们先来看一下World的成员变量:
namespace ecs
{
struct World {
std::vector<EntityStorage> entities;
std::vector<uint32_t> deletedEntities;
robin_hood::unordered_flat_map<uint64_t, std::vector<Archetype*>> archetype_signature_map{};
robin_hood::unordered_flat_map<uint64_t, Archetype*> archetype_map{};
std::vector<Archetype*> archetypes;
//unique archetype hashes
std::vector<size_t> archetypeHashes;
//bytemask hash for checking
std::vector<size_t> archetypeSignatures;
robin_hood::unordered_flat_map<uint64_t, void*> singleton_map{};
int live_entities{ 0 };
int dead_entities{ 0 };
};
}具体的单个成员我们就不一一展开了, decs的使用接口基本都集中在World中, 后续具体的行为代码介绍会逐步了解到相关成员变量的作用.
然后我们来看一下World中一些常用的接口以及核心代码的实现:
6.2.1 Entity的新建
Entity的新建接口如下:
template<typename ... Comps>
inline EntityID new_entity();是一个模板函数, 它返回的是前面我们介绍过的一个64位的EntityID结构体, 另外如果创建的时候传入模板参数Comps, 则对应Entity会自动创建对应的Component(注意默认的desc实现只支持Component的无参构造方式).
我们主要关注整个执行过程:
整个new_enity的过程如上图所示, 我们从其中也能看到一些可能存在性能问题的点, 主要是图中标黄的地方, 当对一个dead entity进行复用的时候, 会发生move_entity_to_archetype(), 这个函数行为较复杂, 可能需要根据实际使用情况做一些调优.
6.2.2 Entity的删除
Entity的删除逻辑比较简单, 我们先来看一下相关代码:
inline void destroy(EntityID eid);
inline void destroy_entity(World* world, EntityID id) {
assert(is_entity_valid(world, id));
erase_entity_in_chunk(world->entities[id.index].chunk, world->entities[id.index].chunkIndex);
deallocate_entity(world, id);
}主要需要注意的是两点:
- decs的实现没有分离内存管理部分, 是自己实现的基于Chunk的分配释放策略, 整体使用比较简单, 下一步可以考虑将内存分配独立出来 , 也方便与共享内存做更好的桥接.
- 通过上面的代码逻辑以及分析具体的源码实现, 我们也能看出, destroy_entity其实会在Chunk块上留下hole, 但这点对于服务器来说影响不大, 留下的hole马上会被新分配的同Archetype的对象填充上, 暂时不需要考虑这部分对内存的影响.
6.2.3 Entity添加Component
添加component的逻辑比较简单, 从上面的图中也能看出decs是不支持一个Entity中存在多个同类型的Component的. 另外此处也复用了set_entity_archetype这个函数.
6.2.4 Entity删除Component
与add_component逻辑基本一致, 区别在于如果存在对应component, 才执行set_entity_archetype(newArch, id)的流程, 这里不再具体列出相关流程了.
6.2.5 遍历(for_each)
template<typename Func>
void for_each(Query& query, Func&& function);
template<typename Func>
void for_each(Func&& function);for_each函数有两个, 一般我们直接使用下面的就可以.
遍历是ECS最核心的地方, ECS数据组织的方式也是为了最好的加速对象的遍历, 主要的处理过程如下:
- 生成符合处理函数需要的Query
- 利用Query筛选出合适的Archetype
- 对Archetype中的每个Chunk, 正确的调用处理函数.
从处理函数的参数推导Query主要用到了参数的type traist, 这块我们之前讲述反射机制的时候也简单提到过, 方式和实现机制都比较成熟, 这里不进行具体展开了.
其中对Archetype的筛选用到了Query对象, 我们先来看实现for_each的辅助对象Query.
6.2.5.1 Query对象
Query对象主要完成对Archetype的筛选, 这样只有符合条件的Archetype才会参与到遍历中. Query的定义如下:
struct Query {
std::vector<MetatypeHash> require_comps;
std::vector<MetatypeHash> exclude_comps;
size_t require_matcher{ 0 };
size_t exclude_matcher{ 0 };
bool built{ false };
template<typename... C>
Query& with() {
require_comps.insert(require_comps.end(), { Metatype::build_hash<C>()... });
return *this;
}
template<typename... C>
Query& exclude() {
exclude_comps.insert(exclude_comps.end(), { Metatype::build_hash<C>()... });
return *this;
}
Query& build() ;
};with()和exclude()模板函数主要用于正确的填充 require_comps和exclude_comps, 最后再调用build函数生成需要的require_matcher和exclude_matcher这两个值(size_t类型), 接着在遍历World的时候, 我们可以很简单的如下代码所示(require_matcher和exclude_matcher主要是做一个初步筛选, 具体的判断其实还是依赖require_comps和exclude_comps的):
template<typename F>
void iterate_matching_archetypes(World* world, const Query& query, F&& function) {
for (int i = 0; i < world->archetypeSignatures.size(); i++)
{
//if there is a good match, doing an and not be 0
uint64_t includeTest = world->archetypeSignatures[i] & query.require_matcher;
//implement later
uint64_t excludeTest = world->archetypeSignatures[i] & query.exclude_matcher;
if (includeTest != 0) {
auto componentList = world->archetypes[i]->componentList;
//might match an excluded component, check here
if (excludeTest != 0) {
bool invalid = false;
//dumb algo, optimize later
for (int mtA = 0; mtA < query.exclude_comps.size(); mtA++) {
for (auto cmp : componentList->components) {
if (cmp.type->hash == query.exclude_comps[mtA]) {
//any check and we out
invalid = true;
break;
}
}
if (invalid) {
break;
}
}
if (invalid) {
continue;
}
}
//dumb algo, optimize later
int matches = 0;
for (int mtA = 0; mtA < query.require_comps.size(); mtA++) {
for (auto cmp : componentList->components) {
if (cmp.type->hash == query.require_comps[mtA]) {
matches++;
break;
}
}
}
//all perfect
if (matches == query.require_comps.size()) {
function(world->archetypes[i]);
}
}
}
}6.2.5.2 处理Archetype中的每个Chunk
在筛选出Archetype后, 我们需要对Archetype中的每个Chunk进行处理, 相关核心代码如下:
for (auto chnk : arch->chunks) {
detail::unpack_chunk(params{}, chnk, function);
}
});
template<typename ...Args, typename Func>
void unpack_chunk(type_list<Args...> types, DataChunk* chunk, Func&& function) {
entity_chunk_iterate<Args...>(chunk, function);
}
//by skypjack
template<typename... Args, typename Func>
void entity_chunk_iterate(DataChunk* chnk, Func&& function) {
auto tup = std::make_tuple(get_chunk_array<Args>(chnk)...);
for (int i = chnk->header.last - 1; i >= 0; i--) {
function(std::get<decltype(get_chunk_array<Args>(chnk))>(tup)[i]...);
}
}前面我们提到过, Chunk内的同类Component是连续存放的, 借助模板推导, 我们可以很容易的完成获取Component Data -> 调用处理函数这个过程, 最终我们借助相关设施, 成功的完成了对调用函数参数的匹配和整个World中所有符合条件的对象的遍历.
7. 总结
整个decs实现借助c++14的相关特性, 很好的完成了Archetype based ecs的实现, 以下几个点是当前比较关注的:
- 整体代码的实现非常简洁
- 从类型T到64位hash值的compiler阶段实现(无运行时开销), 是比较巧妙的, 比ponder库的实现更高明, 而且可以免费获得一个64位的唯一ID, 后续考虑将C++反射的相关实现调整成同样的方案.
- decs对内存的管理代码也比较简洁, 只是我们需要将其做适当的处理, 使它可以更好的跟共享内存或其他内存分配方式搭配
- 面向数据的设计更有利于序列化反序列化, 后续对接C++反射后可以比较自然的完成Entity的序列化反序列化, 有效简化像对象的Cache更新, Real/ghost迁移等一系列的任务.
- 考虑补充简洁的事件机制简化Component间的依赖.
- 其他像ECS常规的系统解耦等特性不再细述.
8. 参考链接
参考文章1: Bevy--ECS部分
腾讯云开发者
