高速な当たり判定を実装してみる

駄文 Ruby

Cによる当たり判定の実装にどれだけの効果があるのか検証してみよう。


まず、32*32サイズの画像50個ほどを画面内で動かすプログラムを作る。
こいつらを全て判定するとしよう。
単純に考えて50*50で2500回の判定が発生する。
同じものを2回判定する必要は無いし、自分同士を判定する必要もないが、ここでは判定の速度差を検証するだけだから気にしない。
サンプルシューティングのCollisionモジュールを引っこ抜いてきて、判定させてみる。
判定の中心になるコードはこんな感じだ。

if o.x1 <= d.x2 and d.x1 <= o.x2 and
   o.y1 <= d.y2 and d.y1 <= o.y2 then

オブジェクトにはx1,y1,x2,y2という判定範囲を取得するためのメソッドが定義してある。
HPCモジュールで実行時間を測るとだいたい17.1msと出て、判定だけで60fpsでの1フレームの時間をオーバーしていることがわかる。
言い忘れたがここで使っているのはRuby1.8.7だ。


この比較をCで書き直してみる。

if Window.hit?(o.x1, o.y1, o.x2, o.y2, d.x1, d.y1, d.x2, d.y2) then

Windowモジュールに入っているのは新しいモジュールを作るのが面倒だったからで、とくに意味は無い。
これで実行すると26msほどとなって、逆に遅くなってしまった。
比較処理よりも、メソッド呼び出しの方がずっと遅いということだ。


Rubyでは、attrを定義するとsetとgetが定義されるという説明がされるが、自分でメソッドを作ってしまうと、メソッド名とインスタンス変数の2重検索が行われることになる。
attr定義はメソッド名とインスタンス名が一致していることが確定していて、検索が省かれるので、自分でメソッドを作るより高速になる。
初めのロジックに戻してx1などをattr定義に変えてHPCモジュールで測ると10.5msとなった。
下手にCで書くよりも、Ruby側の無駄を省くほうが重要ということだ。


オブジェクトの配列を渡すのではなくて、[x1, y1, x2, y2, self, delflag]という配列をオブジェクトごとに作って、当たり判定配列にpushしまくるようにしてみた。
selfはhitとshotを呼ぶためで、delflagはその結果としてオブジェクトが消えたことを表す。
これを、Rubyで処理するようにしたら、10.3msとなった。ほぼ誤差範囲。
メソッドの検索回数が同じだからだろう。
なぜこのような作りにしたのかというと、このあとで全てをCによる処理に書き換えるためだ。
Cで処理する場合にメソッド検索をしていては意味がないから、ポインタ参照できるように配列にした。
Rubyではどっちにしてもメソッド検索するから変わらないが、Cにとっては大違いのはずだ。


ということで、Collisionモジュールの処理全体をCで書き直してみて実行してみた。
結果は50個*50個=2500回の比較で0.2ms。
本当にチェックできてるんかこれ？
と思って確認したが、どうやらちゃんとできているようだ。
思わず我が目を疑うほどの凄まじい速度である。
ちなみにCのコードはこんな感じ。

/*--------------------------------------------------------------------
   実験的な当たり判定メソッド
 ---------------------------------------------------------------------*/
static VALUE Window_hitcheck( VALUE obj, VALUE a1, VALUE a2 )
{
    int i, j;

    Check_Type(a1, T_ARRAY);
    Check_Type(a2, T_ARRAY);

    for( i = 0; i < RARRAY(a1)->len; i++ )
    {
        VALUE a1_data = RARRAY(a1)->ptr[i];

        if( RARRAY(a1_data)->ptr[5] == Qtrue ) continue;

        for( j = 0; j < RARRAY(a2)->len; j++ )
        {
            VALUE a2_data = RARRAY(a2)->ptr[j];

            if( RARRAY(a2_data)->ptr[5] == Qtrue ) continue;

            if( NUM2INT( RARRAY(a1_data)->ptr[0] ) <= NUM2INT( RARRAY(a2_data)->ptr[2] ) &&
                NUM2INT( RARRAY(a2_data)->ptr[0] ) <= NUM2INT( RARRAY(a1_data)->ptr[2] ) &&
                NUM2INT( RARRAY(a1_data)->ptr[1] ) <= NUM2INT( RARRAY(a2_data)->ptr[3] ) &&
                NUM2INT( RARRAY(a2_data)->ptr[1] ) <= NUM2INT( RARRAY(a1_data)->ptr[3] ))
            {
                rb_funcall(RARRAY(a1_data)->ptr[4], rb_intern("shot"), 1, a2_data);
                rb_funcall(RARRAY(a2_data)->ptr[4], rb_intern("hit"), 1, a1_data);
            }

            if( RARRAY(a1_data)->ptr[5] == Qtrue ) break;
        }
    }
}

シューティングゲームでは、敵の弾と自分、自分の弾と敵などの比較となり、同じオブジェクト配列を比較することはないが、ゲームによってはそういう判定をすることもある。
色んな用途で使える色んなパターンの判定ロジックを、Cで提供することができれば、さすがにこれだけ速いのなら需要はあるのではなかろうか。


ていうか、しみじみとRubyの遅さとCの速さを実感してしまった。
Ruby1.9.1ならここまでの差にはならないと思うが、速いといってもせいぜい数倍のオーダーだろう。
実行性能と生産性という意味で言えば、Rubyを使う部分とCを使う部分を切り分けていくのが良いが、普通のRubyユーザーは自分で拡張ライブラリを書いたりしないから、定型処理を抜き出してCで提供していくのは、この結果を見ればかなりアリだと言わざるを得ない。


っていうか、サンプルシューティングでこれ使ったらかなり派手にできそうだなー・・・