利用向量运算解决圆线碰撞问题

日常生活中,你能看到各种各样的球类。

当球与平面发生碰撞时,球会改变其行进的轨迹,由于摩擦,也会改变行进的速度。

在2D游戏中,我们通常把球抽象为一个圆,把平面抽象为一条线。生活中的球和平面的碰撞,就简化成了圆和线的碰撞。

在本文,我们将看到怎么利用向量运算来解决一般的圆线碰撞问题,最后将会有一个DEMO来检验我们的成果。

不要害怕,一切东西都将很简单基础。你只需要保持好舒服的姿势,最好面前有一张纸和一根笔,然后端上一杯水(少喝点碳酸饮料),让我们开始吧~

向量及其运算

定义

向量是一个同时具有大小和方向的几何对象。

字面上的定义总是那么的不容易理解,结合下图,一个以A为起点,B为终点的有向线段。它描述的就是向量$\vec{AB}$。

|center

然而向量和有向线段是有区别的,因为有向线段还需要一个起点,而向量不需要,它只需要终点和起点的相对位移,即可以定义它的大小和方向。

我们可以定义向量$\vec{AB}$为:

vab = { vx:B.x - A.x, vy:B.y - A.y };

有向线段实际是起点+向量,我们将有向线段的起点定义为p0,终点定义为p1。

|center

我们可以将以上的有向线段定义为:

ab = {
p0:{x:10, y:5},
p1:{x:12, y:6},
vx:p1.x - p0.x,
vy:p1.y - p1.y
};

生活中墙可以简化为一条有向线段,球的移动轨迹也可以简化为一条有向线段。

即p0为球当前所在的位置,p1为下一时刻球应该在的位置,所以{vx, vy}就是球的速度向量。

向量运算

向量之间可以像数字一样进行很多运算,运算规则比较简单,然而却能带来很大的便利性。下文将讲述向量的几个基本运算以及它们的意义和应用。

单位向量

单位向量就是其长度为1的向量。

向量的长度其实就是两点距离的问题。

v.len = math.sqrt(v.vx*v.vx + v.vy*v.vy);

而由单位向量的定义,易知v的单位向量为:

v.dx = v.vx / v.len;
v.dy = v.vy / v.len;

单位向量就是是一个纯指向性质的向量,其便利在于不需要去额外计算它的长度,它的长度永远为1。

加法

如果学过初中物理,你们应该对向量的加法不陌生。没错,向量加法就是用来求合力时的运算。 如图:

|center

$\vec{c} = \vec{a} + \vec{b}$在程序中$\vec{c}$可以用如下方式表达:

c = {vx:a.vx+b.vx, vy:a.vy+b.vy};

向量加法的意义在于:有多个向量作用于同一点时,可以通过其来计算出所有向量作用下合成的一个向量,将多个向量简化为一个向量

点积

点积是向量间的乘积,其结果是一个标量(纯数字,不带方向信息)。其定义为:

$\vec{A} \cdot \vec{B} = |\vec{A}|\ |\vec{B}|\ cos\theta,其中\theta为 \vec{A}和\vec{B}的夹角$。

求解点积的代码为:dp = A.vx*B.vx + A.vy*B.vy

|center

由cos函数的性质,可以知道如果夹角为90度,则点积为0;夹角超过90度,则点积小于0;夹角小于90度,则点积大于0。

其意义为可以快速的判断两向量指向的方向是不是相近。若点积大于0,则相近,小于0,则相反。

投影

向量$\vec{A}$在$\vec{B}$上的投影向量就是:

一个向量长度为$\vec{A}$在$\vec{B}$方向上投影长度,向量方向为$\vec{B}$方向的向量。

其实,你只需要参照点积的图,看到$|\vec{A}|\ cos\theta$,就是$\vec{A}$在$\vec{B}$上的投影长度。

投影长度乘$\vec{B}$的单位向量,则为向量$\vec{A}$在$\vec{B}$上的投影向量。

所以$\vec{A}$在$\vec{B}$上投影向量为$(|\vec{A}|\cos\theta)\ \vec{DB}$,其中$\vec{DB}$为$\vec{B}$的单位向量。

