階層構造のための構造コンポーネントストレージ

Question

私はこの問題を数日前から頭に浮かべていましたが、満足のいく結論に達していないので、私は彼らの意見をSOの乗組員に尋ねると考えました。私が作業しているゲームでは、hereとhereのようにコンポーネントオブジェクトモデルを使用しています。実際にはかなりうまくいっていますが、私の現在のストレージソリューションは制限されています（クラス名または任意の "ファミリ"名でコンポーネントを要求することができます）。私が望むのは、与えられた型を要求し、その型のすべてのコンポーネントまたはそれから派生した型を反復する能力です。

これを考慮すると、基本クラス型を派生型でその順序で格納する簡単なRTTIスキームが最初に実装されました。つまり、スプライトのRTTIは：component :: renderable :: spriteです。これにより、Bのすべての要素を単純に比較することによって、型AとBを派生させるかどうかを簡単に比較できます。つまり、component :: renderable :: spriteはcomponent :: renderableから派生していますが、component :: timerではありません。シンプルで、効果的で、すでに実装されています。

私が今したいのは、その階層を表す方法でコンポーネントを保存する方法です。各ノードで

 component 
    /  \ 
    timer   renderable 
/   / \ 
shotTimer sprite  particle 

私はそのタイプのすべてのコンポーネントのリストを格納します：心に来る最初の事はそうのようなノードとしてのタイプを使用して、ツリー、です。このようにして、 "component :: renderable"ノードを要求すると、派生型に関係なく、すべてのレンダリング可能なコンポーネントにアクセスできます。

for_each(renderable.begin(), renderable.end(), renderFunc); 

とレンダリング可能なダウンからツリー全体にわたりその反復を持っている：RUBは、私がこのような何かを行うことができるように、イテレータでそれらのコンポーネントにアクセスできるようにしたいということです。私はこれをかなり醜いmap/vector/treeノード構造と私が行った場所のノードスタックを追跡するカスタム順方向イテレータを使って動作させています。しかし、実装している間は、より良い、より明確な方法が必要であると感じました...私はちょうど考えることができません:(

これは不必要に複雑ですか？いくつかの明白な単純化は、私が行方不明、または私が使用してしなければならない構造を既存の？それとも、このちょうどinheritly複雑な問題であり、私はおそらくあなたが持っている任意の入力に対してうまくすでに？

感謝をやってるんだよ！

Answer 1

あなたは次のことを行う頻度について考えるべきです：

• ツリー
• トラバースあなたはより頻繁にはどれ

を追跡する必要がありますどのように多くのオブジェクトツリー

から要素を追加/削除する代わりに、メイクのおそらく最適なソリューション

を判断するのに役立ちます複雑なツリーで、すべての型のリストを持ち、そこから派生する各型のオブジェクトへのポインタを追加するだけです。このような何か：複数のリスト内の各obejctを登録することにより

map<string,set<componenet *>> myTypeList 

次に型コンポーネントであるオブジェクトについて::レンダリング可能::スプライト

myTypeList["component"].insert(&object); 
myTypeList["renderable"].insert(&object); 
myTypeList["sprite"].insert(&object); 

は、それがすべてに何かをすることが容易になります指定された型のオブジェクトとサブタイプ

はstd ::

for_each(myTypeList["renderable"].begin(),myTypeList["renderable"].end(),renderFunc); 

注意して、私のstd ::マップの構築物は、あなたがそれを使用する方法に応じて、最適な選択ではないかもしれません。

それともツリー

map<string, set<string> > myTypeList; 
map<string, set<component *> myObjectList; 

myTypeList["component"].insert("component"); 
myTypeList["component"].insert("renderable"); 
myTypeList["component"].insert("sprite"); 
myTypeList["renderable"].insert("renderable"); 
myTypeList["renderable"].insert("sprite"); 
myTypeList["sprite"].insert("sprite"); 

// this isn't quite right, but you get the idea 
struct doForList { 
    UnaryFunction f; 
    doForList(UnaryFunction f): func(f) {}; 
    operator()(string typename) { 
     for_each(myTypeList[typename].begin();myTypeList[typename].end(), func); 
    } 
} 

for_each(myTypeList["renderable"].begin(),myTypeList["renderable"].end(), doForList(myFunc)) 

Answer 2

で唯一のクラス階層構造を保存するハイブリッドアプローチの答えは、あなたがそれらに必要な順序に依存します。あなたはかなりinorderを前順、後順との選択肢を持っています。したがって、幅広い最初と深みの最初の検索で明らかな類似点を持っており、一般的にはそれらを打つのに問題があります。

問題をlitleに制約すると、配列として任意のデータのツリーを格納するための古い形式のアルゴリズムがいくつかあります。私たちはFORTRANの時代にそれらを多く使いました。そのうちの1人は、Aの子をA2（インデックス）（A）* 2、index（A）* 2 + 1に格納するという重要なトリックを持っていました。問題は、ツリーが疎であればスペースを無駄にし、ツリーのサイズは配列のサイズによって制限されるということです。しかし、私がこの権利を覚えていれば、単純なDOループで幅優先順に要素を取得します。

クヌス第3巻をご覧ください。そこにはそのようなもののトーンがあります。

Answer 3

既存の実装のコードを見たい場合は、Cowboyプログラミングページで参照されているGame Programming Gems 5の記事に、私たちがコンポーネントシステムで使用したコードを少し削除しました（私はかなりのその記事で説明されているシステムの設計と実装）。

私は戻ってコードを再チェックする必要があります。私は今はできません。私たちは、あなたが表示する方法で階層内のものを表現しませんでした。コンポーネントはコード内のクラス階層に存在していましたが、ランタイム表現はフラットなリストでした。コンポーネントは実装したインタフェースのリストを宣言しました。ユーザは、インタフェースや具体的な型を問い合わせることができます。

したがって、SpriteとParticleはRENDERABLEインターフェイスを実装していると宣言し、すべてのレンダラブルに対して何かを実行したい場合は、アクティブなコンポーネントのリストをループしてそれぞれをチェックします。それに直面しても非常に効率的ではありませんでしたが、実際には問題ありませんでした。それが問題ではなかった主な理由は、実際にはあまり一般的でない操作であることが実際に判明したことでした。例えば、レンダラブルのようなものは、作成時にレンダリングシーンに追加されたため、グローバルシーンマネージャは、レンダリング可能なオブジェクトの独自のリストを保持し、それらのコンポーネントシステムを照会する必要はありませんでした。同様に、phyicsや衝突のコンポーネントとそのようなもの。