www.qjdy.com-奇迹赌场 > www.qjdy.com > “等一下,我碰!”——常见的2D碰撞检测

原标题:“等一下,我碰!”——常见的2D碰撞检测

浏览次数:128 时间:2019-11-29

“等一下,作者碰!”——何足为奇的2D碰撞检查实验

2017/02/22 · HTML5 · 1 评论 · 碰撞检查评定

原作出处: 坑坑洼洼实验室   

图片 1

“碰乜鬼嘢啊,碰走晒本人滴靓牌”。想到“碰”就自然联想到了“麻将”那风流倜傥巨人发明。当然除了“碰”,洗牌的时候也洋溢了各样『碰撞』。

好了,不赘述。直入主旨——碰撞检查实验。

在 2D 遭遇下,平淡无奇的碰撞检查测验方法如下:

  • 外接图形剖断法
    • 轴对称包围盒(Axis-Aligned Bounding 博克斯),即无旋转矩形。
    • 圆形碰撞
  • 光明投射法
  • 分别轴定理
  • 其他
    • 地图格子划分
    • 像素检查评定

下文将由易到难的逐个介绍上述各样碰撞检测方法:外接图形剖断法 > 别的> 光线投射法 > 分离轴定理。

其它,有一点现象只要我们约定好限定标准,也能促成大家想要的冲击,如上边包车型客车碰壁反弹:

当球境遇边框就反弹(如x/y轴方向速度取反)。

JavaScript

if(ball.left < 0 || ball.right > rect.width) ball.velocityX = -ball.velocityX if(ball.top < 0 || ball.bottom > rect.height) ball.velocityY = -ball.velocityY

1
2
if(ball.left < 0 || ball.right > rect.width) ball.velocityX = -ball.velocityX
if(ball.top < 0 || ball.bottom > rect.height) ball.velocityY = -ball.velocityY

再比方当一人走到 100px 地点时不进行跳跃,就能够碰到石头等等。

由此,有个别场景只需通过设定到适当的参数就可以。

外接图形判断法

轴对称包围盒(Axis-阿里gned Bounding Box)

概念:剖断自便七个(无旋转)矩形的放肆大器晚成边是还是不是无间距,进而剖断是不是碰撞。

算法:

JavaScript

rect1.x < rect2.x rect2.width && rect1.x rect1.width > rect2.x && rect1.y < rect2.y rect2.height && rect1.height rect1.y > rect2.y

1
2
3
4
rect1.x < rect2.x rect2.width &&
rect1.x rect1.width > rect2.x &&
rect1.y < rect2.y rect2.height &&
rect1.height rect1.y > rect2.y

两矩形间碰撞的各个气象:
图片 2

在线运转示例(先点击运维示例以拿到关节,下同):

缺点:

  • 相对局限:两实体必需是矩形,且均不容许旋转(即有关水平和垂直方向上择善而从)。
  • 对于包涵着图案(非填满整个矩形)的矩形进行碰撞检查评定,也许存在精度不足的难题。
  • 实体运动速渡过快时,恐怕会在西邻两动漫帧之间急速穿过,招致忽略了本应碰撞的事件发生。

适用案例:

  • (类)矩形物体间的碰撞。

圆形碰撞(Circle Collision)

概念:通过决断任性八个圆圈的圆心间隔是或不是低于两圆半径之和,若小于则为冲击。

两点时期的离开由以下公式可得:
图片 3

判断两圆心间距是或不是低于两半径之和:

JavaScript

Math.sqrt(Math.pow(circleA.x - circleB.x, 2) Math.pow(circleA.y - circleB.y, 2)) < circleA.radius circleB.radius

1
2
3
Math.sqrt(Math.pow(circleA.x - circleB.x, 2)
Math.pow(circleA.y - circleB.y, 2))
< circleA.radius circleB.radius

图例:
图片 4

在线运维示例:

缺点:

  • 与『轴对称包围盒』相似

适用案例:

  • (类)圆形的实体,如各个球类碰撞。

其他

地图格子划分

