2010年11月4日木曜日

当たり判定高速化

ゲームと言えば当たり判定なので、ここを最大限スリムにしておくに越したことはないはず。

作りたいゲームにもよるけど、基本は矩形(四角と四角)で良いと思う。 ゲームによっては円と円にするけども。

まぁ、矩形で考えて、(x1,y1)-(x2,y2)の四角と(x3,y3)-(x4,y4)の四角で当たり判定するとして普通に作ると

boolean hitCheck(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4){

    if(x4 < x1)return false;

    if(y4 < y1)return false;

    if(x3 > x2)return false;

    if(y3 > y2)return false;

    return true;

}

という感じ。
書いてて思ったけど、intを8個引数で渡すのってどうなんだ。 int(4Byte)*8=32Byte? うーん?
ゲームの座標で4Byteも必要ないからshortでいいのか。
もしくは

class Rect{
    public int x1,y1,x2,y2; 
}

ってクラスを作って、参照渡ししたほうがいいのか。

まぁ、それはさておき、高速化の基本はif文を除く事だと思うので、最適化をしまくっていくと

boolean hitCheck(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4){
    final boolean boolean_c[] = {false,true}; 
    return  boolean_c[((x1-x4) & (x3-x2) & (y1-y4) & (y3-y2)) >>> 31];
}

と、if文を削れるところまで行ける。
んじゃぁ、実際これが速いのかどうなのか。 実際にランダム座標で100,000回処理のタイムを測ってみると

 ~1回目~
最適化前:45,111ms
最適化後:45,246ms

~2回目~
最適化前:45,197ms
最適化後:45,944m


あるぇ~~~。
最適化したほうが遅い!!! うっはーー!!!

これは座標にもよるけど、全てのものが重なってるってことはほとんど無いはずなので、if文方式は途中であたってない事が確定してfalseが返って、あとの処理がスキップされることによる結果だと思う。

ええ、じゃぁ、if文方式でいいってことですか。

ちなみにint4つ渡すオーバーヘッドを減らすべく、クラスで参照渡し方式にしてみたら

参照渡し方式:44,800ms

あ、若干マシ・・・。
と、いうわけで、最終的に

     class HitRect{
        public int x1,y1,x2,y2;
    }

を使って、

   public static boolean hitCheck(HitRect a,HitRect b) {
        if (b.x2 < a.x1)return false;
        if (b.y2 < a.y1)return false;
        if (b.x1 > a.x2)return false;
        if (b.y1 > a.y2)return false;
        return true;
    }

が最速でFA???

まぁ、 100,000回実行なので、実際には目に分かるような差はないんだけども。

目指せ25ドル!

0 件のコメント:

コメントを投稿