快捷導(dǎo)航

JS/HTML5游戲常用算法之碰撞檢測(cè) 包圍盒檢測(cè)算法詳解【矩形情況】

更新時(shí)間：2018年12月13日 09:11:50 作者：krapnik

這篇文章主要介紹了JS/HTML5游戲常用算法之碰撞檢測(cè) 包圍盒檢測(cè)算法,結(jié)合實(shí)例形式詳細(xì)分析了游戲算法中針對(duì)碰撞檢測(cè)的包盒矩形情況下的相關(guān)算法原理與操作注意事項(xiàng),需要的朋友可以參考下

本文實(shí)例講述了JS/HTML5游戲常用算法之碰撞檢測(cè) 包圍盒檢測(cè)算法。分享給大家供大家參考，具體如下：

矩形包圍盒，顧名思義，就是使用一個(gè)矩形來(lái)包圍住圖像，矩形的大小以剛好包圍住圖像為最佳，這種包圍盒最適用的場(chǎng)景是剛好物體的形狀接近于矩形。

在具體的應(yīng)用中，描述矩形包圍盒的的常用方式有以下兩種，

一：采用最小最大頂點(diǎn)法描述AABB包圍盒

上圖中使用了最小最大頂點(diǎn)法來(lái)描述包圍盒信息，由于是在屏幕坐標(biāo)系中，y軸是向下延伸的，所以只需要保留矩形中坐標(biāo)的最小值和最大值即可，即矩形的左上角和右下角的頂點(diǎn)，其他的點(diǎn)都在這兩個(gè)點(diǎn)范圍內(nèi)。

在這種情況下要判斷兩個(gè)矩形是否碰撞只需要比較兩個(gè)矩形頂點(diǎn)的坐標(biāo)即可，假設(shè)矩形 A用(x1, y1)表示左上角，(x2, y2)表示右下角，矩形B用(x3, y3)表示左上角，(x4, y4)表示右下角，則滿足下列條件則表示沒(méi)有碰撞，反之則碰撞。

沒(méi)碰撞：x1>x4 或者x2<x3。
沒(méi)碰撞：y1>y4 或者y2<y3。

關(guān)鍵代碼如下：

    function hitTest(source, target) {
      /* 源物體和目標(biāo)物體都包含 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];
      //根據(jù)地圖數(shù)組碰撞將測(cè)
      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) {
      /* 源物體和目標(biāo)物體都包含 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代碼運(yùn)行工具：http://tools.jb51.net/code/HtmlJsRun 測(cè)試上述代碼運(yùn)行效果如下：

二：采用點(diǎn)和半徑描述AABB包圍盒

在上圖中使用了中心點(diǎn)和對(duì)應(yīng)兩個(gè)軸的半徑來(lái)描述包圍盒信息，假設(shè)有兩個(gè)矩形A和B，矩形A 的中心坐標(biāo)為A(x1, y1)，寬度和高度分別為rx1、ry1，矩形B 的中心坐標(biāo)為B(x2, y2)，寬度和高度分別為rx1、ry1，矩形B 的中心坐標(biāo)為B(x2, y2)，寬度和高度分別是rx2、ry2，則采用這種包圍盒檢測(cè)方式如下。

如果滿足兩個(gè)矩形在x方向的距離小于兩個(gè)矩形寬度和的一半，并且在y方向上的距離小于兩個(gè)矩形高度和的一半則表示兩個(gè)矩形有重疊，即表示發(fā)生碰撞，換成公式如下：

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

當(dāng)然，也可以把這種形式換算成第一種形式演算，這兩種方式很顯然第一種的效率比較高效一點(diǎn)，畢竟第二種算法需要使用

Math.abs獲取絕對(duì)值，第一種只是單純使用了坐標(biāo)比較。

以上所描述的矩形包圍盒也稱為 AABB（軸對(duì)齊）包圍盒，軸對(duì)齊包圍盒中的矩形的四條邊分別和坐標(biāo)軸平行，實(shí)際上也就是表示該矩形沒(méi)有進(jìn)行過(guò)旋轉(zhuǎn)操作，使用軸對(duì)齊包圍盒檢測(cè)算法比較簡(jiǎn)單高效，精度上也能滿足大多數(shù)條件，因此實(shí)際應(yīng)用中也比較多。

有興趣的可以搜索下OBB（定向接線）包圍盒。

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

更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《JavaScript數(shù)學(xué)運(yùn)算用法總結(jié)》、《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)組操作技巧總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯(cuò)誤與調(diào)試技巧總結(jié)》

希望本文所述對(duì)大家JavaScript程序設(shè)計(jì)有所幫助。

您可能感興趣的文章: