6

ゲーム エンジンの一部を研究していて、一部を最適化する方法を考えています。

状況は非常に単純で、次のとおりです。

  • s のマップがありますTile(2 次元配列に格納されています) (~260k タイルですが、それ以上の数を想定しています)
  • Item私は常に少なくとも 1 つのタイルと最大 1 つのタイルにある のリストを持っています
  • ATileは論理的に無限の量のItemsを含むことができます
  • ゲームの実行中、多くItemの が継続的に作成され、それらは独自のものから始まりますTile
  • 連続Item的Tileに隣接するもの (上、右、下、左) のいずれかに変化します。

これまで、 everyItemには実際の への参照がありTile、アイテムのリストを保持しているだけです。Item隣接するタイルに移動するたびに、更新するだけitem->tile = ..で問題ありません。これは正常に機能しますが、単方向です。

エンジンを拡張しているときに、タイルに含まれるすべてのアイテムを何度も検索する必要があり、これが事実上パフォーマンスを低下させていることに気付きました (特に、一連のタイルのすべてのアイテムを 1 つずつ検索する必要がある場合)。 .

これは、 O(n)Tileよりも優れた特定のすべてのアイテムを見つけるのに適したデータ構造を見つけたいことを意味しますが、「あるタイルから別のタイルに移動する」フェーズでのオーバーヘッドを大幅に回避したいと考えています (現在は単にポインターを割り当てる場合、非常に頻繁に行われるため、そこで多くの操作を行うことは避けたいと思います)。

アイテムが常に隣のセルに移動するという事実を利用するためのカスタム データ構造について考えていますが、現在暗闇の中で手探り中です! トリッキーなアプローチや不可解なアプローチであっても、アドバイスをいただければ幸いです。残念ながら、メモリを無駄にすることはできないため、適切なトレードオフが必要です。

STLを使用してC++で開発していますが、Boostは使用していません。（はい、私は知っていますmultimap、それは私を満足させませんが、他に良いものが見つからない場合は試してみます）

4

3 に答える 3

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

これにより、タイルマップ上の座標が、そのタイル上にあるアイテムを示すアイテムポインターのセットにマップされます。すべての座標にエントリは必要ありません。実際にアイテムが含まれている座標のみが必要です。今、私はあなたがこれを言ったことを知っています：

ただし、「あるタイルから別のタイルへの移動」フェーズでは、多くのオーバーヘッドを回避したいと思います。

そして、この方法では、そのフェーズでオーバーヘッドを追加する必要があります。しかし、実際にこのようなことをまだ試し、それが問題であると判断したことがありますか？

于 2012-04-16T14:49:44.417 に答える
0

各タイルにアイテムを格納するとスペースがかかりすぎると本当に思う場合は、四分木を使用してアイテムを格納することを検討してください。これにより、タイル上のすべてのアイテムを効率的に取得できますが、アイテムの移動のためにタイル グリッドがそのまま残ります。

于 2012-07-05T20:24:54.740 に答える
0

私には、std::vectora をマトリックス型にラップします（つまり、1d配列に2dアクセスを課します）これにより、任意のタイルへの高速ランダムアクセスが可能になります（マトリックスの実装は簡単です）。

使用する

 vector_index=y_pos*y_size+x_pos;

サイズのベクトルにインデックスを付ける

 vector_size=y_size*x_size;

次に、各アイテムにアイテムの std::vector を含めることができます (タイルに含まれるアイテムの量が非常に動的である場合は、deque の可能性があります)。これらは、オーバーヘッドが非常に少ないランダム アクセスの内容です。

あなたのユースケースでは、間接的なコンテナには近づきません。

PS: 必要に応じて、私のマトリックス テンプレートを使用できます。

于 2012-04-16T14:26:45.507 に答える