碰撞检测的向量实现

吴冠禧

注：1、本文只讨论2d图形碰撞检测。2、本文讨论圆形与圆形，矩形与矩形、圆形与矩形碰撞检测的向量实现

前言

2D游戏中，通常使用矩形、圆形等来代替复杂图形的相交检测。因为这两种形状的碰撞检测速度是最快的。其中矩形包围盒又可以分为轴对齐包围盒（AABB, Axis Aligned Bounding Box）与转向包围盒（OBB, Oriented Bounding Box）。AABB与OBB的区别在于，AABB中的矩形的其中一条边和坐标轴平行，OBB的计算复杂度要高于AABB。根据不同的使用场景，可以用不同的方案。

如上图，明显皮卡超适合用包围盒，精灵球适合用包围球。

向量

向量作为一种数学工具，在碰撞检测中发挥很大作用，后面的计算都是通过向量来完成，所以先来复习一下向量。

向量的代数表示

向量的代数表示指在指定了一个坐标系之后，用一个向量在该坐标系下的坐标来表示该向量，兼具了符号的抽象性和几何形象性，因而具有最高的实用性，被广泛采用于需要定量分析的情形。 对于自由向量，将向量的起点平移到坐标原点后，向量就可以用一个坐标系下的一个点来表示，该点的坐标值即向量的终点坐标。

// 二维平面向量
class Vector2d{
  constructor(vx=1,vy=1){
    this.vx = vx;
    this.vy = vy;
  }
}
const vecA = new Vector2d(1,2);
const vecB = new Vector2d(3,1);

向量运算

加法：向量的加法满足平行四边形法则和三角形法则。具体的，两向量相加还是一个向量，分别是x与y两个分量的相加。

// 向量的加法运算
static add(vec,vec2){
  const vx = vec.vx + vec2.vx;
  const vy = vec.vy + vec2.vy;
  return new Vector2d(vx,vy);
}

减法：两个向量a和b的相减得到的向量可以表示为a和b的起点重合后，从b的终点指向a的终点的向量：

// 向量的减法运算
static sub(vec,vec2){
  const vx = vec.vx - vec2.vx;
  const vy = vec.vy - vec2.vy;
  return new Vector2d(vx,vy);
}

大小：向量的大小，是其各个分量的平方和开方。

// 获取向量长度
length(){
  return Math.sqrt(this.vx * this.vx + this.vy * this.vy);
}

点积：从代数角度看，先对两个数字序列中的每组对应元素求积，再对所有积求和，结果即为点积。

// 向量的数量积
static dot(vec,vec2){
  return vec.vx * vec2.vx + vec.vy * vec2.vy;
}

旋转：向量的旋转可以用旋转矩阵求解

//向量的旋转 
static rotate(vec,angle){
  const cosVal = Math.cos(angle);
  const sinVal = Math.sin(angle);
  const vx = vec.vx * cosVal - vec.vy * sinVal;
  const vy = vec.vx * sinVal + vec.vy * cosVal;
  return new Vector2d(vx,vy);
}

圆

圆形比较简单，只要确认圆心x,y和半径r就行了,然后推导出圆心向量。

class Circle{
  // x,y是圆的圆心 r是半径
  constructor(x=0,y=0,r=1){
    this.x = x;
    this.y = y;
    this.r = r;
  }
  get P(){ return new Vector2d(this.x,this.y) } // 圆心向量
}

矩形

矩形就较为复杂，定义一个矩形需要中心坐标的x,y、两边长w和h，还有根据中心的旋转角度rotation

export class Rect{
  // x,y是矩形中心的坐标 w是宽 h是高 rotation是角度单位deg
  constructor(x=0,y=0,w=1,h=1,rotation=0){
    this.x = x;
    this.y = y;
    this.w = w;
    this.h = h;
    this.rotation = rotation;
  }
}

两圆相交

两圆相交比较简单，只需判断两圆心之间的距离小于两圆的半径之和。

两圆心距离可以用圆心向量相减，然后求相减向量的长度。

circleCircleIntersect(circle1,circle2){
  const P1 = circle1.P;
  const P2 = circle2.P;
  const r1 = circle1.r;
  const r2 = circle2.r;
  const u = Vector2d.sub(P1,P2);
  return u.length() <= r1  + r2 ;
}

圆和矩形相交

涉及到矩形的相交问题都先要判断是否轴对称。

矩形轴对称

先看轴对称的情况，下面是来自知乎问题 怎样判断平面上一个矩形和一个圆形是否有重叠？ 「Milo Yip」的回答搬运：

设c为矩形中心，h为矩形半长，p为圆心，r为半径。

方法是计算圆心与矩形的最短距离 u，若 u 的长度小于 r 则两者相交。

1. 1. 首先利用绝对值把 p – c 转移到第一象限，下图显示不同象限的圆心也能映射至第一象限，这不影响相交测试的结果：

1. 1. 然后，把 v 减去 h，负数的分量设置为0，就得到圆心与矩形最短距离的矢量 u。下图展示了4种情况，红色的u是结果。

