浅析圆形物体的碰撞检测及应用

物体的碰撞检测是游戏动画中常涉及的内容,当然我没做过游戏,只是最近接触canvas比较多,也有不少热衷html5的canvas的人提起了这个碰撞检测,所以试着拿网上一位大牛的canvas检测算法做些分析注释。
先引用些链接:
重力版google:http://mrdoob.com/projects/chromeexperiments/google_gravity/ ——非规则物体的碰撞。
可融性水滴:http://hakim.se/experiments/html5/blob/03/ ——一个物体由多个点连接构成。

本文涉及的一个碰撞检测方法是针对于圆形物体的。显然这是比较有规律可循的,但也不要小看圆形物体的碰撞检测,一些非规则物体也可以包围球的形式使用圆形检测来检测。
代码来自:http://www.benjoffe.com/es/code/demos/collide/
本文做了一些中文翻译,并会稍加分析。

 

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176

// Coliding Discs experiment
// Copyright Benjamin Joffe, 2010

var canvas = document.getElementById('balls');
var ctx = canvas.getContext('2d');
var co = [];
var starter = Math.random()*9 >> 0; //白球序号(随机值用右移位实现去尾取整)

for (var i=0; i<9; i++)
{
co[i] = { //折行排列(x,y)
x: (760/3)*(0.5+i%3),
y: (760/3)*(0.5+((i/3)>>0)),
r: 2*(i*2+15),
c: starter==i ? '#fff' : '#000'
};
// 随机速度(保证向量长度为1)
co[i].vx = 1-2*Math.random();
co[i].vy = Math.sqrt(1-co[i].vx*co[i].vx) * ( Math.random() < 0.5 ? -1 : 1 );

// 起始阶段除白球外其他球保持静止。半径越小,i值越大,速度越大。
co[i].vx *= i==starter ? 200/co[i].r : 0;
co[i].vy *= i==starter ? 200/co[i].r : 0;
}

function draw()
{
ctx.fillStyle='rgba(220,220,220,0.5)';
ctx.fillRect(0,0,canvas.width, canvas.height); //涂白清屏(带透明度)
for (i=0; i<co.length; i++)
{
ctx.fillStyle=co[i].c;
ctx.beginPath();
ctx.moveTo(co[i].x+co[i].r, co[i].y);
ctx.arc(co[i].x, co[i].y, co[i].r, 0, Math.PI*2, true);
ctx.fill();
}
}

function move()
{
var total_time_left = 5;
var t=0;
var col_index; // 肇事球
var col_index2 // 被撞球

var col_time; // 距离发生碰撞的时间
var ball_time; // 碰撞倒计时
var temp;

var i, j, test_method;
var col_method; //碰撞方式

while (true)
{

col_index = -1; // choose an invalid index initially
col_time = total_time_left;

// this loop finds the ball that will collide first
for (i=0; i<co.length; i++)
{
// (god forbid) 若发生了灵异现象,超出了屏幕,立即反向。
if (co[i].vx < 0 && co[i].x < co[i].r || co[i].vx > 0 && co[i].x + co[i].r > canvas.width)
{
co[i].vx *= -1;
continue;
}

if (co[i].vy < 0 && co[i].y < co[i].r || co[i].vy > 0 && co[i].y + co[i].r > canvas.height)
{
co[i].vy *= -1;
continue;
}

// now for the real collision checks

// 球与墙之间检测
for (test_method = 0; test_method < 4; test_method++ )
{
switch (test_method)
{
case 0 :
ball_time = (co[i].r - co[i].x) / co[i].vx; //球与左壁发生碰撞的倒计时
break;
case 1 :
ball_time = (co[i].r - co[i].y) / co[i].vy; // top wall
break;
case 2 :
ball_time = (canvas.width - co[i].r - co[i].x) / co[i].vx; // right wall
break;
case 3 :
ball_time = (canvas.height - co[i].r - co[i].y) / co[i].vy; // bottom wall
break;
}
if (ball_time > 0 && ball_time < col_time) //碰撞时间为正值,且小于之前算出的碰撞时间(求出最迫切的碰撞)。
{
col_time = ball_time;
col_index = i;
col_method = test_method;
}
}

// 球球之间检测(检测第i球与后面所有球)
for (j = i+1; j < co.length; j++)
{
ball_time = check_collision(co[i], co[j]); /* **球球检测算法** */
if (ball_time > 0 && ball_time < col_time)
{
col_method = 5;
col_time = ball_time;
col_index = i;
col_index2 = j;
}
}
}

// 增加位移
for (i=0; i<co.length; i++)
{
co[i].x += col_time * co[i].vx;
co[i].y += col_time * co[i].vy;
}

if (col_index == -1) break; // 如无碰撞,退出循环

// 撞到屏幕,反向
if (col_method == 0 || col_method == 2) // side walls
{
co[col_index].vx*=-1;
}
if (col_method == 1 || col_method == 3) // top and bottom walls
{
co[col_index].vy*=-1;
}
//球球相撞
if (col_method == 5)
{
apply_collision(co[col_index], co[col_index2]); /* ** 球球碰撞后果 ** */
}
total_time_left -= col_time;
}
}

