你被追尾了

缘起

被追尾了,严格来讲,就是你的汽车和别人的汽车发生了碰撞. 所以本文来介绍一些检测碰撞的算法.

分析

鉴于所见即所得的观点,本文的代码使用了 html5, 如果对于 html5 canvas API 如果不清楚的话,可以参考 w3c 手册.

外接图形判别法(Axis-Aligned Bounding Box)

首先是最为简单的外接图形判别法. 例如我们想实现一个小球在如下的盒子内的移动,在移动过程中如果碰到边界就反弹(假定弹性碰撞,无机械能损失).

那么我们只需要在小球外接一个正方形,然后判定该正方形和边框是否发生碰撞就行了. 即想下图这样考虑蓝色的小正方形和矩形边框的碰撞情况就行了

代码如下(选择 JavaScript 完全是出于所见即所得的目的~)

<html>
  <style type="text/css">
    * {
        margin:0;
        padding:0;
    }
    canvas {
        border:1px solid orange;
        margin:10px auto 0;
        display:block;
    }
</style>
  
  <body>
    <!-- html5 画布对象 -->
    <canvas id="canvas" width="300" height="200"></canvas>
  </body>
  <script>
    // 构造小球的函数
    var Ball = function(context) {
      // 球的外切正方形的左上角顶点坐标
      this.left = 0;
      this.top = 0;
      // 小球的半径
      this.radius = 16;
      // 小球的水平速度
      this.velocityX = 3;
      // 小球的垂直速度
      this.velocityY = 2;
      // 传入 H5 画布
      this.context = context;
    }

    // 定义球拥有的方法
    Ball.prototype = {
      // 画球本身
      paint: function() {
        this.context.beginPath();
        this.context.arc(this.left + this.radius, this.top + this.radius, this.radius, 0, Math.PI * 2, false);
        this.context.fill();
      },

      // 球如何移动
      move: function() {
        this.left += this.velocityX;
        this.top += this.velocityY;
      }
    }
    
    // 处理边界碰撞逻辑
    function handleEdgeCollisions(ball) {
      // 球的外切正方形右下角
      var ballRight = ball.left + ball.radius * 2;
      var ballBottom = ball.top + ball.radius * 2;

      // 球碰撞到了画布的左边框
      if (ball.left < 0) {
        ball.left = 0;
        // 速度等值反向实现弹性碰撞
        ball.velocityX = -ball.velocityX;
      // 球碰到了画布的右边框
      } else if (ballRight > canvas.width) {
        ball.left = canvas.width - ball.radius * 2;
        ball.velocityX = -ball.velocityX;
      }

      // 球碰到了画布的上边框
      if (ball.top < 0) {
        ball.top = 0;
        ball.velocityY = -ball.velocityY;
      // 球碰到了画布的下边框
      } else if (ballBottom > canvas.height) {
        ball.top = canvas.height - ball.radius * 2;
        ball.velocityY = -ball.velocityY;
      }
    }
    
    // 重新绘制图帧
    function animate(time) {
      context.clearRect(0, 0, canvas.width, canvas.height);
      ball.move();
      handleEdgeCollisions(ball);
      ball.paint();
      requestAnimationFrame(animate);
    }

    var canvas = document.getElementById('canvas');
    context = canvas.getContext('2d');
    ball = new Ball(context);

    ball.paint();
    requestAnimationFrame(animate);
  </script>

</html>

其中 requestAnimationFrame 这个函数的作用在于传入浏览器重新渲染时的回调函数(即所谓的raf回调)——这里是 animate 函数. 这样 JavaScript 事件环(eventloop)重新渲染页面的时候就会触发 animate 回调.

事实上,通过外接图形判别法,我们将碰撞检测化归为了两个矩形之间的碰撞情况

矩形 rect1 和 rect2 之间相交的充要条件是

rect1.x < rect2.x + rect2.width && rect2.x < rect1.x + rect1.width
&&
rect1.y < rect2.y + rect2.height && rect2.y < rect1.y + rect1.height

我们可以再写一个较为纯粹的矩形物体之间碰撞检测的demo,注意,为节约篇幅,下面仅仅写出最为核心的检测碰撞的逻辑, 而省略掉了其他诸如canvas绘制的逻辑.

// 矩形碰撞检测的逻辑,返回true 表示发生了碰撞, 返回false 表示未发生碰撞, 下同
function handleEgdeCollisions(rect1, rect2) {
    return rect1.left < rect2.left + rect2.width && rect2.left < rect1.left + rect1.width && rect1.top < rect2.top + rect2.height && rect2.top < rect1.height + rect1.top;
}

