YSYSIMONCODE. ART. SCIENCE. VISION.

ECS: 标识符回收

整理 ECS 中实体标识符复用、隐式链表空洞回收，以及版本号校验失效标识符的基本思路。

Dec 1, 2024约 4 分钟Principlesysysimon
ECSC++Sparse SetEntity Identifier

前文已经说过，如果不对 稀疏集 的空洞进行回收，那么将造成其 稀疏数组 过于稀疏的问题，所以我们要想办法填补这些空隙

具体来说，就是在新增实体的时候，优先使用这些空洞位置 (可以认为是被销毁的实体)，也就是说，需要复用 被销毁实体 的 标识符，将空洞处的 标识符 再次赋予新的实体使用

隐式链表

我们一般使用 隐式链表 结构来存储所有的空洞位置，这种结构如下

  • 使用 next 存储当前可以使用的第一个空洞位置的 索引
  • 而空洞位置中直接存储下一个空洞位置的 索引
  • 额外使用一个 available 存储当前存在的空洞总数

Implicit Free List

next + available + sparse holes

free-list chainsparse entitiesnextE2E4E5E8nullE00E11E4next2E33E5next4E8next5E66E77null8E99headnext = E2holesavailable = 4
The free-list head points at the first hole. Each free sparse slot stores the next reusable entity identifier.

可以发现这种 链表 结构是直接借助了 稀疏数组 本身存储的，而不是一个独立的结构，所以称它为 隐式链表

在这种结构下，创建实体 和 销毁实体 需要遵从特殊的步骤

创建实体

  1. 检查 available 是否大于 0
  2. 如果有空闲标识符，使用 next 指向的索引
  3. 更新 next 为链表中的下一个空闲位置
  4. 减少 available 计数

销毁实体

  1. 将当前 next 中的值存储到被销毁 实体 的位置中
  2. 更新 next 指向新销毁的位置
  3. 增加 available 的计数

Destroy Entity

destroy(E6) pushes one slot to the head

before destroy(E6)nextE2E4E5E8nullE00E11E42E33E54E85E66E77null8E99after destroy(E6)nextE6E2E4E5E8nullE00E11E42E33E54E85E26E77null8E99
slot[E6] = old nextnext = E6available++
Destroying an entity does not allocate a new list node. The destroyed slot stores the old head and then becomes the new head.

版本号

看起来很完美，但是这种方案任然存在一个问题，由于被销毁位置存储的是下一个空洞位置的索引我们无法 通过标识符位置检查实体是否已销毁 (因为无法分辨其中存储的索引是真的指向有效的 密集数组 还是 稀疏数组 中的下一个空洞) 如果想通过标识符位置检查实体是否已销毁，需要追溯链表，但隐式链表是单向的，无法轻松实现

解决方案是，同时存储 版本号，例如

entities[1] = 0x00010000; // 实体部分为 0x0001，版本部分为 0x0000
entities[2] = 0x00020001; // 实体部分为 0x0002，版本部分为 0x0001

假设我们要验证标识符 0x00010001 是否有效

  1. 使用实体部分 0x0001 找到其在 entities 数组中的位置（第 1 个位置）
  2. 检查存储的 版本 部分是否等于 标识符 中的 版本 部分
  3. 如果版本部分不一致，说明该 标识符 已经失效

使用版本号可以直接通过实体数组中的版本部分进行验证，无需额外的数据结构来记录已销毁实体，这是因为 标识符 id 本身同时存储 实体编号 和 版本号，例如对于 32bit 的 标识符 可以使用前 16bit 存储 实体编号，后 16bit 存储 版本号，当然可以根据需要来决定哪一部分具体使用多少 bit 位

Generation Version

index reuse is checked by generation bits

32-bit entity identifierhandle0x00010001entity index0x0001generation0x0001use as indexcarried by handlelookup entities[1]entities[1]stored_version = 0x0000handle versionhandle.version= 0x0001entities[1].stored_version0x0000!=handle.version0x0001stale identifier
The index may be reusable, but the generation bits separate a new entity from an old handle that still names the same slot.

所以每次销毁实体时版本号递增，确保新标识符与旧标识符区分开，验证时通过比较标识符中的版本部分与实体数组中存储的版本部分是否一致，即可快速判断有效性 (按位运算)