2Dゲームの衝突のための効率的なアルゴリズム？

Question

チュートリアルの後に私はボンバーマンをJavaでプログラミングしています（これは私の最初のゲームです）。 このチュートリアルでは、衝突を検出するための次のコードを提案しています。今では

 for (int p=0; p<entities.size(); p++) { 
      for (int s=p+1; s<entities.size(); s++) { 
       Entity me = (Entity) entities.get(p); 
       Entity him = (Entity) entities.get(s); 

       if (me.collidesWith(him)) { 
        me.collidedWith(him); 
        him.collidedWith(me); 
       } 
      } 

、エンティティは敵とプレイヤーを含む配列リストです。 プレイヤーが壁に衝突するのを検出したいのであれば、レベルのすべての壁やレンガのタイルをエンティティのarraylistに置く必要がありますか？もしそうなら、このアルゴリズムは非常に効率的ではありませんか？これらのタイルは他のタイルと衝突することはないので、私はさまざまなリストのゲームエンティティを管理することを考えていました。何を指示してるんですか？それを行うより効率的なアルゴリズムはありますか？

注：2Dゲームでの衝突に関する他の質問はすでに読んでいます。 ありがとうございました。

Answer 1

PacManでゴーストの動きと衝突の検出方法についてのこの優れた記事を読むことをお勧めします。

次に、ボンバーマンレベルを論理的にタイルの集合体としてモデル化することをお勧めします。それぞれのタイルはあなたのレベルの離散的な位置を表しており、論理的にはタイルの間にあるか、同時に2つのタイルを占有することはできません。各タイルは、現在どの種類の地形特徴が存在しているか、それがプレーヤーにとって有効な目的地タイルであるかどうかを追跡することができます（敵は通常、通過不可能な地形を横切ることができるプレーヤーのために）。

次に、世界中のすべてのオブジェクトに衝突検出アルゴリズムは必要ありません。敵が移動する時間が来たとき、またはユーザーがキャラクターを移動しようとするとき、現在のタイルに隣接するすべてのタイルをチェックするだけです（斜めの移動を許可する場合は最大4または8）。各タイルが有効な移動方向を表しているかどうかを確認し、有効な方向にない場合は移動をブロックします。

あなたの質問に答えるには、世界中のすべてのオブジェクトをすべての位置更新で反復することは非常に非効率的です。

Answer 2

衝突システムにグリッドを使用する別の方法があります。私はArothの提案のより複雑なバージョンを使用しており、これを使用して衝突のバグを修正しています。

理論的には、各エンティティ（移動可能なもの）ごとに1つのブールチェックしか使用しないため、このシステムは最も高速です（このチェックはif(Grid[x][y] ==true)とします）。

注：上記グリッドチェックの例では、私はあなたから跳ねるような物理学を心配していない場合は通行不能グリッドの座標が

をfalse.`する設定ブール値の2次元配列を使用しましたあなたがこれを使用することができます壁：

1- Divide the map into grids. 
2- Making every entity only fill a tile would be better but not necessary. 
3- Store the previous position or the grid of the entities. 
4- Whenever an entity moves, before visually updating their location (also before 
doing other calculations) check the grids they are in. If they are in grid 
that is not empty or simply in a grid that they are not supposed to 
be, return their position back to the previous position (which you have stored). 

あなたはエンティティがグリッド（グリッドは、彼らが移動できる最小距離よりも大きいです）内で自由に移動できるようにしたい場合、あなたはグリッド彼らに隣接して配置する必要があります入力されていて、それらは想定されていませんでした。それ以外の場合は、前のグリッドに戻します。

壁から跳ね返りたい場合でもこれを使うことができますが、このようにいくつの機能を衝突システムに追加できるかはわかりません。