AS3でのコリソン検出コードの最適化

Question

私はステージ上に2つのMCがあり、最初はミサイルと呼ばれ、2つ目はボックスと呼ばれます。

したがって、ミサイルmcの箱とミサイルに箱を入れます。私の問題は、どのミサイルもボックスに衝突してボックスにダメージを与えるかどうかを検出する方法です。

私は、動作するシンプルで効果的なアルゴリズムを使用していますが、ステージ上に多くのミサイルやボックスがある場合は非常に遅いです。私は2つのネストされた「for」サイクルを使用していますが、これは悪い習慣ですが、現時点で他のアイデアはありません。ボックスは

bmLayer_mcをムービークリップ - - ここで

はコード

public function onEnterFrame(e:Event) { 
     for(var i:int=0;i<ground_mc.boxesLayer_mc.numChildren;i++){ 
      mc1=ground_mc.boxesLayer_mc.getChildAt(i); 
      for(var j:int=0;j<ground_mc.bmLayer_mc.numChildren;j++){ 
       mc2=ground_mc.bmLayer_mc.getChildAt(j); 
       if(mc1.hitTestObject(mc2)){ 
        se=new SmallExplosion(); 
        se.x=mc1.x+randNumber(-20,20); 
        se.y=mc1.y+randNumber(-20,20); 
        ground_mc.addChild(se); 
        mc1.decreaseHealth(mc2.getDamage()); 
       } 
      } 
     } 

    } 

はboxesLayer_mcあるミサイルは

をムービークリップこの問題を解決するが、他の技術です。私はすでにすべてのミサイルに検出コードを追加しようとしましたが、 "for"では遅くなっています。

多分木やハッシュマップ検索私は知らない？それともグラフ:)

任意のアイデアが参考になる

Answer 1

最善の解決策は、（box2dのような）いくつかの物理エンジンを使用することです。あなたはそれをすべてを自分で行いたい場合にも優れています:) ものの、ゲーム開発のためのゲームエンジン（pushButtonEngineなど）を使用して、構造物のようなR-treeはあなたの一品です:)

Answer 2

それが少し滑らかな印象のコードでそれぞれに使用します割り当てが少なくなる

また、onEnterFrameをタイマーイベントに変更すると、必要に応じてタイマーイベントを遅くすることができます。同様のタスク（2D）については

public function onEnterFrame(e:Event) { 
    for each(var box:MovieClip in ground_mc.boxesLayer_mc){ 
    for each(var missle:MovieClip in <ground_mc.bmLayer_mc){ 
     if(box.hitTestObject(missle)){ 
     se=new SmallExplosion(); 
     se.x=box.x+randNumber(-20,20); 
     se.y=box.y+randNumber(-20,20); 
     ground_mc.addChild(se); 
     box.decreaseHealth(missle.getDamage()); 
     } 
    } 
    } 
} 

Answer 3

、私がやったことは、各ノードは、いずれかの他の子ノードまたは衝突検出用の表示オブジェクトのリストを含むことができ、単純な四分木のような構造物を作成することでした。オブジェクト（ケース内のボックス）が多く移動する場合、移動するたびに適切なノードに移動する必要があるため、効率的ではありません。

単純な例のクラスは次のようになります。このクラスの

public class WorldPartitionNode { 
    private var minX : Number; 
    private var minY : Number; 
    private var maxX : Number; 
    private var maxY : Number; 
    private var width : Number; 
    private var height : Number; 

    private var _children : Vector.<WorldPartitionNode>; 
    private var _objects : Vector.<GameObject>; 

    public function WorldPartitionNode(x : Number, y : Number, 
     w : Number, h : Number, childLevels : int) 
    { 
    minX = x; 
    minY = y; 
    maxX = x + w; 
    maxY = y + h; 
    width = h; 
    height = h; 

    if (childLevels == 0) { 
     // This node should have no children, so instead it should 
     // contain display objects 
     _objects = new Vector.<GameObject>; 
    } 
    else { 
     _children = new Vector.<WorldPartitionNode>(4,true); 
    _children[0] = new WorldPartitionTreeNode(minX, minY, width/2, height/2, childLevels-1); 
    _children[1] = new WorldPartitionTreeNode(minX+width/2, minY, width/2, height/2, childLevels-1); 
    _children[2] = new WorldPartitionTreeNode(minX, minY+height/2, width/2, height/2, childLevels-1); 
    _children[3] = new WorldPartitionTreeNode(minX+width/2, minY+height/2, width/2, height/2, childLevels-1); 
    } 
    } 


    public function addObject(obj : GameObject) : void 
    { 
    if (_children) { 
     // This is not a leaf node, so add it to that of the child 
     // nodes in which it belongs. 
     var i : uint; 
     for (i=0; i<4; i++) { 
     var c : WorldPartitionNode = _children[i]; 
     if (obj.x > c.minX && obj.y > c.minY && obj.x < c.maxX && obj.y < c.maxY) { 
      c.addObject(obj); 
      return; // Found node, so bail 
     } 
     } 
    } 
    else { 
     // This is a leaf node, so just add to the internal objects vector 
     _objects.push(obj); 
    } 
    } 

    public function checkCollisions(x : Number, y : Number) : GameObject 
    { 
    if (_children) { 
     // This node has children, so delegate to the right child 
     var i : uint; 
     for (i=0; i<4; i++) { 
     var c : WorldPartitionNode = _children[i]; 
     if (x > c.minX && y > c.minY && x < c.maxX && y < c.maxY) { 
      return c.checkCollisions(x, y); 
     } 
     }   
    } 
    else { 
     // This is a leaf node (with objects directly in it) so loop through 
     // them all and check collision 
     var obj : GameObject; 
     for each (obj in _objects) { 
     if (obj.collidesWith(x, y)) 
      return obj; 
     } 

     return null; //None if reached 
    } 
    } 
} 

インスタンスはchildLevels > 0場合4つの矩形セクション（2行2列）に自身を分割し、それらの各々について同じクラスのインスタンスを作成しますノード。これらのノードは、合計でchildLevelsレベルになるまで、同様にスペースを分割します。

これにより、各ノードが元のスペースの1/64にすぎない3レベルクワッドツリー（64個のパーティションリーフノードを持つ）を作成できます。 addObject()でオブジェクトを追加すると、そのオブジェクトは、オブジェクトが配置されている正方形に対応するパーティションノードに追加されます。

checkCollision()を実行すると、適切なパーティションが見つかるまでchildLevels回再発動し、そのパーティション内のオブジェクトに対してのみ通常の衝突検出ループを実行します。

var treeRoot : WorldPartitionNode = new WorldPartitionNode(0, 0, 1024, 1024, 3); 

そして、あなたのミサイルや、ツリー内のオブジェクト間の衝突をチェックする：

var missile : GameObject; 
for each (missile in _missiles) { 
    var obj : GameObject = treeRoot.checkCollisions(missile.x, missile.y); 
    if (obj != null) 
    obj.kill(); // Was hit by missile 
} 

は1024×1024ピクセルですスペースをカバー3レベルのツリーを作成するにはこれにより、衝突検出が大幅に高速化される可能性がありますが、移動すると正しいパーティションノードに入らなくなり、そうでない場合はツリーが衝突を検出できなくなるため、静的（またはまれに動く）ボックスに依存しますそれらの間の。

そこには賢明なパーティショニングシステムはありませんが、これは大きなスペースにピックアップ（コインなど）を散在させる必要があったプロジェクトで私にとって非常にうまく機能しました。それら。各フレームでは、静的なピックアップとプレーヤーとの間の衝突をツリーで確認します。