三羊

三羊的小站

canvas-核心技术-如何实现碰撞检测

August 26, 2018/「 canvas 」/ Edit on Github ✏️

文章目录

这篇是学习和回顾 canvas 系列笔记的第六篇，完整笔记详见：canvas 核心技术。

在上一篇canvas 核心技术-如何实现复杂的动画笔记中，我们详细讨论了在制作复杂动画时，需要考虑时间因素，物理因素等，同时还回顾了如何使用缓动函数来扭曲时间轴实现非线性运动，比如常见的缓入，缓出，缓入缓出等。在游戏或者动画中，运动的物体在变化的过程中，它们是有可能碰撞在一起的，那么这一篇我们就来详细学习下如何进行碰撞检测。

边界值检测

最简单的检测手段就是边界值检测了，就是对一个运动的物体的某些属性进行条件判断，如果达到了这个条件，则说明发生了碰撞。例如在上一篇中的示例，小球自由下落，当在检测小球是否与地面发生碰撞时，我们是检测小球下落的高度 fh 是否达到了小球本身距离地面的高度 dh，如果 fh > dh，则说明小球与地面发生了碰撞。

let distance = ball.currentSpeed * t
if (ball.offset + distance > ball.verticalHeight) {
  // 落到地面了，发生了碰撞
  // ...
} else {
  // 还没有落到地面，没有发生碰撞
  ball.offset += distance
}

这里是我的小球自由落体完整在线示例

这种检测方式非常的简单且准确，在针对类似业务开发时，我们可以简化成边界值检测。但是当我们开发较为复杂游戏时，边界值检测通常不能很好的实现，为了更加真实，它通常与其他检测方法一起使用。

外接图形检测

在 canvas 游戏中，对于不规则的物体，比如运动的小人等，我们可以通过抽象成一个矩形，使得这个矩形恰好可以包裹这个物体，在进行碰撞检测时，就可以使用这个矩形来代替实际的物体。这种方法，实际上就是通过抽象，将复杂简单化，对于精确度不是那么高的动画或者游戏，我们直接使用这种外接图形来检测就可以了。在抽象图形的时候，我们要根据具体的物体，比如小人可以抽象成矩形，太阳就要抽象成圆了，把具体的物体抽象的跟它相似的形状，这样在检测时就会更加准确。

进行了图形抽象之后，我们在检测就只需对图形进行检测了。对于两个图形是否发生碰撞，我们只需要判断它们是否存在相交的部分，如果存在相交的部分，那么则可以认为是发生了碰撞，否则就没有。下面，我们分别来学习矩形和矩形的碰撞检测，圆和圆的碰撞检测，矩形和圆的碰撞检测。

矩形与矩形碰撞情况，

rect_rect

这里列举两个矩形发生碰撞的所有情况，在 canvas 中具体代码实现如下，

/* 判断是否两个矩形发生碰撞 */
private didRectCollide(sprite: RectSprite, otherSprite: RectSprite) {
  let horizontal = sprite.left + sprite.width > otherSprite.left && sprite.left < otherSprite.left + otherSprite.width;
  let vertical = sprite.top < otherSprite.top + otherSprite.height && sprite.top + sprite.height > otherSprite.top;
  return horizontal && vertical;
}

其实就是分别在水平方向和垂直方向判断这两个矩形是否发生重叠。

圆和圆碰撞情况，

circle_circle

判断两个圆是否发生碰撞，就是判断两个圆的圆心之间的距离是否小于它们的半径之和，如果小于半径之和，则发生碰撞，否则就没有发生碰撞。主要就是计算两个圆心之间的距离，可以根据坐标系中两点之间距离公式得到，

∣AB∣=(x1−x2)2+(y1−y2)2|AB| = \sqrt{(x_1-x_2)^2 + (y_1-y2)^2}

在 canvas 中具体代码实现如下，

/* 判断是否两个圆发生碰撞 */
private didCircleCollide(sprite: CircleSprite, otherSprite: CircleSprite) {
  return distance(sprite.x, sprite.y, otherSprite.x, otherSprite.y) < sprite.radius + otherSprite.radius;
}

矩形和圆碰撞情况，

rect_circle

这种情况，就是判断圆形到矩形上最近的一点的距离是否小于圆的半径，如果小于圆的半径，则发生碰撞，否则就没有发生碰撞。我们首先要找到圆距离矩形上最近的点的坐标，这种就要考虑圆心在矩形左侧，圆心在矩形上面，圆心在矩形右侧，圆心在矩形下面，圆心在矩形里面这五种情况。如果圆心在矩形里面，那么一定是碰撞的。其他四种情况根据每一种情况来计算得到矩形上离圆心最近的一点，下面举例其中一种情况，其他情况原理类似，比如圆心在矩形左侧，

