この記事は LabBaseテックカレンダー Advent Calendar 2024 の 6 日目の記事です。

はじめに

Entity Component System (ECS) について理解を深めるために、機能が非常に限定された ECS を Rust で実装しました。

この記事ではこの実装をもとに、実装過程を再現しながら実装方法を説明します。

背景

ECS は主にゲームやシミュレーションシステムで用いられるデータ指向のアーキテクチャです。Entity, Component, System という 3 種類の構成要素を組み合わせて全体のシステムを作ります。

Entity はデータを持たない識別子、Component はデータ、System はロジックを表します。

Component

順番が前後しますが Entity より先に Component を説明します。

ECS の特徴の一つはデータ = Component のメモリへの配置方法です。多くの人にとって馴染み深いと思われるコンポーネント指向と対比して説明します。この記事では、コンポーネント指向とはオブジェクトがデータを直接持つようなアーキテクチャのこと指すものとします。Unity などで馴染み深いやつです¹。

以下のような主体が登場するゲームを考えます。

プレイヤー
- データ - Position, Velocity, HP
敵キャラクター
- データ - Position, Velocity
セーブポイント
- データ - Position

これをコンポーネント指向で実装する場合、データの配置は以下のようになります。各オブジェクトがデータを持ち、ゲーム全体としてはオブジェクトの配列があるような形です。

struct Player {
    position: [f32; 3],
    velocity: [f32; 3],
    hp: f32,
}

struct Enemy {
    position: [f32; 3],
    velocity: [f32; 3],
}

struct SavePoint {
    position: [f32; 3],
}

struct Game {
    players: Vec<Player>,
    enemies: Vec<Enemy>,
    save_points: Vec<SavePoint>,
}

一方で、ECS では以下のようなイメージでデータを配置します。データの種類ごとに配列があるようなイメージです。

struct Game {
    positions: Vec<[f32; 3]>,
    velocities: Vec<[f32; 3]>,
    hps: Vec<f32>,
}

Entity

Entity はシステム内の主体を識別するための識別子です。Entity は内部データを持たないので、実装の際は単なる整数型を Entity として使います (後述の理由により整数型のペアを Entity とすることも多いです)。

ECS では Component を Entity に「アタッチ」します。つまり、特定の Entity と特定の Component のインスタンスを関連付けて、Entity をキーとして Component を参照できるようにします。具体的な実装方法はあとの節で書きます。

System

System はロジックに相当します。関連する Component を操作することによってゲームの動作を実現します。

例えば「移動」を担当する System は Position Component と Velocity Component がアタッチされている Entity に対して処理を行うように定義します。そのためプレイヤーと敵キャラクターは処理対象になりますが、セーブポイントは処理対象になりません。

World

Entity, Component, System を含む全体を World と呼ぶことがあります。この記事でもこの呼び名を使います。

ECS の利点

ECS の利点として、Component がメモリ上の連続した領域に格納されているので CPU キャッシュの効率が良いことがあげられます。また、処理する Component が重複しない限り System を並列処理できるという利点もあります。ただし、この記事ではキャッシュ効率はストイックには追求せず、並列処理は実装しません。

また、コンポーネント指向よりも Rust との相性が良いように感じます。こちらが Rust で ECS を実装・利用したい主な理由です。筆者の実装力不足かも知れませんが、例えば Vec に格納されている要素同士が相互に mutate し合うような処理 (このような処理はゲームではよくあります) を書く場合、コンポーネント指向だとスッキリ書くのが難しいと感じます。

設計の方針

ここで実装する ECS ライブラリは以下のようなものです。なるべく少ない労力で ECS の本質の部分を実装したいです。

