ゲームの衝突検出の基本

衝突検出とは何か？

衝突検出は主に、ゲーム内のキャラクターやオブジェクト、地形等が互いに当たっているかどうかを判定するために使われる。具体的な例としてあげられるのは、戦闘機の撃った弾やキャラクターのパンチが敵に当たったか？球がプレイヤーのラケットやバットに当たったか？もしくはそれらが、環境内の壁や地面に当たったか？など。そして、衝突検出の結果は物理エンジンやゲームのロジック計算部に渡され、衝突の勢いと関連する物理属性をもとに、反発力を計算し、次のフレームにおける各物体の位置が決定される。

リアルタイムゲームでは、大抵ゲーム内の世界も現実世界と同様に、過去から未来へと時間を進めていく

それ以外にも、キャラクターの進行方向の障害物の有無を確認し、移動経路を決めるとか、敵視野内にプレイヤーがいるかどうかを判定して、AIの判断材料にするなど、アクション性のあるゲームであれば、様々な場面で活用される。古典的なコンピュータゲームから、最新のゲームに至るまで、程度の差はあれ、ゲームの体裁を整えるために、何かしら衝突を検出する機能を実装しているはずである。このように、衝突検出はゲーム内の様々なシステムにコンピュータ内に構築された仮想世界の”形”に関連する情報を伝える、という役割を担っている。

コンピュータが扱う”モノの形”

では、いったいどうやってコンピュータに物体間の衝突を検出させるのか？まず、コンピュータが扱えるのは、いわゆるプリミティブと呼ばれる幾何学形状だけである。こういった形状はパラメトリックに表現でき、判定対象となる形状の特徴をうまく利用することで、交差する点を計算することができる。そして、衝突検出は与えられたプリミティブの組み合わせに合致する関数を選び出し、交差を検出する。例えば、球は中心位置と半径で表すことができ、球と球の交差は、２つの球の中心位置の距離と半径の和から計算することができる。

|C1-C2| < r1+r2のとき、２つの球は衝突している。

プリミティブの例：球、ボックス、カプセル、三角形、凸包(Convex hull)など

struct Sphere
{
    float radius;
};

struct Box
{
    Vector3 extent;
};

struct Capsule
{
    float radius, halfLength;
};

結局のところ、ゲーム内に登場する一見複雑に見えるキャラクターも、コンピュータの解釈する世界では、このようなプリミティブ形状の組み合わせでしかない。最終的に画面にレンダリングされる絵と比べ、かなり簡素な感じに見えるだろう。

交差検出関数の例：球とボックス、カプセルと円柱、ボックスとボックスなど 

プリミティブ形状の組み合わせごとに必要となるアルゴリズムは違うため、このような判定関数はすべての組み合わせに対して個々に用意しなければならない。もし、ゲームに登場する物体がすべてボックスと球体だけで構成されているとすると、必要な衝突検出の組み合わせは、ボックスと球、ボックスとボックス、球と球の3通りだけとなる。

また、3Dゲームであれば、位置は要素数３のベクトル、姿勢は３ｘ３マトリクスかクォータニオンで表現される。もしくは位置と姿勢を１つの４ｘ４マトリクスとして表すこともできる。いずれにしても、衝突検出関数に必要なのは、２つのプリミティブを表現するためのパラメータと、その位置と姿勢である。

struct Vector3
{
    float x,y,z;
};

struct Quaternion
{
    float x,y,z,w;
};

struct Matrix3
{
    float elem[9];
};

ゲームに必要な情報

通常、ゲームでは２つの物体の衝突する点だけが得られたところで、衝突検出の情報としては不十分である。知りたいことは、どこで衝突しているのか、だけではない。どの方向に、どのくらい引き離せばその衝突を解消できるのか、という情報がなければ、後のゲーム的な表現には繋がっていかない。プレイヤーキャラクターの放ったパンチが敵に当たったとき、敵を当たった位置からパンチの逆方向に動かさなければ、当たった感が得られない。車がガードレールにぶつかった際も、衝突と逆方向に車を動かさなければ、車はそのままガードレールを突き破ってしまう。つまり交差検出関数は、衝突した座標以外に、交差の深さ（貫通深度）、そして衝突の解消する方向（衝突法線）を情報として返す必要がある。

P1が球C1の衝突点、ベクトルの方向は衝突法線、大きさが貫通深度を表す。

衝突法線方向に貫通深度の大きさだけ球C1を動かすと貫通が解消される。

衝突検出関数の最終形

まとめると、２つのプリミティブ形状の衝突を検出する最終的な関数は以下のような形式になる。このような関数は、ゲームエンジンや衝突検出システム全体からすると最下層にあって、衝突検出プロセスの最後に呼ばれる。

入力：２つのプリミティブ情報、それぞれの位置と姿勢

出力：衝突点、衝突法線、貫通深度