この状況のた​​めの双方向データ構造

Question

私のゲームエンジンの一部を勉強していて、一部の部分を最適化する方法が不思議です。

状況は非常に簡単であり、それは以下の通りです：

• 私は（双方向次元配列に格納されている）Tile Sのマップ持っている（〜260Kのタイルを、しかし、より多くのを想定）
• 私は多くのItem sが連続している
• Tileは、論理的に、ゲーム実行時にはItemの
• の無限の量を含むことができ、常に少なくとも、ほとんどのタイルであるItemのリストを持っていますLY作成し、彼らはすべてのItemが連続隣人の1にそのTile（アップ、右、下、左）を変更し、独自のTile
• から開始

今までのすべてのItemその実際のTileへの参照を持っています私はアイテムのリストを保持しています。 Itemが隣接するタイルに移動するたびに、私はちょうどitem->tile = ..を更新し、私は問題ありません。これは正常に動作しますが、単方向です。

エンジンを拡張しているうちに、タイルに含まれるすべてのアイテムを何度も見つけなければならないことに気付きました。これはパフォーマンスを効果的に低下させます（特に、一部の状況では、一つずつ）。

これは私がO（n）のでより良い特定Tileのすべてのアイテムを見つけるのに適したデータ構造を発見したいと思いますが、私は「1枚のタイルからの移動に多くのオーバーヘッドを回避したいと思います意味（今はポインタを割り当てているので、かなり頻繁にそこで多くの操作をしないようにしたいと思っています）。

アイテムは常に隣のセルに移動していますが、私は現在暗闇の中で突っ走っているという事実を利用するカスタムデータ構造について考えています！どのようなアドバイスも、トリッキーなやりとりのアプローチにも感謝します。残念ながら私は記憶を浪費するだけでは良いトレードオフが必要ではありません。

私はC++でSTLを使用していますが、Boostは使用していません。 （はい、私はおよそmultimapを知っていますか、それは私を満たしていないが、私はもっと良いものが見つからない場合、私はみます）

Answer 1

struct Coordinate { int x, y; }; 
map<Coordinate, set<Item*>> tile_items; 

これは、タイルマップ上の座標を、どのアイテムがそのタイル上にあるかを示すアイテムポインタのセットにマップします。あなたはすべての座標の項目を必要とせず、実際に項目を持つ項目だけが必要です。今、私はあなたがこれを言った知っている：

が、私はその中で多くのオーバーヘッドを追加伴うだろう相

そして、この方法「別のタイル から移動」で多くのオーバーヘッドを回避したいと思います段階。しかし、実際にこのようなことを実際に試してみて、それが問題であると判断しましたか？

Answer 2

私に、私は（IEは、2Dのアクセスを課すマトリックス型にstd::vectorを包むだろう1d配列で）これはあなたのタイルへの高速ランダムアクセスを提供します（行列の実装は簡単です）。インデックス

使用

vector_index=y_pos*y_size+x_pos; 

タイルが有するアイテムの量は多分非常に動的である場合サイズ

vector_size=y_size*x_size; 

のベクトルは、各項目は（アイテムのスタンダード::ベクトルを有することができますこれらはまた、非常に最小限のオーバーヘッドでランダムアクセスを含みます。

私はあなたのユースケースのために間接的なコンテナから遠ざかります。

PS：希望する場合は、私の行列テンプレートを持つことができます。

Answer 3

実際に各タイルにアイテムを格納すると余計なスペースが必要になると思う場合は、クォードツリーを使用してアイテムを保存することを検討してください。これにより、タイルのすべてのアイテムを効率的に取得できますが、タイルグリッドはアイテムの移動に適した場所に残ります。