// 球球相撞检测
function check_collision(b1, b2){ //返回当b1,b2接触所需要的时间。
var a = b1.x - b2.x,
b = b1.vx - b2.vx,
c = b1.y - b2.y,
d = b1.vy - b2.vy;
// I probably shouldn't have crushed the following logic into one line, makes it just a wee bit unreadable 作者在此处做了一些代码混淆。下面3行是我重写的。
//return b==0&&d==0||(c=(b=2*(a*b+c*d)+0*(d=b*b+d*d))*b-4*d*(a*a+c*c-(c=b1.r+b2.r)*c))<0?-1:(-b-Math.sqrt(c))/(2*d);
if(b==0&&d==0 ) return -1;
var p=(a*b+c*d)/(b*b+d*d);
return -p-Math.sqrt(((b1.r+b2.r)*(b1.r+b2.r)-(a*a+c*c))/(b*b+d*d)+p*p);
}

// 球球相撞处理
function apply_collision(b1, b2){ //b1,b2已接触
var
a = (b2.r * b2.r) / (b1.r * b1.r) , //半径的平方比(反映质量比)
b = (b1.y - b2.y) / (b1.x - b2.x) , //球心连线构成的正切值
c = 2*( (b1.vx - b2.vx) +b* ( b1.vy - b2.vy ) )/((1+b*b)*(1+a)); //改变的速度发生在球心连线上。
b2.vx += c;
b2.vy += c*b;
b1.vx -= c*a;
b1.vy -= c*a*b;
}

setInterval(function()
{
move();
draw();
},30);
draw();

再简略说一下两球之间的碰撞检测方法check_collision:
当前位置两球的x方向距离为a,y方向距离为c,两球x方向上的相对速度为b,y方向上为d。
假设经过时间t之后,两球相撞。
此时,两球的距离为(r1+r2),而在x方向上的距离应为(a+bt),y方向上距离为(c+dt)
根据直角三角形性质:(a+bt)^2+(c+dt)^2=(r1+r2)^2
经过数学换算可得:t=-(ab+cd)/(bb+dd)-Math.sqrt(((b1.r+b2.r)(b1.r+b2.r)-(aa+cc))/(bb+dd)+((ab+cd)/(bb+dd))((ab+cd)/(bb+dd)))
如果你不会换算,可以看看这个链接:http://www.wolframalpha.com/input/?i=(a%2Bb*t)^2%2B(c%2Bd*t)^2%3D(r1%2Br2)^2

碰撞检测符合碰撞条件之后之后,就是碰撞反弹了apply_collision。
碰撞问题其实在高中物理中,已经有所学习了。我们要解的这个问题就是一个弹性斜碰撞的问题。
这种碰撞符合的定律是:动量守恒(碰撞前后矢量和相等)和动能守恒(碰撞后起码不增加)定律。