JS/HTML5游戲常用算法之碰撞檢測(cè) 包圍盒檢測(cè)算法詳解【凹多邊形的分離軸檢測(cè)算法】

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

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

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

概述

分離軸定理是一項(xiàng)用于檢測(cè)碰撞的算法。其適用范圍較廣，涵蓋檢測(cè)圓與多邊形，多邊形與多邊形的碰撞；缺點(diǎn)在于無(wú)法檢測(cè)凹多邊形的碰撞。本demo使用Js進(jìn)行算法實(shí)現(xiàn)，HTML5 canvas進(jìn)行渲染。

詳細(xì)

一、準(zhǔn)備工作，熟悉分離軸定理算法原理

從根本上來(lái)講，分離軸定理（以及其他碰撞算法）的用途就是去檢測(cè)并判斷兩個(gè)圖形之間是否有間隙。分離軸定理中用到的方法使算法本身顯得十分獨(dú)特。

我所聽(tīng)到過(guò)分離軸定理的最好類比方式是這樣的：

假想你拿一個(gè)電筒從不同的角度照射到兩個(gè)圖形上，那么會(huì)有怎樣的一系列的陰影投射到它們之后的墻壁上呢？

如果你用這個(gè)方式從每一個(gè)角度上對(duì)這兩個(gè)圖形進(jìn)行處理，并都找不到任何的間隙，那么這兩個(gè)圖形就一定接觸。如果你找到了一個(gè)間隙，那么這兩個(gè)圖形就顯而易見(jiàn)地沒(méi)有接觸。

從編程的角度來(lái)講，從每個(gè)可能的角度上去檢測(cè)會(huì)使處理變得十分密集。不過(guò)幸運(yùn)的是，由于多邊形的性質(zhì)，你只需要檢測(cè)其中幾個(gè)關(guān)鍵的角度。

你需要檢測(cè)的角度數(shù)量就正是這個(gè)多邊形的邊數(shù)。也就是說(shuō)，你所需檢測(cè)的角度最大數(shù)量就是你要檢測(cè)碰撞的兩個(gè)多邊形邊數(shù)之和。舉個(gè)例子，兩個(gè)五邊形就需要檢測(cè)10個(gè)角度。

這是一個(gè)簡(jiǎn)易但比較啰嗦的方法，以下是基本的步驟：

步驟一：從需要檢測(cè)的多邊形中取出一條邊，并找出它的法向量（垂直于它的向量），這個(gè)向量將會(huì)是我們的一個(gè)“投影軸”。

步驟二：循環(huán)獲取第一個(gè)多邊形的每個(gè)點(diǎn)，并將它們投影到這個(gè)軸上。（記錄這個(gè)多邊形投影到軸上的最高和最低點(diǎn)）

步驟三：對(duì)第二個(gè)多邊形做同樣的處理。

步驟四：分別得到這兩個(gè)多邊形的投影，并檢測(cè)這兩段投影是否重疊。

如果你發(fā)現(xiàn)了這兩個(gè)投影到軸上的“陰影”有間隙，那么這兩個(gè)圖形一定沒(méi)有相交。但如果沒(méi)有間隙，那么它們則可能接觸，你需要繼續(xù)檢測(cè)直到把兩個(gè)多邊形的每條邊都檢測(cè)完。如果你檢測(cè)完每條邊后，都沒(méi)有發(fā)現(xiàn)任何間隙，那么它們是相互碰撞的。

這個(gè)算法基本就是如此的。

順帶提一下，如果你記錄了哪個(gè)軸上的投影重疊值最?。ㄒ约爸丿B了多少），那么你就能用這個(gè)值來(lái)分開(kāi)這兩個(gè)圖形。

那么如何處理圓呢？

在分離軸定理中，檢測(cè)圓與檢測(cè)多邊形相比，會(huì)有點(diǎn)點(diǎn)奇異，但仍然是可以實(shí)現(xiàn)的。

最值得注意的是，圓是沒(méi)有任何的邊，所以是沒(méi)有明顯的用于投影的軸。但它有一條“不是很明顯的”的投影軸。這條軸就是途經(jīng)圓心和多邊形上離圓心最近的頂點(diǎn)的直線。

在這以后就是按套路遍歷另一個(gè)多邊形的每條投影軸，并檢測(cè)是否有投影重疊。

噢，對(duì)了，萬(wàn)一你想知道如何把圓投影到軸上，那你只用簡(jiǎn)單地把圓心投影上去，然后加上和減去半徑就能得到投影長(zhǎng)度了。

二、完整實(shí)例：

<!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>盒包圍碰撞算法-凸多邊形分離軸檢測(cè)算法</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);
      }
      //創(chuàng)建完成 閉合路徑
      ctx.closePath();
      ctx.lineWidth = 3;  //線寬
      ctx.lineJoin = "round";
      ctx.fillStyle = '#00f';
      ctx.fill();
      ctx.stroke();
    }
    //兩個(gè)向量的點(diǎn)積
    function dotV2(v1,v2) {
      return v1.x*v2.x+v1.y*v2.y;
    }
    //計(jì)算polyArr在軸線axis上的投影,polyArr是一系列點(diǎn)坐標(biāo)的集合,數(shù)組表示
    function calcProj(axis,polyArr) {
      var v = {"x":polyArr[0],"y":polyArr[1]};
      var d,min,max;
      min = max = dotV2(axis,v);//計(jì)算投影軸與第一個(gè)坐標(biāo)點(diǎn)的點(diǎn)積
      for(var i=2;i<polyArr.length-1;i+=2) {
        v.x=polyArr[i];
        v.y=polyArr[i+1];
        d = dotV2(axis,v);//計(jì)算v到投影軸的距離,遍歷出最小和最大區(qū)間
        min = (d<min)?d:min;
        max = (d>max)?d:max;
      }
      return [min,max];
    }
    //計(jì)算同一個(gè)軸上線段的距離s1(min1,max1),s2(min2,max2),如果距離小于0則表示兩線段有相交;
    function segDist(min1,max1,min2,max2) {
      if(min1<min2)
      {
        return min2-max1;
      }
      else
      {
        return min1-max2;
      }
    }
    //判斷兩個(gè)多邊形是否相交碰撞,p1,p2用于保存多邊形點(diǎn)的數(shù)組
    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的數(shù)據(jù)
      for(var i=0,len = len1+len2;i<len-1;i+=2)//遍歷所有坐標(biāo)點(diǎn)，i+=2代表xy軸兩個(gè)坐標(biāo)點(diǎn)
      {
        idx = i;
        //計(jì)算兩個(gè)多邊形每條邊
        if(i>len1) {//當(dāng)p1遍歷完畢后，p緩存形狀p2的數(shù)據(jù),從新遍歷
          p=p2;
          idx=(i-len1);//len2
        }
        if(i===p.length-2) {//p包含的點(diǎn)數(shù)據(jù)組成的最后一個(gè)坐標(biāo)點(diǎn)
          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;
        //計(jì)算兩個(gè)多邊形在法向量上的投影
        var pp1 = calcProj(e,p1);//涵蓋到投影軸的最小值與最大值
        var pp2 = calcProj(e,p2);
        //計(jì)算兩個(gè)線段在法向量上距離，如果大于0則可以退出，表示無(wú)相交
        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];
      //根據(jù)地圖數(shù)組碰撞將測(cè)
      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代碼運(yùn)行工具：http://tools.jb51.net/code/HtmlJsRun 測(cè)試上述代碼運(yùn)行結(jié)果如下：