パラフドーム後日談

さて、前回は4分木空間分割について概念的な話をしたんだけど
今回は実際にプログラムを組んでみるよ

プログラムを組むって、何の言語で組むんだ？

今回もjavascriptのphina.jsでやるんだけど、
なるべく応用できるように解説するようにはするよ

さて、まず考えなきゃいけないのは
再帰的に4分割した部屋のどこにオブジェクトが入るの？っていうことなんだけど
あ、今回は3回分割するよ

ん？この番号の振り方ちょっと変わってるな

そこが今回のくそみそ~~テクニック~~なんだよね
モートン序列（モートン順序）っていうんだけど、2進数使って表したら規則性がわかると思うよ

一桁ずつで縦横を表してるのか

そーなんでちゅ
まああとそれぞれの階層とか部屋の番号とかを「2階層の部屋8」みたいに言うの面倒だから
「H2R8」とかっていうね

Hはhierarchy、RはRoomってことだな
それでだ、オブジェクトがどこに入るかをどうやって割り出すんだ

まずはオブジェクトの前に、
「点」がどこに入るかを割り出してみよう
「面」のオブジェクトはそのあとね
点はまあ必ず一番下の階層にあるってことになるんだけど

点がどこにあるかだろ？
横の場合は「X/一つの部屋の横の長さ」（小数点以下切り捨て）
縦の場合は「Y/一つの部屋の縦の長さ」（小数点以下切り捨て）
でそれぞれで「左上の部屋からそれぞれ何番目の部屋にあるか」がわかるが……

00 01 02 03 04 05 06 07
08 09 10 11 ...
って並んでくれていれば「Y*8+X」でわかるんだが

そこは後々で有利に働いてくれるんだけど若干めんどくさいところなんだね、仕方ないね
さっきも言ったように１桁ずつとびとびになってるから
ビット演算で噛み合うようにしないといけないんだよね

javascriptの数値はまあって考えてもらえばいいからこんな感じで
左へビットをずらした奴と元のやつをOR→余計な部分を消すためにマスクをAND
って感じでやってくよ


n
0000 0000 0000 0000 abcd efgh ijkl mnop

n << 8
0000 0000 abcd efgh ijkl mnop 0000 0000

(n or n << 8)
0000 0000 abcd efgh ???? ???? ijkl mnop

0x00ff00ff
0000 0000 1111 1111 0000 0000 1111 1111

(n or n << 8) and 0x00ff00ff
0000 0000 abcd efgh 0000 0000 ijkl mnop


function bitSeparate32(n) {
    n = (n|(n<<8)) & 0x00ff00ff;
    n = (n|(n<<4)) & 0x0f0f0f0f;
    n = (n|(n<<2)) & 0x33333333;
    return (n|(n<<1)) & 0x55555555;
}

bitSeparate32関数を使えば
bitSeparate32(X) | (bitSeparate32(Y)<<1)
でその点がどこの部屋に入っているかを割り出すことができるわけか
点が入る部屋の番号はこれで求め方がわかったな