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

来源:http://www.sh-fengwen.com 作者: 营养排行 人气:106 发布时间:2019-12-04
摘要:“等一下,我碰!”——常见的2D碰撞检测 2017/02/22 · HTML5 · 1评论 ·碰撞检测 原文出处:凹凸实验室    “碰乜鬼嘢啊,碰走晒我滴靓牌”。想到“碰”就自然联想到了“麻将”这一

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

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

原文出处: 凹凸实验室   

图片 1

“碰乜鬼嘢啊,碰走晒我滴靓牌”。想到“碰”就自然联想到了“麻将”这一伟大发明。当然除了“碰”,洗牌的时候也充满了各种『碰撞』。

好了,不废话。直入主题——碰撞检测。

在 2D 环境下,常见的碰撞检测方法如下:

  • 外接图形判别法
    • 轴对称包围盒(Axis-Aligned Bounding Box),即无旋转矩形。
    • 圆形碰撞
  • 光线投射法
  • 分离轴定理
  • 其他
    • 地图格子划分
    • 像素检测

下文将由易到难的顺序介绍上述各种碰撞检测方法:外接图形判别法 > 其他 > 光线投射法 > 分离轴定理。

另外,有一些场景只要我们约定好限定条件,也能实现我们想要的碰撞,如下面的碰壁反弹:

当球碰到边框就反弹(如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-Aligned 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

在线运行示例(先点击运行示例以获取焦点,下同):

缺点:

  • 相对局限:两物体必须是矩形,且均不允许旋转(即关于水平和垂直方向上对称)。
  • 对于包含着图案(非填满整个矩形)的矩形进行碰撞检测,可能存在精度不足的问题。
  • 物体运动速度过快时,可能会在相邻两动画帧之间快速穿越,导致忽略了本应碰撞的事件发生。

适用案例:

  • (类)矩形物体间的碰撞。
var intersectionDetail = path1.Data.FillContainsWithDetail(path2.Data);

if (intersectionDetail != IntersectionDetail.NotCalculated &&
    intersectionDetail != IntersectionDetail.Empty)
{
    // collision
}

圆形碰撞(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 Theorem)

概念:通过判断任意两个 凸多边形 在任意角度下的投影是否均存在重叠,来判断是否发生碰撞。若在某一角度光源下,两物体的投影存在间隙,则为不碰撞,否则为发生碰撞。

图例:
图片 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) 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
}

上述代码有几个需要解决的地方:

  • 如何确定多边形的各个投影轴
  • 如何将多边形投射到某条投影轴上
  • 如何检测两段投影是否发生重叠

本文由美高梅游戏平台网站发布于 营养排行,转载请注明出处:“等一下,我碰!”——常见的2D碰撞检测

关键词:

最火资讯