Androidゲーム開発：どのデータ構造を使用するのですか？

Question

私はAndroid用ゲームを作っています。私はゲームを秘密に保つように努力しているので、あまりにも多くを明らかにすることはできないので、私にも負担してください。基本的にはリアルタイムで実行されるので（オブジェクトの座標を更新するスレッドを実装します）、そのスタイルはDuck Huntのようなものです。しかし、あなたは画面上を移動するオブジェクトを叩く必要があります。しかし、ゲームは時々（時にはハイエンドデバイスの1つであるSamsung Galaxy Sで実行される）わずかに遅れています。より良いデータ構造。

基本的には、画面上のオブジェクトの最大数を動的にしたいので、配列の代わりにこれらのオブジェクトを二重リンクリストに格納しています。言い換えれば、頭と尾のオブジェクトへの参照があり、すべてのゲームオブジェクトは、典型的なリンクリストのように接続されています。これは、次のような問題を提供します。私は尾部に頭部から横断し、確認する必要があるので、オブジェクトが所与の（画面をタッチすることにより）座標と交差する場合に検索

1. はO（N）時間（最悪の場合）を取り各オブジェクトのヒットボックス。
2. すべてのオブジェクトに対して、そのヒットボックスがリンクリスト内の他のすべてのオブジェクトと交差しているかどうかをチェックする必要があるため、2つのオブジェクト間の衝突チェックにはO（n^2）時間がかかります。

リンクされたリストを選択したもう一つの理由は、基本的に2つのリンクされたリスト（アクティブなオブジェクト（つまり、画面上のオブジェクト）と非アクティブオブジェクト）です。つまり、ゲーム画面に最大8つのオブジェクトが存在するとします。アクティブなリンクリストに5つのオブジェクトがある場合、非アクティブなリストには3つのオブジェクトがあります。 2つのリンクされたリストを使用すると、オブジェクトが非アクティブになるたびに、逆参照したり、ガベージコレクタがメモリを再利用するのを待つのではなく、リンクされていないリストにオブジェクトを追加することができます。また、新しいオブジェクトが必要な場合は、新しいオブジェクトを作成するためにメモリを割り当てなくても、リンクされていないリストからオブジェクトを取り出し、アクティブなリンクリストで使用することができます。

多次元配列の使用を検討しました。この方法では、画面をオブジェクトが存在する「セル」に分割します。たとえば、480x800の画面で、オブジェクトの高さと幅がともに80ピクセルの場合は、画面を6x10グリッドに分割するか、JavaコードのコンテキストでGameObject [6] [10]を作成します。オブジェクトの座標（画面上の座標）を80で割って（グリッド上で）そのインデックスを取得することもでき、O（1）の挿入も可能です。これは、タッチ座標で同じことを実行して適切なインデックスを確認できるので、座標O（1）で検索することもできます。

グリッド内のすべてのセルを調べなければならないため、衝突チェックにO（n^2）時間かかる場合があります（この方法では、セルに隣接する最大8個のセルと比較するだけです）。現在検討中）。

しかし、グリッドのアイデアは、独自の問題を提起：画面は480X800以外の解像度を持つ

1. 場合はどうすれば？また、グリッドを6x10に均等に分割できない場合はどうなりますか？これにより、プログラムのエラーが発生しやすくなります。
2. メモリの点でゲームオブジェクトのグリッドを使用していますか？私がモバイルデバイス用に開発していることを考慮すると、これを考慮する必要があります。

したがって、究極の質問は、私がリンクリスト、多次元配列、または私が考慮していない何かを使うべきかどうかです。優れた衝突検出性能のため

private void checkForAllCollisions() { 
GameObject obj1 = mHead; 

while (obj1 != null) { 
     GameObject obj2 = obj1.getNext(); 
      while (obj2 != null) { 
       //getHitBox() returns a Rect object that encompasses the object 
       Rect.intersects(obj1.getHitBox(), obj2.getHitBox()); 
       //Some collision logic 
      } 
      obj1 = obj1.getNext(); 
     } 
} 

