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

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

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

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

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

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

向量及其运算

定义

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

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

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

我们可以定义向量AB为:

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

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

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

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

向量运算

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

单位向量

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

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

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

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

加法

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

c⃗ =a⃗ +b⃗ 
在程序中c⃗ 可以用如下方式表达:

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

点积

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

A⃗ B⃗ =|A⃗ | |B⃗ | cosθθA⃗ B⃗ 

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

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

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

投影

向量A⃗ B⃗ 上的投影向量就是:一个向量长度A⃗ B⃗ 方向上投影长度,向量方向B⃗ 方向的向量。

其实,你只需要参照点积的图,看到|A⃗ | cosθ,就是A⃗ B⃗ 上的投影长度。

投影长度乘B⃗ 的单位向量,则为向量A⃗ B⃗ 上的投影向量。

所以A⃗ B⃗ 上投影向量为(|A⃗ |cosθ) DB,其中DBB⃗ 的单位向量。

我们可以利用点积来简化运算,A⃗ DB=|A⃗ | |DB| cosθ,由于DB为单位向量,所以(|A⃗ |cosθ) DB=(A⃗ DB)DB

代码如下:

叉乘

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

A⃗ ×B⃗ =|A⃗ | |B⃗ | sinθ n⃗ θA⃗ B⃗ n⃗ a⃗  b⃗ 

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

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

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

法向量

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

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

若点在向量左边,则叉乘小于0,则vxfyvyfx<0

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

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

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

同理,左法向量表示为:

坐标更新

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

对于圆的行进更新,很自然会想到每帧将圆的位置从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的法向量上的投影向量即可。

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

代码如下:

反弹

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

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

代码如下:

DEMO

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

有关代码托管于Github:

问题

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

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

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

3 responses

发表评论

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