JS/HTML5游戏常用算法之碰撞检测 包围盒检测算法详解【凹多边形的分离轴检测算法】
作者：krapnik 发布时间：2024-11-17 06:00:41
标签：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>
代码运行结果如下：
github地址：https://github.com/krapnikkk/JS-gameMathematics
参考文章：http://www.demodashi.com/demo/10423.html
希望本文所述对大家JavaScript程序设计有所帮助。
来源：https://blog.csdn.net/krapnik/article/details/80642439
0
投稿猜你喜欢
该章节将学习关于文件查找的操作，大家都知道，无论是 Linux 系统还是 Windows 系统都有基于文件名实现过滤、查找的功能。但是如果想- 最近接触到一个心理学方面的理论：心流理论。大意是一种个人精力完全投注在某件事情上的感觉。心流产生时会有高度的兴奋和充实感。其实也就是说人在进
- 现在使用CSS网页布局，摒弃了传统Table表格布局的模式，但是Table表格在网页中还是少不了的，因为当需要输出表格类数据时，就应该使用表
- 一、常用函数：APP_NAME: 返回当前会话的应用程序名称（如果应用程序进行了设置）。SELECT APP_NAME()COALESCE:
- 通过学习装饰器可以让我们更好更灵活的使用函数，通过学会使用装饰器还可以让我们的代码更加优雅。在我们的实际工作中，很多场景都会用到装饰器，比如
- arguments定义所有的函数都有一个自己的arguments对象，用来储存它实际接受到的参数，而不局限于函数声明时所定义的参数列表。它不
- Ruby Marshal序列化Marshal是Ruby的核心库，可以将一些对象以二进制的方式序列化保存到文件中，需要时再从文件中加载重新构建
- 一、概述公司需要通过网页用户认证登录实现上网，网络设备判断当前帐号12小时没有没上网将会自动断开帐号上网，每天早上上班第一件事就是打开用户认
- <script language="javascript"> function disableRightCl
- 1.定义在某些情况下，一个类的对象是有限且固定的，比如季节类，它只有 4 个对象；再比如行星类，目前只有 8 个对象。这种实例有限且固定的类
- 这两天在用python的bottle框架开发后台管理系统，接口约定使用RESTful风格请求，前端使用jquery ajax与接口进行交互，
- 在判断列表是否为空时，你更喜欢哪种方式？决定因素是什么？在 Python 中有很多检查列表是否是空的方式，在讨论解决方案前，先说一下不同方法
- 今天，数据库的操作越来越成为整个应用的性能瓶颈了，这点对于Web应用尤其明显。关于数据库的性能，这并不只是DBA才需要担心的事，而这更是我们
- 前言hello，大家好，学习一段时间了，学习了框架和后台的内容，为了防止前端的js和jq的熟练度不够，忘记很多算法和基础用法，会陆陆续续更新
- 准备工作VUE开发工具：Visual studio Code倾斜摄影转换工具：CesiumLab—下载地址：http:/
- Pandas库十分强大，但是对于切片操作iloc, loc和ix，很多人对此十分迷惑，因此本篇博客利用例子来说明这3者之一的区别和联系，尤其
- 共4个页面：form.asp; chk.asp; num.asp; count.asp，得到一个随即数字。加密解密后成成XBM图片，利用 s
- 以下备忘升级至 Vue CLI 3.x 版本后，将项目目录改为新结构时所需做的一些改动。1. 卸载与安装npm uninstall vue-
- 如何加点盐(salt)？为了加强MD5的安全性，从而加入了新的算法部分即加盐值，加盐值是随机生成的一组字符串，可以包括随机的大小写字母、数字
- 一、概述MySQL的慢查询日志是MySQL提供的一种日志记录，它用来记录在MySQL中响应时间超过阀值(long_query_time，单位
