【HTML&CSSではじめるミニゲーム作成】高速なアルゴリズムで接触してるスプライトを検索する

オリジナルの原典的なサイトは

こちら

から読めますが、解説の内容がかなり難しいですし、C++ベースの実装を念頭におかれているので、メモリやポインタ等のより機械言語的な知識が必要です。
幸いなことに、この原典の難解そうな内容を極めて分かりやすく解説されている記事がありました。

参考｜超高速2D当たり判定プログラムを作りたかった

ここを読んでいただくと、

「四分木法」

のアルゴリズムの原理はバッチリだと思います。
この記事では、そちらの参考先で説明してあるアルゴリズムをJavascriptで実装してHTMLゲームでも利用するまでを評価することを目指します。

【Html&Cssアプリ】Html/JavascriptとSassを使った四択クイズゲームの作り方

四分木分割空間上のスプライトのモートン番号の求め方

まずは対象となるスプライトが、「四分木分割空間」上のどこに位置しているかを識別する

「モートン番号」

を求めてみるところから話を始めていきましょう。

四分木分割空間について

四分木分割空間とは、2次元空間を

4^L

(

L

は階層数)に等分割し、分割した空間に対して

「モートン順序」

によって識別番号を割り当てた離散空間になります。
例えば、空間の４分割を3回行う(

L = 3

)とすれば、

4^3 = 64

個の正方形領域に分割することになり、その領域の識別番号

0〜63

を「モートン順序」のルールで割り当ててみると、以下のようになります。

この各領域に割り振られた識別番号が、

「モートン番号」

と呼ばれているものです。
対して、

「モートン座標」

とは、モートン分割で作った表上で

(列番号,行番号)

により位置を表している座標のことを指しています。
先ほどの表で言うと、例えば

モートン座標(6,3) --> モートン番号(30)

、となります。
原典のサイトでは、モートン番号が16bit仕様を念頭に実装されているので、こちらの記事も最初から16bit整数でビット演算を行います。
モートン座標からモートン番号への変換則として、

開く/閉じる

            1. モートン座標の各値と、それを8ビット左シフトした値とのOR値を求める
2. 前項1の値と、マスク値0x00ff00ffとのAND値を求める
3. 前項2の値と、それを4ビット左シフトした値とのOR値を求める
4. 前項3の値と、マスク値0x0f0f0f0fとのAND値を求める
5. 前項4の値と、それを2ビット左シフトした値とのOR値を求める
6. 前項5の値と、マスク値0x33333333とのAND値を求める
7. 前項6の値と、それを1ビット左シフトした値とのOR値を求める
8. 前項7の値と、マスク値0x55555555とのAND値を求める
9. 前項1~8までの手順で、モートン座標のX(列番号)に対して演算を行う
10. 前項1~8までの手順で、モートン座標のY(行番号)に対して演算を行う
11. 前項10で求めた値については更に1ビット左シフトをする
12. 前項9で求めた値に、前項11で求めた値とのOR値を求める

という幾つかのビット演算を順番に行います。
このロジックをJavascriptで実装すると以下のようになるでしょう。

開く/閉じる

            //クリックしたときのキャンバス中のクライアント座標
const _x = e.x;
const _y = e.y;

//クライアント座標 --> モートン座標
const _mx = Math.floor(_x/<正方形領域の幅>);
const _my = Math.floor(_y/<正方形領域の幅>);

//モートン座標のX軸側を変換
let _mx_op = _mx | (_mx << 8);
_mx_op = _mx_op & 0x00ff00ff;
_mx_op = _mx_op | (_mx_op << 4);
_mx_op = _mx_op & 0x0f0f0f0f;
_mx_op = _mx_op | (_mx_op << 2);
_mx_op = _mx_op & 0x33333333;
_mx_op = _mx_op | (_mx_op << 1);
_mx_op = _mx_op & 0x55555555;

//モートン座標のY軸側を変換
let _my_op = _my | (_my << 8);
_my_op = _my_op & 0x00ff00ff;
_my_op = _my_op | (_my_op << 4);
_my_op = _my_op & 0x0f0f0f0f;
_my_op = _my_op | (_my_op << 2);
_my_op = _my_op & 0x33333333;
_my_op = _my_op | (_my_op << 1);
_my_op = _my_op & 0x55555555;

