圆圈碰撞检测 HTML5 画布

在开始计算距离的精确差异之前，您至少可以比较中心的 x/y 位置与半径。这些信息在圆圈中隐含可用，只需要一些简单的比较和加法/减法。

这将允许您比较所有圆对之间的 x/y 中的简单距离，并丢弃任何明显不是碰撞候选的距离，例如

abs(x2 - x1) > (r2 + r1)
abs(y2 - y1) > (r2 + r1)

。如果圆心之间的 X 或 Y 距离大于半径之和，则它们不能碰撞。

一旦你削减了可能的对撞机，那么你就会做正式的精确笛卡尔距离，这就是"沉重"乘法/除法的东西出现的地方。

考虑将圆心的坐标存储在四叉树中，然后您只需检查圆是否与该象限或相邻象限中的其他圆相交。

需要注意的是，您需要确保四叉树的叶节点具有最大圆半径的最小直径，否则您将不得不检查的不仅仅是相邻节点的相交。

http://en.wikipedia.org/wiki/Quadtree

如果你的圆很分散，那么你可以做的一个简单的优化是存储你的圆在x或y轴上排序，那么你只需要检查谁的x或y坐标在圆的半径内。

效率将与您使用的算法的速度有关，例如，您计算距离的平方根算法的速度，您的数据结构将决定内存的效率，除了算法。加快计算速度的另一种方法是降低距离计算的精度。

碰撞的最佳方法是，如您所说，将圆的中心坐标和半径存储在变量中，并计算减去半径时中心之间的距离是否等于 0。

我强烈推荐Keith Peter的AdvancED ActionScript 3.0动画书，您可以在其中找到Actionscript中Quadtree算法的具体实现。

以下是基本步骤：

• 首先创建一个二维网格，并将所有球随机散布在场地上。

  private function createGrids():void {
      _grids = new Array();
      for (var i:int = 0; i< stage.stageWidth / GRID_SIZE; i++) {
          _grids[i] = new Array();
          for (var j:int = 0; j< stage.stageHeight / GRID_SIZE; j++) {
              _grids[i][j] = new Array();
          }
      }
  }
  

• 将球分配给网格单元格

  private function assignBallsToGrid():void {
      for (var i:int = 0; i< numBalls; i++) {
          var ball:Ball = Ball(_balls[i]);
          var xpos:int = Math.floor(ball.x / GRID_SIZE);
          var ypos:int = Math.floor(ball.y / GRID_SIZE);
          _grids[xpos][ypos].push(ball);
      }
  }
  

检查

• 两个球是否在单个单元格中碰撞，然后检查相邻单元格中的球。正如Charles Ma所提到的，这里唯一的考虑因素是网格单元的尺寸必须大于或等于最大的球直径。

  private function checkOneCell(x1:Number, y1:Number):void {
      var _cell:Array = _grids[x1][y1] as Array;
      for (var i:int = 0; i< _cell.length-1; i++) {
          var ballA:Ball = _cell[i] as Ball;
          for (var j:int = i+1; j< _cell.length; j++) {
              var ballB:Ball = _cell[j] as Ball;
              checkCollision(ballA, ballB);
          }
      }
  }
  private function checkTwoCell(x1:Number, y1:Number, x2:Number, y2:Number):void {
      if (x2 < 0) { return } 
      if (x2 >= _grids.length) { return }
      if (y2 >= _grids[x2].length) { return }
      var _cell0:Array = _grids[x1][y1] as Array;
      var _cell1:Array = _grids[x2][y2] as Array;
      for (var i:int = 0; i< _cell0.length; i++) {
          var ballA:Ball = _cell0[i] as Ball;
          for (var j:int = 0; j< _cell1.length; j++) {
              var ballB:Ball = _cell1[j] as Ball;
              checkCollision(ballA, ballB);
          }
      }
  }
  private function checkCollision(ballA:Ball, ballB:Ball):void {
      var dx:Number = ballB.x - ballA.x;
      var dy:Number = ballB.y - ballA.y;
      var dist:Number = Math.sqrt(dx*dx + dy*dy);
      if (dist < ballB.radius + ballA.radius) {
                       // do something
      }
  }
  

• 这是它看起来像主要方法的样子：

  private function checkBallsCollision():void {
      for (var i:int = 0; i< _grids.length; i++) {
          for (var j:int = 0; j< _grids[i].length; j++) {
              checkOneCell(i, j);
              checkTwoCell(i, j, i+1, j);
              checkTwoCell(i, j, i, j+1);
              checkTwoCell(i, j, i-1, j);
              checkTwoCell(i, j, i+1, j+1);
          }
      }
  }
  

注意：

代码是用Actionscript编写的，但可以很容易地在Javascript中实现。