JS/HTML5游戏常用算法之碰撞检测包围盒检测算法详解凹多边? 爱问知识人
本文实例讲述了JS/HTML5游戏常用算法之碰撞检测 包围盒检测算法。分享给大家供大家参考，具体如下：概述分离轴定理是一项用于检测碰撞的算法。其适用范围较广，涵盖检测圆与多边形，多边形与多边形的碰撞；缺点在于无法检测凹多边形的碰撞。本demo使用Js进行算法实现，HTML5 canvas进行渲染。
详细一、准备工作，熟悉分离轴定理 算法原理从根本上来讲，分离轴定理（以及其他碰撞算法）的用途就是去检测并判断两个图形之间是否有间隙。分离轴定理中用到的方法使算法本身显得十分独特。我所听到过分离轴定理的最好类比方式是这样的：假想你拿一个电筒从不同的角度照射到两个图形上，那么会有怎样的一系列的阴影投射到它们之后的墙壁上呢？如果你用这个方式从每一个角度上对这两个图形进行处理，并都找不到任何的间隙，那么这两个图形就一定接触。
如果你找到了一个间隙，那么这两个图形就显而易见地没有接触。从编程的角度来讲，从每个可能的角度上去检测会使处理变得十分密集。不过幸运的是，由于多边形的性质，你只需要检测其中几个关键的角度。你需要检测的角度数量就正是这个多边形的边数。也就是说，你所需检测的角度最大数量就是你要检测碰撞的两个多边形边数之和。
举个例子，两个五边形就需要检测10个角度。这是一个简易但比较啰嗦的方法，以下是基本的步骤：步骤一：从需要检测的多边形中取出一条边，并找出它的法向量（垂直于它的向量），这个向量将会是我们的一个“投影轴”。步骤二：循环获取第一个多边形的每个点，并将它们投影到这个轴上。
（记录这个多边形投影到轴上的最高和最低点）步骤三：对第二个多边形做同样的处理。步骤四：分别得到这两个多边形的投影，并检测这两段投影是否重叠。如果你发现了这两个投影到轴上的“阴影”有间隙，那么这两个图形一定没有相交。但如果没有间隙，那么它们则可能接触，你需要继续检测直到把两个多边形的每条边都检测完。
如果你检测完每条边后，都没有发现任何间隙，那么它们是相互碰撞的。这个算法基本就是如此的。顺带提一下，如果你记录了哪个轴上的投影重叠值最小（以及重叠了多少），那么你就能用这个值来分开这两个图形。那么如何处理圆呢？在分离轴定理中，检测圆与检测多边形相比，会有点点奇异，但仍然是可以实现的。
最值得注意的是，圆是没有任何的边，所以是没有明显的用于投影的轴。但它有一条“不是很明显的”的投影轴。这条轴就是途经圆心和多边形上离圆心最近的顶点的直线。在这以后就是按套路遍历另一个多边形的每条投影轴，并检测是否有投影重叠。噢，对了，万一你想知道如何把圆投影到轴上，那你只用简单地把圆心投影上去，然后加上和减去半径就能得到投影长度了。
二、完整实例：<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); } //创建完成 闭合路径 ctx。closePath(); ctx。lineWidth = 3; //线宽 ctx。
lineJoin = "round"; ctx。fillStyle = '#00f'; ctx。fill(); ctx。stroke(); } //两个向量的点积 function dotV2(v1,v2) { return v1。x*v2。
x+v1。y*v2。y; } //计算polyArr在轴线axis上的投影,polyArr是一系列点坐标的集合,数组表示 function calcProj(axis,polyArr) { var v = {"x":polyArr[0],"y":polyArr[1]}; var d,min,max; min = max = dotV2(axis,v);//计算投影轴与第一个坐标点的点积 for(var i=2;i<polyArr。
length-1;i+=2) { v。x=polyArr[i]; v。y=polyArr[i+1]; d = dotV2(axis,v);//计算v到投影轴的距离,遍历出最小和最大区间 min = (d<min)?d:min; max = (d>max)?d:max; } return [min,max]; } //计算同一个轴上线段的距离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用于保存多边形点的数组 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的数据 for(var i=0,len = len1+len2;i<len-1;i+=2)//遍历所有坐标点，i+=2代表xy轴两个坐标点 { idx = i; //计算两个多边形每条边 if(i>len1) {//当p1遍历完毕后，p缓存形状p2的数据,从新遍历 p=p2; idx=(i-len1);//len2 } if(i===p。
length-2) {//p包含的点数据组成的最后一个坐标点 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; //计算两个多边形在法向量上的投影 var pp1 = calcProj(e,p1);//涵盖到投影轴的最小值与最大值 var pp2 = calcProj(e,p2); //计算两个线段在法向量上距离，如果大于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]; //根据地图数组碰撞将测 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代码运行工具：http://tools。
jb51。net/code/HtmlJsRun 测试上述代码运行结果如下：github地址：https://github。com/krapnikkk/JS-gameMathematics参考文章：http://www。demodashi。com/demo/10423。
html。
相关推荐
-
93年虚岁多大2022年 爱问知识人
虚岁,农历,年龄,一岁,计算，93年虚岁指的是农历年份，而2022年是公历年份，两者之间需要进行换算。一般来说，虚岁的计算方法是以农历正月初一为起点，每逢一个农历年，虚岁就会增加一岁。因此，我们需要将2022年转换为农历年份，然后再加上93岁，才能得出93年虚岁在2022年的年龄。2022年是公历的阳历年份，对应的农历年份是辛丑年。根据虚岁的计算方法，我们可以得出：在2022年，已经过了一个农历年，也就是93年虚岁的人已经增加了一岁。因此，...
-
什么是电子狗? 爱问知识人
检测,工具,知识,电磁波,爱问，检测电磁波的工具，通常在考场中用来检测手机信号...
-
反常积分瑕点怎么判断 爱问知识人
函数,瑕点,邻域,计算,前提，反常积分中瑕点意义是如果函数f(x)在点a的一个邻域内无界，那么点a称为函数f(x)的瑕点（也称无界间断点）。瑕点积分是存在的(即收敛的)。而这个积分是不收敛的瑕积分，所以不存在(不收敛)。计算积分值的前提是积分存在。瑕积分这个概念本身就是为了处理函数在某点无定义的情形，不能仅从函数无定义断言瑕积分发散。比如f(x)=1/根号x，它在0点也没有定义，但它在-1~0和0~1的瑕积分都是收敛的。反常积分又叫广义积分...
-
银行利率怎么算？
银行利率怎么算？，银行利率,银行,利率，利息率= 利息量÷ 本金÷时间*100%。银行利率表示一定时期内利息量与本金的比率，通常用百分比表示，按年计算则称为年利率。其计算公式是：利息率= 利息量÷本金÷时间×100%。加上x100%是为了将数字切换成百分率，与乘一的意思相同，计算中可不加，只需记住即可。一般来说，利率根据计量的期限标准不同...
-
电视机32寸是有多大？ 爱问知识人
计算,产品,知识,性价比,屏幕尺寸，电视机32寸是有多大？32寸的液晶电视的屏幕尺寸（以4:3为比例计算）是长65.024cm，宽48.768cm ，（16:9）长69cm，宽39cm；针对于这样尺寸的电视机，宽大的面积放在家里也会显得非常的大气。不同的观看距离决定了不同尺寸，我们不应该盲目追求过大的尺寸，不过，有一点是必然的，那就是在同等尺寸下，应该选择一款性价比更高的产品。...
-
计划工期是什么意？计划工期是什么意思 爱
计划,计算,知识,工期,生词，计划工期是什么意思计划工期 [ jì huà gōng qī ] 生词本基本释义[ jì huà gōng qī ]根据计算工期，结合现场实际确定的完成本工程的时间。...
-
温度巡检仪-温度巡检仪具有什么功能？ 爱问
温度,采样,检测,测量,容量，温度巡检仪 具有什么功能？温度巡检仪 将利用导体和半导体的电阻随温度变化检测的温度信号组成采样输入放大器，经放大、转换、数据线性处理原理设计的多点温度检测仪器。具有测量、显示、报警、记录、通讯等功能。检测的容量最多可达96点，精度±0.5%。常用热电阻有:铀电阻和铜电阻，测量范围：钻电阻：-200-650℃，铜电阻-50-150℃，检测采样速度为10点/s。...
-
景深及超焦距计算器SetMyCamerav1.5.11手
计算器,设置,照片,用户,支持，SetMyCamera app是一款比较很受欢迎专门用于摄影的景深及超焦距计算器软件，支持中文版本使用，用户可以直接使用该软件自定义调节相机的景深和焦距，让拍摄效果更加，更加专业，还有光圈设置，滚轮设置，距离换算等，需要的可以下载SetMyCamera app使用！软件简介如果您是一个摄影爱好者，渴望更高品质的专业照片，SetMyCamera可以帮助您！SetMyCamera包括相机景深（DOF）配置辅助工具...
-
时尚天气预报下载安装时尚天气软件下载
感谢平台给了一个分享的舞台时尚天气预报下载安装！前言：在国内LED光源 DLP显示技术投影慢慢崭露头角的时候，笔者也成为了其中的一位追随者，从小的时候就特别喜欢看电影，一直到现在依然对大屏幕有着久久不能忘怀的情结，甚至是达到痴迷境界，追求大屏，感受大片，在刺激眼睛的同时，震撼着内心世界，大无止境，心随心动，便是影迷一直追寻的目标。在投影固有的世界里，高价，灯...
-
什么是电子信息科学与技术电子信息科学与
知识,训练,能力,基本知识,业务，电子信息科学与技术是学什么的？信息与计算科学是学什么的？信息管理与信息系统是学什么的？电子信息工程是学什么的？电气工程及自动化管理是学什么的？业务培养目标：本专业培养具备电子信息科学与技术的基本理论和基本知识，受到严格的科学实验训练和科学研究初步训练，能在电子信息科学与技术、计算机科学与技术及相关领域和行政部门从事科学研究、教学、科技开发、产品设计、生产技术管理工作的电子信息科学与技术高级专门人才。...
-
问-在韩国的面积"1坪"合多少平
单位,中国,计算,很生,知识，问-在韩国的面积"1坪"合多少平方米?韩国在很多方面还保留着传统的方式，在中国已经很少见了。比如说建筑面积，韩国人在计算建筑面积时使用最多的是“坪”，这个对于中国人来讲是很生疏的，那个这个“坪”的概念又是怎样的呢？简单的说1坪等于6尺乘以6尺，1尺为30.3厘米，所以1坪的面积为(0,303 x 6) x (0.303) = 3.305124平方米。反过来1平方米为0.3025坪。 不过韩国已经立法，将来所有的...
-
扇形计算公式-数学公式请教！扇形面积的计
扇形,知识,上传,请教,数学公式，扇形面积的计算公式是什么，它所对应的弧长如何求？谢谢！！！我上传的文件上有详细说明，你仔细看看就知道了...
-
千分表的主要用途
千分表,测量,检测,部门,计量，用 途: 千分表是一种高度综合的新一代数字化高精密通用测量仪器，在精密机械、零件等生产加工的工艺、质量控制和计量检测单位或部门的检测当中，可直接对长度和位移等几何量进行精密测量，也可配以适当转换器间接测量压力、硬度、重量、液位、应力、应变等。你啊要多买些有关的书看，多点去接触千分表的仪器．...
-
如何计算汽车油耗?
计算,个月,是多少,数据,感觉，诚心提问,这里说的不是百公里油耗,现在知道几个条件,但就是不知道怎么才能计算出按这个跑法,我一个月的汽油钱是多少.09款福克斯两厢,每天跑20~22公里,油箱55L,百公里油耗基本维持在11~12之间,但是我知道这个数据是平均值,由于从未清零,感觉没啥参考价值;还有,由于油表只是平均分成8个格子,没有数字标注,无法直观看到每天的油耗.基本就是这个情况,谁能帮我想个办法,可以计算出按我这个跑法,一个月下来要多少...