結果だけでなく過程も見てください

日々の奮闘を綴る日記です。

実践的な衝突判定(AABB編)

C言語 DirectX ゲーム C++ プログラミング

自作ゲームに組み込んでいる衝突判定について、整理も兼ねてご紹介します。
説明を簡単にするために2D空間で説明します。

バウンディングボリューム

バウンディングボリュームについては、容易に判定可能で実用的ということで
各軸に平行な四角形(以下の図のようなの)を採用します。
このような四角形のことをAABB(axis-aligned bounding box)と言います。

AABBのデータ構造

色々考えられますが、

  1. 最小座標とそれぞれの辺の長さ
  2. 中心座標とそれぞれの辺の半分の長さ
  3. 最小座標と最大座標

ここでは1.を採用します。
データ構造は以下のようになります。

struct AABB
{
  POINT min_;
  SIZE  size_;
};

図にすると以下のようになります。

静止しているAABB同士の衝突判定

上の図でobj1とobj2が衝突する条件を文章で書くと以下のようになります。

  obj1の右側がobj2の左側より大きい　かつ
  obj1の左側がobj2の右側より小さい　かつ
  obj1の上側がobj2の下側より大きい　かつ
  obj1の下側がobj2の上側より小さい
  の場合、衝突している。

ソースコードとしては、左下の座標を(left,bottom)、
右上を(right,top)とすると、以下のようになるでしょう。

// 戻り値 true  :衝突している
//        false :衝突していない
bool collisionTest( const RECT& obj1, const RECT& obj2 )
{
  return ( (obj1.right  > obj2.left  ) &&
           (obj1.left   < obj2.right ) &&
           (obj1.top    > obj2.bottom) &&
           (obj1.bottom < obj2.top   ) );
}

上記AABB構造体で書き直すと以下のようになります。

// 戻り値 true  :衝突している
//        false :衝突していない
bool TestAABBAABB( const AABB& obj1, const AABB& obj2 )
{
  return ( (obj1.min_.x + obj1.size_.cx > obj2.min_.x                ) &&
           (obj1.min_.x                 < obj2.min_.x + obj2.size_.cx) &&
           (obj1.min_.y + obj1.size_.cy > obj2.min_.y                ) &&
           (obj1.min_.y                 < obj2.min_.y + obj2.size_.y ) );
}

動いているAABB同士の衝突判定

静止しているAABB同士の衝突は単純なものでした。
しかし普通ゲームでは各オブジェクトは、画面を縦横無尽に動き回っていますね。

ここで、ゲーム中に「オブジェクトが動いているように見える」ことの仕組みについて説明しておきます。

ゲーム中の計算は、通常1/60秒に一回行われます。
この一回の計算をフレームと言います。

オブジェクトの移動は、各フレームでその瞬間の座標に速度を加算し続けていくことで表現されます。
図にするとこんな感じです。

1フレーム目の座標はP0
2フレーム目の座標はP0+v
3フレーム目の座標はP0+2v
:
nフレーム目の座標はP0+nv

このような離散的な座標の移動が、人間の目に軌跡として映るわけです。

このことから、上で説明した「静止しているAABB同士の衝突判定」では、
以下のような問題が起こる可能性がありますね。

obj1がとても大きな速度vを持っていたとします。obj2は静止しています。
普通に考えればobj1はobj2に衝突しますが・・・。

速度vが非常に大きいため、もともとの座標にvを加算すると、obj2を通り越してしまいます。
すり抜け現象が発生してしまうわけです。

つまり、オブジェクトの衝突を正しく判定するには、
その瞬間瞬間の座標だけでなく、速度や加速度からどういう軌跡を描くかを考えなければいけません。

点とAABBの衝突

いきなりAABB同士の衝突は難しいので、まずは点とAABBの衝突について考えます。

複雑な軌跡も、1フレーム単位で見れば等速運動とみなすことができます。
現在座標がP0で速度がvの点は、点P0を通りベクトルvに平行なベクトルとして以下の式で表すことができます。

1フレーム間の取りうる値についてなのでtは0と1の間の値を取ります。

さて上の図を見てみましょう。点は速度vで動いてます。objも速度v1で動いてます。
双方が動いている状況での判定は複雑です。

ということで、ここではobjの動きを止めてしまいます。
要は相対速度で判定を行えばよいのです。相対速度をrv=v-v1とすると

となります。これでobjが静止しました。

次にこの点の軌跡がobjの左辺に当たっているかどうかを計算します。
AABBは軸に平行なので、rvをxとy軸にわけ、それぞれ左右の辺、上下の辺に当たっているかを判定します。

それではまずx方向の衝突判定を見ていきましょう。

点はP1 = P0 + tvの式で表すことができるので、左辺に衝突する時刻は以下の式で求められます。

このtが0と1の間であれば、rv.xとAABBは1フレームの間に交差したとみなすことができます。
ただしvが0になるときは平行に移動しており交差することはありません。
相対速度が0ならば衝突判定処理を行わない等の対応が必要になります。

さて線と線が交差することはわかりましたが、まだ衝突が確定したわけではありません。
なぜなら上の判定はベクトルと"線"の交差を判定したにすぎないからです。
例えば下図のベクトルたちはすべて「交差」していると判定されます。
上と下は明らかに当たってないですよね？

実際には左辺は"線"ではなく「線分」ですので、y座標方向の点の座標がAABBの
y1からy2の間にあるかどうかを確認する必要があります。

t=t0のときに交差したとすると、衝突するためには衝突点のｙ座標は

P1 = (P0.x + t0 * rv.x,  P0.y + t0 * rv.y)

より

y1 <= P0.y + t0 * rv.y <= y2

の範囲にあれば衝突ということになります。

さて、上で述べてきたことは左辺についてのみですが、
右辺もまったく同じように計算してもらえればよいです。
AABBのx座標が違うだけですね。

ただし、AABBは軸に平行なので、rv.xが正か負かによって、左右どちらか一方だけ判定すればいいです。
下図の(1)ならば左辺だけテストすればいいですし、(2)の場合は右辺だけテストすれば良いでしょう。
すでに点がAABBの中にある場合を除いて、外側からの衝突において点が相対速度で右に進んでいるのに
AABBの右辺に当たることはないですよね？
またrvが0のときは衝突無しとすればよいでしょう。

さて、これをプログラムにしてみます。すごく単純です。

bool testDotAABB( const POINT& P0, const D3DXVECTOR2& v,  // 点の情報
                         const RECT& rcAABB, const D3DXVECTOR2& v1 )  // AABBの情報
{
  D3DXVECTOR2 rv = v - v1;  // 相対速度を出す

  if ( rv.x != 0 )
  {
    FLOAT fLineX = (rv.x > 0) ? rcAABB.left : rcAABB.right;
    FLOAT t = fLineX - (P0.x + rv.x) / rv.x;

    if ( (t >= 0) && (t <= 1.0f) )
    {
      // 衝突点(ｙ方向)がAABBの線分に収まっていれば衝突
      FLOAT hitY = P0.y + t * rv.y;
      if ( (hitY >= rcAABB.bottom) && (hitY <= rcAABB.top) )
      {
        return true;
      }
    }
  }

  if ( rv.y != 0 )
  {
    FLOAT fLineY = (rv.y > 0) ? rcAABB.bottom : rcAABB.top;
    FLOAT t = fLineY - (P0.y + rv.y) / rv.y;

    if ( (t >= 0) && (t <= 1.0f) )
    {
      // 衝突点(x方向)がAABBの線分に収まっていれば衝突
      FLOAT hitX = P0.x + t * rv.x;
      if ( (hitX >= rcAABB.left) && (hitX <= rcAABB.right) )
      {
        return true;
      }
    }
  }

  return false;
}

AABBとAABBの衝突

今度は点ではなくAABB同士の衝突なのですが、実はこれ、理屈は点とAABBと変わりません。

今度はお互いがサイズを持っているのでめんどくさそうです。
たしか速度のときも、お互いが動いているのはめんどくさいから片方を止めて相対速度で計算をしましたよね？

今回も考え方の発想としてはそれと同じで、片方のAABBを小さくして点にしてしまいます。
その代わり、もう片方のAABBは小さくした分大きさを加算すればよいです。

これで、点とAABBの関係に落とすことができました！
あとは、上で説明したプログラムをちょいちょいと改造すればよさそうですね。

bool testDotAABB( const RECT& rcAABB1, const D3DXVECTOR2& v,     // obj1の情報
                         const RECT& rcAABB2, const D3DXVECTOR2& v1 )  // obj2の情報
{
  D3DXVECTOR2 rv = v - v1;  // 相対速度を出す

  // obj1を点として扱い、obj2を拡張する
  POINT P0 = { rcAABB1.left, rcAABB1.bottom };
  RECT exAABB2 = { rcAABB2.left - (rcAABB1.right - rcAABB1.left),            // 左
                            rcAABB2.top,      // 上
                            rcAABB2.right,    // 右
                            rcAABB2.bottom - (rcAABB1.top - rcAABB1.bottom) };  // 下
  if ( rv.x != 0 )
  {
    FLOAT fLineX = (rv.x > 0) ? exAABB2.left : exAABB2.right;
    FLOAT t = fLineX - (P0.x + rv.x) / rv.x;

    if ( (t >= 0) && (t <= 1.0f) )
    {
      // 衝突点(ｙ方向)がAABBの線分に収まっていれば衝突
      FLOAT hitY = P0.y + t * rv.y;
      if ( (hitY >= exAABB2.bottom) && (hitY <= exAABB2.top) )
      {
        return true;
      }
    }
  }

  if ( rv.y != 0 )
  {
    FLOAT fLineY = (rv.y > 0) ? exAABB2.bottom : exAABB2.top;
    FLOAT t = fLineY - (P0.y + rv.y) / rv.y;

    if ( (t >= 0) && (t <= 1.0f) )
    {
      // 衝突点(x方向)がAABBの線分に収まっていれば衝突
      FLOAT hitX = P0.x + t * rv.x;
      if ( (hitX >= exAABB2.left) && (hitX <= exAABB2.right) )
      {
        return true;
      }
    }
  }

  return false;
}

まとめ

今回はAABB同士の衝突判定を見てきましたがポイントは

  • 相対速度で片方を静止させる
  • 点と線の関係に持ち込んで考える

より、単純な問題に置き換える、これが重要です。

注意

ソースコードは十分な動作確認をしていませんのでご注意ください。

プライバシーポリシー お問い合わせ