运行效果如下

外接图形判别法的优点是极为简单,但是缺点也是瞎眼可见的

  • 相对局限:两物体必须是矩形,且均不允许旋转,即上面的矩形的边必须平行于坐标轴.
  • 对于包含着图案(非填满整个矩形)的矩形进行碰撞检测,可能存在精度不足的问题。例如你写一个坦克大战游戏

其实坦克模型并非标准的矩形(例如炮管和坦克机身就有缝隙), 但是你使用一个外接矩形来模拟坦克之间的碰撞,就可能存在精度不足的问题,或者说没办法模拟的很真实.

物体运动速度过快时,可能会在相邻两动画帧之间快速穿越,导致忽略了本应碰撞的事件发生。这一点其实也很好理解,就拿浏览器来说,浏览器上运行JavaScript代码其实是通过事件环(EventLoop)机制的. 浏览器的两个动画帧之间会加入我们指定浏览器要做的任务回调,如果两个矩形的运动速度过快会导致浏览器根本来不及渲染,它俩就互相穿透彼此而过了. 然后就忽略了此次碰撞. 不过这貌似并不是碰撞检测算法的问题, 而是显示设备的渲染逻辑问题

适用案例:

  • (类)矩形物体间的碰撞。

圆形碰撞(Circle Collision)

圆心物体之间的碰撞是很好处理的. 只需要 通过判断任意两个圆形的圆心距离是否小于两圆半径之和,若小于则为碰撞。

示例代码(和矩形碰撞检测的代码几乎一样)

function handleEgdeCollisions(circle1, circle2) {
    var circle1X = circle1.left + circle1.radius;
    var circle1Y = circle1.top + circle1.radius;
    var circle2X = circle2.left + circle2.radius;
    var circle2Y = circle2.top + circle2.radius;
    var distance = Math.sqrt(Math.pow(circle1X - circle2X, 2) + Math.pow(circle1Y - circle2Y, 2));
    return distance < circle1.radius + circle2.radius;
}

运行效果

既然代码和矩形碰撞检测的代码类似,那么优缺点和适用场景和矩形碰撞检测也就完全类似了

圆形与无旋转矩形

所谓无旋转前面已经解释过了, 就是矩形的边需要平行于坐标轴

那么这种检测算法就很简单了. 只需要找出 矩形上离圆心最近的点,然后通过判断该点与圆心的距离是否小于圆的半径,若小于则为碰撞。

那么如何找出矩形上离圆心最近的点呢? 一种比较粗暴的算法是

  1. 判断圆心是不是在矩形内部,如果都在内部的话,没什么好说的,肯定发生碰撞了.
  2. 然后直接暴力计算圆心到矩形的四条边的最短距离.

但是有没有简单点的办法呢? 因为这里限定了矩形是不旋转的. 所以按直觉理应有更为简单的做法.

令 closestPoint 为我们想求的那个 矩形上离圆心最近的点,则

  • 如果圆心在矩形的左侧(if(circle.x < rect.x)),那么closestPoint.x = rect.x

如果圆心在矩形的右侧(else if(circle.x > rect.x + rect.w)),那么 closestPoint.x = rect.x + rect.w

如果圆心在矩形的正上下方(else),那么 closestPoint.x = circle.x

对于 Y 轴方向做完全类似的分析, 于是我们可以得到如下代码

function detectCollision(rect, circle) {
    var cx, cy;
    if (circle.x < rect.x) {
        cx = rect.x;
    } else if (circle.x > rect.x + rect.w) {
        cx = rect.x + rect.w;
    } else {
        cx = circle.x;
    }
    if (circle.y < rect.y) {
        cy = rect.y;
    } else if (circle.y > rect.y + rect.h) {
        cy = rect.y + rect.h;
    } else {
        cy = circle.y;
    }
    return distance(circle.x, circle.y, cx, cy) < circle.r;
}

运行效果

圆形与旋转矩形(以矩形中心为旋转轴)

算法和上面 圆和无旋转矩形 碰撞的思想完全类似,即本质依旧是求出 矩形上离圆心的最近点

看似有点小困难,但其实你把矩形旋转视作是圆绕着矩形中心反方向旋转的话,就很好理解了. 如下图所示,

绿色的矩形(是蓝色矩形逆时针旋转了

\beta

后的矩形)+绿色的圆形的问题 和 蓝色的矩形+蓝色的圆形的问题 是等价的. 所以我们只需从蓝色矩形逆时针旋转

\beta

变成绿色矩形这一视角转变为绿色圆形顺时针旋转

\beta

转变为蓝色圆形这一视角就行了. 而假设 矩形的中心坐标是 R(rectCenterX, rectCenterY), 令 C(rotateCircleX, rotateCircleY) 是旋转后的圆心的坐标,那么就有如下等式

\overrightarrow{RC'} = \overrightarrow{RC} * e^{-i\beta}

其中 C' 是 C 顺时针旋转

\beta

后的. 则就可以使用上述数学公式方便的计算旋转之后的 圆心坐标.

转换为蓝色矩形和蓝色圆形之后,就可以使用 圆形与无旋转矩形 相交的判定方法了.

示例代码如下

function detectCollision(rect, circle) {
    var cx, cy;
    var angleOfRad = degToRad(-deg);
    // 矩形中心
    var rectCenterX = rect.x + rect.w / 2;
    var rectCenterY = rect.y + rect.h / 2;
    // 顺时针旋转 angleOfRad 后的圆心坐标
    var rotateCircleX = Math.cos(angleOfRad) * (circle.x - rectCenterX) - Math.sin(angleOfRad) * (circle.y - rectCenterY) + rectCenterX;
    var rotateCircleY = Math.sin(angleOfRad) * (circle.x - rectCenterX) + Math.cos(angleOfRad) * (circle.y - rectCenterY) + rectCenterY;
    if (rotateCircleX < rect.x) {
        cx = rect.x;
    } else if (rotateCircleX > rect.x + rect.w) {
        cx = rect.x + rect.w;
    } else {
        cx = rotateCircleX;
    }
    // 和圆形与无旋转矩形一样的步骤获取矩形上距离圆心最近的点
    if (rotateCircleY < rect.y) {
        cy = rect.y;
    } else if (rotateCircleY > rect.y + rect.h) {
        cy = rect.y + rect.h;
    } else {
        cy = rotateCircleY;
    }
    return distance(rotateCircleX, rotateCircleY, cx, cy) < circle.r;
}

运行效果

显然,这种碰撞检测笔之前的碰撞检测适用范围更广了一些.

地图格子划分

其实玩过推箱子游戏的话,这种碰撞检测就很容易理解

即把所有的物体格子化,然后移动物体的过程中,如果两个物体在同一格子的话,就认为两个物体发生了碰撞.

map = [[0, 0, 1, 1, 1, 0, 0, 0, 0], 
       [0, 1, 1, 0, 0, 1, 0, 0, 0], 
       [0, 1, 0, 0, 0, 0, 1, 0, 0], 
       [0, 1, 0, 0, 0, 0, 1, 0, 0], 
       [0, 1, 1, 1, 1, 1, 1, 0, 0]];
function handleEgdeCollisions(player, map) {
    return map[player.top][player.left];
}

运行效果

本算法的缺点是显然的,使用场景的局限性太大,仅仅局限于 推箱子、扫雷等上世纪像素游戏中.

像素检测(Pixel checking)

以像素级别检测物体是否存在重叠,从而判定是否发生碰撞. 这就解决了 外接图形判别法 的第二个缺陷. 该方法的思路可以拿下面的图作为例子予以说明

上图中,效仿外接图形判别法,我们将熊猫和竹子皆视为矩形,则注意,两个矩形有相交并不能说明熊猫和竹子有交,因为熊猫和竹子都并非标准的矩形(因为熊猫和竹子的像素点未必填满整个其所在的矩形),但是矩形相交是熊猫和竹子相交的必要条件. 所以我们判定熊猫和竹子相交的方法是,先求出熊猫和竹子所在矩形的交集,如果该交集是空集,则显然熊猫和竹子不相交,如果不是空集,则势必也是一个矩形(记做P),所以我们只需要取出熊猫在P中的像素点,和竹子在P中的像素点——这是两个长度相等的字节数组,如果存在某个数组索引,使得这两个数组在此索引的值都 > 0 的话,则表明熊猫和竹子相交了.

示例代码

// rect 是交集矩形 P
function handleEgdeCollisions(rect) {
    // 取出熊猫在 P 中的像素字节数组
    var imgData1 = offscreenContextPanda.getImageData(rect.left, rect.top, rect.width, rect.height);
    // 取出竹子在 P 中的像素字节数组
    var imgData2 = offscreenContextBamboo.getImageData(rect.left, rect.top, rect.width, rect.height);
    var imgData1Data = imgData1.data;
    var imgData2Data = imgData2.data;
    // 这里一个像素 4字节, 所以 i += 4
    for(var i = 3, len = imgData1Data.length; i < len; i += 4) {
        if(imgData1Data[i] > 0 && imgData2Data[i] > 0) {
            return true
        }
    }
    return false
}

运行效果

注意,熊猫和竹子所在的矩形已经相交了,但是熊猫和竹子其实并没有相交.

熊猫和竹子这才真正的相交了. 而且,熊猫(竹子)离屏渲染 和 实际显示的canvas 中熊猫(竹子)的位置是完全一致的. 其实上面将熊猫(竹子)离屏数据渲染出来只是为了效果直观一些,实际运用过程中,肯定不会将这些离屏数据在屏幕上渲染出来,而是在内存中使用,因为内存中操作这些数据肯定远比在屏幕上渲染出这些数据快的多.

换言之,实际显示的canvas 只是起到展示作用,碰撞检测完全是在离屏数据offscreenContextPanda、offscreenContextBamboo 中进行的.

该方法的缺点是 因为需要检查每一像素来判定是否碰撞,性能要求比较高。适用于需要以像素级别检测物体是否碰撞的情形.

分离轴定理(Separating Axis Theorem SAT)

通过判断任意两个 凸多边形 在任意角度下的投影是否均存在重叠,来判断是否发生碰撞。若在某一角度光源下,两物体的投影存在间隙,则为不碰撞,否则为发生碰撞。

注意,一旦存在间隙的情况,表明从光源到间隙存在一条直线可以将这两个多边形分离开来,从而这两个多边形不相交. 这就是分离轴定理名字的由来.

但是程序中遍历所有光源的角度是不现实的,那如何确定 投影轴 呢?其实投影轴的数量与多边形的边数相等即可。

如果写伪代码的话,则

function polygonsCollide(polygon1, polygon2) { // 检测 polygon1 和 polygon2 两个多边形是否碰撞, 返回 true 表示发生了碰撞, 返回 false 表示没有发生碰撞
    var axes, projection1, projection2; // 投影轴
    // 根据多边形获取所有投影轴
    axes = polygon1.getAxes();
    axes.push(polygon2.getAxes());
    // 遍历所有投影轴,获取多边形在每条投影轴上的投影
    for(each axis in axes) {
        projection1 = polygon1.project(axis)
        projection2 = polygon2.project(axis)
        // 判断投影轴上的投影是否存在重叠
        if(!projection1.overlaps(projection2))
            return false
    }
    return true
}

算法的复杂度是

O(n^2)

的, 其中 n 是多边形顶点的个数.

显然,上述代码有几个需要解决的地方:

  • 如何确定多边形的各个投影轴,也就是上述 getAxes 函数怎么实现
  • 如何将多边形投射到某条投影轴上,也就是上述 project 函数怎么写
  • 如何检测两段投影是否发生重叠, 也就是上述 overlaps 函数怎么写

我们一个一个的解决这些问题

投影轴(getAxes )

对于凸多边形的边 p1p2 ,它对应的投影轴就如上图所示. 我们首先确定该边的边缘法向量,然后投影轴就是平行于该边缘法向量的直线.

于是,每条多边形的边都可以构造相应的投影轴. 这就是上述 getAxes 函数

投影(project)

通过将一个多边形上的每个顶点与原点(0,0)组成的向量,投影在某一投影轴上,然后维护该多边形在该投影轴上所有投影中的最大值和最小值,这样即可表示一个多边形在某投影轴上的投影了。

注意,上图的投影轴是边 1 对应的投影轴. 为了易于理解,示例图将坐标轴原点(0,0)放置于三角形边1投影轴的适当位置。使得三角形 T 在投影轴上的投影恰好起点为0.

如上图所示,T在投影轴上的投影为黄色的 [Tmin = 0, Tmax], 而 P 在投影轴上的投影为 蓝色的 [Pmin, Pmax].

至于投影使用向量的点积就可以搞定了.

注意,从投影的过程中,我们就能看出为什么 SAT 定理只能针对凸多边形有效,因为凸多边形有一个凹多边形不具备的性质.就是凸多边形在它的任何一条边的同侧,而凹多边形可能在它的某条边的异侧. 于是SAT 定理对凹多边形是不能成立的.

判断重叠(overlaps)

所以投影有重叠部分的重要条件是

projection1.max > projection2.min && projection2.max > projection1.min

圆形与多边形之间的碰撞检测

由于圆形可近似地看成一个有无数条边的正多边形,但是我们不可能按照这些边一一进行投影与测试。我们只需将圆形投射到一条投影轴上即可,这条轴就是圆心与多边形顶点中最近的一点的连线,如图所示:

因此,该投影轴和多边形自身的投影轴就组成了全部待检测的投影轴了。

最后,因为我们判断是否碰撞的图形有圆形和多边形,所以学过一点设计模式的话,就知道应该设计一个抽象的 Shape 类, 然后 圆形和 凸多边形都应该是 Shape 的子类.

示例代码

<html>
    <style type="text/css">
        * {
            margin: 0;
            padding: 0;
        }

        canvas {
            border: 1px solid orange;
            margin: 20px auto 0;
            display: block;
        }
    </style>
    <body>
        <canvas id="canvas" width="600" height="280"></canvas>
    </body>
    <script>
    // 封装向量
    var Vector = function(point) {
        if (point === undefined) {
          this.x = 0;
          this.y = 0;
       }
       else {
          this.x = point.x;
          this.y = point.y;
       }
    }

    Vector.prototype = {
        // 获取向量的模
        getMagnitude: function() {
            return Math.sqrt(Math.pow(this.x, 2) + Math.pow(this.y, 2))
        },
        // 向量的加法
        add: function(vector) {
            var v = new Vector()
            v.x = this.x + vector.x
            v.y = this.y + vector.y
            return v
        },
        // 向量的减法
        subtract: function(vector) {
            var v = new Vector()
            v.x = this.x - vector.x
            v.y = this.y - vector.y
            return v
        },
        // 点积
        dotProduct: function(vector) {
            return this.x * vector.x + this.y * vector.y
        },
        
        // 生成起点为vector的向量
        edge: function(vector) {
            return this.subtract(vector)
        },

        // 法向量, 即投影轴
        perpendicular: function() {
            var v = new Vector()
            v.x = this.y
            v.y = -this.x
            return v
        },
        // 规范化
        normalize: function() {
            var v = new Vector(0, 0),
                m = this.getMagnitude()

            if(m !== 0) {
                v.x = this.x / m
                v.y = this.y /m
            }
            return v
        },

        // 投影轴的单位向量
        normal: function() {
            var p = this.perpendicular()
            return p.normalize()
        }
    }

    // 封装投影
    var Projection = function(min, max) {
        this.min = min
        this.max = max
    }

    Projection.prototype = {
        overlaps: function(projection) {
            return this.max > projection.min && projection.max > this.min
        }
    }

    // 封装多边形
    var Shape = function() {
        this.x = undefined
        this.y = undefined
        this.strokeStyle = 'rgba(255, 253, 208, 0.9)'
        this.fillStyle = 'rgba(147, 147, 147, .8)'
    }

    Shape.prototype = {
        // 返回 true 表示两个多边形相交, 否则没有
        collidesWith: function(shape) {
            // 计算两个多边形的所有投影轴
            var axes = this.getAxes().concat(shape.getAxes())
            return !this.separationOnAxes(axes, shape)
        },
        // 返回 true 表示分离轴存在, 即这两个多边形不相交
        separationOnAxes: function(axes, shape) {
            for(var i = 0, len = axes.length; i < len; i++) {
                axis = axes[i]
                projection1 = shape.project(axis)
                projection2 = this.project(axis)
                // 一旦发现不重叠, 则分离轴存在
                if(!projection1.overlaps(projection2)) {
                    return true
                }
            }
            return false
        },
        
        // 抽象类不实现方法, 实现交给子类 Polygon
        project: function(axis) {
            throw 'project(axis) not implemented'
        },

        getAxes: function() {
            throw 'getAxes() not implemented'
        },

        move: function(dx, dy) {
            throw 'move(dx, dy) not implemented'
        },
        
        createPath: function(context) {
            throw 'createPath(context) not implemented'
        },
        
        // 模板设计模式
        fill: function(context) {
            context.save()
            context.fillStyle = this.fillStyle
            this.createPath(context)
            context.fill()
            // 恢复画布设置
            context.restore()
        },

        stroke: function(context) {
            context.save()
            context.strokeStyle = this.strokeStyle
            this.createPath(context)
            context.stroke()
            context.restore()
        },

        // 如果指定的点位于当前路径中,则返回 true,否则返回 false
        isPointInPath: function(context, x, y) {
            this.createPath(context)
            return context.isPointInPath(x, y)
        } 
    }
    
    // 封装点
    var Point = function(x, y) {
        this.x = x
        this.y = y
    }

    // 封装(凸)多边形
    var Polygon = function() {
        this.points = []
        this.strokeStyle = 'blue'
        this.fillStyle = 'white'
    }
    
    // 在凸多边形的原型链上挂Shape, 表明 凸多边形是 Shape 类型的, 则 new Polygon 可以调用 Shape 的方法
    Polygon.prototype = new Shape()

    // 获取凸多边形的投影轴
    Polygon.prototype.getAxes = function() {
        var v1 = new Vector(),
            v2 = new Vector(),
            axes = []

        for(var i = 0, len = this.points.length - 1; i < len; i++) {
            v1.x = this.points[i].x
            v1.y = this.points[i].y

            v2.x = this.points[i + 1].x
            v2.y = this.points[i + 1].y
            // v2v1
            axes.push(v1.edge(v2).normal())
        }
        // 别漏了最后一条边
        v1.x = this.points[this.points.length - 1].x
        v1.y = this.points[this.points.length - 1].y

        v2.x = this.points[0].x
        v2.y = this.points[0].y

        axes.push(v1.edge(v2).normal())

        return axes
    }
    
    // 获取多边形到投影轴 axis 上的投影 scalars (标量的意思)
    Polygon.prototype.project = function(axis) {
        var scalars = [],
            v = new Vector()
        // 遍历多边形所有的顶点
        this.points.forEach(function(point) {
            v.x = point.x
            v.y = point.y
            // 做点积, 即做投影
            scalars.push(v.dotProduct(axis))
        })
        // 得到多边形在 axis 投影轴上的投影范围 
        return new Projection(Math.min.apply(Math, scalars), Math.max.apply(Math, scalars))
    }

    Polygon.prototype.addPoint = function(x, y) {
        this.points.push(new Point(x, y))
    }

    // 画多边形
    Polygon.prototype.createPath = function(context) {
        if(this.points.length === 0) {
            return
        }

        context.beginPath()
        context.moveTo(this.points[0].x, this.points[0].y)

        for(var i = 0, len = this.points.length; i < len; i++) {
            context.lineTo(this.points[i].x, this.points[i].y)
        }

        context.closePath()
    }
    
    // 多边形平移 (dx, dy) , 用于实现拖拽回调
    Polygon.prototype.move = function(dx, dy) {
        for(var i = 0, point, len = this.points.length; i < len; i++) {
            point = this.points[i]
            point.x += dx
            point.y += dy
        }
    }

    // 多边形是否和shape(圆形或者凸多边形)发生碰撞
    Polygon.prototype.collidesWith = function(shape) {
        var axes = shape.getAxes()
        if(axes === undefined) {
            return polygonCollidesWithCircle(this, shape)
        } else {
            axes = axes.concat(this.getAxes())
            return !this.separationOnAxes(axes, shape)
        }
    }

    // 封装圆形
    var Circle = function(x, y, radius) {
        this.x = x
        this.y = y
        this.radius = radius
        this.strokeStyle = 'rgba(255, 253, 208, .9)'
        this.fillStyle = 'rgba(147, 197, 114, .8)'
    }
    
    Circle.prototype = new Shape()

    // 圆形是否和 shape (圆形或者凸多边形) 发生碰撞
    Circle.prototype.collidesWith = function(shape) {
        var point, length, min = 10000, v1, v2,
            edge, perpendicular, normal,
            axes = shape.getAxes(), distance
        // shape 是圆形
        if(axes === undefined) {
            distance = Math.sqrt(Math.pow(shape.x - this.x, 2) + Math.pow(shape.y - this.y, 2))
            return distance < Math.abs(this.radius + shape.radius)
            // shape 是凸多边形
        } else {
            return polygonCollidesWithCircle(shape, this)
        }
    }
    
    // 圆形的投影轴取决于判断是否和它相交的凸多边形, 而不能由圆形自己决定, 所以这里取 undefined
    Circle.prototype.getAxes = function() {
        return undefined
    }
    
    // 圆形向投影轴 axis 的投影
    Circle.prototype.project = function(axis) {
        var scalars = [],
            point = new Point(this.x, this.y),
            dotProduct = new Vector(point).dotProduct(axis)

        scalars.push(dotProduct)
        scalars.push(dotProduct + this.radius)
        scalars.push(dotProduct - this.radius)

        return new Projection(Math.min.apply(Math, scalars),
                                                    Math.max.apply(Math, scalars))
    }
    
    // 圆形平移, 用于实现拖拽回调
    Circle.prototype.move = function(dx, dy) {
        this.x += dx
        this.y += dy
    }

    Circle.prototype.createPath = function(context) {
        context.beginPath()
        context.arc(this.x, this.y, this.radius, 0, Math.PI * 2, false)
    }
    
    // 获取和圆心最近的凸多边形上的一个点
    function getPolygonPointClosestToCircle(polygon, circle) {
        var min = 10000, length, testPoint, closestPoint

        for(var i = 0, len = polygon.points.length; i < len; i++) {
            testPoint = polygon.points[i]
            length = Math.sqrt(Math.pow(testPoint.x - circle.x, 2), Math.pow(testPoint.y - circle.y, 2))

            if(length < min) {
                min = length
                closestPoint = testPoint
            }
        }

        return closestPoint
    }
    
    // 凸多边形 和 圆形是否发生碰撞
    function polygonCollidesWithCircle(polygon, circle) {
        var min = 10000, v1, v2,
            edge, perpendicular,
            axes = polygon.getAxes(),
            closestPoint = getPolygonPointClosestToCircle(polygon, circle)
        v1 = new Vector(new Point(circle.x, circle.y))
        v2 = new Vector(new Point(closestPoint.x, closestPoint.y))
        axes.push(v1.subtract(v2).normalize()) // 在凸多边形的投影轴基础上再加一条圆形的投影轴
        return !polygon.separationOnAxes(axes, circle)
    }
    
    var canvas = document.getElementById('canvas'),
        context = canvas.getContext('2d'),
        shapes = [],
        polygonPoints = [
            [ new Point(250, 150), new Point(250, 250),
          new Point(350, 250) ],

        [ new Point(100, 100), new Point(100, 150),
          new Point(150, 150), new Point(150, 100) ],

        [ new Point(400, 100), new Point(380, 150),
          new Point(500, 150), new Point(520, 100) ]
        ],

      polygonStrokeStyles = [ 'blue', 'yellow', 'red'],
      polygonFillStyles   = [ 'rgba(255,255,0,0.7)',
                              'rgba(100,140,230,0.6)',
                              'rgba(255,255,255,0.8)' ],

      circle1 = new Circle(150, 75, 20),
      circle2 = new Circle(350, 45, 30),

      mousedown = { x: 0, y: 0 },
      lastdrag = { x: 0, y: 0 },
       // 被拖拽的图形
      shapeBeingDragged = undefined;
    // 根据鼠标在浏览器窗口中点击的位置计算出在画布中的坐标
    function windowToCanvas(e) {
       var x = e.x || e.clientX,
           y = e.y || e.clientY,
           bbox = canvas.getBoundingClientRect();

       return { x: x - bbox.left * (canvas.width  / bbox.width),
                y: y - bbox.top  * (canvas.height / bbox.height)
              };
    };

    function drawShapes() {
       shapes.forEach( function (shape) {
          shape.stroke(context);
          shape.fill(context);
       });
    }
    function detectCollisions() {
       var textY = 30,
           numShapes = shapes.length,
           shape,
           i;
       
       if (shapeBeingDragged) {
          for(i = 0; i < numShapes; ++i) {
             shape = shapes[i];

             if (shape !== shapeBeingDragged) {
                if (shapeBeingDragged.collidesWith(shape)) {
                   context.fillStyle = shape.fillStyle;
                   context.fillText('撞了...', 20, textY);
                   textY += 40;
                }
             }
          }
       }
    }

    canvas.onmousedown = function (e) {
       var location = windowToCanvas(e);
       // 确定画布中被拖拽的图形(shape)是哪一个
       shapes.forEach( function (shape) {
          if (shape.isPointInPath(context, location.x, location.y)) {
             shapeBeingDragged = shape;
             mousedown.x = location.x;
             mousedown.y = location.y;
             lastdrag.x = location.x;
             lastdrag.y = location.y;
          }   
       });
    }

    canvas.onmousemove = function (e) {
       var location,
           dragVector;

       if (shapeBeingDragged !== undefined) {
          location = windowToCanvas(e);
          dragVector = { x: location.x - lastdrag.x,
                         y: location.y - lastdrag.y
                       };

          shapeBeingDragged.move(dragVector.x, dragVector.y);
          
          lastdrag.x = location.x;
          lastdrag.y = location.y;

          context.clearRect(0,0,canvas.width,canvas.height);
          drawShapes();
          detectCollisions();
       }
    }

    canvas.onmouseup = function (e) {
       shapeBeingDragged = undefined;
    }
       
    for (var i=0; i < polygonPoints.length; ++i) {
       var polygon = new Polygon(),
           points = polygonPoints[i];

       polygon.strokeStyle = polygonStrokeStyles[i];
       polygon.fillStyle = polygonFillStyles[i];

       points.forEach( function (point) {
          polygon.addPoint(point.x, point.y);
       });

       shapes.push(polygon);
    }

    shapes.push(circle1)
    shapes.push(circle2)

    context.shadowColor = 'rgba(100,140,255,0.5)';
    context.shadowBlur = 4;
    context.shadowOffsetX = 2;
    context.shadowOffsetY = 2;
    context.font = '38px Arial';

    drawShapes();

    context.save();
    context.fillStyle = 'cornflowerblue';
    context.font = '24px Arial';
    context.fillText('拖拽物体', 10, 25);
    context.restore();
    </script>

</html>

运行效果如下

显然,分离轴算法适用于圆形、凸多边形之间的碰撞检测. 还是有一定的价值的. 关于 SAT 定理,还有更为优秀的 GJK 碰撞检测算法. GJK 比 SAT 更适用于推广到 3D 场景. 关于 GJK 算法,后续推文会再介绍.

关于碰撞检测的优化

假想一下,我们现在在设计一个程序,它能有效的监测路面上车辆的位置,我们的程序要去发现发生碰撞的车辆. 怎么做才比较有效率呢? 回顾我们上面的碰撞算法,是

O(n^2)

的, 所以碰撞检测并不是一件轻松的事情.

若每个图帧都需要对全部物体进行两两判断,会造成性能浪费,因为有些物体分布在不同区域,根本不会发生碰撞。例如下图

我们事先将整个游戏沙盒分成了四个象限(用细黑线标识了)

上图中小汽车A和 小汽车B 、 C根本不在一个象限,就更谈不上碰撞,所以更不值得去花费

O(n^2)

去检测A和B、A 和 C 是否发生碰撞。

所以,大部分游戏都会将碰撞检测分为两个阶段:粗略阶段和精细阶段(broad/narrow)。

粗略阶段(Broad Phase)

Broad phase 能为你提供有可能碰撞的实体列表。这可通过一些特殊的数据结构实现,它们能为你提供这些信息:实体存在哪里和哪些实体在其周围。这些数据结构可以是:四叉树(Quad Trees)、八叉树(OcTree)、R树(R-Trees)或空间哈希映射(Spatial Hashmap)等,但据笔者所知,R 树在数据库的高维索引方面应用可能更加广泛,而不是用于游戏中的碰撞检测. 关于四叉树、八叉树,后续推文会再介绍.

精细阶段(Narrow Phase)

当你有了较小的实体列表,你可以利用精细阶段的算法(如上述讲述的碰撞算法)得到一个确切的答案(是否发生碰撞)。

温馨提示

如果你喜欢本文,请分享到朋友圈,想要获得更多信息,请关注ACM算法日常

本文分享自微信公众号 - ACM算法日常(acm-clan),作者:影法師の物語

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 一个关于仰望,崇拜和梦想的故事

    从我接触程序竞赛到现在应该有十多年了,单说ACM竞赛,从第一次非正式参赛到现在也差不多有7年多的样子。有太多的故事,想说的话,却一直没能有机会写...

    ACM算法日常
  • 农夫与牛(STL-Queue、广度优先搜索)

    现有一农夫和一母牛,假设农夫和母牛都站在一条数轴上,农夫开始的位置为N,母牛的位置为K。农夫有三种行动方式,每行动一次需要一秒钟时间,假设农夫的现在的位置为X,...

    ACM算法日常
  • DP专题 3 | LCS最长公共子序列 - POJ 1458

    A subsequence of a given sequence is the given sequence with some elements (poss...

    ACM算法日常
  • JQuery碎碎念

    IT故事会
  • 50行javaScript代码实现简单版的 call , apply ,bind 【中级前端面试基础必备】

    其实 this 的指向,始终坚持一个原理:this 永远指向最后调用它的那个对象,这就是精髓。最关键所在

    Peter谭金杰
  • 设计模式 | 建造者模式

    这个设计模式主要是解决复杂对象的创建问题, 使这个抽象过程的不同实现方法可以构造出不同表现(属性)的对象。

    憧憬博客
  • 【JS 口袋书】第 8 章:以更细的角度来看 JS 中的 this

    JS 中的this关键字对于初学者来说是一个谜,对于经验丰富的开发人员来说则是一个永恒的难题。this 实际上是一个移动的目标,在代码执行过程中可能会发生变化,...

    前端小智@大迁世界
  • Uncaught Error: _registerComponent(...): Target container is not a DOM element

    Uncaught Error: _registerComponent(...): Target container is not a DOM element

    一个会写诗的程序员
  • Laravel源码分析之Route

    路由是外界访问Laravel应用程序的通路或者说路由定义了Laravel的应用程序向外界提供服务的具体方式:通过指定的URI、HTTP请求方法以及路由参数(可选...

    KevinYan
  • 聊聊原型 Prototype | 技术创作101训练营

    原型和原型链,一直是 JavaScript 中的重要概念,也是面试官必问的知识点,或许有的同学认为,自己虽然没有很深入了解过原型和原型链,但并不影响自己日常的开...

    Nian糕

扫码关注云+社区

领取腾讯云代金券