rect_circle_left

这种情况下，最近一点的 X 轴坐标跟矩形左上角坐标的 X 轴坐标相等，跟圆心 Y 轴坐标相等，这样就可以得出来了，(rectx,circley)(rect_x,circle_y)。在 canvas 中具体代码实现如下，

/* 判断是否矩形和圆形发生碰撞 */
private didRectWidthCircleCollide(rectSprite: RectSprite, circleSprite: CircleSprite) {
  let closePoint = { x: undefined, y: undefined };
  if (circleSprite.x < rectSprite.left) {
    closePoint.x = rectSprite.left;
  } else if (circleSprite.x < rectSprite.left + rectSprite.width) {
    closePoint.x = circleSprite.x;
  } else {
    closePoint.x = rectSprite.left + rectSprite.width;
  }
  if (circleSprite.y < rectSprite.top) {
    closePoint.y = rectSprite.top;
  } else if (circleSprite.y < rectSprite.top + rectSprite.height) {
    closePoint.y = circleSprite.y;
  } else {
    closePoint.y = rectSprite.top + rectSprite.height;
  }
  return distance(circleSprite.x, circleSprite.y, closePoint.x, closePoint.y) < circleSprite.radius;
}

这里是我的外接图形碰撞检测在线示例。

光线投射检测

光线投射法：画一条与物体的速度向量相重合的线，然后再从另外一个待检测物体出发，绘制第二条线，根据两条线的交点位置来判定是否发生碰撞。

light_collide

光线投射法一般还会结合边界值检测来进行严格准确的判断，这种方法要求我们在动画更新中，不断计算出两个速度向量的交点坐标，根据交点坐标判断是否满足碰撞条件，交点满足了条件，我们还要运用边界值检测方法来检测运动物体是否满足边界值条件，只有同时满足才判断为发生碰撞。这种检测，准确度一般比较高，特别是适用于运动速度快的物体。以小球投桶示例，检测代码如下，

/* 是否发生碰撞 */
public didCollide(ball: CircleSprite, bucket: ImageSprite) {
  let k1 = ball.verticalVelocity / ball.horizontalVelocity;
  let b1 = ball.y - k1 * ball.x;
  let inertSectionY = bucket.mockTop; //计算交点Y坐标
  let insertSectionX = (inertSectionY - b1) / k1; //计算交点X坐标
  return (
    insertSectionX > bucket.mockLeft &&
    insertSectionX < bucket.mockLeft + bucket.mockWidth &&
    ball.x > bucket.mockLeft &&
    ball.x < bucket.mockLeft + bucket.mockWidth &&
    ball.y > bucket.mockTop &&
    ball.y < bucket.mockTop + bucket.mockHeight
  );
}

这里是我的光线投射检测在线示例。

分离轴检测

在判断凸多边形的碰撞检测时，我们可以使用分离轴方法。在学习分离轴检测之前，我们需要先熟悉向量的一些基础知识。

向量基础知识：

  • 在平面二维坐标系中，我们可以使用向量来表示某个点的位置。向量表示法就是从坐标原点（0，0）指向目标点（x，y） 。
  • 两个向量相减，结果是另外一条新的向量。
  • 两个向量做点积，可以得到投影的值。
  • 单位向量，就是长度为 1 的向量，其实际作用是表示方向。
  • 一个向量垂直于另外一个向量，我们叫做法向量。

system

图中可以看到，oa→−ob→=ba→\overrightarrow{oa} -\overrightarrow{ob} = \overrightarrow{ba}，oa→∗ob→=∣od∣\overrightarrow{oa} * \overrightarrow{ob} = |od|。多余凸多边形的每个顶点，我们可以用向量来表示。

分离轴检测思路，

  1. 先获取被检测多边形的所有的投影轴，一般只需要计算出多边形对应边的投影轴即可
  2. 计算出被检测多边形在每一条投影轴上的投影
  3. 判断它们的投影是否重叠，如果存在在任意一条投影轴的投影不重叠，则说明它们没有发生碰撞，否则就发生了碰撞