Answer 1

共通のデータ構造quadtrees（2次元）があるとoctrees（3次元）：

以下は、私が衝突を実装しています方法のアイデアです。

リストを貼り付ける場合は、LinkedListを使用していて、ArrayListを使用していない理由がありますか？ I 希望あなたは現在、組み込みのリンクリストの実装を使用している...

---

AサムスンギャラクシーSは、512 MBのRAMを持っている - 単一のデータ構造にあまりにも多くのメモリを占有して心配しないでください（まだ）。このデータ構造が大量のRAMを吸い上げる前に、相対的に重いオブジェクトを比較的多く持たなければなりません。 1000 GameObjectインスタンスがあり、データ構造内の各インスタンス（前記データ構造内にインスタンスを格納する関連の重みを含む）は10,000バイト（これはかなり大きい）ですが、これはまだ9.5メガバイトのメモリです。

Answer 2

私は最初に考慮する必要があると確信しています。

1）LL対アレイ

あなたはLLはあなたを与えるために動的プロパティの配列の代わりにLLを使用していると述べました。しかし、私はあなたがそれがあなたのO（1）の実行時間を与えるamortized（配列がunkept/unsortedされていることを与える）を充填した後、そのサイズを倍増させることで十分に動的な配列を使用することができます）。ただし、データを適切にコピーする必要があるため、今すぐ挿入してもO（n）を取るシナリオがあります。だから、このようなライブゲームでは、LLは良い選択だと思う。

2.）ゲームオブジェクトに関するメモリの考慮。

これは、各ゲームオブジェクトの構造に大きく依存しています。詳細については十分に説明していません。各ゲームオブジェクトに2つのintまたはプリミティブ型しか含まれていない場合は、メモリを買う余裕があります。各GameObjectのメモリが非常に高く、非常に大きなグリッドを使用している場合、メモリのコストは間違いありませんが、各GameObjectのメモリ使用量とグリッドのサイズの両方に依存します。

3.解像度が480x800と異なる場合は、心配しないでください。あなたはすべてのために6×10のグリッドを使用している場合は、そのように密度の乗数を使用することを検討してください：

float scale = getContext().getResources().getDisplayMetrics().density; 

、その後のgetWidth（）とのgetHeight（）デバイスの正確な幅と高さを取得するには、この規模で乗算する必要がありますそれはあなたのアプリを使用しています。これらの数値を6と10で割ることができます。ただし、一部のグリッドでは、このように正しくスケーリングされていても、デバイスによっては見栄えが悪い場合があります。

4.）衝突処理

あなたは衝突処理を行っていると述べました。私はあなたの状況でこれを処理する最良の方法は何も言うことはできませんが（私はあなたの質問に基づいてこれを実際どのように行っているのかまだまだ混乱しています）、これらの選択肢を覚えておいてください：

） Linear Probing b。）Separate Chaining C。）全て明らかにハッシュ衝突の取り扱い方針ですが、再び、あなたはあなたが戻っていくつかの情報を保持しているので、詳細を知っているだろうあなたのゲーム（与えられた実装可能かもしれDouble Hashing

）。しかし、グリッドを使用する場合は、線形プロービングの線に沿って何かを実行したり、2つのハッシュテーブルを作成したりすることもできます（適切な場合は、グリッドレイアウトを取り除いているようです）あなたの裁量を再度達成してください）。また、高速な衝突検出を得るために、ある種のツリー（クアッドツリーのようなもの）を使用することもできます。四分木について分からない場合は、hereをチェックしてください。 1つのアイデアを考える良い方法は、正方形の画像を葉で別々のピクセルに分割し、親ノードで平均色をpruningに格納することです。意味のある四分木について考えてみましょう。

援助されました。また、あなたの質問のあいまいな性質のために何かを誤解しているかもしれないので、私に知らせてください。私は喜んでお手伝いします。