canvas-核心技术-如何实现碰撞检测
August 26, 2018/ 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 游戏中,对于不规则的物体,比如运动的小人等,我们可以通过抽象成一个矩形,使得这个矩形恰好可以包裹这个物体,在进行碰撞检测时,就可以使用这个矩形来代替实际的物体。这种方法,实际上就是通过抽象,将复杂简单化,对于精确度不是那么高的动画或者游戏,我们直接使用这种外接图形来检测就可以了。在抽象图形的时候,我们要根据具体的物体,比如小人可以抽象成矩形,太阳就要抽象成圆了,把具体的物体抽象的跟它相似的形状,这样在检测时就会更加准确。
进行了图形抽象之后,我们在检测就只需对图形进行检测了。对于两个图形是否发生碰撞,我们只需要判断它们是否存在相交的部分,如果存在相交的部分,那么则可以认为是发生了碰撞,否则就没有。下面,我们分别来学习矩形和矩形的碰撞检测,圆和圆的碰撞检测,矩形和圆的碰撞检测。
矩形与矩形碰撞情况,
这里列举两个矩形发生碰撞的所有情况,在 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;
}
其实就是分别在水平方向和垂直方向判断这两个矩形是否发生重叠。
圆和圆碰撞情况,
判断两个圆是否发生碰撞,就是判断两个圆的圆心之间的距离是否小于它们的半径之和,如果小于半径之和,则发生碰撞,否则就没有发生碰撞。主要就是计算两个圆心之间的距离,可以根据坐标系中两点之间距离公式得到,
在 canvas 中具体代码实现如下,
/* 判断是否两个圆发生碰撞 */
private didCircleCollide(sprite: CircleSprite, otherSprite: CircleSprite) {
return distance(sprite.x, sprite.y, otherSprite.x, otherSprite.y) < sprite.radius + otherSprite.radius;
}
矩形和圆碰撞情况,
这种情况,就是判断圆形到矩形上最近的一点的距离是否小于圆的半径,如果小于圆的半径,则发生碰撞,否则就没有发生碰撞。我们首先要找到圆距离矩形上最近的点的坐标,这种就要考虑圆心在矩形左侧,圆心在矩形上面,圆心在矩形右侧,圆心在矩形下面,圆心在矩形里面这五种情况。如果圆心在矩形里面,那么一定是碰撞的。其他四种情况根据每一种情况来计算得到矩形上离圆心最近的一点,下面举例其中一种情况,其他情况原理类似,比如圆心在矩形左侧,
这种情况下,最近一点的 X 轴坐标跟矩形左上角坐标的 X 轴坐标相等,跟圆心 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;
}
光线投射检测
光线投射法:画一条与物体的速度向量相重合的线,然后再从另外一个待检测物体出发,绘制第二条线,根据两条线的交点位置来判定是否发生碰撞。
光线投射法一般还会结合边界值检测来进行严格准确的判断,这种方法要求我们在动画更新中,不断计算出两个速度向量的交点坐标,根据交点坐标判断是否满足碰撞条件,交点满足了条件,我们还要运用边界值检测方法来检测运动物体是否满足边界值条件,只有同时满足才判断为发生碰撞。这种检测,准确度一般比较高,特别是适用于运动速度快的物体。以小球投桶示例,检测代码如下,
/* 是否发生碰撞 */
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 的向量,其实际作用是表示方向。
- 一个向量垂直于另外一个向量,我们叫做法向量。
图中可以看到,,。多余凸多边形的每个顶点,我们可以用向量来表示。
分离轴检测思路,
- 先获取被检测多边形的所有的投影轴,一般只需要计算出多边形对应边的投影轴即可
- 计算出被检测多边形在每一条投影轴上的投影
- 判断它们的投影是否重叠,如果存在在任意一条投影轴的投影不重叠,则说明它们没有发生碰撞,否则就发生了碰撞
/* 判断是否发生碰撞 */
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;
}
下面我们就按照这三个步骤来,一步一步实现分离轴检测方法。
获取投影轴
在多边形中,我们是以边来建立边向量的,边向量的法向量,就是这条边的投影轴了。对于投影轴,我们只需它的方向,所以一般会把它格式化为单位向量。
// 获取凸多边形的投影轴
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。
对于这几种检测方法,强力建议熟悉掌握分离轴法,因为它使用的范围最为广泛,对于任意的凸多边形,它都可以较精确的检测出来。由于分离轴检测法计算量一般比较大,所以在检测之前,我们先过滤掉那些根本不可能发生碰撞的图形,一般方法是空间分隔法,或者过滤可视区间不可见的图形等,然后再对较小的一部分可能发生碰撞的图形来进行计算检测,这样可以提升检测的速度。
参考
- “等一下,我碰!”——常见的 2D 碰撞检测 「部分图片引用这篇文章的,这篇文章写的较好,建议读者看看」
- 《HTML5 Canvas 核心技术:图形、动画与游戏开发》
若有收获,小额鼓励