1. 1. 最后要比较 u 和 r 的长度，若距离少于 r，则两者相交。可以只求 u 的长度平方是否小于 r 的平方。

下面我用js实现一下：

其中矩形的四个顶点命名为A1，A2，A3，A4，矩形在第一象限的半长h等于CA3

class Rect{
  // x,y是矩形中心的坐标 w是宽 h是高 rotation是角度单位deg
  constructor(x=0,y=0,w=1,h=1,rotation=0){
    this.x = x;
    this.y = y;
    this.w = w;
    this.h = h;
    this.rotation = rotation;
  }
  get C(){ return new Vector2d(this.x,this.y); } // 矩形中心向量
  get A3(){ return new Vector2d(this.x+this.w/2,this.y+this.h/2); } // 顶点A3向量
}
rectCircleIntersect(rect,circle){
  const C = rect.C;
  const r = circle.r;
  const A3 = rect.A3;
  const P = circle.P;
  const h = Vector2d.sub(A3,C); // 矩形半长
  const v = new Vector2d(Math.abs(P.vx - C.vx),Math.abs(P.vy - C.vy));
  const u = new Vector2d(Math.max(v.vx - h.vx,0),Math.max(v.vy - h.vy,0));
  return u.lengthSquared() <= r * r;
}

矩形非轴对称

这个问题其实也很好解决，将矩形中心视为旋转中心，将矩形和圆形一起反向旋转将矩形转为轴对称，然后就可以套用上面的解法。

矩形中心到圆心向量为是CP

反向旋转θ度得向量CP’

然后根据向量得三角形定律得OP’ = OC + CP’

后面就代入矩形是轴对称的公式进行计算

class Rect{
  // x,y是矩形中心的坐标 w是宽 h是高 rotation是角度单位deg
  constructor(x=0,y=0,w=1,h=1,rotation=0){
    this.x = x;
    this.y = y;
    this.w = w;
    this.h = h;
    this.rotation = rotation;
  }
  get C(){ return new Vector2d(this.x,this.y); } // 矩形中心向量
  get A3(){ return new Vector2d(this.x+this.w/2,this.y+this.h/2); } // 顶点A3向量
  get _rotation(){ return this.rotation / 180 * Math.PI; }  // 角度单位转换
}
p(rect,circle){
  const rotation = rect.rotation;
  const C = rect.C;
  let P;
  if (rotation % 360 === 0) {
    P = circle.P; // 轴对称直接输出P
  } else {
    P = Vector2d.add(C,Vector2d.rotate(Vector2d.sub(circle.P,C),rect._rotation*-1)); // 非轴对称，计算P‘
  }
  return P;
}
rectCircleIntersect(rect,circle){
  const rotation = rect.rotation;
  const C = rect.C;
  const r = circle.r;
  const A3 = rect.A3;
  const P = p(rect,circle);
  const h = Vector2d.sub(A3,C);
  const v = new Vector2d(Math.abs(P.vx - C.vx),Math.abs(P.vy - C.vy));
  const u = new Vector2d(Math.max(v.vx - h.vx,0),Math.max(v.vy - h.vy,0));
  return u.lengthSquared() <= r * r;
}

查看Demo1 rococolate.github.io/blog/gom/te…

两矩形相交

两矩形都轴对称AABB

想象一下两个矩形A和B，B贴着A的边走了一圈，B的矩形中心的轨迹是一个新的矩形，这样就简化成新矩形与B中心点这一点的相交问题，又因为点可以看成是半径为0的圆，所以问题又转换为圆形和矩形相交。

class Rect{
  // x,y是矩形中心的坐标 w是宽 h是高 rotation是角度单位deg
  constructor(x=0,y=0,w=1,h=1,rotation=0){
    this.x = x;
    this.y = y;
    this.w = w;
    this.h = h;
    this.rotation = rotation;
  }
  get C(){ return new Vector2d(this.x,this.y); } // 矩形中心向量
  get A3(){ return new Vector2d(this.x+this.w/2,this.y+this.h/2); } // 顶点A3向量
  get _rotation(){ return this.rotation / 180 * Math.PI; }  // 角度单位转换
}
AABBrectRectIntersect(rect1,rect2){
  const P = rect2.C;
  const w2 = rect2.w; 
  const h2 = rect2.h; 
  const {w,h,x,y} = rect1;
  const C = rect1.C;
  const A3 = new Vector2d(x+w/2+w2/2,y+h/2+h2/2); // 新矩形的半长
  const H = Vector2d.sub(A3,C);
  const v = new Vector2d(Math.abs(P.vx - C.vx),Math.abs(P.vy - C.vy));
  const u = new Vector2d(Math.max(v.vx - H.vx,0),Math.max(v.vy - H.vy,0));
  return u.lengthSquared() === 0; // 点可以看成是半径为0的圆
}

两矩形相交非轴对称OBB

两个矩形的OBB检测使用分离轴定理（Separating Axis Theorem）

