5

私は最近、データ指向設計の利点を発見しました。とても印象的です。ポイントの 1 つは、タイプとアクセスごとにデータをグループ化することです。すべてをオブジェクトにまとめるのではなく、配列にまとめて、キャッシュ ミスを防ぎ、処理を改善します。

そのため、ゲームではまだインスタンスがあり、ユーザーはそれらのいずれかを破棄できます (配列内に残るだけではありません)。配列の途中でオブジェクトの削除を効果的に処理する方法がわかりません。

私には 1 つの考えがあります:isAlive値を持つことですが、すべてのオブジェクトが処理、描画などで何度もチェックされるため、多くの条件に非常に大きな影響を与えます...

もう 1 つのアイデアは、削除する必要があるスペースを埋めるために配列全体をシフトすることですが、これは削除時に多くのリソースを消費します。

DODでこれをどのように処理できますか？

したがって、要件を提示します。

  • DOD で説明されているキャッシュ ミスを減らすには、配列にする必要があります。
  • 高速なランダム位置オブジェクトの削除が必要です。最大 o(log n)
  • オブジェクトは作成されてから移動できません。不明な場所で参照される可能性があるため、プログラムの誤動作を引き起こす可能性があります
4

2 に答える 2

5

実際には非常に簡単です。直接参照を使用しないでください。IDなどの間接参照のレイヤーを使用します。例えば：

すべてのFoo「オブジェクト」（OOPの意味でのオブジェクトではなく、各Fooプロパティの配列のコレクション）を管理するFooManagerがあるとします。私が理解しているように、あなたが今していることはただインデックスを返すことです。Foo＃42は、すべての配列のインデックス42にデータが配置されているFooであるとしましょう。次に、配列に穴を開けるFoo＃42を削除します。他のすべての配列エントリを移動することはできますが、Foo＃43は実際のインデックス43をポイントしなくなります。

したがって、IDテーブルを追加し、インデックスを返す代わりにIDを返します。新しいFooを作成するときは、そのデータを配列の最初の空きインデックスに追加します（たとえば42）。次に、新しい未使用のID（たとえば、1337）を生成します。これで、IDテーブルを更新して（（ハッシュ）マップはこれに最適です）、ID 1337がインデックス42を指すようにすることができます。これで、ID1337を呼び出し元の関数に返すことができます。（呼び出し元の関数がデータが実際に格納されている場所を検出しないことに注意してください。これは無関係な情報です）

次回Fooを別のコードから更新する必要がある場合は、IDが使用されます。したがって、FooManagerのsetBar関数は、ID1337と新しいBar値を引数として呼び出されます。FooManagerはIDテーブルで1337を検索し、それがまだインデックス42にあることを確認し、Bar配列インデックス42を新しいBar値で更新します。

ここで、このシステムがその値を取得します。Foo1337を削除しましょう。FooManagerのremoveFooは、引数としてID1337で呼び出されます。1337を検索し、インデックス42にあります。ただし、その間に、10個の新しいFooが追加されました。したがって、現在できることは、インデックス42の値を52の値に置き換えるだけで、52から42に効果的に移動します。これは古いシステムで大きな問題を引き起こしますが、今はインデックステーブルを更新するだけで済みます。そこで、どのIDが52を指しているか（たとえば、1401）を調べて42に更新します。次に誰かがFooをID 1401で更新しようとすると、インデックステーブルで調べて、インデックス42にあることがわかります。

そのため、データを連続メモリに保持し、削除にかかるデータコピー操作の数は非常に少なく（Fooのプロパティごとに1つのコピー）、FooManagerの「外部」のコードは何かが起こったことに気付くことさえありません。それは死んだrefenceの問題さえ解決します。いくつかのコードがまだ削除された1337IDを持っていると仮定します（ぶら下がっている参照、これは悪いです！）、それがアクセス/変更しようとすると、FooManagerはそれを調べ、1337が存在しないことを確認し（もう）、きれいな警告を生成できます/ errorとcallstack。これにより、どのコードにまだぶら下がっている参照があるかを直接識別できます。

唯一の欠点は、IDテーブルでの余分なルックアップです。これで、ハッシュテーブルは非常に高速になりますが、Fooオブジェクトを変更するたびに追加の操作が必要になります。ただし、ほとんどの場合、マネージャーの外部からのアクセスは、マネージャーの内部へのアクセスよりもはるかに少なくなります。BulletManagerを使用すると、フレームごとに各弾丸が更新されますが、弾丸にアクセスして何かを変更/要求したり、弾丸を作成/削除するための呼び出しが発生する可能性は低くなります。ただし、これが逆の場合は、その状況に合わせて最適化するためにデータ構造を更新する必要があります。繰り返しになりますが、このような状況では、データがメモリ内のどこにあるかはそれほど重要ではないため、配列に「穴」があるか、まったく異なるデータレイアウトを使用することもできます。

于 2013-02-20T14:48:08.043 に答える
0

制約とワークロードによって異なりますが、削除された要素を配列の最後の要素と交換してから、削除された要素を末尾から削除する方法があります ( pop_back)。これは、配列の順序が特に重要ではないことを前提としています。もう 1 つのアプローチはスパース配列です。これは、メモリ バジェットが固定されている環境で機能する可能性があります。

shared_ptr::resetEDIT：配列への外部ポインタを維持している場合、配列要素が移動されたときに基になるアドレスが更新される（）スマートポインタを使用して管理できます。同じ長さの 2 つの並列配列になってしまいます。

typedef std::vector<thing> thingVec;
thingVec things;

// smart pointers for each object
std::vector<boost::shared_ptr<thingVec::iterator>> references;

createThing関数では、カスタム デリータを使用して a を返します(shared_ptrすべての参照が消滅すると、自動的に配列の更新が行われます)。

http://www.boost.org/doc/libs/1_51_0/libs/smart_ptr/sp_techniques.html#static

スマート ポインターは、要素が削除されたときにどの配列を圧縮するかをカスタム デリーターが認識している限り、最終的に異なる配列に格納される複数のフィールドを持つ構造体を指すことができます。

于 2012-10-06T19:31:19.253 に答える