Component として様々な型を使える
- ライブラリのユーザが定義した型を Component として使うことができるようにします
System は 1 個または 2 個の Component を受け取る
- 普通はもっと多くの Component を受け取れるようにしますが、今回はシンプルさを重視して 1 個と 2 個のみサポートすることにします
System は Component の不変参照か可変参照を受け取れる
- Component の所有権を奪うことはできないものとします
System から Entity を追加・削除できない
- これは余力が無かったので実装していません
他の実装と比べて極端に遅くない
- あくまで学習のためなのでパフォーマンスは諦めているのですが、10 倍とか遅くなるのは避けたいです

ECS を実装するにあたって主に考えなければならないことが 2 つあります。Entity と Component のアタッチの関係をどのように記録するのかと、System をどのように実行するのかです。

Entity と Component のアタッチ関係

Component の型を T として Vec<Option<T>> 相当のコレクションを Component の種類ごとに用意します。各コレクションのインデックスを Entity とします。

これで Entity と Component の関係が保存され、Entity をキーとしてアクセスできるようになります。この実装方法の問題点として、大量の None によってメモリが無駄に消費されてしまう、Entity の並び順によってはキャッシュ効率があまり良くないという欠点があります。実用の ECS ライブラリではもっと効率の良い方法を使っていますが、今回はシンプルさを重視してこれを採用します。

Component を格納しておくデータ構造をストレージと呼ぶようなので、この記事でも今後この呼び名を使います。

System の実行方法

World から System へイテレータを渡します。System 内でそのイテレータを回すと Component への参照が得られるように実装します。

実装

API を決める

まず API を考えます。これから作る ECS ライブラリが提供する機能は以下の 3 つです。

新しい Entity を生成する
Entity に Component をアタッチする
System を実行する

それぞれ以下のような形で呼び出せるようにします。

fn main() {
    // 大元となる World 構造体
    let mut world = World::new();

    // 新しい Entity を生成する
    let entity = world.new_entity();

    // Entity に Component をアタッチする
    world.attach_component(
        entity,
        Position {
            x: 0.1,
            y: 0.2,
            z: 0.3,
        }
    );
    world.attach_component(
        entity,
        Velocity {
            dx: 0.3,
            dy: 0.4,
            dz: 0.5,
        }
    );

    // System を実行する
    world.execute(move_system);
}

// Component はユーザが自由に定義できる
struct Position { x: f32, y: f32, z: f32 }
struct Velocity { dx: f32, dy: f32, dz: f32 }

// System はイテレータを受け取る関数として実装する
fn move_system(iter: NantokaIterator<Position, Velocity>) {
    for (pos, vel) in iter {
        pos.x += vel.dx;
        pos.y += vel.dy;
        pos.z += vel.dz;
    }
}

`World` 構造体

World 構造体が持つべきものは 2 つです。

Entity を発行するもの
Component のストレージ

struct World {
    entities: ???,
    components: ???,
}

このような感じです。??? はまだ型が定まっていないという意味です。

Entity の発行

まず World#entities の型を考えていきます。この型は Entity の発行機として以下のような機能を持っていてほしいです。

「値」を発行してくれる
その「値」は一意である
「値」は整数と対応していて、対応する整数が小さいものを優先的に発行してくれる
過去に発行した「値」を無効化できる
過去に発行されたことがある「値」が再び発行されることはない
発行されてまだ無効化されていないすべての「値」について、対応する整数が重複しない

この「値」をそのまま Entity として使用することにより、World に対して Entity の追加・削除ができ、追加・削除の後も Entity の一意性を保証できるようになります。さらに、Entity に対応する整数を Component のストレージのインデックスとして使うことができて便利です。

実はこれらの性質を満たすデータ構造が存在します。正確な名前がわからなかったのですが、generational_arena や slotmap クレートなどで実装されています。筆者は GenerationalVec<T> という名前で独自に実装しました。

このデータ構造については [Rust] ゲーム向け世代型Idアリーナによる最適化で非常にわかりやすく解説されているのでご覧ください。

Entity はなんのデータも持たないので GenerationalVec<()> を Entity の発行機として使用することにします。

World#new_entity() が実装できます。

