Chapter 06

ストレージ 3: Entity

toyboot 4e
toyboot 4e
2022.03.28に更新

EntitySparseSet<T> の亜種に保存します。

このストレージは Entity の世代番号をインクリメントします。

Entity = SparseIndex

ent.rs
#[repr(transparent)]
pub struct Entity(SparseIndex);

// SparseIndex { u32, Generation }

後で &SparseIndex&Entity のキャストができるように #[transparent] にしました。

EntityPool

Entity も sparse set に入れます:

前章の SparseSet<T> の違いとしては、保存するデータ (Entity) 自体が sparse index であるため Vec<SparseIndex> がありません。

世代番号の引き継ぎ

EntityPool は sparse index のアロケータです。空欄をリサイクルするときは世代番号を引き継いでインクリメントします。そのため空欄が世代番号を保持します:

ent.rs
pub struct EntityPool {
    entries: Vec<Entry>,
    data: Vec<Entity>,
    // free_root: Option<NonZeroU32>,
}

enum Entry {
    ToDense(DenseIndex),
    Empty {
        gen: Generation,
        // next: Option<NonZeroU32>,
    },
}

空欄で連結リストを作ると新規 Entity の作成コストが一定になります。

WorldEntityPool を追加しておきます:

lib.rs
#[derive(Debug, Default)]
pub struct World {
    res: ResourceMap,
    ents: EntityPool,
}

リファレンス実装: 0359776

備考: 連結リストで空きスロット管理

以下を初期状態とします:

挿入時はルートが指す空きスロットを使います。ルートは 2 番目の空きスロットを指すように書き換えます:

削除時はルートが新たな空きスロットを指します。また新たな空きスロットは以前のルートが指すスロットを指します: