JS/HTML5游戏常用算法之碰撞检测包围盒检测算法详解【凹多边形的分离轴检测算法】

程序员文章站 2022-03-13 17:10:29

本文实例讲述了js/html5游戏常用算法之碰撞检测包围盒检测算法。分享给大家供大家参考，具体如下：概述分离轴定理是一项用于检测碰撞的算法。其适用范围较广，涵盖检...

本文实例讲述了js/html5游戏常用算法之碰撞检测包围盒检测算法。分享给大家供大家参考，具体如下：

概述

分离轴定理是一项用于检测碰撞的算法。其适用范围较广，涵盖检测圆与多边形，多边形与多边形的碰撞；缺点在于无法检测凹多边形的碰撞。本demo使用js进行算法实现，html5 canvas进行渲染。

详细

一、准备工作，熟悉分离轴定理算法原理

从根本上来讲，分离轴定理（以及其他碰撞算法）的用途就是去检测并判断两个图形之间是否有间隙。分离轴定理中用到的方法使算法本身显得十分独特。

我所听到过分离轴定理的最好类比方式是这样的：

假想你拿一个电筒从不同的角度照射到两个图形上，那么会有怎样的一系列的阴影投射到它们之后的墙壁上呢？

JS/HTML5游戏常用算法之碰撞检测包围盒检测算法详解【凹多边形的分离轴检测算法】

如果你用这个方式从每一个角度上对这两个图形进行处理，并都找不到任何的间隙，那么这两个图形就一定接触。如果你找到了一个间隙，那么这两个图形就显而易见地没有接触。

从编程的角度来讲，从每个可能的角度上去检测会使处理变得十分密集。不过幸运的是，由于多边形的性质，你只需要检测其中几个关键的角度。

你需要检测的角度数量就正是这个多边形的边数。也就是说，你所需检测的角度最大数量就是你要检测碰撞的两个多边形边数之和。举个例子，两个五边形就需要检测10个角度。

JS/HTML5游戏常用算法之碰撞检测包围盒检测算法详解【凹多边形的分离轴检测算法】

这是一个简易但比较啰嗦的方法，以下是基本的步骤：

步骤一：从需要检测的多边形中取出一条边，并找出它的法向量（垂直于它的向量），这个向量将会是我们的一个“投影轴”。

JS/HTML5游戏常用算法之碰撞检测包围盒检测算法详解【凹多边形的分离轴检测算法】

步骤二：循环获取第一个多边形的每个点，并将它们投影到这个轴上。（记录这个多边形投影到轴上的最高和最低点）

JS/HTML5游戏常用算法之碰撞检测包围盒检测算法详解【凹多边形的分离轴检测算法】

步骤三：对第二个多边形做同样的处理。

JS/HTML5游戏常用算法之碰撞检测包围盒检测算法详解【凹多边形的分离轴检测算法】

步骤四：分别得到这两个多边形的投影，并检测这两段投影是否重叠。

JS/HTML5游戏常用算法之碰撞检测包围盒检测算法详解【凹多边形的分离轴检测算法】

如果你发现了这两个投影到轴上的“阴影”有间隙，那么这两个图形一定没有相交。但如果没有间隙，那么它们则可能接触，你需要继续检测直到把两个多边形的每条边都检测完。如果你检测完每条边后，都没有发现任何间隙，那么它们是相互碰撞的。

这个算法基本就是如此的。

顺带提一下，如果你记录了哪个轴上的投影重叠值最小（以及重叠了多少），那么你就能用这个值来分开这两个图形。

那么如何处理圆呢？

在分离轴定理中，检测圆与检测多边形相比，会有点点奇异，但仍然是可以实现的。

最值得注意的是，圆是没有任何的边，所以是没有明显的用于投影的轴。但它有一条“不是很明显的”的投影轴。这条轴就是途经圆心和多边形上离圆心最近的顶点的直线。

JS/HTML5游戏常用算法之碰撞检测包围盒检测算法详解【凹多边形的分离轴检测算法】

在这以后就是按套路遍历另一个多边形的每条投影轴，并检测是否有投影重叠。

噢，对了，万一你想知道如何把圆投影到轴上，那你只用简单地把圆心投影上去，然后加上和减去半径就能得到投影长度了。

二、完整实例：

<!doctype html>
<html lang="en">
<head>
  <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0">
  <meta charset="utf-8">
  <title>盒包围碰撞算法-凸多边形分离轴检测算法</title>
  <style>
    #stage {
      border: 1px solid lightgray;
    }
  </style>
</head>
<body>
<h1>是否碰撞：<span class="hittest">否</span></h1>
<canvas id="stage"></canvas>
</body>
<script>
  window.onload = function () {
    var stage = document.queryselector('#stage'),
      ctx = stage.getcontext('2d');
    stage.width = 400;
    stage.height = 400;
    var starpointarr = [];
//    绘制五角星
    function drawstar(ctx,r,r,x,y,rot,c){
      ctx.beginpath();
      for(var i =0;i<5;i++){
        var startposx = math.cos((18 + i*72 - rot)/180 * math.pi )*r + x,
          startposy = - math.sin((18 + i*72 - rot)/180 * math.pi)*r + y,
          endposx = math.cos((54 + i*72 - rot)/180 * math.pi )*r + x,
          endposy = - math.sin((54 + i*72 - rot)/180 * math.pi)*r + y;
        ctx.lineto(startposx,startposy);
        ctx.lineto(endposx, endposy);
        starpointarr.push(startposx,startposy,endposx,endposy);
      }
      ctx.closepath();
      ctx.fillstyle = c;
      ctx.linewidth = 3;
      ctx.linejoin = "round";
      ctx.fill();
      ctx.stroke();
    }
    var polygonpointarr = [];
//    绘制多边形
    function drawpolygon(numsides,radius,x,y){
      ctx.beginpath();
      for(i = 1;i<=numsides; i++){
        var xpos = x+radius*math.cos(2*math.pi*i/numsides);
        var ypos = x+radius*math.sin(2*math.pi*i/numsides);
        polygonpointarr.push(xpos,ypos);
        ctx.lineto(xpos,ypos);
      }
      //创建完成 闭合路径
      ctx.closepath();
      ctx.linewidth = 3;  //线宽
      ctx.linejoin = "round";
      ctx.fillstyle = '#00f';
      ctx.fill();
      ctx.stroke();
    }
    //两个向量的点积
    function dotv2(v1,v2) {
      return v1.x*v2.x+v1.y*v2.y;
    }
    //计算polyarr在轴线axis上的投影,polyarr是一系列点坐标的集合,数组表示
    function calcproj(axis,polyarr) {
      var v = {"x":polyarr[0],"y":polyarr[1]};
      var d,min,max;
      min = max = dotv2(axis,v);//计算投影轴与第一个坐标点的点积
      for(var i=2;i<polyarr.length-1;i+=2) {
        v.x=polyarr[i];
        v.y=polyarr[i+1];
        d = dotv2(axis,v);//计算v到投影轴的距离,遍历出最小和最大区间
        min = (d<min)?d:min;
        max = (d>max)?d:max;
      }
      return [min,max];
    }
    //计算同一个轴上线段的距离s1(min1,max1),s2(min2,max2),如果距离小于0则表示两线段有相交;
    function segdist(min1,max1,min2,max2) {
      if(min1<min2)
      {
        return min2-max1;
      }
      else
      {
        return min1-max2;
      }
    }
    //判断两个多边形是否相交碰撞,p1,p2用于保存多边形点的数组
    function iscollide(p1,p2) {
      //定义法向量
      var e = {"x":0,"y":0};
      var p = p1,idx=0,len1=p1.length,len2=p2.length,px,py;//p缓存形状p1的数据
      for(var i=0,len = len1+len2;i<len-1;i+=2)//遍历所有坐标点，i+=2代表xy轴两个坐标点
      {
        idx = i;
        //计算两个多边形每条边
        if(i>len1) {//当p1遍历完毕后，p缓存形状p2的数据,从新遍历
          p=p2;
          idx=(i-len1);//len2
        }
        if(i===p.length-2) {//p包含的点数据组成的最后一个坐标点
          px=p[0]-p[idx];//首尾的x轴相连
          py=p[1]-p[idx+1];//首尾的y轴相连
        } else {
          px = p[idx+2]-p[idx];//递增的x轴相连
          py = p[idx+3]-p[idx+1];//递减的y轴相连
        }
        //得到边的法向量【垂直相交】，即投影轴
        e.x = -py;
        e.y = px;
        //计算两个多边形在法向量上的投影
        var pp1 = calcproj(e,p1);//涵盖到投影轴的最小值与最大值
        var pp2 = calcproj(e,p2);
        //计算两个线段在法向量上距离，如果大于0则可以退出，表示无相交
        if(segdist(pp1[0],pp1[1],pp2[0],pp2[1])>0) {
          return false;
        }
      }
      return true;
    }
    document.onkeydown = function (event) {
      var e = event || window.event || arguments.callee.caller.arguments[0];
      //根据地图数组碰撞将测
      switch (e.keycode) {
        case 37:
          console.log("left");
          if (starposx > 0) {
            starposx -= 2;
          }
          break;
        case 38:
          console.log("top");
          if (starposy > 0) {
            starposy -= 2;
          }
          break;
        case 39:
          console.log("right");
          if (starposx < stage.width) {
            starposx += 2;
          }
          break;
        case 40:
          console.log("bottom");
          if (starposy < stage.height) {
            starposy += 2;
          }
          break;
        default:
          return false;
      }
    };
    var starposx = stage.width/2,starposy = stage.height/2;
    stage.addeventlistener('click', function (event) {
      var x = event.clientx - stage.getboundingclientrect().left;
      var y = event.clienty - stage.getboundingclientrect().top;
      starposx = x;
      starposy = y;
    });
    function update() {
      ctx.clearrect(0, 0, 400, 400);
      starpointarr = [];
      polygonpointarr = [];
      drawpolygon(7,50,300,300);
      drawstar(ctx,30,50,starposx,starposy,30,"yellow");
      document.queryselector('.hittest').innerhtml = "否";
      var flag = iscollide(starpointarr, polygonpointarr);
      if (flag) {
        document.queryselector('.hittest').innerhtml = "是";
      }
      requestanimationframe(update);
    }
    update();
  };
</script>
</html>

这里使用在线html/css/javascript代码运行工具：http://tools.jb51.net/code/htmljsrun 测试上述代码运行结果如下：

JS/HTML5游戏常用算法之碰撞检测包围盒检测算法详解【凹多边形的分离轴检测算法】

github地址：https://github.com/krapnikkk/js-gamemathematics

参考文章：

更多关于javascript相关内容感兴趣的读者可查看本站专题：《javascript数学运算用法总结》、《javascript数据结构与算法技巧总结》、《javascript数组操作技巧总结》、《javascript排序算法总结》、《javascript遍历算法与技巧总结》、《javascript查找算法技巧总结》及《javascript错误与调试技巧总结》

希望本文所述对大家javascript程序设计有所帮助。

上一篇： Sting、StringBuffer、StringBuilder

下一篇：当面试官问线程池时，你应该知道些什么？

JS/HTML5游戏常用算法之碰撞检测包围盒检测算法详解【凹多边形的分离轴检测算法】