sweep and prune実装

なんか拍子抜けするぐらい簡単だった。確かに総当たりよりは高速化していると思うけど、これで当ってるのかなぁ・・・。
コードは疑似コードっぽいC++コードで、座標値的にはup > downな世界(Y軸の向きが画面上方を向いている場合)です。

  typedef CollideTargets::iterator Iterator;
  for (Iterator p = collideList_.begin(), pend = collideList_.end(); p != pend - 1; ++p) {
    // 衝突している場合は除く
    if (p->isCollide())
       continue;

    double p_right    = p->right();
    double p_up       = p->up();
    double p_down     = p->down();

    for (Iterator q = p + 1; q != pend; ++q) {
      // 既に衝突している場合は除く
      if (q->isCollide()) 
        continue;

      // pの矩形の右端よりも、qの矩形の左側がより右だった場合は
      // この後のオブジェクトは衝突のしようがないので、次の衝突判定へ
      // (ここがsweep & pruneの肝?)
      if (p_right <= q->left()) 
        break;

      // BBOXの交差判定
      // (既にX軸では交差しているのでY軸のみチェックする)
      if (p_down >= q->up() || q->down() >= p_up) 
        continue;

      bool result;

      /** 正確な衝突判定 **/

      // 実際に衝突していた場合には後の衝突判定は中止
      if (result)
      {
        p->collide();
        q->collide();
        break;
      }
    }
  } 

案の定というのか、それみたことかというのか、やっぱり30程度のオブジェクトでは全然目に見えた高速化はしなかったとさ。
まあ、今後の衝突判定のコスト増のリスクを抑えられたので、これはこれで良いとしましょう。
ちょっとだけコードを整形しておかないと絶対後で分からないだろうな。

その次はアイテム処理だな。状態を持つ主体が沢山いるのでいろいろ面倒くさそうだ。