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

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

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

在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，其中→DB为→B的单位向量。

我们可以利用点积来简化运算，→A⋅→DB=|→A| |→DB| cosθ，由于→DB为单位向量，所以(|→A|cosθ) →DB=(→A⋅→DB)∗→DB 代码如下：

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

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

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

注意：在以上代码中判断的是<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的右法向量表示为：

同理，左法向量表示为：

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

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

代码如下：

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

有关代码托管于Github:

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

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

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

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