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
更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript数学运算用法总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript数组操作技巧总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》
希望本文所述对大家JavaScript程序设计有所帮助。
相关推荐
-
JS散列表碰撞处理、开链法、HashTable散列示例
本文实例讲述了JS散列表碰撞处理.开链法.HashTable散列.分享给大家供大家参考,具体如下: /** * 散列表碰撞处理.开链法.HashTable散列. * 将数组里的元素位置,也设置为数组,当两个数据的散列在同一个位置时, * 就可以放在这个位置的二维数组里,解决了散列函数的碰撞处理问题 */ function HashTable() { this.table = new Array(137); this.betterHash = betterHash;//散列函数 this.show
-
javascript 哈希表(hashtable)的简单实现
首先简单的介绍关于属性的一些方法: 属性的枚举: for/in循环是遍历对象属性的方法.如 复制代码 代码如下: var obj = { name : 'obj1', age : 20, height : '176cm' } var str = ''; for(var name in obj) { str += name + ':' + obj[name] + '\n'; } alert(str); 输出为:name:obj1 age:20 height:176cm 检查属性是否存在: in运算
-
js实现HashTable(哈希表)的实例分析
一.javascript哈希表简介 javascript里面是没有哈希表的,一直在java,C#中有时候用到了这一种数据结构,javascript里面若没有,感觉非常不顺手.细细看来,其实javascript的object的属性其实与哈希表非常类似. 如: var person = {}; person["name"] = "关羽"; 我们只需要在其基础上再封装一些HashTable的函数,就能够得到一个精简版的哈希表. 加入函数如下: 函数名 说明 返回值 add
-
JS/HTML5游戏常用算法之碰撞检测 地图格子算法实例详解
本文实例讲述了JS/HTML5游戏常用算法之碰撞检测 地图格子算法.分享给大家供大家参考,具体如下: 这种算法经常用于RPG(早期的<最终幻想>.<DQ>.<仙剑奇侠传>).SLG(<炎龙骑士团>.<超级机器人大战>).PUZ(<俄罗斯方块>.<宝石谜阵>)类型的游戏.这类游戏中,通常情况下整个地图都是由一些地图块元素组成,在制作的时候首先给制作出地图所需要的最基本的元素进行编号,然后把这些编号的地图块组合起来就可以根据需
-
JS+CSS3实现超炫的散列画廊特效
下面来介绍下我按照网上的视频讲解实现的照片墙效果图. 最终实现的效果包括如下: •当点击某张图片时,该图片移到中间区域并放大显示.当图片被点击时正反面切换显示. •某张图片被点击时,所有的图片的位置被随机重排 •某个控制按钮被点击时,对应的图片显示到正中间,控制按钮进行相应的样式切换.当连续点击某个控制按钮时,图片伴随着按钮的点击进行正反面切换 对整个效果进行VCD分解,如下图: 按照计算机能理解的方式来分解案例. •View视觉 : HTML + css 基本界面模板 •Controller
-
JS/HTML5游戏常用算法之碰撞检测 像素检测算法实例详解
本文实例讲述了JS/HTML5游戏常用算法之碰撞检测 像素检测算法.分享给大家供大家参考,具体如下: 使用像素碰撞检测法算是最精确的算法了,当然,带来的代价也是比较明显的,那就是效率上的低下.除非是在极为特殊的情况下,要求使用非常精确的碰撞,否则,一般情况下在游戏中是不建议使用这种算法,特别是在运行效率不太高的HTML5游戏中. 一般来说在使用像素碰撞检测之前会使用AABB矩形包围盒先检测两个精灵是否有碰撞,如果AABB包围盒检测没有碰撞,那一定是没有碰撞到,反之,则不一定,需要进一步进行像素检
-
js中哈希表的几种用法总结
1. 复制代码 代码如下: <html><head><script type="text/javascript">// by Go_Rush(我们) from http://www.jb51.net/ var hash={ "百度" :"http://www.baidu.com/", "Google" :"http://www.go
-
JavaScript中实现键值对应的字典与哈希表结构的示例
字典(Dictionary)的javascript实现 编程思路: 使用了裸对象datastore来进行元素存储: 实现了两种得到字典长度的方法,一种为变量跟踪,一种为实时计算. 代码: function(){ "use strict"; function Dictionary(){ this._size = 0; this.datastore = Object.create(null); } Dictionary.prototype.isEmpty = function(){ ret
-
JS/HTML5游戏常用算法之碰撞检测 包围盒检测算法详解【凹多边形的分离轴检测算法】
本文实例讲述了JS/HTML5游戏常用算法之碰撞检测 包围盒检测算法.分享给大家供大家参考,具体如下: 概述 分离轴定理是一项用于检测碰撞的算法.其适用范围较广,涵盖检测圆与多边形,多边形与多边形的碰撞:缺点在于无法检测凹多边形的碰撞.本demo使用Js进行算法实现,HTML5 canvas进行渲染. 详细 一.准备工作,熟悉分离轴定理 算法原理 从根本上来讲,分离轴定理(以及其他碰撞算法)的用途就是去检测并判断两个图形之间是否有间隙.分离轴定理中用到的方法使算法本身显得十分独特. 我所听到过分
-
JS/HTML5游戏常用算法之路径搜索算法 随机迷宫算法详解【普里姆算法】
本文实例讲述了JS/HTML5游戏常用算法之路径搜索算法 随机迷宫算法.分享给大家供大家参考,具体如下: 路径搜索算法在游戏中非常常见,特别是在 RPG.SLG 中经常用到.在这些游戏中,通过鼠标指定行走目的地,人物或者NPC就会自动行走到目标地点,这就是通过路径搜索或者称为寻路算法来实现的.通俗地说,就是在一张地图中,如何让主角自动行走到指定的地点,如图6-21所示,假设主角在A处,然后玩家在地图中点击B处,要求主角能够从A点自动找寻一条到 B 点的路径,然后自动移动到 B处,要求就这么简单.
-
JS/HTML5游戏常用算法之追踪算法实例详解
本文实例讲述了JS/HTML5游戏常用算法之追踪算法.分享给大家供大家参考,具体如下: 追踪算法在动作游戏中非常常见,从很早的游戏<吃豆人>到大型的街机机战类游戏,到处可见追踪效果的身影.一个好的追踪算法将会大大提高游戏的可玩性和玩家的兴趣. [简单算法] 先来看一个简单的跟踪算法,如下图所示,假设在canvas坐标系中存在物体A和B,物体A将把B作为追踪目标,物体在二维空间中的运动可以分解为坐标系中X.Y轴的运动,其在X和Y方向的速度决定了物体运行的方向和速率.别忘了,速度是有方向和大小的,
-
JS/HTML5游戏常用算法之路径搜索算法 A*寻路算法完整实例
本文实例讲述了JS/HTML5游戏常用算法之路径搜索算法 A*寻路算法.分享给大家供大家参考,具体如下: 原理可参考:https://www.jb51.net/article/152744.htm 完整实例代码如下: <!DOCTYPE html> <html lang="en"> <head> <meta name="viewport" content="width=device-width, initial-s
-
国庆节到了,利用JS实现一个生成国庆风头像的小工具 详解实现过程
目录 1. 页面布局 2. 图片上传和展示 3. 初始化画布 4. 切换模板 5. 输出图片 这里用到的技术: HTML+ CSS+ JavaScript: download.js库: fabric.js库: 先上体验链接:g.cuggz.com/. 注:可以点击上方的连接进行使用,不过我的域名被TX屏蔽了,还在申诉中,所以无法在QQ.微信中打开,需要复制链接到浏览器进行查看.使用. 下面是这个小工具的截图: 1. 页面布局 这部分不多说,直接上代码: <div class="wrap
-
js基础之DOM中元素对象的属性方法详解
在 HTML DOM (文档对象模型)中,每个部分都是节点. 节点是DOM结构中最基本的组成单元,每一个HTML标签都是DOM结构的节点. 文档是一个 文档节点 . 所有的HTML元素都是 元素节点 所有 HTML 属性都是 属性节点 文本插入到 HTML 元素是 文本节点 注释是 注释节点. 最基本的节点类型是Node类型,其他所有类型都继承自Node,DOM操作往往是js中开销最大的部分,因而NodeList导致的问题最多.要注意:NodeList是'动态的',
-
TF-IDF算法解析与Python实现方法详解
TF-IDF(term frequency–inverse document frequency)是一种用于信息检索(information retrieval)与文本挖掘(text mining)的常用加权技术.比较容易理解的一个应用场景是当我们手头有一些文章时,我们希望计算机能够自动地进行关键词提取.而TF-IDF就是可以帮我们完成这项任务的一种统计方法.它能够用于评估一个词语对于一个文集或一个语料库中的其中一份文档的重要程度. 在一份给定的文件里,词频 (term frequency, T
-
JS写XSS cookie stealer来窃取密码的步骤详解
JavaScript是web中最常用的脚本开发语言,js可以自动执行站点组件,管理站点内容,在web业内实现其他有用的函数.JS可以有很多的函数可以用做恶意用途,包括窃取含有密码等内容的用户cookie. Cookie是站点请求和保持特定访问页面的信息.Cookie含有访问的方式.时间.用户名密码等认证信息等.当用户访问给定站点时,必须使用cookie:如果攻击者可以拦截cookie,就可以利用cookie窃取用户的一些信息.对某个特定的域名,使用JS可以保存或修改用户的cookie.也就是说,