2

私はAndroidでこのゲームを書いています。そこでは、たくさんのキャラクターが動き回り、互いに衝突します。すべて正常に動作しますが、画面上で一定数の文字を同時に通過すると、アプリのパフォーマンスが大幅に低下します。私はテストを行いましたが、描画によってフレームレートが低下することはありません。これは、衝突検出のアルゴリズムです。移動するたびに、他のすべてのキャラクターの位置を確認する必要があるためです。だから現在、私はキャラクターごとにそれらすべてをループしているだけです。これを改善する方法はありますか？私が知らない多数のオブジェクトの衝突検出にパフォーマンスのトリックはありますか？

4

4 に答える 4

3

はい、最初の広相および2番目の狭相の衝突検出に基づく技術があります。

MarioZechnerによる「 BeginningAndroidGames」からいくつかのパラグラフを引用します。

ブロードフェーズ：このフェーズでは、どのオブジェクトが潜在的に衝突する可能性があるかを把握しようとします。それぞれが互いに衝突する可能性のある100個のオブジェクトがあると想像してください。各オブジェクトを他のオブジェクトに対して単純にテストすることを選択した場合は、100*100/2のオーバーラップテストを実行する必要があります。この素朴なオーバーラップテストアプローチは、O（n ^ 2）漸近的複雑さであり、完了するのにn ^ 2ステップかかることを意味します（実際にはその半分のステップで終了しますが、漸近的複雑さは定数を除外します）。良い、ブルートフォースではない広範なフェーズでは、オブジェクトのどのペアが実際に衝突の危険にさらされているかを把握しようとします。他のペア（たとえば、衝突が発生するには離れすぎている2つのオブジェクト）はチェックされません。狭相テストは通常​​かなり費用がかかるため、この方法で計算負荷を減らすことができます。

狭いフェーズ：オブジェクトのどのペアが潜在的に衝突する可能性があるかがわかったら、境界形状のオーバーラップテストを実行して、それらが実際に衝突するかどうかをテストします。

広いフェーズでは、世界を大きなセルに分割し、ある種のグリッドを作成します。各セルのサイズはまったく同じで、全世界がセルで覆われています。2つのオブジェクトが同じセルにない場合、それらの2つのオブジェクトの狭いフェーズは必要ありません。

もう一度引用してください：

私たちがする必要があるのは次のことだけです。

  • 物理学とコントローラーのステップに基づいて、世界中のすべてのオブジェクトを更新します。

  • オブジェクトの位置に応じて、各オブジェクトの各境界形状の位置を更新します。もちろん、ここに方向とスケールも含めることができます。

  • 境界形状に基づいて各オブジェクトが含まれているセルを特定し、それらのセルに含まれているオブジェクトのリストに追加します。

  • 衝突をチェックしますが、衝突する可能性があり（たとえば、クリボーは他のクリボーと衝突しない）、同じセル内にあるオブジェクトペア間でのみです。

これは空間ハッシュグリッドブロードフェーズと呼ばれ、実装は非常に簡単です。最初に定義する必要があるのは、各セルのサイズです。これは、ゲームの世界で使用するスケールと単位に大きく依存します。

また、使用している境界形状によっても異なります。文字の周りの単純な長方形または円とそのユークリッド距離は計算するのが簡単なことの1つですが、より細かい形状（「頭」、「脚」などの詳細を含み、境界形状がほとんど追加されていない）は、計算コストがはるかに高くなります。計算します。

于 2012-11-21T04:12:37.027 に答える
0

すべてのオブジェクトが画面の任意の部分に自由に移動できる場合、実行できる最善の方法はO(n^2)アルゴリズムです。オブジェクトAがオブジェクトBと衝突するかどうかを確認するときに、後でオブジェクトBがオブジェクトAと衝突するかどうかを確認する必要がないことを理解することで、一定の係数で改善できます。

于 2012-11-21T03:53:49.910 に答える
0

各文字を固定サイズの正方形で囲みます。文字の衝突をチェックする前に、それらが囲まれている正方形が衝突していないかどうかを確認してください。正方形が衝突した場合にのみ、キャラクターが衝突する可能性があります。x座標とy座標を比較するだけなので、正方形の衝突を簡単にチェックできます。

于 2012-11-21T05:58:20.307 に答える
0

Federicoが提案するように、広いフェーズと狭いフェーズに分割することは、衝突検出アルゴリズムが高価な場合、つまり単純なバウンディングボックスではない場合にのみ役立ちます。

幸いなことに、他のオプションがあります。

衝突マスクテクニックを試すことができます。レンダリング速度に制限されていないように見えるので、各オブジェクトのバウンディングボックスを非表示のビットマップにレンダリングします。次のオブジェクトをレンダリングする前に、バウンディングボックスの四隅にあるピクセルをチェックして、それらがすでに書き込まれているかどうかを確認します。オブジェクトごとに異なる色を使用して、衝突が発生したオブジェクトを色で示すこともできます。

もう1つの一般的なトリックは、すべてのフレームですべての衝突チェックを実行しないことです。たとえば、スーパーマリオブラザーズのようなゲームは、実際には、プレーヤーと敵の間の衝突を1フレームおきにチェックするだけです。フレームごとにできるだけ多くのことを実行して、ラウンドロビン方式ですべてのオブジェクトをチェックする、より高度なバージョンを実行できます。物事が忙しくなると、各オブジェクトは1フレームおきに、または3フレームごとにチェックされるだけかもしれませんが、プレーヤーは気付かないでしょう。これは、オブジェクトが1フレームの衝突でのみ相互に通過できるほど速く移動していない場合に、最も効果的に機能します。

于 2019-06-06T08:42:29.643 に答える