# 【HTML&CSSではじめるミニゲーム作成】高速なアルゴリズムで接触してるスプライトを検索する |p2>2023/12/31{3}「四分木法」{1}「モートン番号」{3}「モートン順序」 body { display: block; width: 100%; margin: 0; padding: 0; } #game-stage-1__art110 { display: block; position: relative; width: 480px; height: 480px; padding: 0; margin: 0; pointer-events: none; } p.morton-block { position: absolute; background: aqua; padding: 0; margin: 0; width: 60px; height: 60px; display: flex; justify-content: center; align-items: center; border: 1px solid; } p.morton-block::before { font-size: 15px; content: attr(data-order); } #console-area-1__art110 { display: block; position: absolute; width: 480px; height: 20px; top: 480px; padding: 0; margin: 40px auto 0; } #game-status-1__art110 { width: 100%; font-size: 1.1rem; background: #f5b560; pointer-events: none; border: navajowhite; outline: none; }

@@@% この各領域に割り振られた識別番号が、|px>{1}「モートン番号」{1}「モートン座標」モートン番号(30)`、となります。原典のサイトでは、モートン番号が16bit仕様を念頭に実装されているので、こちらの記事も最初から16bit整数でビット演算を行います。モートン座標からモートン番号への変換則として、 ```text モートン座標からモートン番号への変換 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で実装すると以下のようになるでしょう。 ```js //クリックしたときのキャンバス中のクライアント座標 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アプリでモートン番号を確認することができます。 @@@css2%[2.html]{640px}{680px}

@@@% - - - ## スプライトの所属空間番号(分割階層の深さ)を求める先程はモートン座標点から、モートン番号を算出するまでのロジックを実装しましたが、実際のスプライトは「点」としては扱えず、縦横にサイズがあるために複数の分割領域をまたぐ場合も出てきます。そうなると、1つのスプライトはモートン番号を何個も持つことになってしまいます。考え方の原則として、|px>{2}「１つのスプライトに対して、1つのモートン番号」右シフト数6 L=1 ... 親階層 --> 右シフト数4 L=2 ... 子階層 --> 右シフト数2 L=3 ... 孫階層 --> 右シフト数0 ``` 見ての通り、右シフト数を求めることと、所属空間を求めることは同意義になります。つまり、右シフト数から所属空間(分割階層数)への変換は`L - (右シフト数)/2`です。また、この右シフト数に従って、スプライトの左上か右下の座標のモートン番号を右シフトさせることで、所属空間上のモートン番号が１つに決定されます。 ### JSスクリプトで右シフト数を算出する実装先程説明したアルゴリズムをそのまま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アプリに組み込むことで、以下のようになります。キーボードの矢印キーからスプライトを動作させて、右シフト数が算出されるのを確認してみてください。 ※以下のゲームを動かす場合、キーボード入力が受け付けないときは|px>{3}ゲーム画面枠内を一度クリック body { display: block; width: 100%; margin: 0; padding: 0; } #game-stage-3__art110 { display: block; position: relative; width: 480px; height: 480px; padding: 0; margin: 0; pointer-events: none; --x-pos: 20px; --y-pos: 0px; } #taco-3-screen__art110 { display: block; position: absolute; background: #ff6a109c; padding: 0 0 0 0; top: var(--y-pos); left: var(--x-pos); width: 50px; height: 50px; z-index: 1; } #taco-3__art110 { display: block; width: 100%; height: 100%; background: transparent url('https://raw.githubusercontent.com/tacoskingdom/commonBlogMaterial/main/tacokin-p-school/blog109/character_juken_tako_okuto_pass.svg') no-repeat 0 0; background-size: 50px 50px; } p.morton-block { position: absolute; background: aqua; padding: 0; margin: 0; width: 60px; height: 60px; display: flex; justify-content: center; align-items: center; border: 1px solid; } p.morton-block::before { font-size: 15px; content: attr(data-order); } #console-area-3__art110 { display: block; position: absolute; width: 480px; height: 20px; top: 480px; padding: 0; margin: 40px auto 0; } #game-status-3__art110 { width: 100%; font-size: 1.1rem; background: #f5b560; pointer-events: none; border: navajowhite; outline: none; }

@@@% これで所属階層やモートン番号の重なり具合を見ながら、スプライト同士のより細かな衝突判定を行っていくことができます。 - - - ## まとめ今回は四分木分割法によるモートン番号を活用した高速な衝突判定法の基礎をJavascriptベースのコードに落とし込むまでを解説してみました。この方法を実践的に扱うには、もう一つ|px>{1}「線形四分木配列を使った衝突オブジェクトの検索」