我们可以利用点积来简化运算,$\vec{A} \cdot \vec{DB} = |\vec{A}|\ |\vec{DB}|\ cos\theta$,由于$\vec{DB}$为单位向量,所以$(|\vec{A}|\cos\theta)\ \vec{DB} = (\vec{A} \cdot \vec{DB}) *\vec{DB}$ 代码如下:

function getProjectVector(u, dx, dy) {
var dp = u.vx*dx + u.vy*dy
return {vx: dp*dx, vy: dp*dy}
}

叉乘

叉乘也是向量间的乘积,但是其结果仍然是一个向量。

|center

叉乘的一个重要便利在于:它能用来判断点在向量的哪边。若点在向量的左边,则夹角小于180度;若点在向量的右边,则夹角大于180度。

以下是利用叉乘(矩阵运算),来获知点c是否在有向线段ab的左侧。

//判断点c是否在线段ab的左侧
function isLeft(a, b, c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x) < 0;
}

注意:在以上代码中判断的是$<0$,是因为本文中DEMO使用的坐标系的Y轴朝向是朝下递增,如果是正常的坐标系朝向,即Y轴朝上递增,应该判断的是$>0$。

法向量

法向量是与向量方向垂直的向量。对于每条向量它都有左右两条法向量。想象你的眼睛和屏幕构成了一个向量,如果你坐姿正确的话,张开你的双手,你左手就是左法向量,右手就是右法向量。

因为法向量与原向量垂直,所以其点积为0,fx*vx + fy*vy = 0,最简单的解为{fx:-vy, fy:vx}{fx:vy, fy:-vx}

若点在向量左边,则叉乘小于0,则$vx * fy – vy * fx < 0$。

由上易知左法向量为:{fx:vy, fy:-vx},右法向量为:{fx:-vy, fy:vx}

一般来说,我们更希望用单位向量来表示法向量。

所以我们可以将v的右法向量表示为:

v.rx = -v.dy
v.ry = v.dx

同理,左法向量表示为:

v.lx = v.dy
v.ly = -v.dx

坐标更新

在游戏引擎中都有一个每帧循环,循环在每一帧调用一次来更新游戏逻辑。

对于圆的行进更新,很自然会想到每帧将圆的位置从p0更新到p1。

但是这么做是不准确的,因为程序的帧率不会恒定,也就意味着每帧的间隔时间是不一样的。

举个栗子:假设你的引擎设定的FPS是50,即每秒有50帧,每帧你想移动的距离是1px,这样球每秒将会移动50px。但是由于还有其他的运算和渲染,引擎的FPS只能达到40,这样球每秒只能移动40px,跟你的预期完全不一样。

如果球在规定时间内的位置和你的预期不符,那样会导致很多的问题。

解决办法是利用每帧的间隔时间乘与移动速率来得到下一帧的位置。

碰撞

当圆在行进过程中,我们必须判断圆是否与线段发生碰撞。而确定碰撞的方式也很直观,就是确定圆心与线段的距离是否小于圆的半径。

而且发生碰撞之后,我们需要将圆的位置回移到其恰好与线相交的那点。

任意移动线段的两点,若圆线相交,则圆变为半透明,绿色的线段为圆需要回移的有向线段。

注意,当圆碰撞到线段的两端时,其回弹向量的大小为圆与线段端点的距离;否则为圆与线段的距离。

|center

第一步,我们设圆的位置为obj.p1,墙为有向线段w。

我们将墙的起点w.p0和obj.p1的向量称为v1向量,将墙的终点w.p1和obj.p1的向量称为v2向量。

第二步,若v1与w的点积小于0(夹角大于90度,最左侧情况),或v2与w的点积大于0(夹角小于90度,最右侧情况),则可知圆碰撞到了线段的两端。返回的碰撞向量为v1或v2。

若前两种情况都不符合,则圆碰撞到了线段内。这时,我们只需要返回v1在w的法向量上的投影向量即可。

第三步,若返回的向量的长度小于圆的半径,则说明发生了碰撞。

代码如下:

