日常生活中,你能看到各种各样的球类。
当球与平面发生碰撞时,球会改变其行进的轨迹,由于摩擦,也会改变行进的速度。
在2D游戏中,我们通常把球抽象为一个圆,把平面抽象为一条线。生活中的球和平面的碰撞,就简化成了圆和线的碰撞。
在本文,我们将看到怎么利用向量运算来解决一般的圆线碰撞问题,最后将会有一个DEMO来检验我们的成果。
不要害怕,一切东西都将很简单基础。你只需要保持好舒服的姿势,最好面前有一张纸和一根笔,然后端上一杯水(少喝点碳酸饮料),让我们开始吧~
向量及其运算
定义
向量是一个同时具有大小和方向的几何对象。
字面上的定义总是那么的不容易理解,结合下图,一个以A为起点,B为终点的有向线段。它描述的就是向量
然而向量和有向线段是有区别的,因为有向线段还需要一个起点,而向量不需要,它只需要终点和起点的相对位移,即可以定义它的大小和方向。
我们可以定义向量
0 |
vab = { vx:B.x - A.x, vy:B.y - A.y }; |
有向线段实际是起点+向量
,我们将有向线段的起点定义为p0,终点定义为p1。
我们可以将以上的有向线段定义为:
0 1 2 3 4 5 |
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的向量。
向量的长度其实就是两点距离的问题。
0 |
v.len = math.sqrt(v.vx*v.vx + v.vy*v.vy); |
而由单位向量的定义,易知v的单位向量为:
0 1 |
v.dx = v.vx / v.len; v.dy = v.vy / v.len; |
单位向量就是是一个纯指向性质的向量,其便利在于不需要去额外计算它的长度,它的长度永远为1。
加法
如果学过初中物理,你们应该对向量的加法不陌生。没错,向量加法就是用来求合力时的运算。
如图:
0 |
c = {vx:a.vx+b.vx, vy:a.vy+b.vy}; |
向量加法的意义在于,有多个向量作用于同一点时,可以通过其来计算出所有向量作用下合成的一个向量,将多个向量简化为一个向量。
点积
点积是向量间的乘积,其结果是一个标量(纯数字,不带方向信息)。其定义为:
A⃗ ⋅B⃗ =|A⃗ | |B⃗ | cosθ ,θ 为A⃗ 和B⃗ 的夹角 。
求解点积的代码为:dp = A.vx*B.vx + A.vy*B.vy
由
其意义为可以快速的判断两向量指向的方向是不是相近。若点积大于0,则相近,小于0,则相反。
投影
向量
其实,你只需要参照点积的图,看到
投影长度乘
所以
我们可以利用点积来简化运算,
代码如下:
0 1 2 3 4 |
function getProjectVector(u, dx, dy) { var dp = u.vx*dx + u.vy*dy return {vx: dp*dx, vy: dp*dy} } |
叉乘
叉乘也是向量间的乘积,但是其结果仍然是一个向量。其定义为:
A⃗ ×B⃗ =|A⃗ | |B⃗ | sinθ n⃗ ,θ 为A⃗ 和B⃗ 的夹角,n⃗ 为垂直于a⃗ b⃗ 平面的单位向量 。
叉乘的一个重要便利在于:它能用来判断点在向量的哪边。若点在向量的左边,则夹角小于180度;若点在向量的右边,则夹角大于180度。
以下是利用叉乘(矩阵运算),来获知点c是否在有向线段ab的左侧。
0 1 2 3 |
//判断点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:-vy, fy:vx}
和{fx:vy, fy:-vx}
。
若点在向量左边,则叉乘小于0,则
由上易知左法向量为:{fx:vy, fy:-vx}
,右法向量为:{fx:-vy, fy:vx}
。
一般来说,我们更希望用单位向量来表示法向量。
所以我们可以将v的右法向量表示为:
0 1 |
v.rx = -v.dy v.ry = v.dx |
同理,左法向量表示为:
0 1 |
v.lx = v.dy v.ly = -v.dx |
坐标更新
在游戏引擎中都有一个每帧循环,循环在每一帧调用一次来更新游戏逻辑。
对于圆的行进更新,很自然会想到每帧将圆的位置从p0更新到p1。
但是这么做是不准确的,因为程序的帧率不会恒定,也就意味着每帧的间隔时间是不一样的。
举个栗子:假设你的引擎设定的FPS是50,即每秒有50帧,每帧你想移动的距离是1px,这样球每秒将会移动50px。但是由于还有其他的运算和渲染,引擎的FPS只能达到40,这样球每秒只能移动40px,跟你的预期完全不一样。
如果球在规定时间内的位置和你的预期不符,那样会导致很多的问题。
解决办法是利用每帧的间隔时间乘与移动速率来得到下一帧的位置。
碰撞
当圆在行进过程中,我们必须判断圆是否与线段发生碰撞。而确定碰撞的方式也很直观,就是确定圆心与线段的距离是否小于圆的半径。
而且发生碰撞之后,我们需要将圆的位置回移到其恰好与线相交的那点。
任意移动线段的两点,若圆线相交,则圆变为半透明,绿色的线段为圆需要回移的有向线段。
注意,当圆碰撞到线段的两端时,其回弹向量的大小为圆与线段端点的距离;否则为圆与线段的距离。
第一步,我们设圆的位置为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的法向量上的投影向量即可。
第三步,若返回的向量的长度小于圆的半径,则说明发生了碰撞。
代码如下:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
//获取圆与线段的碰撞修正向量 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 < 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 > 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); } |
反弹
由上图可以清晰的知道,回弹向量沿墙壁(v2)的投影向量与v1沿墙壁(v2)的投影向量一致,而回弹向量沿墙壁法向量(v2n)的投影向量与v1的刚好相反。
所以,我们只需要求出v1的以上两个投影向量,即可得到反弹的向量。
代码如下:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
//获取回弹向量 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:
问题
以上方法的问题在于:若圆球的速度过快,则会下一帧判断的时候,直接穿越了墙壁,而没有检测到碰撞。
这个问题有两种解决方案:一种是预测圆线的碰撞,并进行相应的处理;还有一种是对每帧的时间进行切片,如果时间切片足够小的话,则在一个时间切片内圆的移动不会超过其直径,则避免了穿越墙壁的情况。
下面是时间切片方案的伪代码:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// 每帧更新,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 < 1){ segment = 1; } for (var i = 1; i <= segment; i++) { totalDelta = totalDelta + minTimeGap; checkCollison(minTimeGap); // 做一次碰撞检测 } if (delta - totalDelta >= maxTimeCutGap) { checkCollison(delta - totalDelta); // 剩余时间再做一次碰撞检测 } // post code... } |
cool.
如果是做游戏里的碰撞检测,最好加上判断穿越的情况……
与常见的圆形多边形碰撞算法是一样的
“由上图可以清晰的知道,回弹向量沿墙壁(v2)的投影向量与v1沿墙壁(v2)的投影向量一致,而回弹向量沿墙壁法向量(v2n)的投影向量与v1的刚好相反。”是中文吗?
啥意思?
语法有点模糊。不过终于看懂了。吐槽您的表达方式与吐槽我自己的理解方式是等效的。还是感谢您的文章。请问w.wf和w.bf是什么?
嗯,四年前的文章了,现在看代码都感觉完全可以写的更明白一点。bf和wf确实没有讲明白是什么。bf是指BounceForce也就是回弹向量沿着墙壁法向量方向分量的强度,默认为1;wf是指WallForce也就是沿着墙壁向量方向分量的强度,默认也为1。之所以做这个是可以自定义两个方向分量的一些强度,做一些摩擦或者更强的效果。
非常感谢。请问矩形内圆形碰撞的完整代码例子能否上传到Github?
我把它放fiddle里了,https://jsfiddle.net/timwzw/bLGC6/