impl World {
    pub fn new_entity(&mut self) -> GenerationalId {
        self.entities.add(())
    }
}

World 構造体の定義は以下のように更新されます。

struct World {
    entities: GenerationalVec<()>
    components: ???,
}

ちなみに GenerationalVec<T> を Component のストレージとして使用することもできるようですが、この記事では使用しません。

ストレージ - `SparseVec<T>` 構造体

続いて World#components の型を考えます。Component の種類ごとに Vec<Option<T>> 相当のストレージをもたせることにしたので、

components: HashMap<TypeId, Vec<Option<???>>>

のような形が良さそうです。TypeId は標準ライブラリにある型で、個別の型に対応する一意な値です。Component の TypeId をキー、Component のストレージを値として HashMap に格納します。

Vec<Option<T>> の部分を SparseVec<T> として取り出します。

struct SparseVec<T> {
    data: Vec<Option<T>>
}

get, remove などのメソッドを定義します。replace は少し説明が必要で、与えられたインデックスまで内部の data を伸ばして値を交換します。

impl<T> SparseVec<T> {
    pub fn replace(&mut self, index: usize, component: T) -> Option<T> {
        if index >= self.data.len() {
            self.data.resize_with(index + 1, || None);
        }
        self.data[index].replace(component)
    }

    pub fn get(&self, index: usize) -> Option<&T> {
        self.data.get(index).and_then(|v| v.as_ref())
    }

    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
        self.data.get_mut(index).and_then(|v| v.as_mut())
    }

    pub fn remove(&mut self, index: usize) -> Option<T> {
        self.data.get_mut(index).and_then(|v| v.take())
    }
}

ストレージ - 型消去

World#components の型は HashMap<TypeId, SparseVec<???>> になりましたが、??? の部分をうまく埋めることができません。ここには Component の具体的な型を入れたいですが、それは HashMap のキーごとに異なるからです。

そこで、Any とダウンキャストを利用して SparseVec<T> からジェネリクスの部分を取り除いた TypeErasedSparseVec を用意します。

pub struct TypeErasedSparseVec {
    inner: Box<dyn Any>,
}

impl<T: 'static> From<SparseVec<T>> for TypeErasedSparseVec {
    fn from(value: SparseVec<T>) -> Self {
        Self {
            inner: Box::new(value),
        }
    }
}

impl TypeErasedSparseVec {
    pub fn downcast<T: 'static>(&self) -> Option<&SparseVec<T>> {
        self.inner.downcast_ref()
    }

    pub fn downcast_mut<T: 'static>(&mut self) -> Option<&mut SparseVec<T>> {
        self.inner.downcast_mut()
    }
}

Any は Rust の大抵の型に自動で実装されているトレイトです。そのため、Box<dyn Any> は Java の Object 型のように使うことができます。

ダウンキャストを使用していますが、キャスト先の型を間違えたとしても panic はしません。

World 構造体の定義は下のように更新されます。

struct World {
    entities: GenerationalVec<()>,
    components: HashMap<TypeId, TypeErasedSparseVec>,
}

ストレージ - `RefCell`

唐突かつ天下り的ですが、World#components の型を HashMap<TypeId, TypeErasedSparseVec> から HashMap<TypeId, RefCell<TypeErasedSparseVec>> に変更します。TypeErasedSparseVec を RefCell で包んでいます。そうしないと Component の可変参照を 2 つ取る System で問題が起きるからです。

例えば Component A と Component B の可変参照を受け取る System を実行する場合、World 側で下記のようなコードを書く必要がありますが、これはコンパイルできません。

let a_storage: &mut TypeErasedSparseVec = components.get_mut(TypeId::of::<A>()).unwrap();
let b_storage: &mut TypeErasedSparseVec = components.get_mut(TypeId::of::<B>()).unwrap();

RefCell を使用することにより、components から複数の可変参照を取り出すことができるようになります。components.get_mut() ではなく components.get() を使用しているのがポイントです。

