在AS3中优化collison检测代码

Question

我在台上有两个mc，第一个叫导弹，第二个叫盒子。

因此，我把盒子放在盒子里，导弹放在导弹盒子里。我的问题是如何检测任何导弹是否与盒子相撞并对盒子造成损坏。

我正在使用简单有效的算法，但当舞台上有许多导弹和盒子时，它非常慢。我使用了两个嵌套的"for“循环，这是一个糟糕的做法，但我目前没有其他想法。

以下是代码

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 - boxes电影剪辑

bmLayer_mc -导弹电影剪辑

有没有其他技术可以解决这个问题。我已经尝试在每个导弹中添加检测代码，但使用"for“也很慢。

也许是树或散列映射搜索，我不知道？或者可能是graphs :)

任何想法都会有帮助

Answer 1

对于类似的任务(2D)，我所做的是创建一个简单的四叉树结构，其中每个节点可以包含其他子节点或用于碰撞检测的显示对象列表。请注意，如果对象(在您的情况下)移动很多，这将不会有效率，因为每次移动时都需要将它们移动到正确的节点中。

一个简单的示例类是：

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，则该类的实例将自身划分为四个矩形部分(两行、两列)，并为每个节点创建相同类的实例。这些节点反过来会以相同的方式划分它们的空间，直到总共有childLevels级别。

因此，您可以创建一个三级四叉树(具有64个分区叶节点)，其中每个节点的大小仅为原始空间的1/64。当您使用addObject()添加对象时，该对象将被添加到与其所在的正方形相对应的分区节点。

当您执行checkCollision()时，它将递归childLevels时间，直到找到正确的分区，然后仅对该分区中的对象执行常规的碰撞检测循环。

要创建覆盖1024x1024像素空间的三级树，请执行以下操作：

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
}

这可能会大大加快碰撞检测，但依赖于框是静态的(或很少移动)，因为如果它们移动，它们将不再位于正确的分区节点中，如果它们不是，树将无法找到它们之间的冲突。

毫无疑问，有更智能的分区系统，但这对我来说工作得很好，在一个项目中，我需要在很大的空间内散布拾取器(硬币等)，玩家会飞过来收集它们。每一帧我都会让树检查静态拾取器和播放器之间的冲突。

Answer 2

最好的解决方案是使用一些物理引擎(如box2d)。使用游戏引擎(如pushButtonEngine)进行游戏开发甚至更好:)尽管，如果您想自己完成所有这些工作，R-tree like structures是您的选择:)

Answer 3

使用for each它的代码更整洁，赋值更少。

另外，将onEnterFrame更改为计时器事件，如果需要，可以降低计时器事件的速度。

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());
      }
    }
  }
}