【HTML&CSSではじめるミニゲーム作成】高速なアルゴリズムで接触してるスプライトを検索する
※ 当ページには【広告/PR】を含む場合があります。
2023/12/31
四分木分割空間上のスプライトのモートン番号の求め方
四分木分割空間について
4^L
L
L = 3
4^3 = 64
0〜63
(列番号,行番号)
モートン座標(6,3) --> モートン番号(30)
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値を求める
//クリックしたときのキャンバス中のクライアント座標
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);
スプライトの所属空間番号(分割階層の深さ)を求める
所属空間(右シフト数)の算出方法
2*L
L=3
L=0 ... ルート階層 --> 右シフト数6
L=1 ... 親階層 --> 右シフト数4
L=2 ... 子階層 --> 右シフト数2
L=3 ... 孫階層 --> 右シフト数0
L - (右シフト数)/2
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;
まとめ
記事を書いた人
ナンデモ系エンジニア
これからの"地方格差"なきプログラミング教育とは何かを考えながら、 地方密着型プログラミング学習関連テーマの記事を不定期で独自にブログ発信しています。
カテゴリー