概念:将地图(场景)划分为叁个个格子。地图中出席检查测量检验的指标都存储着自己所在格子的坐标,那么您即能够以为八个物体在相邻格未时为冲击,又恐怕五个物体在同意气风发格才为冲击。别的,接纳此方法的前提是:地图中颇负可能参加碰撞的物体都如果格子单元的深浅照旧是其整好数倍。

蓝色X 为障碍物:
图片 5

落实情势:

JavaScript

// 通过一定标志钦定(非)可行区域 map = [ [0, 0, 1, 1, 1, 0, 0, 0, 0], [0, 1, 1, 0, 0, 1, 0, 0, 0], [0, 1, 0, 0, 0, 0, 1, 0, 0], [0, 1, 0, 0, 0, 0, 1, 0, 0], [0, 1, 1, 1, 1, 1, 1, 0, 0] ], // 设定剧中人物的初叶地方 player = {left: 2, top: 2}   // 移动前(后)剖断角色的下一步的动作(如不可能前进) ...

1
2
3
4
5
6
7
8
9
10
11
12
13
// 通过特定标识指定(非)可行区域
map = [
[0, 0, 1, 1, 1, 0, 0, 0, 0],
[0, 1, 1, 0, 0, 1, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 1, 0, 0],
[0, 1, 0, 0, 0, 0, 1, 0, 0],
[0, 1, 1, 1, 1, 1, 1, 0, 0]
],
// 设定角色的初始位置
player = {left: 2, top: 2}
 
// 移动前(后)判断角色的下一步的动作(如不能前行)
...

在线运转示例:

缺点:

  • 适用途景局限。

适用案例:

  • 推箱子、踩地雷等

像素检查实验

概念:以像素等第检测物体之间是还是不是留存重叠,进而判别是不是碰撞。

达成格局有多样,下边列举在 Canvas 中的两种完毕格局:

  1. 如下述的案例中,通过将五个物体在 offscreen canvas 中决断生龙活虎致职分(坐标)下是还是不是同期存在非透明的像素。
  2. 利用 canvas 的 globalCompositeOperation = 'destination-in' 属性。该属性会让两个的重合部分会被封存,别的区域都成为透明。由此,若存在非透明像素,则为冲击。

留心,当待检查实验碰撞物体为三个时,第风姿洒脱种办法必要多少个 offscreen canvas,而第两种只需三个。

offscreen canvas:与之相关的是 offscreen rendering。正如其名,它会在有些地点进行渲染,但不是荧屏。“某些地方”其实是内存。渲染到内部存储器比渲染到荧屏更加快。—— Offscreen Rendering

本来,我们那边实际不是使用 offscreen render 的品质优势,而是接收 offscreen canvas 保存独立物体的像素。换句话说:onscreen canvas 只是起显示效果,碰撞检查测量检验是在 offscreen canvas 中进行

别的,由于须要逐像素检查评定,若对任何 Canvas 内全体像素都进行此操作,无疑会浪费广大财富。由此,大家得以先经过运算获得两岸结交区域,然后只对该区域内的像素实行检查实验就能够。

图例:
图片 6

上边示例体现了第生机勃勃种达成格局:

缺点:

  • 因为急需检查每生龙活虎像一向剖断是不是碰撞,质量须求相比高。

适用案例:

  • 亟需以像素等级检查实验物体是不是碰撞。

光线投射法(Ray Casting)

概念:通过检测多个物体的进度矢量是或不是存在交点,且该交点满意一定规范。

