当たり判定

　基本的な矩形の交差判定についてちょっと書いてみます。
とりあえず二つの矩形は次のようにして交差判定できます。

(Rect1.Left<=Rect2.Right)and
(Rect1.Top<=Rect2.Bottom)and
(Rect1.Right>=Rect2.Left)and
(Rect1.Bottom>=Rect2.Top)

この場合ではこれが最良だと思います。
次に、n個の場合はどうするかということを考えてみようと思います。

とりあえず、総当たりで調べてみます。
ソースコードata1.lzh(2.31kbyte) 
     for i:=0 to num-1 do
        begin
        for j:=i+1 to num-1 do
          begin
          if (Rts[i].Rec.Left<=Rts[j].Rec.Right)and
             (Rts[i].Rec.Top<=Rts[j].Rec.Bottom)and
             (Rts[i].Rec.Right>=Rts[j].Rec.Left)and
             (Rts[i].Rec.Bottom>=Rts[j].Rec.Top) then
            begin
            Rts[i].Col:=$000000ff;
            Rts[j].Col:=$000000ff;
            end;
          end;
        end;

//
500個の矩形判定に20msほど。
1000個の矩形判定に110msほど。
3000個の矩形判定に1000msほど。
まあ、私のMachineでは100個ぐらいなら3msもかからないようなので
大概の2Dスクロール型のシューティングはこれで十分です。
（とくに敵同士の当たり判定をしないとかすればもっと速くなります。）



次は、クイックソートを使った当たり判定です。
手順：
１．矩形のLeftの値でクイックソートする。
２．ソートされた順番に次の処理を行っていく。
　・リストに当たり判定を調べる矩形を加える。
　・リストにある矩形を順に調べていく
　　　(1)　リストからとってきた矩形の右端が今調べている矩形の左端より左の場合は
　　　　　リストからはずす
　　　(2)　リストからはずさなかった場合は交差判定を行う
これにより計算量は平均的にO(n*log(n))になるといわれています。
もちろん矩形が全部同じxで並んでいたらO(n^2)になってしまいますが。

ソースコードata2.lzh(2.75kbyte) 
      QSort(idx,0,num-1);
      idx[0].Next:=nil;
      Lst:=idx[0];
      for i:=1 to num-1 do
        begin
        idx[i].Next:=Lst;
        Lst:=idx[i];


        ltm:=Lst;

        while ltm.Next<>nil do
          begin
          if  ltm.Next.Rec.Right < Lst.Rec.Left-3 then
            begin
            ltm.Next:=ltm.Next.Next;
            continue;
            end;

          if (ltm.Next.Rec.Right >= Lst.Rec.Left)and
             (Lst.Rec.Right >= ltm.Next.Rec.Left)and
             (ltm.Next.Rec.Bottom >= Lst.Rec.Top)and
             (Lst.Rec.Bottom >= ltm.Next.Rec.Top) then
　　　　　　　　　　//うまくやるとXの判定はいらなくなるが
 　　　　　　　　　 //ここでは念のため入れている
            begin
            ltm.Next.Col:=$000000ff;
            Lst.Col:=$000000ff;
            end;


          ltm:=ltm.Next;
          end;

        end;

//
500個の矩形判定に4msほど。
1000個の矩形判定に7msほど。
3000個の矩形判定に96msほど。

3000個でいきなり遅くなっているような気もしますが
これは多分縦の重なりが増えてきたのが関係しているのだと思います。


最後に、空間を桝目に分割して、それぞれの桝目ごとに
その桝目にかかっている矩形のリストを作るという方法を紹介します
１．矩形の範囲からその矩形を含んでいる桝目のリストに、そのリストを加える。
２．桝目のリスト毎で通常の当たり判定の計算を行う。
ソースコードata3.lzh(2.75kbyte) 
      for i:=-2 to 65 do
        begin
        for j:=-2 to 65 do
          begin
          Hash[i,j]:=nil;
          end;
        end;

      ct:=0;

      for i:=0 to num-1 do
        begin
        ra:=Rts[i].Rec.Right div(512 div 64);//桝目の大きさで割っています。
        ba:=Rts[i].Rec.Bottom div(384 div 64);
        ta:=Rts[i].Rec.Top div(384 div 64);
        la:=Rts[i].Rec.Left div(512 div 64);

        for j:=ta to ba do
          begin
          for k:=la to ra do
            begin
            Nodes[ct].rt:=@Rts[i];
            Nodes[ct].Next:=Hash[j,k];
            Hash[j,k]:=@Nodes[ct];
            inc(ct);
            end;
          end;
        end;

      for i:=-2 to 65 do
        begin
        for j:=-2 to 65 do
          begin
          tmp:=Hash[i,j];
          while tmp<>nil do
            begin
            tmp2:=tmp.Next;
            while tmp2<>nil do
              begin
              if (tmp.rt.Rec.Left<=tmp2.rt.Rec.Right)and
                 (tmp.rt.Rec.Top<=tmp2.rt.Rec.Bottom)and
                 (tmp.rt.Rec.Right>=tmp2.rt.Rec.Left)and
                 (tmp.rt.Rec.Bottom>=tmp2.rt.Rec.Top) then
                begin
                tmp.rt.Col:=$000000ff;
                tmp2.rt.Col:=$000000ff;
                //Rts[i].Col:=0;
                //Rts[j].Col:=0;
                end;
              tmp2:=tmp2.Next;
              end;
            tmp:=tmp.Next;
            end;
          end;
        end;

//
500個の矩形判定に10msほど。
1000個の矩形判定に10msほど。
3000個の矩形判定に45msほど。
3000個では最速ですが、少ない数では案外遅いです。
わざわざ、毎回リストを初期化し直しているのと
めぐる必要の無い桝目まで調べていたりする関係だとおもいます。

クイックソートでも桝目分割するのでも
工夫するとソートとか桝目に振り分ける作業は
前回のものを一部（条件によっては大部分）再利用する事ができます。
また、動いたものに関してのみ当たり判定の計算をするという方法もあります。

・ソースコードの著作権など
　ソースコードは自由に使ってください。



上へ
目次

GigaHit