2D衝突編
その１ 点と点
点と点の衝突は、言うまでも無く「2点が同じ座標にあれば衝突」です。はい終了･･･と言いたいのですが、パソコンというデジタルな環境、そしてゲームという離散的な時間を考えたとき、ちょっと厄介な事が生じます。
① 点が重なる難しさ
点を表す座標が整数の場合、衝突判定は気楽に出来ます。
if(P1.x == P2.x && P1.y == P2.y)
{
// 衝突！
}
ところが、点を表す座標が浮動小数点の場合、上のプログラムは意味を持ちません。一般に、演算を繰り返した浮動小数点が、理論上は同じになる場合であっても等しくなることは保障されません。それは、浮動小数点は2進数で表される有限近似小数なので、無限小数や循環小数を正しく表すことができないからです。演算を繰り返すと、その誤差が蓄積されてしまうのです。処理系にもよりますが、Visual C++6の場合、次の結果はFALSEでした。
float a = 1/47.0;
float c = a * 47.0;
if(c == 1.0)
return TRUE;
return FALSE;
これは結構ショックなもんです。a = 1/47 * 47という何気ない演算の結果が1.0と等しくないと判定されるのですから。こんな不確かな衝突判定はしてはいけません。
浮動小数点を扱う場合、誤差を許容する工夫が必要になります。例えば、誤差が0.00001よりも小さいときには衝突と認めるといった工夫です。上のプログラムも、
float a = 1/47.0;
float c = a * 47.0;
if(fabs(c - 1.0) < 0.00001)
return TRUE;
return FALSE;
と誤差を取ると、ちゃんとTRUEになります。誤差を幾つにするかは考えているゲームの精度によります。
② 通り抜ける点
次のような正面衝突を考えます。
左の青は1フレームごとに右に2、右の赤点は左に2ずつ進行します。座標を追ってみましょう。
1フレーム経過 ： 青(2, 0) - 赤(8, 0)
2フレーム経過 ： 青(4, 0) - 赤(6, 0)
さ、予定では次のフレームで衝突が起こるはずなのですが･･･
3フレーム経過 ： 青(6, 0) - 赤(4, 0)
値が等しくならず、点は何事も無くすり抜けてしまいました。これは、整数だろうと実数だろうと関係なく同じことが起こります。 ゲームはフレームという離散時間で画面を更新しますから、こういうことはいくらでも起きてしまうのです。
これを厳密に防ぐには、１つ前の点の位置と今の位置までの軌跡を描き、それが交差している場合には、2点がその交点に達した時刻を算出し、その時刻が等しければ「衝突」と判定します。ただ、物理学のシミュレータを作るならまだしもゲームですから、そのような厳密性は必ずしも必要にはなりません。例えば、軌跡が交差した場合は衝突とみなすとか、そういう状況が起こらないように工夫した方が賢明です。
線分の交差については、「線分と線分」の章で紹介します。