/* 判断是否发生碰撞 */
public didCollide(sprite: Sprite, otherSprite: Sprite) {
  let axes1 = sprite.type === 'circle' ? (sprite as Circle).getAxes(otherSprite as Polygon) : (sprite as Polygon).getAxes();
  let axes2 = otherSprite.type === 'circle' ? (otherSprite as Circle).getAxes(sprite as Polygon) : (otherSprite as Polygon).getAxes();
  // 第一步：获取所有的投影轴
  // 第二步：获取多边形在各个投影轴的投影
  // 第三步：判断是否存在一条投影轴上，多边形的投影不相交，如果存在不相交的投影则直接返回false，如果有所的投影轴上的投影都存在相交，则说明相碰了。
  let axes = [...axes1, ...axes2];
  for (let axis of axes) {
    let projections1 = sprite.getProjection(axis);
    let projections2 = otherSprite.getProjection(axis);
    if (!projections1.overlaps(projections2)) {
      return false;
    }
  }
  return true;
}

下面我们就按照这三个步骤来，一步一步实现分离轴检测方法。

获取投影轴

projection

在多边形中，我们是以边来建立边向量的，边向量的法向量，就是这条边的投影轴了。对于投影轴，我们只需它的方向，所以一般会把它格式化为单位向量。

// 获取凸多边形的投影轴
public getAxes() {
  let points = this.points;
  let axes = [];
  for (let i = 0, j = points.length - 1; i < j; i++) {
      let v1 = new Vector(points[i].x, points[i].y);
      let v2 = new Vector(points[i + 1].x, points[i + 1].y);
      axes.push(
          v1
          .subtract(v2)
          .perpendicular()
          .normalize(),
      );
  }
  let firstPoint = points[0];
  let lastPoint = points[points.length - 1];
  let v1 = new Vector(lastPoint.x, lastPoint.y);
  let v2 = new Vector(firstPoint.x, firstPoint.y);
  axes.push(
      v1
      .subtract(v2)
      .perpendicular()
      .normalize(),
  );
  return axes;
}

获取了待检测图形的投影轴之后，我们就需要计算图形在每条投影轴上的投影

public getProjection(v: Vector) {
  let min = Number.MAX_SAFE_INTEGER;
  let max = Number.MIN_SAFE_INTEGER;
  for (let point of this.points) {
    let p = new Vector(point.x, point.y);
    let dotProduct = p.dotProduct(v);
    min = Math.min(min, dotProduct);
    max = Math.max(max, dotProduct);
  }
  return new Projection(min, max);
}

最后判断投影是否重叠

/* 投影是否重叠 */
overlaps(p: Projection) {
  return this.max > p.min && p.max > this.min;
}

其中，如果是一个圆形与一个凸多边形的检测时，在计算圆对应的投影轴时比较特殊，圆只有一条投影轴，就是圆心与它距离多边形最近顶点的向量，

// 获取圆的投影轴
public getAxes(polygon: Polygon) {
  // 对于圆来说，获取其投影轴就是将圆心与他距离多边形最近顶点的连线
  let { x, y } = this;
  let nearestPoint = null;
  let nearestDistance = Number.MAX_SAFE_INTEGER;
  for (let [index, point] of polygon.points.entries()) {
    let d = distance(x, y, point.x, point.y);
    if (d < nearestDistance) {
      nearestDistance = d;
      nearestPoint = point;
    }
  }
  let v1 = new Vector(x, y);
  let v2 = new Vector(nearestPoint.x, nearestPoint.y);
  return [v1.subtract(v2).normalize()];
}

这里是我的分离轴检测在线示例。

小结

这篇笔记详细记录了 2d 图形中碰撞检测的方法，比较简单的方法是外接图形法和边界值检测法，它们相对不是那么精确，比较复杂和精确的方法有光线投射法和分离轴法。根据不同的场景和精确度要求，我们选择不同的方法。其他，除了上面几种，还有像素检测等方法也可以实现碰撞检测，像素检测是以像素为单位来检测，如果存在不透明的像素在同一个坐标上重叠，则说明发生了碰撞，具体实现可以查看Pixel accurate collision detection with Javascript and Canvas。

对于这几种检测方法，强力建议熟悉掌握分离轴法，因为它使用的范围最为广泛，对于任意的凸多边形，它都可以较精确的检测出来。由于分离轴检测法计算量一般比较大，所以在检测之前，我们先过滤掉那些根本不可能发生碰撞的图形，一般方法是空间分隔法，或者过滤可视区间不可见的图形等，然后再对较小的一部分可能发生碰撞的图形来进行计算检测，这样可以提升检测的速度。

参考

若有收获，小额鼓励