//获取圆与线段的碰撞修正向量
function getIntersectVector(obj, w) {
var v1 = {vx:obj.p1.x-w.p0.x, vy:obj.p1.y-w.p0.y};
if(v1.vx*w.vx + v1.vy*w.vy &lt; 0) {
return v1;
}
var v2 = {vx:obj.p1.x-w.p1.x, vy:obj.p1.y-w.p1.y};
if(v2.vx*w.vx + v2.vy*w.vy &gt; 0) {
return v2;
}
if(isLeft(w.p0, w.p1, obj.p0)){
return getProjectVector(v1, w.lx, w.ly);
}
return getProjectVector(v1, w.rx, w.ry);
}

反弹

|center

由上图可以清晰的知道,回弹向量沿墙壁(v2)的投影向量与v1沿墙壁(v2)的投影向量一致,而回弹向量沿墙壁法向量(v2n)的投影向量与v1的刚好相反。

所以,我们只需要求出v1的以上两个投影向量,即可得到反弹的向量。

代码如下:

//获取回弹向量
function getBounceVector(obj, w) {
var projw = getProjectVector(obj, w.dx, w.dy);
var projn;
var left = isLeft(w.p0, w.p1, obj.p0);
if(left) {
projn = getProjectVector(obj, w.rx, w.ry);
}else {
projn = getProjectVector(obj, w.lx, w.ly);
}
projn.vx *= -1;
projn.vy *= -1;
return {
vx: w.wf*projw.vx + w.bf*projn.vx,
vy: w.wf*projw.vy + w.bf*projn.vy,
};
}

DEMO

拖拽红色圆球,然后释放给与其方向,即可测试。

有关代码托管于Github:

问题

以上方法的问题在于:若圆球的速度过快,则会下一帧判断的时候,直接穿越了墙壁,而没有检测到碰撞。

这个问题有两种解决方案:一种是预测圆线的碰撞,并进行相应的处理;还有一种是对每帧的时间进行切片,如果时间切片足够小的话,则在一个时间切片内圆的移动不会超过其直径,则避免了穿越墙壁的情况。

下面是时间切片方案的伪代码:

// 每帧更新,delta为每帧时间
function update(delta) {
// pre code...
// 球碰撞更新
// 做切片
var minTimeGap = VECTOR_MIN_TIME_GAP; // 时间切片的单元
var maxTimeCutGap = VECTOR_MAX_CUT_TIME_GAP; // 一帧内最后切剩下的时间如果超过此值也做一次碰撞
var totalDelta = 0;
var segment = Math.floor(delta / minTimeGap)
if (segment &lt; 1){
segment = 1;
}
for (var i = 1; i &lt;= segment; i++) {
totalDelta = totalDelta + minTimeGap;
checkCollison(minTimeGap); // 做一次碰撞检测
}
if (delta - totalDelta &gt;= maxTimeCutGap) {
checkCollison(delta - totalDelta); // 剩余时间再做一次碰撞检测
}
// post code...
}

P.S. 推荐一个可以直观理解线性代数的视频集合,非常nice:http://space.bilibili.com/88461692/#!/channel/detail?cid=9450

关注微信公众号:timind

10 responses

  1. 如果是做游戏里的碰撞检测,最好加上判断穿越的情况……

  2. “由上图可以清晰的知道,回弹向量沿墙壁(v2)的投影向量与v1沿墙壁(v2)的投影向量一致,而回弹向量沿墙壁法向量(v2n)的投影向量与v1的刚好相反。”是中文吗?

      • 语法有点模糊。不过终于看懂了。吐槽您的表达方式与吐槽我自己的理解方式是等效的。还是感谢您的文章。请问w.wf和w.bf是什么?

        • 嗯,四年前的文章了,现在看代码都感觉完全可以写的更明白一点。bf和wf确实没有讲明白是什么。bf是指BounceForce也就是回弹向量沿着墙壁法向量方向分量的强度,默认为1;wf是指WallForce也就是沿着墙壁向量方向分量的强度,默认也为1。之所以做这个是可以自定义两个方向分量的一些强度,做一些摩擦或者更强的效果。

          • 非常感谢。请问矩形内圆形碰撞的完整代码例子能否上传到Github?

  3. 非常好的文章,不过好像没处理小球碰到线段两端的情况,不过这个demo确实也不会发生这种情况就是。

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注