您好,登錄后才能下訂單哦!
小編給大家分享一下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ò)分離軸定理的最好類(lèi)比方式是這樣的:
假想你拿一個(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> <h2>是否碰撞:<span class="hitTest">否</span></h2> <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é)果如下:
以上是“JS/HTML5常用算法之碰撞檢測(cè)和包圍盒檢測(cè)算法的示例分析”這篇文章的所有內(nèi)容,感謝各位的閱讀!相信大家都有了一定的了解,希望分享的內(nèi)容對(duì)大家有所幫助,如果還想學(xué)習(xí)更多知識(shí),歡迎關(guān)注億速云行業(yè)資訊頻道!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。