JS/HTML5游戏常用算法之碰撞检测包围盒检测算法详解【矩形情况】

2019-11-19 12:20:54

字体：大中小

来源：转载

供稿：网友

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

矩形包围盒，顾名思义，就是使用一个矩形来包围住图像，矩形的大小以刚好包围住图像为最佳，这种包围盒最适用的场景是刚好物体的形状接近于矩形。

在具体的应用中，描述矩形包围盒的的常用方式有以下两种，

一：采用最小最大顶点法描述AABB包围盒

上图中使用了最小最大顶点法来描述包围盒信息，由于是在屏幕坐标系中，y轴是向下延伸的，所以只需要保留矩形中坐标的最小值和最大值即可，即矩形的左上角和右下角的顶点，其他的点都在这两个点范围内。

在这种情况下要判断两个矩形是否碰撞只需要比较两个矩形顶点的坐标即可，假设矩形 A用(x1, y1)表示左上角，(x2, y2)表示右下角，矩形B用(x3, y3)表示左上角，(x4, y4)表示右下角，则满足下列条件则表示没有碰撞，反之则碰撞。

没碰撞：x1>x4 或者x2<x3。
没碰撞：y1>y4 或者y2<y3。

关键代码如下：

    function hitTest(source, target) {      /* 源物体和目标物体都包含 x, y 以及 width, height */      return !(        ( ( source.y + source.r ) < ( target.y ) ) ||        ( source.y > ( target.y + target.r ) ) ||        ( ( source.x + source.r ) < target.x ) ||        ( source.x > ( target.x + target.r ) )      );    }

DEMO代码：

<!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;    //栅格线条    function drawGrid(context, color, stepx, stepy) {      context.strokeStyle = color;      context.lineWidth = 0.5;      for (var i = stepx + 0.5; i < context.canvas.width; i += stepx) {        context.beginPath();        context.moveTo(i, 0);        context.lineTo(i, context.canvas.height);        context.stroke();      }      for (var i = stepy + 0.5; i < context.canvas.height; i += stepy) {        context.beginPath();        context.moveTo(0, i);        context.lineTo(context.canvas.width, i);        context.stroke();      }    }    var rect = {      x: stage.width / 2 - 20,      y: stage.height / 2 - 20,      r: 40,      c: "red"    }, rects = [];;    rects.push(rect);    for (var i = 0; i < 10; i++) {      var trace = {        x: 40 * i,        y: 40 * i,        r: 40,        c: "blue"      };      rects.push(trace);    }    function createRect(x, y, r, c) {      ctx.beginPath();      ctx.fillStyle = c;      ctx.rect(x, y, r, r);      ctx.fill();    }    document.onkeydown = function (event) {      var e = event || window.event || arguments.callee.caller.arguments[0];      //根据地图数组碰撞将测      switch (e.keyCode) {        case 37:          console.log("Left");          if (rects[0].x > 0) {            rects[0].x -= 2;          }          break;        case 38:          console.log("Top");          if (rects[0].y > 0) {            rects[0].y -= 2;          }          break;        case 39:          console.log("Right");          if (rects[0].x < stage.width) {            rects[0].x += 2;          }          break;        case 40:          console.log("Bottom");          if (rects[0].y < stage.height) {            rects[0].y += 2;          }          break;        default:          return false;      }    };    stage.addEventListener('click', function (event) {      var x = event.clientX - stage.getBoundingClientRect().left;      var y = event.clientY - stage.getBoundingClientRect().top;      rects[0].x = x - rects[0].r/2;      rects[0].y = y - rects[0].r/2;    });    function hitTest(source, target) {      /* 源物体和目标物体都包含 x, y 以及 width, height */      return !(        ( ( source.y + source.r ) < ( target.y ) ) ||        ( source.y > ( target.y + target.r ) ) ||        ( ( source.x + source.r ) < target.x ) ||        ( source.x > ( target.x + target.r ) )      );    }    function update() {      ctx.globalAlpha = 1;      ctx.clearRect(0, 0, 400, 400);      drawGrid(ctx, 'lightgray', 40, 40);      document.querySelector('.hitTest').innerHTML = "否";      for (var i = 1, len = rects.length; i < len; i++) {        createRect(rects[i].x, rects[i].y, rects[i].r, rects[i].c);        var flag = hitTest(rects[0], rects[i]);        if (flag) {          document.querySelector('.hitTest').innerHTML = "是";          ctx.globalAlpha = 0.5;        }      }      createRect(rects[0].x, rects[0].y, rects[0].r, rects[0].c);      requestAnimationFrame(update);    }    update();  };</script></html>

这里使用在线HTML/CSS/JavaScript代码运行工具：http://tools.VeVB.COm/code/HtmlJsRun 测试上述代码运行效果如下：

二：采用点和半径描述AABB包围盒

在上图中使用了中心点和对应两个轴的半径来描述包围盒信息，假设有两个矩形A和B，矩形A 的中心坐标为A(x1, y1)，宽度和高度分别为rx1、ry1，矩形B 的中心坐标为B(x2, y2)，宽度和高度分别为rx1、ry1，矩形B 的中心坐标为B(x2, y2)，宽度和高度分别是rx2、ry2，则采用这种包围盒检测方式如下。

如果满足两个矩形在x方向的距离小于两个矩形宽度和的一半，并且在y方向上的距离小于两个矩形高度和的一半则表示两个矩形有重叠，即表示发生碰撞，换成公式如下：

X方向满足：|x2-x1|<=rx1+rx2并且Y方向满足：|y2-y1|<=ry1+ry2

当然，也可以把这种形式换算成第一种形式演算，这两种方式很显然第一种的效率比较高效一点，毕竟第二种算法需要使用

Math.abs获取绝对值，第一种只是单纯使用了坐标比较。

以上所描述的矩形包围盒也称为 AABB（轴对齐）包围盒，轴对齐包围盒中的矩形的四条边分别和坐标轴平行，实际上也就是表示该矩形没有进行过旋转操作，使用轴对齐包围盒检测算法比较简单高效，精度上也能满足大多数条件，因此实际应用中也比较多。

有兴趣的可以搜索下OBB（定向接线）包围盒。

github地址：https://github.com/krapnikkk/JS-gameMathematics

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

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

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

下一篇：详解Express笔记之动态渲染HTML(新手入坑)