let a_refcell: &RefCell<TypeErasedSparseVec> = components.get(TypeId::of::<A>()).unwrap();
let a_storage: RefMut<'_, TypeErasedSparseVec> = a_refcell.borrow_mut();
let b_refcell: &RefCell<TypeErasedSparseVec> = components.get(TypeId::of::<B>()).unwrap();
let b_storage: RefMut<'_, TypeErasedSparseVec> = b_refcell.borrow_mut();

TypeErasedSparseVec をダウンキャストして SparseVec<T> を取得するようにします。

let a_refcell: &RefCell<TypeErasedSparseVec> = components.get(TypeId::of::<A>()).unwrap();
let a_storage: RefMut<'_, SparseVec<A>> = RefMut::map(a_refcell.borrow_mut(), |v| v.downcast_mut::<A>().unwrap());
let b_refcell: &RefCell<TypeErasedSparseVec> = components.get(TypeId::of::<B>()).unwrap();
let b_storage: RefMut<'_, SparseVec<B>> = RefMut::map(a_refcell.borrow_mut(), |v| v.downcast_mut::<B>().unwrap());

World#components からストレージを取り出す処理が複雑になってきたため、Components 型を導入します。

struct World {
    entities: GenerationalVec<()>,
    components: Components,
}

struct Components {
    map: HashMap<TypeId, RefCell<TypeErasedSparseVec>>,
}

impl Components {
    fn borrow_mut<T: 'static>(&self) -> Option<RefMut<'_, SparseVec<T>>> {
        let refcell = self.map.get(&TypeId::of::<T>())?;
        let vec = RefMut::map(refcell.borrow_mut(), |vec| {
            // SAFETY:
            // self.map[TypeId::of<T>] には SparseVec<T> が登録されているので、ダウンキャストは必ず成功する
            unsafe { vec.downcast_mut::<T>().unwrap_unchecked() }
        });
        Some(vec)
    }
}

これで SparseVec<A>, SparseVec<B> を取り出す処理は下のようにシンプルに書けるようになります。

let a_storage: Option<RefMut<'_, SparseVec<A>>> = components.borrow_mut::<A>();
let b_storage: Option<RefMut<'_, SparseVec<B>>> = components.borrow_mut::<B>();

ようやく World#components の実装は完了です。最後に World#attach_component() を実装します。

impl World {
    /// エンティティにコンポーネントを追加する
    ///
    ///
    /// ## Returns
    ///
    /// 以前のコンポーネントがあればそれを返す。なければNoneを返す
    pub fn attach_component<T: 'static>(
        &mut self,
        entity: GenerationalId,
        component: T,
    ) -> Option<T> {
        if let Some(mut array) = self.components.borrow_mut::<T>() {
            return array.borrow_mut().replace(entity.index, component);
        }
        None
    }
}

System - `SingleComponentExclusiveIter` 構造体

ストレージが完成したので System の実装に入ります。System はイテレータを受け取る関数として実装することにしたのでした。World から Component のイテレータを作る必要があるため、作っていきます。

最もシンプルな System は Component の不変参照を 1 つだけ受け取るものです。これに対応するイテレータ SingleComponentExclusiveIter を実装します。

Vec<Option<T>> から None だけ飛ばして値を返せば良いので実装は簡単です。

まず SparseVec<T> から内部の Vec のイテレータを得られるようにします。

impl<T> SparseVec<T> {
    fn data_iter_mut(&mut self) -> std::slice::IterMut<'_, Option<T>> {
        self.data.iter_mut()
    }
}

次に Components からイテレータを取得するメソッドを追加します。

impl Components {
    fn get_exclusive_iter_mut<T: Component>(
        &mut self,
    ) -> Option<std::slice::IterMut<'_, Option<T>>> {
        let refcell = self.map.get_mut(&TypeId::of::<T>())?;
        let optional_vec = refcell.get_mut().downcast_mut::<T>();
        // SAFETY:
        // self.map[TypeId::of<T>] には SparseVec<T> が登録されているので、ダウンキャストは必ず成功する
        let vec = unsafe { optional_vec.unwrap_unchecked() };
        Some(vec.data_iter_mut())
    }
}

