ECS への関心

以前 sparse set ベースの ECS を作りました (toecs) 。肝心のグループ機能がお留守ですし Scheduler もありませんが、自分のゲーム開発にはもう十分。ある程度満足してしまいました。

ところが archetype ベースの ECS に関しては、内部実装がイメージできません。たとえば struct Entity の内部データはどのようになっていて、どのように Component との対応を取るのでしょうか。

さらに sparse set ベースの ECS と archetype ベースの ECS のハイブリッドもあり (bevy ECS) 、この内部構造も気になります。 2 つの ECS を上手く繋ぐだけで済むのか、他方が一方の中に組み込まれるのか、何か細かいサポートが大量に必要になるのか？

たまにソースを読んで調べていきます。

どのライブラリを読むか

まだ Query ベースの API と和解していないので、特にどれかに惹かれることもないです。強いて言うなら flax というスペルは良いですね。

• bevy_ecs (29,733 行)
  読むメリットが大きいため、逆に気分が乗らないかもしれません。
• dotrix_ecs (892 行)
  短い！　概要は観れるかもしれません。
• edict (15,802 行)
  参照カウントや変更の検出を builtin でやってくれるそうです。実験的過ぎるかな。
• flax (15,586 行)
  かなり特徴的な API を持つ ECS です。面白いかも。
• flecs (40,979 行)
  憧れがありますが、どこまで C に付き合うか。コスパは良くないでしょう。
• hecs (7,508 行)
  無難な選択で気分も乗りますが、無難過ぎるきらいはあります。
• legion (13,616 行)
  開発も止まっている気がしますし、さすが古いですね。

Building an ECS シリーズ

Sparse set ベースの ECS と言えば EnTT, archetype ベースの ECS と言えば flex! flex の作者こと Sander Mertens の記事を読んでいきます。

※ 訳ではなく僕の解釈を書いています 。

Building an ECS #1: Where are my Entities and Components

(Archetype ベースの) ECS の作り方を教えるぞというシリーズです。

• Type とは component 組である
• Archetype とは Type 毎のストレージである
• 実装のため、以下のマップを作る:
  • entity_index: Entity → Archetype
  • component_index: ComponentId → ArchetypeSet (ID のセット)
  • ComponentId → ArchetypeSet, ArcheTypeSet → ArchetypeId という形でマップを作る

Building an ECS #2: Archetypes and Vectorization

• 配列のループはキャッシュ効率が良いため高速である。さらに SIMD (single instruction / multiple data: 固定長ベクトル演算) 命令を使用できる可能性があり、 2 ~ 16 倍速くなる。
• SIMD 命令は空欄の無い連続した配列にのみ適用できる。
• (Sparse set ベースの ECS で見られるような) グループを使った並べ方の工夫では、任意の component の組み合わせに対して連続した配列を作ってループすることはできない。たとえば (A, B), (B, C), (C, A) という 3 つの組み合わせがあれば、すべてのループを密な配列に対するループにすることはできない。
• Archetype ベースのストレージでは、 Type 毎に (component 組毎に) SoA ストレージ (vector<Column>) を用意する。なおこのストレージでは対象の型が動的に決まるため、 Vec<T> の T に相当する型情報を消す必要がある (Column) 。
  • entity_index: Entity → (Archetype, Row) に変更 (Row = size_t)

pub fn get_component<'w, T>(e: Entity, c: ComponentId, world: &'w World) -> Option<&'w T> {
    let e_index = world.entity_info.index.get(&e)?;
    let c_index = world.component_info.index.get(&c)?;

    let archetype = &world.archetypes[e_index.archetype_id.raw as usize];
    let component_index = c_index.map.get(&archetype.id)?.clone();

    Some(&archetype.vecs[e_index.component_vec_id][component_index])
}

• Component の挿入は Archetype の変更に繋がる。
• ここまで、記事では Type { Vec<ComponendId> } をハッシュマップのキーにしていたが、これは非常に遅い。そこで archetype のグラフを考える。
• ある Archetype の Entity から 1 つの Component を追加／削除したとき、移動する先の Archetype をキャッシュする: (ArchetypeId, ComponentId) → ArchetypeId 。 Edge { add: ArchetypeId, rm: ArchetypeId } を使って Archetype の移動をグラフの形でキャッシュする。この Edge はレジーに生成 (キャッシュ) して、とんでもない量のメモリを使わないようにする。
• これまで SoA (Struct of Arrays) の形で Archetype ストレージを実装してきた (vector<Column>) 。 AoS (Array of Structs) の形と比べてどうなのだろうか？
  • SoA は特定の component のみをキャッシュに載せる。 AoS はすべての component をキャッシュに載せる。特定の component のみにアクセスすると分かっているなら SoA の方が効率が良い。どの component にアクセスするか分からないなら AoS の形ですべてキャッシュに載せたほうが効率が良い。
  • AoS ストレージはオフセットやアラインメントの計算が難しい。
  • 通常 Archetype は SoA の形で実装される。 Component の数が多くても SoA なら影響が少ないし、重いシステムは大抵特定の component のみに関心がある。

所々『本当か〜？』と思いつつも 良かった ！　めちゃめちゃ良かった。

やはり archetype ベースの方が sparse set よりも複雑ですが、すでに内部実装が大体把握できてしまったのが凄い。後はイテレータのために、ある component 組を持つすべての Archetype を列挙する操作とキャッシュが必要な気がします。自力で実装するのはまだキツいかな〜。

もっと Sander Mertens ……を挫折

※ 訳ではなく僕の解釈を書いています 。

Making the most of ECS identifiers

flex の C++ 版 API を把握していないと読めませんでした。内容的にもエクストリームな感じがします。

Why Vanilla ECS Is Not Enough

この話も難しく、実装はハックです。うーむ

Building Games in ECS with Entity Relationships

前の 2 つよりは分かるけれども、ついていくのは難しい……

• Entity 同士の関係性がフレームワークに 1 級市民として支持されることは少ない。たとえば関係性のある Entity が破壊されたり、複数の Entity との関係性を作りたい場合はどうするだろうか？
• (flex の) entity relashionships は entity のグラフを描きグラフのクエリを書くための統合された手段である。その実装は 1 見複雑に見えるが、大半は ECS の中に存在する機能を作り直したり調整するだけである。
• Relation というのは 2 つのものを追加することである。たとえば (Likes, Dog) を追加すれば entity likes dog という関係性を表現できる。 Generics のある言語で表現するなら、 Relation<Likes, Dog> を追加するようなものだ。
• ここで Dog の部分を型ではなく変数にすれば、 entity attacks entity2 のような表現ができる。 entity2 は実行時に決定できるというのが component 型を使うのと異なるところだ。
• ここでの relashionship は値毎に別のものとして扱われる (?) 。同じものとして扱って重複を避けるためには、 exclusive relashionship を作る。
• 以下略

うーむストレージの話以外はついていくのが難しい。

Archetype ベースのストレージを可視化

Building an ECS シリーズで紹介されたストレージは、以下のように図示できると思います:

わりとシンプルですね。