对于下述抛小球入桶的案例:画一条与实体的快慢向量相交汇的线(#1卡塔尔国,然后再从另三个待检查实验物体出发,连线到前三个物体,绘制第二条线(#2卡塔尔(قطر‎,依据两条线的交点地点来判定是还是不是产生相撞。

抛球进桶图例:
图片 7

在小球飞行的经过中,需求不断简政放权两直线的交点。

当满意以下五个标准时,那么应用程序就能够剖断小球已落入桶中:

  • 两直线交点在桶口的左侧边沿间
  • 小球坐落于第二条线(#2)下方

在线运转示例:

优点:

  • 适合运动速度快的实体

缺点:

  • 适用范围相对局限。

适用案例:

  • 抛球运动进桶。

分手轴定理(Separating Axis 西奥rem)

概念:通过判定率性八个 凸多边形 在猖狂角度下的阴影是还是不是均设有重叠,来判别是或不是产生相撞。若在某意气风发角度光源下,两实体的影子存在间隙,则为不碰撞,不然为发出冲击。

图例:
图片 8

在前后相继中,遍历全数角度是不现实的。那什么显著 投影轴 呢?其实投影轴的数据与多边形的边数相等就可以。

图片 9

以较高抽象等级次序判别五个凸多边形是不是碰撞:

JavaScript

function polygonsCollide(polygon1, polygon2卡塔尔 { var axes, projection1, projection2   // 依照多边形获取具备投影轴 axes = polygon1.getAxes(卡塔尔axes.push(polygon2.getAxes(卡塔尔卡塔尔国   // 遍历全部投影轴,获取多边形在每条投影轴上的投影 for(each axis in axes卡塔尔 { projection1 = polygon1.project(axis卡塔尔(英语:State of Qatar) projection2 = polygon2.project(axis卡塔尔(قطر‎   // 剖断投影轴上的阴影是否留存重叠,若检查评定到存在间隙则立时退出剖断,肃清不供给的演算。 if(!projection1.overlaps(projection2)) return false } return true }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function polygonsCollide(polygon1, polygon2) {
var axes, projection1, projection2
 
// 根据多边形获取所有投影轴
axes = polygon1.getAxes()
axes.push(polygon2.getAxes())
 
// 遍历所有投影轴,获取多边形在每条投影轴上的投影
for(each axis in axes) {
projection1 = polygon1.project(axis)
projection2 = polygon2.project(axis)
 
// 判断投影轴上的投影是否存在重叠,若检测到存在间隙则立刻退出判断,消除不必要的运算。
if(!projection1.overlaps(projection2))
return false
}
return true
}

上述代码有多少个须要消除的地点:

  • 如何分明多边形的相继投影轴
  • 什么样将大举形投射到某条投影轴上
  • 什么检查实验两段投影是还是不是爆发重叠

投影轴

平常来讲图所示,大家利用一条从 p1 指向 p2 的向量来表示多边形的某条边,大家称为边缘向量。在分别轴定理中,还亟需规定一条垂直于边缘向量的法向量,大家称为“边缘法向量”。

投影轴平行于边缘法向量。投影轴之处不限,因为其长度是最佳的,故而多边形在该轴上的阴影是生龙活虎致的。该轴的矛头才是根本的。

图片 10

JavaScript

// 以原点(0,0卡塔尔(قطر‎为始,极点为末。最终经过向量减法获得 边缘向量。 var v1 = new Vector(p1.x, p1.y卡塔尔(قطر‎ v2 = new Vector(p2.x, p2.y卡塔尔   // 首先得到边缘向量,然后再通过边缘向量获得对应边缘法向量(单位向量)。 // 两向量相减获得边缘向量 p2p1(注:下面应该有个右箭头,以象征向量)。 // 设向量 p2p1 为(A,B卡塔尔国,那么其法向量通过 x1x2 y1y2 = 0 可得:(-B,A卡塔尔 或 (B,-A卡塔尔。 axis = v1.edge(v2卡塔尔.normal(卡塔尔(英语:State of Qatar)

1
2
3
4
5
6
7
8
// 以原点(0,0)为始,顶点为末。最后通过向量减法得到 边缘向量。
var v1 = new Vector(p1.x, p1.y)
v2 = new Vector(p2.x, p2.y)
 
// 首先得到边缘向量,然后再通过边缘向量获得相应边缘法向量(单位向量)。
// 两向量相减得到边缘向量 p2p1(注:上面应该有个右箭头,以表示向量)。
// 设向量 p2p1 为(A,B),那么其法向量通过 x1x2 y1y2 = 0 可得:(-B,A) 或 (B,-A)。
axis = v1.edge(v2).normal()

以下是向量对象的片段达成,具体可看源码。

JavaScript

var Vector = function(x, y卡塔尔(英语:State of Qatar) { this.x = x this.y = y }   Vector.prototype = { // 获取向量尺寸(即向量的模),即两点间隔离 getMagnitude: function(卡塔尔{ return Math.sqrt(Math.pow(this.x, 2卡塔尔国, Math.pow(this.y, 2卡塔尔(英语:State of Qatar)卡塔尔(英语:State of Qatar) }, // 点积的几何意义之一是:一个向量在平行于另一个向量方向上的黑影的数值乘积。 // 后续将会用其计算出投影的尺寸 dotProduct: function(vector卡塔尔(قطر‎ { return this.x * vector.x this.y vector.y }, // 向量相减 获得边 subtarct: function(vector卡塔尔 { var v = new Vector(卡塔尔(قطر‎ v.x = this.x - vector.x v.y = this.y - vector.y return v }, edge: function(vector卡塔尔 { return this.substract(vector卡塔尔国 }, // 获取当前向量的法向量(垂直) perpendicular: function(卡塔尔国 { var v = new Vector(卡塔尔(英语:State of Qatar) v.x = this.y v.y = 0 - this.x return v }, // 获取单位向量(即向量尺寸为1,用于表示向量方向),三个非零向量除以它的模就能够得到单位向量 normalize: function(卡塔尔 { var v = new Vector(0, 0卡塔尔(英语:State of Qatar) m = this.getMagnitude()if(m !== 0卡塔尔(قطر‎ { v.x = this.x / m v.y = this.y /m } return v }, // 获取边缘法向量的单位向量,即投影轴 normal: function(卡塔尔(英语:State of Qatar) { var p = this.perpendicular(卡塔尔(英语:State of Qatar) return p .normalize(卡塔尔(英语:State of Qatar) } }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
var Vector = function(x, y) {
this.x = x
this.y = y
}
 
Vector.prototype = {
// 获取向量大小(即向量的模),即两点间距离
getMagnitude: function() {
return Math.sqrt(Math.pow(this.x, 2),
Math.pow(this.y, 2))
},
// 点积的几何意义之一是:一个向量在平行于另一个向量方向上的投影的数值乘积。
// 后续将会用其计算出投影的长度
dotProduct: function(vector) {
return this.x * vector.x this.y vector.y
},
// 向量相减 得到边
subtarct: function(vector) {
var v = new Vector()
v.x = this.x - vector.x
v.y = this.y - vector.y
return v
},
edge: function(vector) {
return this.substract(vector)
},
// 获取当前向量的法向量(垂直)
perpendicular: function() {
var v = new Vector()
v.x = this.y
v.y = 0 - this.x
return v
},
// 获取单位向量(即向量大小为1,用于表示向量方向),一个非零向量除以它的模即可得到单位向量
normalize: function() {
var v = new Vector(0, 0)
m = this.getMagnitude()
if(m !== 0) {
v.x = this.x / m
v.y = this.y /m
}
return v
},
// 获取边缘法向量的单位向量,即投影轴
normal: function() {
var p = this.perpendicular()
return p .normalize()
}
}

图片 11
向量相减

更加多关于向量的知识可通过别的渠道学习。

投影

黑影的尺寸:通过将三个多方形上的各种终端与原点(0,0卡塔尔(قطر‎组成的向量,投影在某风流倜傥投影轴上,然后保留该多边形在该投影轴上具备投影中的最大值和微小值,那样就能够表示三个多头形在某投影轴上的影子了。

判别两多边形的阴影是不是重合:projection1.max > projection2.min && project2.max > projection.min

图片 12
为了轻易领悟,示例图将坐标轴原点(0,0)停放于三角形边1投影轴的适宜地方。

由上述可得投影对象:

JavaScript

// 用最大和最小值表示某生机勃勃凸多边形在某风姿洒脱投影轴上的影子地方 var Projection = function (min, max卡塔尔 { this.min this.max } projection.prototype = { // 决断两阴影是还是不是重叠 overlaps: function(projection卡塔尔 { return this.max > projection.min && projection.max > this.min } }

1
2
3
4
5
6
7
8
9
10
11
// 用最大和最小值表示某一凸多边形在某一投影轴上的投影位置
var Projection = function (min, max) {
    this.min
    this.max
}
projection.prototype = {
    // 判断两投影是否重叠
    overlaps: function(projection) {
        return this.max > projection.min && projection.max > this.min
    }
}

哪些得到向量在投影轴上的长度?
向量的点积的在这之中贰个几何意义是:二个向量在平行于另四个向量方向上的黑影的数值乘积。
由于投影轴是单位向量(长度为1),投影的长短为 x1 * x2 y1 * y2

图片 13

JavaScript

// 遵照多边形的各类确定地点,获得投影的最大和纤维值,以象征投影。 function project = function (axis卡塔尔国 { var scalars = [], v = new Vector()   this.points.forEach(function (point) { v.x = point.x v.y = point.y scalars.push(v.dotProduct(axis)) }) return new Projection(Math.min.apply(Math, scalars), Math.max,apply(Math, scalars)) }

1
2
3
4
5
6
7
8
9
10
11
12
// 根据多边形的每个定点,得到投影的最大和最小值,以表示投影。
function project = function (axis) {
var scalars = [], v = new Vector()
 
this.points.forEach(function (point) {
v.x = point.x
v.y = point.y
scalars.push(v.dotProduct(axis))
})
return new Projection(Math.min.apply(Math, scalars),
Math.max,apply(Math, scalars))
}

圆形与多边形之间的碰撞检查评定

由于圆形可相同地看成四个有许多条边的正多方形,而笔者辈不只怕根据这一个边豆蔻梢头风华正茂举办投影与测验。我们只需将圆形投射到一条投影轴上就可以,那条轴正是圆心与绝大多数形极点中近年来的少数的连线,如图所示:

图片 14

为此,该投影轴和多方形自己的投影轴就重新组合了大器晚成组待检查评定的投影轴了。

而对于圆形与圆圈之间的碰撞检查测量检验依旧是开始的一段时期的两圆心间距是不是低于两半径之和。

告别轴定理的完整代码达成,可查看以下案例:

优点:

  • 精确

缺点:

  • 不适用于凹多边形

适用案例:

  • 私行凸多边形和圆形。

越来越多关于抽离轴定理的素材:

  • Separating Axis Theorem (SAT) explanation
  • Collision detection and response
  • Collision detection Using the Separating Axis Theorem
  • SAT (Separating Axis Theorem)
  • Separation of Axis Theorem (SAT) for Collision Detection

拉开:最小平移向量(MIT)

平日来讲,假若碰撞之后,相撞的两侧依然存在,那么就须要将两端分别。分开之后,能够使原先相撞的两实体相互弹开,也能够让她们黏在一起,还能依照具体供给来落实任何行为。但是首先要做的是,依旧将两者分别,那就须求用到最小平移向量(Minimum Translation Vector, MIT)。

图片 15

冲击质量优化

若各种周期都亟需对全部实体举办两两推断,会产生浪费(因为稍微物体布满在区别区域,根本不会发生相撞)。所以,当先二分一游戏都会将碰撞分为四个级次:粗略和Mini(broad/narrow)。

简言之阶段(Broad Phase)

布罗兹 phase 能为您提供有超大希望碰上的实体列表。那可经过一些破例的数据布局完结,它们能为你提供新闻:实体存在什么地方和什么实体在其周围。这个数据构造能够是:四叉树(Quad Trees)、Enclave树(凯雷德-Trees)或空中哈希映射(Spatial Hashmap)等。

读者若感兴趣,能够自行查阅有关新闻。

精雕细刻阶段(Narrow Phase)

当您有了比较小的实业列表,你能够接纳精细阶段的算法(如上述陈说的冲击算法)得到三个适度的答案(是或不是产生相撞)。

最后

随意你碰不碰,作者都会自摸️✌️。

完!

参谋资料

  • MDN:2D collision detection
  • 《HTML5 Canvas 主题技能:图形、动漫与娱乐开拓》

    2 赞 3 收藏 1 评论

图片 16

本文由www.qjdy.com-奇迹赌场发布于www.qjdy.com,转载请注明出处:“等一下,我碰!”——常见的2D碰撞检测

关键词: HTML5 ag电子游艺

上一篇:JS核心系列:浅谈 原型对象和原型链

下一篇:没有了