はじめに
ゲームを作っていると、階層構造を実装したくなることがあります。
階層構造とは、オブジェクトとオブジェクトを紐づけて上下関係を設定するもので、様々なゲームエンジンやモデリングツールでよく見るあれです。
普通に実装する分には可変長配列をオブジェクトごとに用意すれば簡単にできますが、それではデータがメモリ上で分散してしまいます。
そこで今回は、データがメモリ上で連続する階層構造を実装する方法を紹介します。
階層構造に限らず、オブジェクトごとに可変長なデータを扱いたいときに幅広く使える方法なので、データをメモリ上で連続するように管理している方は覚えておいて損はないと思います。
ECSについては、こちらの記事でECSの基本概念と簡単な実装について紹介しているので読んでいただけると嬉しいです。
C++の可変長配列の仕様
たとえば、以下のような構造体があったとします。
この構造体は、メモリ上でこのように配置されます。
一見、可変長配列も構造体内のデータ上に格納されているように見えます。
では、次はこの可変長配列に値E、F、Gを追加してみます。
構造体とは関係ない場所に値を格納するメモリが確保されました。
実は、可変長配列のデータにはメモリ上のどこかに存在する可変長配列へのポインタしか入っていないのです。
そのため、データがメモリ上で連続するように可変長配列のデータを配置しても、肝心の配列の本体は全く関係のない場所に存在するため意味がなくなってしまいます。
(↑頑張ってデータを連続させたのが無駄になってしまう図)
異なる可変長配列のデータを連続させるには
まずはすべてのデータを一つの配列に格納します。
これにより、それぞれの構造体がもつ可変長配列のデータが1か所にまとまり、データが連続しました。
しかし、これではどのデータがどの構造体と紐づいているのか分かりません。そこで登場するのがイテレータパターンです。
イテレータパターン
イテレータパターンとは、自分の前の要素と次の要素がどこにあるのかを保存しておくことで、離れた場所にあるデータ同士を紐づけることができるデザインパターンです。
このようなデータをすべての要素と紐づけることで、データ同士を繋げることができます。
可変長配列を持ちたい構造体は、先頭のイテレータの居場所を覚えておくことでデータの連携が完了します。
これで、可変長なデータ同士もメモリ上で連続するように管理することができました。
それでは、この方法を活かして階層構造を実装してみましょう
データがメモリ上で連続する階層構造
先程まではデータの場所を示す方法として配列の添え字を使用していましたが、ここからはEntityのIDを使用します。
また、階層構造は上下にも関係を持つため、前後だけでなく上下のデータの場所も覚えておく必要があります。
これらの情報を元に、今回使うイテレータのデータ構造はこのようになりました。
先程のイテレータに加え自身も先頭の子のイテレータのIDを覚えておくことで、イテレータ同士で上下関係を構築することができました。
実装
こちらが今回解説した階層構造を実装したものになります。
兄弟と子のIDを使って関数をループさせているだけなので、非常にシンプルな実装になりました。
struct HierarchyComponent
{
// このコンポーネントの持ち主のID
size_t m_ownerID = 0;
// 先頭の子オブジェクトのID
size_t m_firstChildID = 0;
// 兄のID
size_t m_frontBrotherID = 0;
// 弟のID
size_t m_nextBrotherID = 0;
};
// 仮のコンポーネント管理クラス
ECSManager manager;
//
// 階層最上位のEntityのIDを引数に入れることで起動
void HierarchyUpdate(const size_t a_entityID)
{
// 無効なエンティティだったらreturn
if (a_entityID == 0)
{
return;
}
// このエンティティのHierarchtComponentを取得
HierarchyComponent* pHier = manager.GetComponent<HierarchyComponent>(a_entityID);
// 親がいなければreturn
if (pHier->m_parentID == 0)
{
return;
}
~~ 行列合成等の処理 ~~
// 兄弟の行列を更新
if (pHier->m_nextBrotherID != 0)
{
HierarchyUpdate(pHier->m_nextBrotherID);
}
// 子の行列を更新
if (pHier->m_firstChildID != 0)
{
HierarchyUpdate(pHier->m_firstChildID);
}
}
おわりに
冒頭にも紹介したように階層構造に限らず当たり判定の範囲など様々な機能にも使えるものだと思うので、汎用的なクラスにするなど独自にアレンジして使ってみてください。
また、おそらくこれは非常に初歩的な手法だと思うので、より良い方法を知っているという方がいらっしゃいましたら是非コメントやTwitterなどで教えていただけるととても助かります。
Discussion