衝突判定の外側

DXRuby 駄文

Spriteの衝突判定では、まず全オブジェクトのAABBボリュームを計算して保存し、それを判定する。AABBの算出はそれなりに負荷がかかるから、これを保存するのは効率的に必要な処理だ。Spriteは複数の衝突判定範囲を持つことができるから、SpriteのAABBを算出するにはそれらすべての座標を回転・スケーリングして比較し、全体を囲う矩形を作ることになる。また、詳細の判定をする際にはそれら個々のAABBを比較してからの判定になる。従って、個々の範囲であるCollision構造体と、まとめたものであるCollisionGroup構造体は、それぞれ別にAABBボリュームを持っている、ということになる。これらを生成するところまでが前処理だ。
本処理ではCollisionGroupレベルでAABB判定を行い、それが当たっていたらCollision単位のAABB判定をして、更に当たっていたら詳細判定をする。なぜそこまでするのかというと、本判定の負荷が非常に高いからだ。回転してない矩形同士とかなら簡単なのだが(AABBだけだし)、回転していたり、円と矩形だったり、三角形と矩形だったりするとその判定処理はかなりの負荷となる。それがたくさんあったりすると、ある程度の枝狩りをしないと話にならない。
DXRubyExと比較して判定が複雑になっているのに速度がほぼ変わらないのは、そういう地味な努力の賜物なのだ。って言ってもそれなりの規模の処理であればみんな当たり前にやってるようなことなんだろうとは思う。

今回はCollisionの構造について。


とりあえずCollisionGroupから。

struct DXRubyCollisionGroup
{
    int index;
    VALUE vsprite;
    int count;
    int x1, y1, x2, y2; /* AABBボリューム */
};

vspriteはSpriteオブジェクトだ。ここに設定されている衝突判定範囲の全体を表すAABBボリュームがx1/y1/x2/y2で、indexとcountはCollision配列の位置と数を表す。衝突判定範囲1個を1つのCollision構造体で表していて、それの配列という形でCollisionGroupを表すわけだが、この配列はまとめて取ったメモリを全CollisionGroupで共有しているから、どの場所からどんだけ、という情報で自分配下のCollision構造体を表現している。CollisionGroupごとに専用のメモリを割り当てようとすると大量のmalloc/freeが必要になるから、速度的な理由でそれを避けた。
次にCollision構造体。

struct DXRubyCollision
{
    /* 衝突判定用 */
    int x1, y1, x2, y2; /* AABBボリューム */
    VALUE vsprite;
    float bx1, by1, bx2, by2; /* 回転前・相対座標での矩形判定範囲（省略時もここに設定する） */
    float angle, base_x, base_y, scale_x, scale_y, center_x, center_y;
    int rotation_flg, scaling_flg;
    VALUE vcollision;
};

Spriteオブジェクトに複数の衝突判定を設定した場合には、その数だけCollision情報が作成される。bx1/by1/bx2/by2は矩形の場合にのみ使われる情報で、通常Sprite#collision=で設定された値が入るが、省略することができるという仕様だから、省略された場合はSprite#image=で設定された画像データから値を引っ張ってきてここに設定する。この情報を持っていないと衝突判定のタイミングでimageを見に行くという非効率な処理が必要になる。あと、なんちゃらflgというのは回転しているか、スケーリングしているかを表している。vcollisionはSprite#collision=に設定されたオブジェクトで、通常はArrayオブジェクトとなる。判定処理のほうは矩形の場合はbx1/by1/bx2/by2を使って、矩形以外はvcollisionを参照するような感じになる。

しかし、まあ、なんだ。collision.cを眺めていて、これをここに貼り付けて説明できる気がまったくしない。ちょっとやばい。
外堀から埋める努力をしてみようか。とりあえずsprite.c側のSprite#checkの関数を。Sprite#checkとSprite#===の違いは衝突した対象を返すかどうかだけである。Sprite.checkのほうはでかくてややこしいのであとで考える。

/*--------------------------------------------------------------------
   単体と配列の判定
 ---------------------------------------------------------------------*/
static VALUE Sprite_hitcheck( VALUE self, VALUE vsprite )
{
    VALUE o, d;
    int i;
    struct DXRubyCollisionGroup collision1;
    struct DXRubyCollisionGroup *collision2;
    int o_total, d_total;
    VALUE ary;
    int ary_count = 0;

    /* 単体指定の場合はとりあえず配列に突っ込む */
    if( TYPE(vsprite) != T_ARRAY )
    {
        d = rb_ary_new3( 1, vsprite );
    }
    else
    {
        d = vsprite;
    }

    o = rb_ary_new3( 1, self );

    /* AABBボリューム計算 */
    o_total = make_volume( o, &collision1 );
    collision2 = (struct DXRubyCollisionGroup *)malloc( RARRAY_LEN(d) * sizeof(struct DXRubyCollisionGroup) );
    d_total = make_volume( d, collision2 );

    /* 衝突お知らせ対象 */
    ary = rb_ary_new();

    /* 防御側オブジェクトのループ */
    for( i = 0; i < d_total; i++ )
    {
        /* 判定 */
        if( check_box_box( &collision1, collision2 + i ) && check( &collision1, collision2 + i ) )
        {
            rb_ary_push( ary, (collision2 + i)->vsprite );
            ary_count += 1;
        }
    }

    free( collision2 );
    collision_clear();

    return ary;
}

DXRubyCollisionGroupの変数だが、単体と配列のチェックなので、selfのほうは直接定義していて、配列側は数は不定だからmallocで確保するためにポインタとなっている。単体と配列と言っているが、配列じゃなくて直接Spriteオブジェクトが設定されていても勝手に配列に突っ込むことで動作するようにしてある。また、AABBボリュームを作るmake_volume関数は配列を引数にとる作りにしちゃったので、selfも結局配列に突っ込む。こうしてみるとあまり効率はよろしくないが、衝突判定の処理全体から見るとたいした問題ではない。逆に1対1の衝突判定は思いのほか遅く、Sprite#===を大量に発行するような処理は苦手だ。
変数名はcollision1なのに型はCollisionGroupである。これは直したほうがいいような気がする。とりあえず、まあ、make_volume関数は第1引数で渡した配列のAABBボリュームを求めて、第2引数で渡したCollisionGroupのメモリに保存する。個別のCollisionについては内部で生成して設定するが、このレベルには出てこない。
んで、ここでcheck_box_boxというマクロ(これマクロなんです)を使ってAABB判定をして、当たっていたらcheck関数で詳細判定に行く。ary_countという変数はたぶんいらない。ゴミだろう。
check_box_boxはこのようなマクロになっている。

#define check_box_box(b1, b2) ( (b1)->x1 < (b2)->x2 && \
                                (b1)->y1 < (b2)->y2 && \
                                (b2)->x1 < (b1)->x2 && \
                                (b2)->y1 < (b1)->y2 )

普通に矩形同士の衝突判定だ。
改めて見ると細かいところで非効率が目立つが、それはこの衝突判定ロジックが新規で書かれたものだからというのと、徹底的に高速化するほどの理由がいまのところ見当たらないからである。これを書いたのが5年前ならかなり気合を入れて取り組んだだろうが、いまやそこまでする時代でもない。現状で必要十分だろう。