//モートン番号
const _mnum = _mx_op | (_my_op << 1);

実際にクリックした位置の座標から、モートン座標を割り出し、モートン番号の算出を試してみたら、以下のようなHTMLアプリでモートン番号を確認することができます。

【Html&Cssアプリ】Html/JavascriptとSassを使った四択クイズゲームの作り方

スプライトの所属空間番号(分割階層の深さ)を求める

先程はモートン座標点から、モートン番号を算出するまでのロジックを実装しましたが、実際のスプライトは「点」としては扱えず、縦横にサイズがあるために複数の分割領域をまたぐ場合も出てきます。
そうなると、1つのスプライトはモートン番号を何個も持つことになってしまいます。
考え方の原則として、

「１つのスプライトに対して、1つのモートン番号」

を割り振るためには、対象のスプライト全体を包み込むことのできる四分木分割領域を見つける必要があります。
スプライトをすっぽり覆えるような分割階層(所属空間)を決定し、「どの"分割階層"に属するモートン番号か」を割り出すための実装を考えてみましょう。

所属空間(右シフト数)の算出方法

所属空間を見つけるには、スプライトの左上と右下のモートン番号の排他的論理和(XOR)の結果を、右から2ビットずつ評価していきます。
右2ビットシフトを繰り返しながら、下位2ビットの値が0ならスキップ、0以外ならその累積シフト数を採用し、ルート階層になるまでを繰り返します。
なお、「ルート階層までシフト」するとは、モートン番号を

2*L

だけ右シフトさせるという意味です。
今回は分割階層数

L=3

までの四分木分割でしたので、各階層のモートン番号を求めるのに必要な右シフト数は以下の通りです。

開く/閉じる

            L=0 ... ルート階層 --> 右シフト数6
L=1 ... 親階層 --> 右シフト数4
L=2 ... 子階層 --> 右シフト数2
L=3 ... 孫階層 --> 右シフト数0

見ての通り、右シフト数を求めることと、所属空間を求めることは同意義になります。
つまり、右シフト数から所属空間(分割階層数)への変換は

L - (右シフト数)/2

です。
また、この右シフト数に従って、スプライトの左上か右下の座標のモートン番号を右シフトさせることで、所属空間上のモートン番号が１つに決定されます。

JSスクリプトで右シフト数を算出する実装

先程説明したアルゴリズムをそのままjsコードで実装すると以下のようになるでしょう。

開く/閉じる

            let _xor = <左上のモートン番号> ^ <右下のモートン番号>;
let _shift = 0;
const L = 3;
for (let i=0;i<=L;i++) {
    //👇1,2ビット目だけを抽出
    const _tst = _xor & 0x00000003;

    //👇0でなければ右シフト数を更新
    if (_tst > 0) {_shift += 2;}

    //次の階層数を評価するために2ビット右シフト
    if (i < L) {_xor = _xor >> 2;}
}

//👇所属空間のモートン番号
const _mnum = <左上のモートン番号> >> _shift;

これをHTMLアプリに組み込むことで、以下のようになります。
キーボードの矢印キーからスプライトを動作させて、右シフト数が算出されるのを確認してみてください。
※以下のゲームを動かす場合、キーボード入力が受け付けないときは

ゲーム画面枠内を一度クリック

してみてください。

これで所属階層やモートン番号の重なり具合を見ながら、スプライト同士のより細かな衝突判定を行っていくことができます。

【Html&Cssアプリ】Html/JavascriptとSassを使った四択クイズゲームの作り方

まとめ

今回は四分木分割法によるモートン番号を活用した高速な衝突判定法の基礎をJavascriptベースのコードに落とし込むまでを解説してみました。
この方法を実践的に扱うには、もう一つ

「線形四分木配列を使った衝突オブジェクトの検索」

のテクニックを理解されたほうがよいでしょう。
そちらのほうは実装も兼ねて、また今後別の機会に説明していきたいと思います。