8

タイル状の2Dマップの領域に、多数のオブジェクトが「エリア効果」を持つゲームを書いています。

必要な機能：

  • これらのエリア効果のいくつかは重複し、同じタイルに影響を与える可能性があります
  • 任意のタイルの効果のリストに非常に効率的にアクセスできる必要があります
  • エリア効果は任意の形状にすることができますが、通常は「効果を引き起こすオブジェクトから最大Xタイルの距離」の形式になります。ここで、Xは小さな整数で、通常は1〜10です。
  • エリア効果は頻繁に変化します。たとえば、オブジェクトがマップ上の別の場所に移動される場合などです。
  • マップは潜在的に大きくなる可能性があります（例：1000 * 1000タイル）

これにはどのデータ構造が最適ですか？

4

5 に答える 5

2

通常、マップの密度に依存します。

すべてのタイル (またはタイルの大部分) に少なくとも 1 つの効果が含まれていることがわかっている場合は、通常のグリッド (タイルの単純な 2D 配列) を使用する必要があります。

マップの塗りつぶしが弱く、空のタイルがたくさんある場合は、四分木、R ツリー、または BSP ツリーなどの空間インデックスを使用するのが理にかなっています。

于 2010-06-28T20:25:30.640 に答える
2

実際に多くのエリア効果が同時に発生していて、それらが任意の形状を持っている場合は、次のようにします。

  • 新しい効果が作成されると、効果のグローバル リストに保存されます (必ずしもグローバル変数ではなく、ゲーム全体または現在のゲーム マップに適用されるものにすぎません)。
  • 影響するタイルを計算し、効果に対してそれらのタイルのリストを保存します
  • これらのタイルのそれぞれに新しい効果が通知され、それへの参照がタイルごとのリストに格納されます (C++ では、これには std::vector を使用します。リンクされたリストではなく、連続したストレージを使用します)。
  • 効果の終了は、関心のあるタイルを反復処理し、それへの参照を削除してから破棄することで処理されます
  • 移動または形状の変更は、上記のように参照を削除し、変更計算を実行してから、影響を受けるタイルに参照を再アタッチすることで処理されます
  • また、マップ全体を反復処理し、エフェクト内のタイルのリストがそれを参照するマップ内のタイルと正確に一致することを確認する、デバッグ専用の不変チェックも必要です。
于 2010-06-29T10:18:24.940 に答える
1

派手なコンピュータサイエンスに依存しないブルートフォースソリューション：

1000x1000は大きすぎません-ただのメガです。コンピューターにはギグがあります。2D配列を持つことができます。バイト内の各ビットは、「領域のタイプ」である可能性があります。より大きな「影響を受ける領域」は別のビットである可能性があります。さまざまなタイプの領域が適度にある場合でも、マルチバイトビットマスクを使用できます。それがばかげている場合は、配列要素を重複するエリアタイプオブジェクトのリストへのポインタにすることができます。しかし、その後、効率が低下します。

また、座標からハッシュテーブルキーを使用してスパース配列を実装することもできます（たとえば、key = 1000 * x + y）が、これは何倍も遅くなります。

もちろん、あなたが派手なコンピュータサイエンスの方法をコーディングすることを気にしないのであれば、それらは通常はるかにうまく機能します！

于 2010-06-28T20:08:41.660 に答える
1

各エリア効果の最大範囲がわかっている場合は、選択したデータ構造を使用して、通常の2D衝突テスト用に最適化された実際のソースのみを保存できます。

次に、タイルへの影響を確認するときは、最大範囲内のすべての影響源を確認し（衝突検出スタイル、データ構造に最適化）、定義されたテスト関数を適用します（たとえば、領域が円の場合は、確認します）。距離が定数未満の場合、正方形の場合は、x距離とy距離がそれぞれ定数内にあるかどうかを確認します）。

エフェクトの「フィールド」シェイプの量が少ない（<10）場合は、事前に計算された最大範囲内で、エフェクトフィールドタイプごとに一意の衝突検出を実行することもできます。

于 2010-06-29T07:29:31.087 に答える
1

通常、BSP-Trees（またはquadtreesまたはoctrees）。

于 2010-06-28T20:03:40.213 に答える