これで World から SingleComponentExclusiveIter を作れるようになります。

pub struct SingleComponentExclusiveIter<'world, C>
where
    C: 'static,
{
    iter: std::slice::IterMut<'world, Option<C>>,
}

impl<'world, C> SingleComponentExclusiveIter<'world, C>
where
    C: 'static,
{
    fn from_world(world: &'world mut World) -> Self {
        let iter = world
            .components
            .get_exclusive_iter_mut::<C>()
            .expect("Component not registered");
        Self { iter }
    }
}

最後にイテレータの next() メソッドを実装します。Components から取得したイテレータをもとに None を飛ばしてイテレーションすればよいです。

impl<'world, C> Iterator for SingleComponentExclusiveIter<'world, C>
where
    C: 'static,
{
    type Item = &'world C;

    fn next(&mut self) -> Option<Self::Item> {
        for item in self.iter.by_ref() {
            if item.is_some() {
                return item.as_ref();
            }
        }
        None
    }
}

可変参照版の SingleComponentExclusiveIterMut も同様に実装できます。

System - `PairComponentsRefIter`

2 つの Component の不変参照を受け取る System に対応するイテレータ PairComponentsRefIter を実装します。

方針としては、2 つの SparseVec<T> を前から順に見ていき、両方とも Some だったら値を返すようなイテレータにします。

素朴に考えると以下のような実装になります。

pub struct PairComponentsRefIter<'world, C1, C2>
where
    C1: 'static,
    C2: 'static,
{
    iter1: std::slice::IterMut<'world, Option<C1>>,
    iter2: std::slice::IterMut<'world, Option<C2>>,
}

impl<'world, C1, C2> Iterator for PairComponentsRefIter<'world, C1, C2>
where
    C1: 'static,
    C2: 'static,
{
    type Item = (&'world C1, &'world C2);
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            let next1 = self.iter1.next();
            let next2 = self.iter2.next();
            if next1.is_none() || next2.is_none() {
                return None;
            }
            if let (Some(Some(c1)), Some(Some(c2))) = (next1, next2) {
                return Some((c1, c2));
            } else {
                continue;
            }
        }
    }
}

このコード自体はコンパイルできますが、World から PairComponentsRefIter を作成できません。&'world Components から IterMut<'world, Option<C1>> を取得する関数が必要ですが、実装できないからです。 IterMut<'world, Option<C1>> ではなく Ref<'world, IterMut<'world, Option<C1>>> まで条件を緩めても無理でした。

そのため、イテレータではなくスライスを使用することにします。

まず SparseVec<T> から内部データのスライスを得られるようにします。

impl<T> SparseVec<T> {
    fn data_slice(&self) -> &[Option<T>] {
        &self.data
    }
}

次に Components からスライスの Ref を取得するメソッドを追加します。

impl Components {
    fn borrow_slice<T: 'static>(&self) -> Option<Ref<'_, [Option<T>]>> {
        let refcell = self.map.get(&TypeId::of::<T>())?;
        let slice = Ref::map(refcell.borrow(), |vec| {
            // SAFETY:
            // self.map[TypeId::of<T>] には SparseVec<T> が登録されているので、ダウンキャストは必ず成功する
            unsafe { vec.downcast::<T>().unwrap_unchecked() }.data_slice()
        });
        Some(slice)
    }
}

これで World から PairComponentsRefIter を作れるようになります。

pub struct PairComponentsRefIter<'world, C1, C2>
where
    C1: 'static,
    C2: 'static,
{
    slice1: Option<Ref<'world, [Option<C1>]>>,
    slice2: Option<Ref<'world, [Option<C2>]>>,
}

