15

ゲーム エンジンのエンティティ コンポーネント システムに取り組んでいます。私の目標の 1 つは、最適なデータ処理のためにデータ指向のアプローチを使用することです。言い換えれば、構造体の配列よりも配列の構造体が欲しいというガイドラインに従いたいのです。ただし、私の問題は、これを解決するためのきちんとした方法を見つけることができなかったことです。

これまでの私の考えでは、システム内のすべてのコンポーネントがゲームロジックの特定の部分を担当し、重力コンポーネントが質量、速度などに応じてフレームごとに力を計算し、他のコンポーネントが他のものを処理するとします。したがって、すべてのコンポーネントは異なるデータセットに関心があります。重力コンポーネントは質量と速度に関心があるかもしれませんが、衝突コンポーネントはバウンディング ボックスと位置などに関心があるかもしれません。

これまでのところ、属性ごとに 1 つの配列を保存するデータ マネージャーを使用できると考えました。つまり、エンティティには、重量、位置、速度などの 1 つ以上があり、一意の ID を持つとします。データ マネージャーのデータは次のように表されます。ここで、すべての数字はエンティティ ID を表します。

weightarray ->   [0,1,2,3]
positionarray -> [0,1,2,3]
velocityarray -> [0,1,2,3]

このアプローチは、すべてのエンティティがそれぞれの属性を持っている場合にうまく機能します。ただし、エンティティ 0 と 2 のみがすべての木の属性を持ち、他のエンティティが移動しないタイプのエンティティである場合、それらには速度がなく、データは次のようになります。

weightarray ->   [0,1,2,3]
positionarray -> [0,1,2,3]
velocityarray -> [0,2]     //either squash it like this
velocityarray -> [0  ,2  ]     //or leave "empty gaps" to keep alignment

突然、それを反復するのは簡単ではありません。反復処理と速度の操作のみに関心のあるコンポーネントは、2 番目のアプローチで行った場合、何らかの方法で空のギャップをスキップする必要があります。配列を短くする最初のアプローチは、より複雑な状況ではうまく機能しません。3 つの属性すべてを持つ 1 つのエンティティ 0、重量と位置のみを持つ別のエンティティ 1、位置と速度のみを持つエンティティ 2 があるとします。最後に、重みだけを持つ最後のエンティティ 3 が 1 つあります。押しつぶされた配列は次のようになります。

weightarray ->   [0,1,3]
positionarray -> [0,1,2]
velocityarray -> [0,2]

他のアプローチでは、次のようなギャップが残ります。

weightarray ->   [0,1, ,3]
positionarray -> [0,1,2, ]
velocityarray -> [0, ,2, ]

これらの状況はどちらも、少数の属性しか持たないエンティティーのセットを反復することにのみ関心がある場合、反復するのは自明ではありません。特定のコンポーネント X は、たとえば位置と速度を持つエンティティの処理に関心があります。反復可能な配列ポインタを抽出して、このコンポーネントに計算を実行させるにはどうすればよいですか? 要素が隣り合っている配列を指定したいのですが、それは不可能に思えます。

私は、すべての配列にビットフィールドを用意し、どのスポットが有効で、どのスポットがギャップであるかを記述する、または穴のない一時的な配列にデータをコピーしてからコンポーネントに与えるシステムなどのソリューションについて考えてきました。アイデアはありましたが、私が考えたものはエレガントではなく、処理のための追加のオーバーヘッドがありませんでした (データが有効かどうかの追加のチェック、またはデータの追加のコピーなど)。

誰かが似たような経験をしたり、この問題を追求するのに役立つアイデアや考えを持っていることを願っているので、ここで質問しています. :) また、このアイデア全体がくだらないものであり、正しく理解することが不可能であり、代わりにもっと良いアイデアがある場合は、教えてください. 質問が長すぎたり、雑然としたりしないことを願っています。

ありがとう。

4

4 に答える 4

12

良い質問。ただし、私が知る限り、この問題に対する直接的な解決策はありません。複数の解決策があります (その一部はあなたが言及したものです) が、すぐに解決できる特効薬はありません。

まずはゴールを見てみましょう。目標は、すべてのデータを線形配列に配置することではなく、目標を達成するための手段にすぎません。目標は、キャッシュ ミスを最小限に抑えてパフォーマンスを最適化することです。それで全部です。OOP オブジェクトを使用する場合、エンティティ データは必ずしも必要ではないデータに囲まれます。アーキテクチャのキャッシュ ライン サイズが 64 バイトで、重み (float)、位置 (vec3)、および速度 (vec3) のみが必要な場合は、28 バイトを使用しますが、残りの 36 バイトはとにかくロードされます。さらに悪いことに、これらの 3 つの値がメモリ内で並んでいない場合や、データ構造がキャッシュ ラインの境界とオーバーラップしている場合、実際に使用される 28 バイトのデータに対して複数のキャッシュ ラインをロードすることになります。

