JS/HTML5游戲常用算法之碰撞檢測 包圍盒檢測算法詳解【凹多邊形的分離軸檢測算法】
本文實(shí)例講述了JS/HTML5游戲常用算法之碰撞檢測 包圍盒檢測算法。分享給大家供大家參考，具體如下：
概述
分離軸定理是一項(xiàng)用于檢測碰撞的算法。其適用范圍較廣，涵蓋檢測圓與多邊形，多邊形與多邊形的碰撞；缺點(diǎn)在于無法檢測凹多邊形的碰撞。本demo使用Js進(jìn)行算法實(shí)現(xiàn)，HTML5 canvas進(jìn)行渲染。
詳細(xì)
一、準(zhǔn)備工作，熟悉分離軸定理 算法原理
從根本上來講，分離軸定理（以及其他碰撞算法）的用途就是去檢測并判斷兩個圖形之間是否有間隙。分離軸定理中用到的方法使算法本身顯得十分獨(dú)特。
我所聽到過分離軸定理的最好類比方式是這樣的：
假想你拿一個電筒從不同的角度照射到兩個圖形上，那么會有怎樣的一系列的陰影投射到它們之后的墻壁上呢？
如果你用這個方式從每一個角度上對這兩個圖形進(jìn)行處理，并都找不到任何的間隙，那么這兩個圖形就一定接觸。如果你找到了一個間隙，那么這兩個圖形就顯而易見地沒有接觸。
從編程的角度來講，從每個可能的角度上去檢測會使處理變得十分密集。不過幸運(yùn)的是，由于多邊形的性質(zhì)，你只需要檢測其中幾個關(guān)鍵的角度。
你需要檢測的角度數(shù)量就正是這個多邊形的邊數(shù)。也就是說，你所需檢測的角度最大數(shù)量就是你要檢測碰撞的兩個多邊形邊數(shù)之和。舉個例子，兩個五邊形就需要檢測10個角度。
這是一個簡易但比較啰嗦的方法，以下是基本的步驟：
步驟一：從需要檢測的多邊形中取出一條邊，并找出它的法向量（垂直于它的向量），這個向量將會是我們的一個“投影軸”。
步驟二：循環(huán)獲取第一個多邊形的每個點(diǎn)，并將它們投影到這個軸上。（記錄這個多邊形投影到軸上的最高和最低點(diǎn)）
步驟三：對第二個多邊形做同樣的處理。
步驟四：分別得到這兩個多邊形的投影，并檢測這兩段投影是否重疊。
如果你發(fā)現(xiàn)了這兩個投影到軸上的“陰影”有間隙，那么這兩個圖形一定沒有相交。但如果沒有間隙，那么它們則可能接觸，你需要繼續(xù)檢測直到把兩個多邊形的每條邊都檢測完。如果你檢測完每條邊后，都沒有發(fā)現(xiàn)任何間隙，那么它們是相互碰撞的。
這個算法基本就是如此的。
順帶提一下，如果你記錄了哪個軸上的投影重疊值最?。ㄒ约爸丿B了多少），那么你就能用這個值來分開這兩個圖形。
那么如何處理圓呢？
在分離軸定理中，檢測圓與檢測多邊形相比，會有點(diǎn)點(diǎn)奇異，但仍然是可以實(shí)現(xiàn)的。
最值得注意的是，圓是沒有任何的邊，所以是沒有明顯的用于投影的軸。但它有一條“不是很明顯的”的投影軸。這條軸就是途經(jīng)圓心和多邊形上離圓心最近的頂點(diǎn)的直線。
在這以后就是按套路遍歷另一個多邊形的每條投影軸，并檢測是否有投影重疊。
噢，對了，萬一你想知道如何把圓投影到軸上，那你只用簡單地把圓心投影上去，然后加上和減去半徑就能得到投影長度了。
二、完整實(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>盒包圍碰撞算法-凸多邊形分離軸檢測算法</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();
}
//兩個向量的點(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ì)算投影軸與第一個坐標(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ì)算同一個軸上線段的距離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用于保存多邊形點(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軸兩個坐標(biāo)點(diǎn)
{
idx = i;
//計(jì)算兩個多邊形每條邊
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ù)組成的最后一個坐標(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ì)算兩個多邊形在法向量上的投影
var pp1 = calcProj(e,p1);//涵蓋到投影軸的最小值與最大值
var pp2 = calcProj(e,p2);
//計(jì)算兩個線段在法向量上距離，如果大于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];
//根據(jù)地圖數(shù)組碰撞將測
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 測試上述代碼運(yùn)行結(jié)果如下：
github地址：https://github.com/krapnikkk/JS-gameMathematics
參考文章：http://www.demodashi.com/demo/10423.html
更多關(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錯誤與調(diào)試技巧總結(jié)》
希望本文所述對大家JavaScript程序設(shè)計(jì)有所幫助。
相關(guān)文章
本篇文章主要是對JS數(shù)組去重與取重的示例代碼進(jìn)行了介紹，需要的朋友可以過來參考下，希望對大家有所幫助2014-01-01
JavaScript navigator.userAgent獲取瀏覽器信息案例講解
這篇文章主要介紹了JavaScript navigator.userAgent獲取瀏覽器信息案例講解,本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08
這篇文章介紹了JS中的幾種循環(huán)和跳出方式，文中通過示例代碼介紹的非常詳細(xì)。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-07-07
js判斷undefined類型，可以使用typeof方法，typeof 返回的是字符串,其中就有一個是undefined2014-07-07
這篇文章主要源碼解讀了Bootstrap下拉菜單，介紹了Bootstrap各式各樣的下拉菜單,具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2016-12-12
這篇文章主要為大家詳細(xì)介紹了原生JS九宮格抽獎，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-09-09
這篇文章主要介紹了在小程序中使用騰訊視頻插件播放教程視頻的方法，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-07-07
這篇文章主要介紹了使用javascript如何生成隨機(jī)顏色,需要的朋友可以參考下2014-05-05
最精簡的JavaScript實(shí)現(xiàn)鼠標(biāo)拖動效果的方法
這篇文章主要介紹了最精簡的JavaScript實(shí)現(xiàn)鼠標(biāo)拖動效果的方法,可實(shí)現(xiàn)javascript控制鼠標(biāo)拖動div層效果的方法,需要的朋友可以參考下2015-05-05
js使用visibilitychange處理頁面關(guān)閉事件
本文主要介紹了js使用visibilitychange處理頁面關(guān)閉事件，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-06-06