被追尾了,严格来讲,就是你的汽车和别人的汽车发生了碰撞. 所以本文来介绍一些检测碰撞的算法.
鉴于所见即所得的观点,本文的代码使用了 html5, 如果对于 html5 canvas API 如果不清楚的话,可以参考 w3c 手册.
首先是最为简单的外接图形判别法. 例如我们想实现一个小球在如下的盒子内的移动,在移动过程中如果碰到边界就反弹(假定弹性碰撞,无机械能损失).
那么我们只需要在小球外接一个正方形,然后判定该正方形和边框是否发生碰撞就行了. 即想下图这样考虑蓝色的小正方形和矩形边框的碰撞情况就行了
代码如下(选择 JavaScript 完全是出于所见即所得的目的~)
<html>
<style type="text/css">
* {
margin:0;
padding:0;
}
canvas {
border:1px solid orange;
margin:10px auto 0;
display:block;
}
</style>
<body>
<!-- html5 画布对象 -->
<canvas id="canvas" width="300" height="200"></canvas>
</body>
<script>
// 构造小球的函数
var Ball = function(context) {
// 球的外切正方形的左上角顶点坐标
this.left = 0;
this.top = 0;
// 小球的半径
this.radius = 16;
// 小球的水平速度
this.velocityX = 3;
// 小球的垂直速度
this.velocityY = 2;
// 传入 H5 画布
this.context = context;
}
// 定义球拥有的方法
Ball.prototype = {
// 画球本身
paint: function() {
this.context.beginPath();
this.context.arc(this.left + this.radius, this.top + this.radius, this.radius, 0, Math.PI * 2, false);
this.context.fill();
},
// 球如何移动
move: function() {
this.left += this.velocityX;
this.top += this.velocityY;
}
}
// 处理边界碰撞逻辑
function handleEdgeCollisions(ball) {
// 球的外切正方形右下角
var ballRight = ball.left + ball.radius * 2;
var ballBottom = ball.top + ball.radius * 2;
// 球碰撞到了画布的左边框
if (ball.left < 0) {
ball.left = 0;
// 速度等值反向实现弹性碰撞
ball.velocityX = -ball.velocityX;
// 球碰到了画布的右边框
} else if (ballRight > canvas.width) {
ball.left = canvas.width - ball.radius * 2;
ball.velocityX = -ball.velocityX;
}
// 球碰到了画布的上边框
if (ball.top < 0) {
ball.top = 0;
ball.velocityY = -ball.velocityY;
// 球碰到了画布的下边框
} else if (ballBottom > canvas.height) {
ball.top = canvas.height - ball.radius * 2;
ball.velocityY = -ball.velocityY;
}
}
// 重新绘制图帧
function animate(time) {
context.clearRect(0, 0, canvas.width, canvas.height);
ball.move();
handleEdgeCollisions(ball);
ball.paint();
requestAnimationFrame(animate);
}
var canvas = document.getElementById('canvas');
context = canvas.getContext('2d');
ball = new Ball(context);
ball.paint();
requestAnimationFrame(animate);
</script>
</html>
其中 requestAnimationFrame 这个函数的作用在于传入浏览器重新渲染时的回调函数(即所谓的raf回调)——这里是 animate 函数. 这样 JavaScript 事件环(eventloop)重新渲染页面的时候就会触发 animate 回调.
事实上,通过外接图形判别法,我们将碰撞检测化归为了两个矩形之间的碰撞情况
矩形 rect1 和 rect2 之间相交的充要条件是
rect1.x < rect2.x + rect2.width && rect2.x < rect1.x + rect1.width
&&
rect1.y < rect2.y + rect2.height && rect2.y < rect1.y + rect1.height
我们可以再写一个较为纯粹的矩形物体之间碰撞检测的demo,注意,为节约篇幅,下面仅仅写出最为核心的检测碰撞的逻辑, 而省略掉了其他诸如canvas绘制的逻辑.
// 矩形碰撞检测的逻辑,返回true 表示发生了碰撞, 返回false 表示未发生碰撞, 下同
function handleEgdeCollisions(rect1, rect2) {
return rect1.left < rect2.left + rect2.width && rect2.left < rect1.left + rect1.width && rect1.top < rect2.top + rect2.height && rect2.top < rect1.height + rect1.top;
}
运行效果如下
外接图形判别法的优点是极为简单,但是缺点也是瞎眼可见的
其实坦克模型并非标准的矩形(例如炮管和坦克机身就有缝隙), 但是你使用一个外接矩形来模拟坦克之间的碰撞,就可能存在精度不足的问题,或者说没办法模拟的很真实.
物体运动速度过快时,可能会在相邻两动画帧之间快速穿越,导致忽略了本应碰撞的事件发生。这一点其实也很好理解,就拿浏览器来说,浏览器上运行JavaScript代码其实是通过事件环(EventLoop)机制的. 浏览器的两个动画帧之间会加入我们指定浏览器要做的任务回调,如果两个矩形的运动速度过快会导致浏览器根本来不及渲染,它俩就互相穿透彼此而过了. 然后就忽略了此次碰撞. 不过这貌似并不是碰撞检测算法的问题, 而是显示设备的渲染逻辑问题
适用案例:
圆心物体之间的碰撞是很好处理的. 只需要 通过判断任意两个圆形的圆心距离是否小于两圆半径之和,若小于则为碰撞。
示例代码(和矩形碰撞检测的代码几乎一样)
function handleEgdeCollisions(circle1, circle2) {
var circle1X = circle1.left + circle1.radius;
var circle1Y = circle1.top + circle1.radius;
var circle2X = circle2.left + circle2.radius;
var circle2Y = circle2.top + circle2.radius;
var distance = Math.sqrt(Math.pow(circle1X - circle2X, 2) + Math.pow(circle1Y - circle2Y, 2));
return distance < circle1.radius + circle2.radius;
}
运行效果
既然代码和矩形碰撞检测的代码类似,那么优缺点和适用场景和矩形碰撞检测也就完全类似了
所谓无旋转前面已经解释过了, 就是矩形的边需要平行于坐标轴
那么这种检测算法就很简单了. 只需要找出 矩形上离圆心最近的点,然后通过判断该点与圆心的距离是否小于圆的半径,若小于则为碰撞。
那么如何找出矩形上离圆心最近的点呢? 一种比较粗暴的算法是
但是有没有简单点的办法呢? 因为这里限定了矩形是不旋转的. 所以按直觉理应有更为简单的做法.
令 closestPoint 为我们想求的那个 矩形上离圆心最近的点,则
if(circle.x < rect.x)
),那么closestPoint.x = rect.x
如果圆心在矩形的右侧(else if(circle.x > rect.x + rect.w)
),那么 closestPoint.x = rect.x + rect.w
如果圆心在矩形的正上下方(else
),那么 closestPoint.x = circle.x
对于 Y 轴方向做完全类似的分析, 于是我们可以得到如下代码
function detectCollision(rect, circle) {
var cx, cy;
if (circle.x < rect.x) {
cx = rect.x;
} else if (circle.x > rect.x + rect.w) {
cx = rect.x + rect.w;
} else {
cx = circle.x;
}
if (circle.y < rect.y) {
cy = rect.y;
} else if (circle.y > rect.y + rect.h) {
cy = rect.y + rect.h;
} else {
cy = circle.y;
}
return distance(circle.x, circle.y, cx, cy) < circle.r;
}
运行效果
算法和上面 圆和无旋转矩形
碰撞的思想完全类似,即本质依旧是求出 矩形上离圆心的最近点
看似有点小困难,但其实你把矩形旋转视作是圆绕着矩形中心反方向旋转的话,就很好理解了. 如下图所示,
绿色的矩形(是蓝色矩形逆时针旋转了
后的矩形)+绿色的圆形的问题 和 蓝色的矩形+蓝色的圆形的问题 是等价的. 所以我们只需从蓝色矩形逆时针旋转
变成绿色矩形这一视角转变为绿色圆形顺时针旋转
转变为蓝色圆形这一视角就行了. 而假设 矩形的中心坐标是 R(rectCenterX, rectCenterY), 令 C(rotateCircleX, rotateCircleY) 是旋转后的圆心的坐标,那么就有如下等式
其中 C' 是 C 顺时针旋转
后的. 则就可以使用上述数学公式方便的计算旋转之后的 圆心坐标.
转换为蓝色矩形和蓝色圆形之后,就可以使用 圆形与无旋转矩形
相交的判定方法了.
示例代码如下
function detectCollision(rect, circle) {
var cx, cy;
var angleOfRad = degToRad(-deg);
// 矩形中心
var rectCenterX = rect.x + rect.w / 2;
var rectCenterY = rect.y + rect.h / 2;
// 顺时针旋转 angleOfRad 后的圆心坐标
var rotateCircleX = Math.cos(angleOfRad) * (circle.x - rectCenterX) - Math.sin(angleOfRad) * (circle.y - rectCenterY) + rectCenterX;
var rotateCircleY = Math.sin(angleOfRad) * (circle.x - rectCenterX) + Math.cos(angleOfRad) * (circle.y - rectCenterY) + rectCenterY;
if (rotateCircleX < rect.x) {
cx = rect.x;
} else if (rotateCircleX > rect.x + rect.w) {
cx = rect.x + rect.w;
} else {
cx = rotateCircleX;
}
// 和圆形与无旋转矩形一样的步骤获取矩形上距离圆心最近的点
if (rotateCircleY < rect.y) {
cy = rect.y;
} else if (rotateCircleY > rect.y + rect.h) {
cy = rect.y + rect.h;
} else {
cy = rotateCircleY;
}
return distance(rotateCircleX, rotateCircleY, cx, cy) < circle.r;
}
运行效果
显然,这种碰撞检测笔之前的碰撞检测适用范围更广了一些.
其实玩过推箱子游戏的话,这种碰撞检测就很容易理解
即把所有的物体格子化,然后移动物体的过程中,如果两个物体在同一格子的话,就认为两个物体发生了碰撞.
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]];
function handleEgdeCollisions(player, map) {
return map[player.top][player.left];
}
运行效果
本算法的缺点是显然的,使用场景的局限性太大,仅仅局限于 推箱子、扫雷等上世纪像素游戏中.
以像素级别检测物体是否存在重叠,从而判定是否发生碰撞. 这就解决了 外接图形判别法 的第二个缺陷. 该方法的思路可以拿下面的图作为例子予以说明
上图中,效仿外接图形判别法,我们将熊猫和竹子皆视为矩形,则注意,两个矩形有相交并不能说明熊猫和竹子有交,因为熊猫和竹子都并非标准的矩形(因为熊猫和竹子的像素点未必填满整个其所在的矩形),但是矩形相交是熊猫和竹子相交的必要条件. 所以我们判定熊猫和竹子相交的方法是,先求出熊猫和竹子所在矩形的交集,如果该交集是空集,则显然熊猫和竹子不相交,如果不是空集,则势必也是一个矩形(记做P),所以我们只需要取出熊猫在P中的像素点,和竹子在P中的像素点——这是两个长度相等的字节数组,如果存在某个数组索引,使得这两个数组在此索引的值都 > 0 的话,则表明熊猫和竹子相交了.
示例代码
// rect 是交集矩形 P
function handleEgdeCollisions(rect) {
// 取出熊猫在 P 中的像素字节数组
var imgData1 = offscreenContextPanda.getImageData(rect.left, rect.top, rect.width, rect.height);
// 取出竹子在 P 中的像素字节数组
var imgData2 = offscreenContextBamboo.getImageData(rect.left, rect.top, rect.width, rect.height);
var imgData1Data = imgData1.data;
var imgData2Data = imgData2.data;
// 这里一个像素 4字节, 所以 i += 4
for(var i = 3, len = imgData1Data.length; i < len; i += 4) {
if(imgData1Data[i] > 0 && imgData2Data[i] > 0) {
return true
}
}
return false
}
运行效果
注意,熊猫和竹子所在的矩形已经相交了,但是熊猫和竹子其实并没有相交.
熊猫和竹子这才真正的相交了. 而且,熊猫(竹子)离屏渲染 和 实际显示的canvas 中熊猫(竹子)的位置是完全一致的. 其实上面将熊猫(竹子)离屏数据渲染出来只是为了效果直观一些,实际运用过程中,肯定不会将这些离屏数据在屏幕上渲染出来,而是在内存中使用,因为内存中操作这些数据肯定远比在屏幕上渲染出这些数据快的多.
换言之,实际显示的canvas 只是起到展示作用,碰撞检测完全是在离屏数据offscreenContextPanda、offscreenContextBamboo 中进行的.
该方法的缺点是 因为需要检查每一像素来判定是否碰撞,性能要求比较高。适用于需要以像素级别检测物体是否碰撞的情形.
通过判断任意两个 凸多边形
在任意角度下的投影是否均存在重叠,来判断是否发生碰撞。若在某一角度光源下,两物体的投影存在间隙,则为不碰撞,否则为发生碰撞。
注意,一旦存在间隙的情况,表明从光源到间隙存在一条直线可以将这两个多边形分离开来,从而这两个多边形不相交. 这就是分离轴定理名字的由来.
但是程序中遍历所有光源的角度是不现实的,那如何确定 投影轴
呢?其实投影轴的数量与多边形的边数相等即可。
如果写伪代码的话,则
function polygonsCollide(polygon1, polygon2) { // 检测 polygon1 和 polygon2 两个多边形是否碰撞, 返回 true 表示发生了碰撞, 返回 false 表示没有发生碰撞
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
}
算法的复杂度是
的, 其中 n 是多边形顶点的个数.
显然,上述代码有几个需要解决的地方:
我们一个一个的解决这些问题
对于凸多边形的边 p1p2 ,它对应的投影轴就如上图所示. 我们首先确定该边的边缘法向量,然后投影轴就是平行于该边缘法向量的直线.
于是,每条多边形的边都可以构造相应的投影轴. 这就是上述 getAxes 函数
通过将一个多边形上的每个顶点与原点(0,0)组成的向量,投影在某一投影轴上,然后维护该多边形在该投影轴上所有投影中的最大值和最小值,这样即可表示一个多边形在某投影轴上的投影了。
注意,上图的投影轴是边 1 对应的投影轴. 为了易于理解,示例图将坐标轴原点(0,0)
放置于三角形边1
投影轴的适当位置。使得三角形 T 在投影轴上的投影恰好起点为0.
如上图所示,T在投影轴上的投影为黄色的 [Tmin = 0, Tmax], 而 P 在投影轴上的投影为 蓝色的 [Pmin, Pmax].
至于投影使用向量的点积就可以搞定了.
注意,从投影的过程中,我们就能看出为什么 SAT 定理只能针对凸多边形有效,因为凸多边形有一个凹多边形不具备的性质.就是凸多边形在它的任何一条边的同侧,而凹多边形可能在它的某条边的异侧. 于是SAT 定理对凹多边形是不能成立的.
所以投影有重叠部分的重要条件是
projection1.max > projection2.min && projection2.max > projection1.min
由于圆形可近似地看成一个有无数条边的正多边形,但是我们不可能按照这些边一一进行投影与测试。我们只需将圆形投射到一条投影轴上即可,这条轴就是圆心与多边形顶点中最近的一点的连线,如图所示:
因此,该投影轴和多边形自身的投影轴就组成了全部待检测的投影轴了。
最后,因为我们判断是否碰撞的图形有圆形和多边形,所以学过一点设计模式的话,就知道应该设计一个抽象的 Shape 类, 然后 圆形和 凸多边形都应该是 Shape 的子类.
示例代码
<html>
<style type="text/css">
* {
margin: 0;
padding: 0;
}
canvas {
border: 1px solid orange;
margin: 20px auto 0;
display: block;
}
</style>
<body>
<canvas id="canvas" width="600" height="280"></canvas>
</body>
<script>
// 封装向量
var Vector = function(point) {
if (point === undefined) {
this.x = 0;
this.y = 0;
}
else {
this.x = point.x;
this.y = point.y;
}
}
Vector.prototype = {
// 获取向量的模
getMagnitude: function() {
return Math.sqrt(Math.pow(this.x, 2) + Math.pow(this.y, 2))
},
// 向量的加法
add: function(vector) {
var v = new Vector()
v.x = this.x + vector.x
v.y = this.y + vector.y
return v
},
// 向量的减法
subtract: function(vector) {
var v = new Vector()
v.x = this.x - vector.x
v.y = this.y - vector.y
return v
},
// 点积
dotProduct: function(vector) {
return this.x * vector.x + this.y * vector.y
},
// 生成起点为vector的向量
edge: function(vector) {
return this.subtract(vector)
},
// 法向量, 即投影轴
perpendicular: function() {
var v = new Vector()
v.x = this.y
v.y = -this.x
return v
},
// 规范化
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()
}
}
// 封装投影
var Projection = function(min, max) {
this.min = min
this.max = max
}
Projection.prototype = {
overlaps: function(projection) {
return this.max > projection.min && projection.max > this.min
}
}
// 封装多边形
var Shape = function() {
this.x = undefined
this.y = undefined
this.strokeStyle = 'rgba(255, 253, 208, 0.9)'
this.fillStyle = 'rgba(147, 147, 147, .8)'
}
Shape.prototype = {
// 返回 true 表示两个多边形相交, 否则没有
collidesWith: function(shape) {
// 计算两个多边形的所有投影轴
var axes = this.getAxes().concat(shape.getAxes())
return !this.separationOnAxes(axes, shape)
},
// 返回 true 表示分离轴存在, 即这两个多边形不相交
separationOnAxes: function(axes, shape) {
for(var i = 0, len = axes.length; i < len; i++) {
axis = axes[i]
projection1 = shape.project(axis)
projection2 = this.project(axis)
// 一旦发现不重叠, 则分离轴存在
if(!projection1.overlaps(projection2)) {
return true
}
}
return false
},
// 抽象类不实现方法, 实现交给子类 Polygon
project: function(axis) {
throw 'project(axis) not implemented'
},
getAxes: function() {
throw 'getAxes() not implemented'
},
move: function(dx, dy) {
throw 'move(dx, dy) not implemented'
},
createPath: function(context) {
throw 'createPath(context) not implemented'
},
// 模板设计模式
fill: function(context) {
context.save()
context.fillStyle = this.fillStyle
this.createPath(context)
context.fill()
// 恢复画布设置
context.restore()
},
stroke: function(context) {
context.save()
context.strokeStyle = this.strokeStyle
this.createPath(context)
context.stroke()
context.restore()
},
// 如果指定的点位于当前路径中,则返回 true,否则返回 false
isPointInPath: function(context, x, y) {
this.createPath(context)
return context.isPointInPath(x, y)
}
}
// 封装点
var Point = function(x, y) {
this.x = x
this.y = y
}
// 封装(凸)多边形
var Polygon = function() {
this.points = []
this.strokeStyle = 'blue'
this.fillStyle = 'white'
}
// 在凸多边形的原型链上挂Shape, 表明 凸多边形是 Shape 类型的, 则 new Polygon 可以调用 Shape 的方法
Polygon.prototype = new Shape()
// 获取凸多边形的投影轴
Polygon.prototype.getAxes = function() {
var v1 = new Vector(),
v2 = new Vector(),
axes = []
for(var i = 0, len = this.points.length - 1; i < len; i++) {
v1.x = this.points[i].x
v1.y = this.points[i].y
v2.x = this.points[i + 1].x
v2.y = this.points[i + 1].y
// v2v1
axes.push(v1.edge(v2).normal())
}
// 别漏了最后一条边
v1.x = this.points[this.points.length - 1].x
v1.y = this.points[this.points.length - 1].y
v2.x = this.points[0].x
v2.y = this.points[0].y
axes.push(v1.edge(v2).normal())
return axes
}
// 获取多边形到投影轴 axis 上的投影 scalars (标量的意思)
Polygon.prototype.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))
})
// 得到多边形在 axis 投影轴上的投影范围
return new Projection(Math.min.apply(Math, scalars), Math.max.apply(Math, scalars))
}
Polygon.prototype.addPoint = function(x, y) {
this.points.push(new Point(x, y))
}
// 画多边形
Polygon.prototype.createPath = function(context) {
if(this.points.length === 0) {
return
}
context.beginPath()
context.moveTo(this.points[0].x, this.points[0].y)
for(var i = 0, len = this.points.length; i < len; i++) {
context.lineTo(this.points[i].x, this.points[i].y)
}
context.closePath()
}
// 多边形平移 (dx, dy) , 用于实现拖拽回调
Polygon.prototype.move = function(dx, dy) {
for(var i = 0, point, len = this.points.length; i < len; i++) {
point = this.points[i]
point.x += dx
point.y += dy
}
}
// 多边形是否和shape(圆形或者凸多边形)发生碰撞
Polygon.prototype.collidesWith = function(shape) {
var axes = shape.getAxes()
if(axes === undefined) {
return polygonCollidesWithCircle(this, shape)
} else {
axes = axes.concat(this.getAxes())
return !this.separationOnAxes(axes, shape)
}
}
// 封装圆形
var Circle = function(x, y, radius) {
this.x = x
this.y = y
this.radius = radius
this.strokeStyle = 'rgba(255, 253, 208, .9)'
this.fillStyle = 'rgba(147, 197, 114, .8)'
}
Circle.prototype = new Shape()
// 圆形是否和 shape (圆形或者凸多边形) 发生碰撞
Circle.prototype.collidesWith = function(shape) {
var point, length, min = 10000, v1, v2,
edge, perpendicular, normal,
axes = shape.getAxes(), distance
// shape 是圆形
if(axes === undefined) {
distance = Math.sqrt(Math.pow(shape.x - this.x, 2) + Math.pow(shape.y - this.y, 2))
return distance < Math.abs(this.radius + shape.radius)
// shape 是凸多边形
} else {
return polygonCollidesWithCircle(shape, this)
}
}
// 圆形的投影轴取决于判断是否和它相交的凸多边形, 而不能由圆形自己决定, 所以这里取 undefined
Circle.prototype.getAxes = function() {
return undefined
}
// 圆形向投影轴 axis 的投影
Circle.prototype.project = function(axis) {
var scalars = [],
point = new Point(this.x, this.y),
dotProduct = new Vector(point).dotProduct(axis)
scalars.push(dotProduct)
scalars.push(dotProduct + this.radius)
scalars.push(dotProduct - this.radius)
return new Projection(Math.min.apply(Math, scalars),
Math.max.apply(Math, scalars))
}
// 圆形平移, 用于实现拖拽回调
Circle.prototype.move = function(dx, dy) {
this.x += dx
this.y += dy
}
Circle.prototype.createPath = function(context) {
context.beginPath()
context.arc(this.x, this.y, this.radius, 0, Math.PI * 2, false)
}
// 获取和圆心最近的凸多边形上的一个点
function getPolygonPointClosestToCircle(polygon, circle) {
var min = 10000, length, testPoint, closestPoint
for(var i = 0, len = polygon.points.length; i < len; i++) {
testPoint = polygon.points[i]
length = Math.sqrt(Math.pow(testPoint.x - circle.x, 2), Math.pow(testPoint.y - circle.y, 2))
if(length < min) {
min = length
closestPoint = testPoint
}
}
return closestPoint
}
// 凸多边形 和 圆形是否发生碰撞
function polygonCollidesWithCircle(polygon, circle) {
var min = 10000, v1, v2,
edge, perpendicular,
axes = polygon.getAxes(),
closestPoint = getPolygonPointClosestToCircle(polygon, circle)
v1 = new Vector(new Point(circle.x, circle.y))
v2 = new Vector(new Point(closestPoint.x, closestPoint.y))
axes.push(v1.subtract(v2).normalize()) // 在凸多边形的投影轴基础上再加一条圆形的投影轴
return !polygon.separationOnAxes(axes, circle)
}
var canvas = document.getElementById('canvas'),
context = canvas.getContext('2d'),
shapes = [],
polygonPoints = [
[ new Point(250, 150), new Point(250, 250),
new Point(350, 250) ],
[ new Point(100, 100), new Point(100, 150),
new Point(150, 150), new Point(150, 100) ],
[ new Point(400, 100), new Point(380, 150),
new Point(500, 150), new Point(520, 100) ]
],
polygonStrokeStyles = [ 'blue', 'yellow', 'red'],
polygonFillStyles = [ 'rgba(255,255,0,0.7)',
'rgba(100,140,230,0.6)',
'rgba(255,255,255,0.8)' ],
circle1 = new Circle(150, 75, 20),
circle2 = new Circle(350, 45, 30),
mousedown = { x: 0, y: 0 },
lastdrag = { x: 0, y: 0 },
// 被拖拽的图形
shapeBeingDragged = undefined;
// 根据鼠标在浏览器窗口中点击的位置计算出在画布中的坐标
function windowToCanvas(e) {
var x = e.x || e.clientX,
y = e.y || e.clientY,
bbox = canvas.getBoundingClientRect();
return { x: x - bbox.left * (canvas.width / bbox.width),
y: y - bbox.top * (canvas.height / bbox.height)
};
};
function drawShapes() {
shapes.forEach( function (shape) {
shape.stroke(context);
shape.fill(context);
});
}
function detectCollisions() {
var textY = 30,
numShapes = shapes.length,
shape,
i;
if (shapeBeingDragged) {
for(i = 0; i < numShapes; ++i) {
shape = shapes[i];
if (shape !== shapeBeingDragged) {
if (shapeBeingDragged.collidesWith(shape)) {
context.fillStyle = shape.fillStyle;
context.fillText('撞了...', 20, textY);
textY += 40;
}
}
}
}
}
canvas.onmousedown = function (e) {
var location = windowToCanvas(e);
// 确定画布中被拖拽的图形(shape)是哪一个
shapes.forEach( function (shape) {
if (shape.isPointInPath(context, location.x, location.y)) {
shapeBeingDragged = shape;
mousedown.x = location.x;
mousedown.y = location.y;
lastdrag.x = location.x;
lastdrag.y = location.y;
}
});
}
canvas.onmousemove = function (e) {
var location,
dragVector;
if (shapeBeingDragged !== undefined) {
location = windowToCanvas(e);
dragVector = { x: location.x - lastdrag.x,
y: location.y - lastdrag.y
};
shapeBeingDragged.move(dragVector.x, dragVector.y);
lastdrag.x = location.x;
lastdrag.y = location.y;
context.clearRect(0,0,canvas.width,canvas.height);
drawShapes();
detectCollisions();
}
}
canvas.onmouseup = function (e) {
shapeBeingDragged = undefined;
}
for (var i=0; i < polygonPoints.length; ++i) {
var polygon = new Polygon(),
points = polygonPoints[i];
polygon.strokeStyle = polygonStrokeStyles[i];
polygon.fillStyle = polygonFillStyles[i];
points.forEach( function (point) {
polygon.addPoint(point.x, point.y);
});
shapes.push(polygon);
}
shapes.push(circle1)
shapes.push(circle2)
context.shadowColor = 'rgba(100,140,255,0.5)';
context.shadowBlur = 4;
context.shadowOffsetX = 2;
context.shadowOffsetY = 2;
context.font = '38px Arial';
drawShapes();
context.save();
context.fillStyle = 'cornflowerblue';
context.font = '24px Arial';
context.fillText('拖拽物体', 10, 25);
context.restore();
</script>
</html>
运行效果如下
显然,分离轴算法适用于圆形、凸多边形之间的碰撞检测. 还是有一定的价值的. 关于 SAT 定理,还有更为优秀的 GJK 碰撞检测算法. GJK 比 SAT 更适用于推广到 3D 场景. 关于 GJK 算法,后续推文会再介绍.
假想一下,我们现在在设计一个程序,它能有效的监测路面上车辆的位置,我们的程序要去发现发生碰撞的车辆. 怎么做才比较有效率呢? 回顾我们上面的碰撞算法,是
的, 所以碰撞检测并不是一件轻松的事情.
若每个图帧都需要对全部物体进行两两判断,会造成性能浪费,因为有些物体分布在不同区域,根本不会发生碰撞。例如下图
我们事先将整个游戏沙盒分成了四个象限(用细黑线标识了)
上图中小汽车A和 小汽车B 、 C根本不在一个象限,就更谈不上碰撞,所以更不值得去花费
去检测A和B、A 和 C 是否发生碰撞。
所以,大部分游戏都会将碰撞检测分为两个阶段:粗略阶段和精细阶段(broad/narrow)。
Broad phase 能为你提供有可能碰撞的实体列表。这可通过一些特殊的数据结构实现,它们能为你提供这些信息:实体存在哪里和哪些实体在其周围。这些数据结构可以是:四叉树(Quad Trees)、八叉树(OcTree)、R树(R-Trees)或空间哈希映射(Spatial Hashmap)等,但据笔者所知,R 树在数据库的高维索引方面应用可能更加广泛,而不是用于游戏中的碰撞检测. 关于四叉树、八叉树,后续推文会再介绍.
当你有了较小的实体列表,你可以利用精细阶段的算法(如上述讲述的碰撞算法)得到一个确切的答案(是否发生碰撞)。
温馨提示
如果你喜欢本文,请分享到朋友圈,想要获得更多信息,请关注ACM算法日常。