これを数回行うと、これはそれほど悪くはありません。何百回やってもほとんど気にならない。ただし、これを毎秒何千回も行うと、問題になる可能性があります。したがって、線形アクセス パターンがある状況では、通常は変数ごとに線形配列を作成することにより、キャッシュ使用率を最適化する DOD に入ります。あなたの場合、重量、位置、速度の配列です。1 つのエンティティの位置を読み込むと、再び 64 バイトのデータが読み込まれます。ただし、位置データは配列内に並んでいるため、1 つの位置値をロードするのではなく、隣接する 5 つのエンティティのデータをロードします。更新ループの次の繰り返しでは、キャッシュに既に読み込まれている次の位置の値が必要になる可能性が高く、6 番目のエンティティでのみメイン メモリから新しいデータを読み込む必要があります。

したがって、DOD の目標は線形配列を使用することではなく、(ほぼ) 同時にアクセスされるデータをメモリ内で隣接して配置することにより、キャッシュの使用率を最大化することです。ほぼ常に 3 つの変数に同時にアクセスする場合、変数ごとに 3 つの配列を作成する必要はありません。これらの 3 つの値のみを含む構造体を簡単に作成し、これらの構造体の配列を作成することができます。最適なソリューションは、常にデータの使用方法によって異なります。アクセス パターンが線形であるが、常にすべての変数を使用するとは限らない場合は、個別の線形配列を使用してください。アクセス パターンがより不規則であるが、常にすべての変数を同時に使用する場合は、それらを構造体にまとめて、それらの構造体の配列を作成します。

したがって、短い形式で答えがあります。それはすべて、データの使用状況に依存します。これが、あなたの質問に直接答えることができない理由です。あなたのデータをどのように扱うかについていくつかのアイデアを提供することができます.あなたの状況で最も役立つものを自分で決めることができます.

最もアクセスされたデータを連続した配列に保持できます。たとえば、位置は多くの異なるコンポーネントで頻繁に使用されるため、連続配列の最有力候補です。一方、重量は重力コンポーネントによってのみ使用されるため、ここにギャップが生じる可能性があります。最も使用頻度の高いケースに合わせて最適化したので、使用頻度の低いデータのパフォーマンスは低下します。それでも、私はいくつかの理由でこのソリューションの大ファンではありません。まだ効率が悪い、空のデータをロードしすぎる、#特定のコンポーネント/#合計エンティティの比率が低いほど、悪化します。エンティティの 8 つに 1 つだけが重力コンポーネントを持ち、これらのエンティティがアレイ全体に均等に分散している場合でも、更新ごとに 1 つのキャッシュ ミスが発生します。また、すべてのエンティティが位置 (または共通の変数) を持つことを前提としています。エンティティを追加および削除するのは難しく、柔軟性がなく、単純に醜いです(とにかく私見)。しかし、それは最も簡単な解決策かもしれません。

これを解決する別の方法は、インデックスを使用することです。コンポーネントのすべての配列はパックされますが、追加の配列が 2 つあります。1 つはコンポーネント配列インデックスからエンティティ ID を取得するためのもので、もう 1 つはエンティティ ID からコンポーネント配列インデックスを取得するためのものです。位置はすべてのエンティティで共有され、重量と速度は重力によってのみ使用されるとしましょう。パックされた重量と速度の配列を繰り返し処理し、対応する位置を取得/設定するには、gravityIndex -> entityID 値を取得し、Position コンポーネントに移動し、その entityID -> positionIndex を使用して、位置配列。利点は、重量と速度のアクセスでキャッシュ ミスが発生しなくなることですが、# 重力コンポーネント / # 位置コンポーネントの比率が低い場合は、位置のキャッシュ ミスが発生します。また、追加の 2 つの配列ルックアップも取得しますが、ほとんどの場合、16 ビットの unsigned int インデックスで十分であるため、これらの配列はキャッシュにうまく収まります。つまり、ほとんどの場合、これは非常に高価な操作ではない可能性があります。それでもプロフィールプロフィールプロフィールはこれで安心!

3 番目のオプションは、データの複製です。さて、重力コンポーネントの場合、これは努力する価値がないと確信しています。計算量が多い状況ではより興味深いと思いますが、とにかく例として取り上げましょう。この場合、Gravity コンポーネントには、重量、速度、位置の 3 つのパック配列があります。また、2 番目のオプションで見たものと同様のインデックス テーブルもあります。Gravity コンポーネントの更新を開始するときは、最初に、例 2 のようにインデックス テーブルを使用して、Position コンポーネントの元の位置配列から位置配列を更新します。これで、最大キャッシュで直線的に計算を実行できる 3 つのパックされた配列ができました。利用。完了したら、インデックス テーブルを使用してポジションを元のポジション コンポーネントにコピーします。さぁ、これで」重力のようなものに使用する場合、2 番目のオプションよりも高速 (実際にはおそらく低速) になります。ただし、エンティティが相互に対話するコンポーネントがあり、更新パスごとに複数の読み取りと書き込みが必要であると仮定すると、これはより高速になる可能性があります。それでも、すべてはアクセスパターンに依存します。

私が言及する最後のオプションは、変更ベースのシステムです。これをメッセージング システムのようなものに簡単に適応させることができます。この場合、変更されたデータのみを更新します。Gravity コンポーネントでは、ほとんどのオブジェクトがそのまま床に置かれていますが、いくつかは落下しています。Gravity コンポーネントには、位置、速度、重量の配列がパックされています。更新ループ中にポジションが更新された場合は、エンティティ ID と新しいポジションを変更リストに追加します。完了したら、これらの変更を、位置の値を保持している他のコンポーネントに送信します。他のコンポーネント (たとえば、プレーヤー コントロール コンポーネント) が位置を変更した場合と同じ原理で、変更されたエンティティの新しい位置が送信されます。Gravity コンポーネントはそれをリッスンし、位置配列内のそれらの位置のみを更新できます。君は' 前の例と同じように大量のデータを複製しますが、更新サイクルごとにすべてのデータを再読み取りする代わりに、データが変更されたときにのみデータを更新します。少量のデータが各フレームで実際に変更される状況では非常に便利ですが、大量のデータが変更されると効果がなくなる可能性があります。

したがって、特効薬はありません。多くのオプションがあります。最適なソリューションは、状況、データ、およびそのデータの処理方法に完全に依存します。私が挙げた例のどれもがあなたに適していないかもしれません。すべてのコンポーネントが同じように動作する必要はありません。変更/メッセージ システムを使用するものもあれば、インデックス オプションを使用するものもあります。多くの DOD パフォーマンス ガイドラインは、パフォーマンスが必要な場合に優れていますが、特定の状況でのみ役立つことに注意してください。DOD は、常に配列を使用することではなく、キャッシュの使用率を常に最大化することでもありません。これは、実際に重要な場合にのみ行う必要があります。プロフィール プロフィール プロフィール。あなたのデータを知ってください。データ アクセスのパターンを把握します。(キャッシュ) アーキテクチャを理解します。あなたがそれをすべてやると、あなたがそれについて考えるときに解決策が明らかになります:)

お役に立てれば!

于 2013-03-14T18:07:05.960 に答える
7

解決策は、最適化できる範囲に限界があることを実際に受け入れることです。

ギャップの問題を解決すると、次のことが導入されるだけです。

  • データの例外 (コンポーネントが欠落しているエンティティ) を処理するための If ステートメント (分岐)。
  • ホールを導入すると、リストをランダムに反復することもできます。DoD の強みは、すべてのデータが密にパックされ、処理される方法で順序付けられることです。

やりたいこと:

さまざまなシステム / ケースに最適化されたさまざまなリストを作成します。フレームごと: あるシステムから別のシステムにプロパティをコピーする必要があるエンティティ (特定のコンポーネントを持つ) のみにコピーします。

次の簡略化されたリストとその属性を持つ:

  • 剛体(力、速度、変換)
  • 衝突(境界ボックス、変換)
  • ドローアブル(texture_id、shader_id、transform)
  • Rigidbody_to_collision (rigidbody_index、collision_index)
  • collision_to_rigidbody (collision_index、rigidbody_index)
  • rigidbody_to_drawable (rigidbody_index, drawable_index)

等...