分离轴定理：通过判断任意两个矩形 在任意角度下的投影是否均存在重叠，来判断是否发生碰撞。若在某一角度光源下，两物体的投影存在间隙，则为不碰撞，否则为发生碰撞。

因为矩形的对边平行，所以只要判断四条对称轴上的投影即可。

如何投影？这里补充一下向量点积的几何意义。

在欧几里得空间中，点积可以直观地定义为 A·B = |A||B|cosθ ,其中|A|cosθ是A到B的投影，如果B是单位向量，那幺A·B就是A到单位向量B的投影

回到矩形，将矩形4个顶点都投影到对称轴上，我们分别将其点乘即可。

class Rect{
  // x,y是矩形中心的坐标 w是宽 h是高 rotation是角度单位deg
  constructor(x=0,y=0,w=1,h=1,rotation=0){
    this.x = x;
    this.y = y;
    this.w = w;
    this.h = h;
    this.rotation = rotation;
  }
  get C(){ return new Vector2d(this.x,this.y); }
  get _A1(){ return new Vector2d(this.x-this.w/2,this.y-this.h/2); }  // 4角顶点
  get _A2(){ return new Vector2d(this.x+this.w/2,this.y-this.h/2); }
  get _A3(){ return new Vector2d(this.x+this.w/2,this.y+this.h/2); }
  get _A4(){ return new Vector2d(this.x-this.w/2,this.y+this.h/2); }
  get _axisX(){ return new Vector2d(1,0); } // 未旋转时的对称轴X
  get _axisY(){ return new Vector2d(0,1); } // 未旋转时的对称轴Y
  get _CA1(){ return Vector2d.sub(this._A1,this.C); }
  get _CA2(){ return Vector2d.sub(this._A2,this.C); }
  get _CA3(){ return Vector2d.sub(this._A3,this.C); }
  get _CA4(){ return Vector2d.sub(this._A4,this.C); }
  get _rotation(){ return this.rotation / 180 * Math.PI; }
  get A1(){ return this.rotation % 360 === 0 ?  this._A1 :  Vector2d.add(this.C,Vector2d.rotate(this._CA1,this._rotation)); } // 计算上旋转后4角顶点
  get A2(){ return this.rotation % 360 === 0 ?  this._A2 :  Vector2d.add(this.C,Vector2d.rotate(this._CA2,this._rotation)); }
  get A3(){ return this.rotation % 360 === 0 ?  this._A3 :  Vector2d.add(this.C,Vector2d.rotate(this._CA3,this._rotation)); }
  get A4(){ return this.rotation % 360 === 0 ?  this._A4 :  Vector2d.add(this.C,Vector2d.rotate(this._CA4,this._rotation)); }
  get axisX(){ return this.rotation % 360 === 0 ?  this._axisX :  Vector2d.rotate(this._axisX,this._rotation); } // 计算上旋转后的对称轴X
  get axisY(){ return this.rotation % 360 === 0 ?  this._axisY :  Vector2d.rotate(this._axisY,this._rotation); } // 计算上旋转后的对称轴Y
  get _vertexs(){ return [this._A1,this._A2,this._A3,this._A4]; } 
  get vertexs(){ return [this.A1,this.A2,this.A3,this.A4]; } // 4角顶点数组
}
OBBrectRectIntersect(rect1,rect2){
  const rect1AxisX = rect1.axisX;
  const rect1AxisY = rect1.axisY;
  const rect2AxisX = rect2.axisX;
  const rect2AxisY = rect2.axisY;
  if (!cross(rect1,rect2,rect1AxisX)) return false;  // 一旦有不相交的轴就可以return false
  if (!cross(rect1,rect2,rect1AxisY)) return false;
  if (!cross(rect1,rect2,rect2AxisX)) return false;
  if (!cross(rect1,rect2,rect2AxisY)) return false;
  return true;  // 4轴投影都相交 return true
}
cross(rect1,rect2,axis){
  const vertexs1ScalarProjection = rect1.vertexs.map(vex => Vector2d.dot(vex,axis)).sort((a,b)=>a-b); // 矩形1的4个顶点投影并排序
  const vertexs2ScalarProjection = rect2.vertexs.map(vex => Vector2d.dot(vex,axis)).sort((a,b)=>a-b); // 矩形2的4个顶点投影并排序
  const rect1Min = vertexs1ScalarProjection[0]; // 矩形1最小长度
  const rect1Max = vertexs1ScalarProjection[vertexs1ScalarProjection.length - 1]; // 矩形1最大长度
  const rect2Min = vertexs2ScalarProjection[0]; // 矩形2最小长度
  const rect2Max = vertexs2ScalarProjection[vertexs1ScalarProjection.length - 1]; // 矩形2最大长度
  return rect1Max >= rect2Min && rect2Max >= rect1Min;  // 相交判断 
}

最后放上一个相交的应用Demo rococolate.github.io/blog/gom/te… ,Demo里的形状都可以拖拽，当碰到其他形状时会变透明。