impl<'world, C1, C2> PairComponentsRefIter<'world, C1, C2>
where
    C1: 'static,
    C2: 'static,
{
    fn from_world(world: &'world mut World) -> Self {
        let slice1 = world
            .components
            .borrow_slice::<C1>()
            .expect("Component not registered");
        let slice2 = world
            .components
            .borrow_slice::<C2>()
            .expect("Component not registered");
        Self {
            slice1: Some(slice1),
            slice2: Some(slice2),
        }
    }
}

最後にイテレータとして使えるように実装します。

前半部分ではスライスの Ref を先頭要素の Ref と残りの部分の Ref に分割しています。もとのスライスを残りの部分で置き換えることで Iterator#next() でイテレータを 1 つ進める処理と同じことをしています。

後半部分では、2 つのスライスの先頭要素が両方 Some だった場合に値を返しています。

impl<'world, C1, C2> Iterator for PairComponentsRefIter<'world, C1, C2>
where
    C1: 'static,
    C2: 'static,
{
    type Item = (Ref<'world, C1>, Ref<'world, C2>);
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            let next1 = match self.slice1.take() {
                Some(borrow) => match *borrow {
                    [] => return None,
                    [_, ..] => {
                        let (head, tail) = Ref::map_split(borrow, |slice| (&slice[0], &slice[1..]));
                        self.slice1.replace(tail);
                        head
                    }
                },
                None => return None,
            };
            let next2 = match self.slice2.take() {
                Some(borrow) => match *borrow {
                    [] => return None,
                    [_, ..] => {
                        let (head, tail) = Ref::map_split(borrow, |slice| (&slice[0], &slice[1..]));
                        self.slice2.replace(tail);
                        head
                    }
                },
                None => return None,
            };
            if next1.is_some() && next2.is_some() {
                let c1 = Ref::map(next1, |v| {
                    // SAFETY: next1 is Some
                    unsafe { v.as_ref().unwrap_unchecked() }
                });
                let c2 = Ref::map(next2, |v| {
                    // SAFETY: next2 is Some
                    unsafe { v.as_ref().unwrap_unchecked() }
                });
                return Some((c1, c2));
            } else {
                continue;
            }
        }
    }
}

可変参照版の PairComponentsRefIterMut も同様に実装できます。

System - `FromWorld` トレイト

イテレータを 4 種類実装しましたが、どれも World から作成できるという共通点があります。FromWorld トレイトを定義してそれぞれのイテレータで実装します。

pub trait FromWorld<'world> {
    fn from_world(world: &'world mut World) -> Self;
}

System - `System` トレイト

System を表す System トレイトを定義し、FromWorld を受け取る関数に対して実装します。

pub trait System<'world, T> {
    fn execute(self, world: &'world mut World);
}

impl<'world, T, F> System<'world, T> for F
where
    T: FromWorld<'world>,
    F: FnOnce(T),
{
    fn execute(self, world: &'world mut World) {
        self(T::from_world(world));
    }
}

World#execute() が実装できるようになります。

impl World {
    pub fn execute<'world, T>(&'world mut self, system: impl System<'world, T>) {
        system.execute(self);
    }
}

これで完成です。

ベンチマーク

念の為ベンチマークを取りました。

横軸は Entity の数、縦軸は実行時間です。bevy_ecs と specs が既存の実装です。これらと比べて極端に遅いわけではないので良いと思います。

まとめ

Rust で ECS ライブラリを実装しました。

感想

今回の実装にはまだまだ改善の余地があります。ストレージの部分についてはメモリ効率が悪い実装になっているため改善したいと考えています。ストレージの実装が変わるとイテレータの作り方も変わってくると思います。また、System の並列処理や実行順序のスケジューリングなどを行うような拡張も考えられます。他の ECS 実装などを読んで ECS の実装方法に対する理解を深めていきたいです。

GameObject や MonoBehavior を使った従来の方法がコンポーネント指向です。最近は Unity DOTS など Unity でも ECS を使うことができるようです。 ↩