プロセス/ジョブについては、次のものが必要になる場合があります。

  • RigidbodyApplyForces(...)、力 (重力など) を速度に適用します
  • RigidbodyIntegrate(...)、変換に速度を適用します。
  • RigidbodyToCollision(...)、衝突コンポーネントを持つエンティティに対してのみ、rigidbody 変換を衝突変換にコピーします。「rigidbody_to_collision」リストには、どのリジッドボディ ID をどのコリジョン ID にコピーするかのインデックスが含まれています。これにより、衝突リストがぎっしり詰まった状態になります。
  • RigidbodyToDrawable(...)、 Rigidbody 変換を描画コンポーネントを持つエンティティの描画可能な変換にコピーします。「rigidbody_to_drawable」リストには、どのリジッドボディ ID をどのドローアブル ID にコピーするかのインデックスが含まれています。これにより、drawabkl リストがぎっしり詰まった状態になります。
  • CollisionUpdateBoundingBoxes(...)、新しい変換を使用してバウンディング ボックスを更新します。
  • CollisionRecalculateHashgrid(...)、境界ボックスを使用してハッシュグリッドを更新します。負荷を分散するために、これをいくつかのフレームに分割して実行することをお勧めします。
  • CollisionBroadphaseResolve(...)、ハッシュグリッドなどを使用して可能な衝突を計算します....
  • CollisionMidphaseResolve(...)、ブロードフェーズなどのバウンディング ボックスを使用して衝突を計算します。
  • CollisionNarrowphaseResolve(...)、ミッドフェーズなどのポリゴンを使用して衝突を計算します....
  • CollisionToRigidbody(...)、衝突するオブジェクトの反力を Rigidbody 力に追加します。「collision_to_rigidbody」リストには、どのリジッドボディ ID にフォースを追加する必要があるコリジョン ID のインデックスが含まれています。「reactive_forces_to_be_added」という別のリストを作成することもできます。これを使用して、力の追加を遅らせることができます。
  • RenderDrawable(...)、ドローアブルを画面にレンダリングします (レンダラーは単純化されています)。

もちろん、さらに多くのプロセス/ジョブが必要になります。おそらく、ドローアブルをオクルードして並べ替えたり、物理演算とドローアブルの間に変換グラフ システムを追加したりする必要があるでしょう (これを行う方法については、Sony のプレゼンテーションを参照してください)。ジョブの実行は、複数のコアに分散して実行できます。複数のリストに分割できるため、すべてが単なるリストである場合、これは非常に簡単です。

エンティティが作成されると、コンポーネント データも一緒に作成され、同じ順序で格納されます。つまり、リストはほとんど同じ順序のままです。

「オブジェクトからオブジェクトへのコピー」プロセスの場合。穴のスキップが本当に問題なっている場合は、常に「オブジェクトの並べ替え」プロセスを作成できます。このプロセスは、各フレームの最後に、複数のフレームに分散して、オブジェクトを最適な順序に並べ替えます。穴のスキップが最も少ない順序。穴をスキップすることは、すべてのリストを可能な限りぎっしり詰め込み、処理される方法で順序付けできるようにするために支払う代償です。

于 2013-03-14T16:12:48.150 に答える
3

データの構造化に取り組むのではなく、過去にこのようなことをどのように行ったかについての展望を提供したいと思います.

ゲーム エンジンには、ゲーム内のさまざまなシステム (InputManager、PhysicsManager、RenderManager など) を担当するマネージャーのリストがあります。

3D の世界のほとんどのものは Object クラスによって表され、各オブジェクトは任意の数のコンポーネントを持つことができます。各コンポーネントは、オブジェクトの動作のさまざまな側面を担当します (RenderComponent、PhysicsComponent など)。

物理コンポーネントは、物理メッシュをロードし、質量、密度、重心、慣性応答データなどの必要なすべてのプロパティを与えます。このコンポーネントには、位置、回転、線速度、角速度など、世界に存在した物理モデルに関する情報も格納されていました。

PhysicsManager は、物理コンポーネントによってロードされたすべての物理メッシュの情報を持っていたため、そのマネージャーは、衝突検出、衝突メッセージのディスパッチ、物理レイ キャストの実行など、すべての物理関連タスクを処理できました。

少数のオブジェクトだけが必要とする特殊な動作が必要な場合は、そのコンポーネントを作成し、そのコンポーネントに速度や摩擦などのデータを操作させます。これらの変更は PhysicsManager によって確認され、物理シミュレーションで考慮されます。

データ構造に関する限り、前述のシステムを使用して、いくつかの方法で構造化できます。通常、オブジェクトはベクターまたはマップに保持され、コンポーネントはオブジェクトのベクターまたはリストに保持されます。物理情報に関する限り、PhysicsManager には配列/ベクトルに格納できるすべての物理オブジェクトのリストがあり、PhysicsComponent にはその位置、速度、およびその他のデータのコピーがあり、あらゆることができるようになっています。そのデータを物理マネージャーで操作する必要があります。たとえば、オブジェクトの速度を変更したい場合は、PhysicsComponent に伝えるだけで、その速度値を変更してから PhysicsManager に通知します。

ここで、オブジェクト/コンポーネント エンジン構造の主題について詳しく説明します: https://gamedev.stackexchange.com/a/23578/12611

于 2013-03-13T16:46:16.227 に答える