作者：吴冠希注：1.本文只讨论2D图形碰撞检测。2、本文讨论圆与圆、矩形与矩形、圆与矩形碰撞检测的矢量实现前言在2D游戏中，通常用矩形和圆来代替复杂图形的交点检测。因为这两种形状的碰撞检测速度是最快的。其中，矩形包围盒又可分为轴对齐包围盒（AABB，AxisAlignedBoundingBox）和转向包围盒（OBB，OrientedBoundingBox）。AABB和OBB的区别在于AABB中矩形的一条边平行于坐标轴，OBB的计算复杂度比AABB高。根据不同的使用场景，可以采用不同的方案。如上图所示，很明显pickup适合boundingbox，pokeball适合boundingball。矢量作为一种数学工具，矢量在碰撞检测中起着很大的作用。后面的计算都是通过vector来完成的，所以我们先复习一下vector。向量的代数表示向量的代数表示是指在指定一个坐标系后，用一个向量在该坐标系中的坐标来表示该向量，它结合了符号的抽象和几何意象，因此具有最高的实用性，广泛应用于需要定量分析的场合。对于自由向量，将向量的起点平移到坐标原点后，向量可以用坐标系中的一个点来表示，该点的坐标值就是向量的终点坐标。//二维平面向量类Vector2d{constructor(vx=1,vy=1){this.vx=vx;这个.vy=vy；}}constvecA=newVector2d(1,2);constvecB=newVector2d(3,1);向量运算与加法：向量的加法满足平行四边形法则和三角形法则。具体来说，两个向量相加还是一个向量，分别是x和y的两个分量相加。//向量加法staticadd(vec,vec2){constvx=vec.vx+vec2.vx;constvy=vec.vy+vec2.vy；returnnewVector2d(vx,vy);}相减：两个向量a和b相减得到的向量可以表示为a和b的起点之后从b的终点到a的终点的向量coincident://向量减法staticsub(vec,vec2){constvx=vec.vx-vec2.vx;constvy=vec.vy-vec2.vy；returnnewVector2d(vx,vy);}大小：向量的大小是每个分量的平方和根。//获取向量的长度length(){returnMath.sqrt(this.vx*this.vx+this.vy*this.vy);}点积：从代数的角度来看，首先对中的每一组将两个数列对应的元素相乘，然后将所有乘积相加，结果就是点积。//向量的量积staticdot(vec,vec2){returnvec.vx*vec2.vx+vec.vy*vec2.vy;}旋转：向量的旋转可以通过旋转矩阵求解//矢量的旋转staticrotate(vec,angle){constcosVal=Math.cos(angle);constsinVal=Math.sin(角度);constvx=vec.vx*cosVal-vec.vy*sinVal;constvy=vec.vx*sinVal+vec.vy*cosVal;returnnewVector2d(vx,vy);}圆比较简单，确定圆心x、y和半径r即可，然后推导出圆心向量。classCircle{//x,y为圆心r为半径构造函数(x=0,y=0,r=1){this.x=x;这个.y=y;这个.r=r;}getP(){returnnewVector2d(this.x,this.y)}//centervector}矩形比较复杂。定义一个矩形需要x,y的圆心坐标，两边的长度w和h，并根据圆心旋转角度rotationexportclassRect{//x,y是矩形圆心的坐标w是宽度h为高度rotation为角度单位degconstructor(x=0,y=0,w=1,h=1,rotation=0){this.x=x;这个.y=y;这个.w=w;这个.h=h;this.rotation=旋转；}}两圆相交两圆相交比较简单，只需要判断两圆心的距离小于两圆半径之和即可。两个中心之间的距离可以减去中心向量，然后求出减去向量的长度。circleCircleIntersect(circle1,circle2){constP1=circle1.P;constP2=circle2.P;constr1=circle1.r;constr2=circle2.r;constu=Vector2d.sub(P1,P2);返回你。length()<=r1+r2;}圆与矩形的交集涉及到矩形的交集。首先要确定它是否是轴对称的。矩形轴对称先看轴对称情况，以下来自知乎问题如何判断矩形和圆在平面上是否重合？“MiloYip”的答案转：设c为长方形的圆心，h为长方形的一半长度，p为圆心，r为半径。方法是计算圆心到矩形的最短距离u，如果u的长度小于r，则两者相交。先用绝对值将p-c转移到第一象限。下图可以看出，不同象限的中心也可以映射到第一象限，不影响相交测试的结果：然后，v减去h，负分量设为0，向量u的求出圆心到矩形的最短距离。下图显示了4种情况，红色的u是结果。最后比较u和r的长度，如果距离小于r，则两者相交。只能求u的长度的平方是否小于r的平方。我用js实现一下：矩形的四个顶点分别命名为A1、A2、A3、A4，第一象限矩形的半长h等于CA3classRect{//x,y为坐标矩形中心的w为宽h为高旋转为角度单位degconstructor(x=0,y=0,w=1,h=1,rotation=0){this.x=x;这个.y=y;这个.w=w;这。h=h;this.rotation=旋转；}getC(){returnnewVector2d(this.x,this.y);}//矩形中心向量getA3(){returnnewVector2d(this.x+this.w/2,this.y+this.h/2);}//顶点A3向量}rectCircleIntersect(rect,circle){constC=rect.C;constr=circle.r;constA3=rect.A3;constP=circle.P;consth=Vector2d.sub(A3,C);//矩形半长constv=newVector2d(Math.abs(P.vx-C.vx),Math.abs(P.vy-C.vy));constu=newVector2d(Math.max(v.vx-h.vx,0),Math.max(v.vy-h.vy,0));returnu.lengthSquared()<=r*r;}非轴对称矩形的问题其实很好解决。以矩形的中心为旋转中心，将矩形和圆反向旋转，使矩形变为轴对称，即可应用上述解法。从矩形圆心到圆心的向量就是向量CP'，就是CP反向旋转θ度。然后根据向量的三角定律，将OP'=OC+CP'代入矩形轴对称的公式中进行计算。classRect{//x,y是矩形中心的坐标w是宽度h是高度rotation是角度单位degconstructor(x=0,y=0,w=1,h=1,rotation=0){这个.x=x;这个.y=y;这个.w=w;这个.h=h;this.rotation=旋转；}getC(){returnnewVector2d(this.x,this.y);}//矩形中心向量getA3(){returnnewVector2d(this.x+this.w/2,this.y+this.h/2);}//顶点A3向量get_rotation(){returnthis.rotation/180*Math.PI;}//角度单位转换}p(rect,circle){constrotation=rect.rotation;constC=rect.C;让P;if(旋转%360===0){P=circle.P;//直接轴对称输出P}else{P=Vector2d.add(C,Vector2d.rotate(Vector2d.sub(circle.P,C),rect._rotation*-1));//非轴对称，计算P'}returnP;}rectCircleIntersect(rect,circle){constrotation=rect.rotation;constC=rect.C;constr=circle.r;constA3=rect.A3;constP=p（矩形，圆）；Vector2d.sub(A3,C);constv=newVector2d(Math.abs(P.vx-C.vx),Math.abs(P.vy-C.vy));constu=newVector2d(Math.max(v.vx-h.vx,0),Math.max(v.vy-h.vy,0));returnu.lengthSquared()<=r*r;}查看Demo1https://rococolate.github.io/blog/gom/test1.html两个矩形相交两个矩形都是轴对称的AABB想象两个矩形A和B，B是附加的向A走一圈，B的矩形中心的轨迹就是一个新的矩形，这就简化为新的矩形与B的中心点的交点问题，又因为点可以看成一个半径为圆的圆的0，所以问题是转换为圆和矩形相交classRect{//x,y是矩形中心的坐标w是宽度h是高度rotation是角度单位degconstructor(x=0,y=0,w=1,h=1,rotation=0){这个.x=x;这个.y=y;这个.w=w;这个.h=h;this.rotation=旋转；}getC(){returnnewVector2d(this.x,this.y);}//矩形中心向量getA3(){returnnewVector2d(this.x+this.w/2,this.y+this.h/2);}//顶点A3向量get_rotation(){returnthis.rotation/180*Math.PI;}//角度单位转换}AABBrectRectIntersect(rect1,rect2){constP=rect2.C;constw2=rect2.w;consth2=rect2.h;const{w,h,x,y}=rect1;constC=rect1.C;constA3=newVector2d(x+w/2+w2/2,y+h/2+h2/2);//新矩形的一半长度constH=Vector2d.sub(A3,C);constv=newVector2d(Math.abs(P.vx-C.vx),Math.abs(P.vy-C.vy));constu=newVector2d(Math.max(v.vx-H.vx,0),Math.max(v.vy-H.vy,0));返回u.lengthSquared()===0;//一个点可以看作是一个半径为0的圆}两个矩形相交的非轴对称OBB两个矩形的OBB检测使用了分离轴定理（SeparatingAxisTheorem）：通过判断任意两个矩形的投影是否在任意角度重叠，判断是否发生碰撞。如果两个物体在某个角度的光源下的投影之间存在一定的间隙，那么就没有碰撞；否则，就会发生碰撞。因为矩形的对边平行，所以只需要判断在四个对称轴上的投影即可。如何投射？这里补充一下向量点积的几何意义。在欧氏空间中，点积可以直观地定义为AB=|A||B|cosθ，其中|A|cosθ是A到B的投影，如果B是单位向量，那么AB就是A的投影到单位向量B返回矩形，矩形的四个顶点投影到对称轴上，分别相乘即可。classRect{//x,y是矩形中心的坐标w是宽度h是高度rotation是角度单位degconstructor(x=0,y=0,w=1,h=1,rotation=0){这个.x=x;这个.y=y;这个.w=w;这个.h=h;this.rotation=旋转；}getC(){returnnewVector2d(this.x,this.y);}get_A1(){returnnewVector2d(this.x-this.w/2,this.y-this.h/2);}//4个角顶点get_A2(){returnnewVector2d(this.x+this.w/2,this.y-this.h/2);}get_A3(){returnnewVector2d(this.x+this.w/2,this.y+this.h/2);}get_A4(){returnnewVector2d(this.x-this.w/2,this.y+this.h/2);}get_axisX(){返回新的Vector2d(1,0);}//不旋转时的对称轴Xget_axisY(){returnnewVector2d(0,1);}//不旋转时的对称轴Yget_CA1(){returnVector2d.sub(this._A1,this.C);}get_CA2(){返回Vector2d.sub(this._A2,this.C);}get_CA3(){返回Vector2d.sub(this._A3,this.C);}get_CA4(){returnVector2d.sub(this._A4,this.C);}get_rotation(){returnthis.rotation/180*Math.PI;}getA1(){returnthis.rotation%360===0?这个._A1:Vector2d.add(this.C,Vector2d.rotate(this._CA1,this._rotation));}//计算4角顶点getA2(){returnthis.rotation%360===0?this._A2:Vector2d.add(this.C,Vector2d.rotate(this._CA2,this._rotation));}getA3(){returnthis.rotation%360===0?this._A3:Vector2d.add(this.C,Vector2d.rotate(this._CA3,this._rotation));}getA4(){returnthis.rotation%360===0?this._A4:Vector2d.add(this.C,Vector2d.rotate(this._CA4,this._rotation));}getaxisX(){returnthis.rotation%360===0吗？this._axisX:Vector2d.rotate(this._axisX,this._rotation);}//计算旋转的对称轴XgetaxisY(){returnthis.rotation%360===0?this._axisY:Vector2d.rotate(this._axisY,this._rotation);}//计算上旋转后的对称轴Yget_vertexs(){return[this._A1,this._A2,this._A3,this._A4];}getvertexs(){返回[this.A1,this.A2,this.A3,this.A4];}//4角顶点数组}OBBrectRectIntersect(rect1,rect2){constrect1AxisX=rect1.axisX;constrect1AxisY=rect1.axisY;constrect2AxisX=rect2.axisX;constrect2AxisY=rect2.axisY;如果(!cross(rect1,rect2,rect1AxisX))返回false；//一旦轴不相交就返回falseif(!cross(rect1,rect2,rect1AxisY))returnfalse;如果(!cross(rect1,rect2,rect2AxisX))返回false；如果(!cross(rect1,rect2,rect2AxisY))返回false；返回真；//4轴投影全部相交returntrue}cross(rect1,rect2,axis){constvertexs1ScalarProjection=rect1.vertexs.map(vex=>Vector2d.dot(vex,axis)).sort((a,b)=>a-b);//矩形1的4个顶点投影和Sortconstvertexs2ScalarProjection=rect2.vertexs.map(vex=>Vector2d.dot(vex,axis)).sort((a,b)=>a-b);//矩形2的4个顶点被投影和排序constrect1Min=vertexs1ScalarProjection[0];//矩形1的最小长度constrect1Max=vertexs1ScalarProjection[vertexs1ScalarProjection.length-1];//矩形1的最大长度constrect2Min=vertexs2ScalarProjection[0];//矩形2的最小长度constrect2Max=vertexs2ScalarProjection[vertexs1ScalarProjection.length-1];//矩形2的最大长度returnrect1Max>=rect2Min&&rect2Max>=rect1Min;//相交判断}最后放一个相交的应用Demohttps://rococolate.github.io/blog/gom/test2.html，demo中的形状可以拖拽，碰到其他形状会变透明。参考文章第15章：碰撞检测http://blog.jmecn.net/chapter-15-collision-detection/方块大战：说说格斗游戏的精髓http://daily.zhihu.com/story/4761397如何判断矩形和圆形在平面上是否重叠？https://www.zhihu.com/question/24251545“等一下，我摸！”-常见2D碰撞检测https://aotu.io/notes/2017/02/16/2d-collision-detection/index.html码农干货系列【1】--OrientationBoundingBox(OBB)CollisionDetectionhttps：//www.cnblogs.com/iamzhanglei/archive/2012/06/07/2539751.html旋转矩阵https://en.wikipedia.org/wiki/Rotation_matrix量积https://zh.wikipedia.org/wiki/%E7%82%B9%E7%A7%AF向量https://zh.wikipedia.org/wiki/%E5%90%91%E9%87%8F如果您觉得这篇内容对您有价值，请点个赞，关注我们的官网和我们的微信公众号(WecTeam)，每周都有优质文章推送：
