LOCKYOUで学ぶ

パラフドーム後日談

戻る
さて、前回は4分木空間分割について概念的な話をしたんだけど
今回は実際にプログラムを組んでみるよ
前回も聞いたぞ
今回は本当にプログラム組むから許してや……赤口
というわけでphina.jsのひな形をこんな感じで 

// phina.js をグローバル領域に展開
phina.globalize();

// MainScene クラスを定義
phina.define('MainScene', {
	superClass: 'DisplayScene',

	// 初期処理
	init: function() {

		// 親クラス初期化
		this.superInit({
			// 画面サイズ
			width: 600,
			height: 600,
		});
		// 背景色を指定
		this.backgroundColor = '#EEE';

		// ラベルを生成
		this.label = Label('Hello, phina.js!').addChildTo(this);
		this.label.x = this.gridX.center(); // x 座標
		this.label.y = this.gridY.center(); // y 座標
		this.label.fill = 'black'; // 塗りつぶし色
		
		// グリッド線作成
		(9).times(function(i){
			var path1 = PathShape()
				.addPath(0, 600/8*i)
				.addPath(600, 600/8*i)
				.addChildTo(this);
			var path2 = PathShape()
				.addPath(600/8*i, 0)
				.addPath(600/8*i, 600)
				.addChildTo(this);
		}, this);

		// ラベル（画面に表示するテキスト）を生成
		this.kaisou = Label('test').addChildTo(this);
		this.kaisou.setPosition(this.gridX.span(10), this.gridY.span(1));
		this.heya = Label('test').addChildTo(this);
		this.heya.setPosition(this.gridX.span(10), this.gridY.span(2));

		// 初期処理部分
		this.hierarchyLevel = 3; // 階層
		this.unitWidth = this.width / (Math.pow(2, this.hierarchyLevel)); // 部屋の横のサイズ
		this.unitHeight = this.height / (Math.pow(2, this.hierarchyLevel)); // 部屋の縦のサイズ

		// 四角を作成
		this.rect = RectangleShape().addChildTo(this);
		this.rect.setPosition(100,100); // 位置の指定 xとy
		this.rect.setSize(30,30); // サイズの指定 縦と横
		this.rect.draggable; // ドラッグで移動可能にする

		this.rect.headRoomNo = 0; // 左上の部屋番号（最下層）
		this.rect.tailRoomNo = 0; // 右下の部屋番号（最下層）
		this.rect.hierNo = 0; // 階層番号
		this.rect.roomNo = 0; // 部屋番号
		
	},

	// 毎フレーム処理
	update: function(app) {
		// ここに処理を記述
		let rect = this.rect;
		
		
		// 階層と部屋を表示
		this.kaisou.text = "階層：" + rect.hierNo;
		this.heya.text = "部屋：" + rect.roomNo;
	}, 
	
	bitSeparate32: function(n) {
		n = (n|(n<<8)) & 0x00ff00ff;
		n = (n|(n<<4)) & 0x0f0f0f0f;
		n = (n|(n<<2)) & 0x33333333;
		return (n|(n<<1)) & 0x55555555;
	},

});

// メイン処理
phina.main(function() {
	// アプリケーション生成
	let app = GameApp({
		startLabel: 'main',
		fit: false,
		query: '#sample01',
		width: 600, //縦のサイズ
		height: 600, //横のサイズ
	});
	// アプリケーション実行
	app.run();
});
四角をドラッグで動かせますが右上の階層と部屋の数値は動きません
canvas非対応
phina.jsで書いてるからいろいろ
特有のもの 見ての通り文字を灰色にしてあります
環境によってコードが異なると思うので適宜自分で書いてくださいまし
があるけど
特に注目してもらいたいのは「rect」っていう変数だね
これに左上の部屋番号、右下の部屋番号、階層番号、部屋番号を設定していくよ
ほかのコードの詳細については
行き当たりばったりゲーム制作（javascript（phina.js））を参考にしてね
途中で止まってるけど
階層と部屋を割り出すのにまずやることと言ったら
右上と左下の点の部屋の位置を割り出すことだな 

// ここに処理を記述
let rect = this.rect;

// 左上の部屋番号を割り出す
let headRoomX = Math.trunc(rect.left / this.unitWidth);
let headRoomY = Math.trunc(rect.top / this.unitHeight);
rect.headRoomNo = this.bitSeparate32(headRoomX) | (this.bitSeparate32(headRoomY)<<1);

// 右下の部屋番号を割り出す
let tailRoomX = Math.trunc(rect.right / this.unitWidth);
let tailRoomY = Math.trunc(rect.bottom / this.unitHeight);
rect.tailRoomNo = this.bitSeparate32(tailRoomX) | (this.bitSeparate32(tailRoomY)<<1);
座標を一つの部屋の長さで
割って Math.truncで小数点以下を切り捨てています
から
ビットをかみ合わせる、だったね
ちなみにphina.jsだと.leftやら.topやらでそのオブジェクトの左端、上端とかが
取得できる 大体は左端はx座標、右端はx座標+オブジェクトの横の長さだったりすると思います
よ
まあこれは単純だな
次は左上と右下の点からオブジェクトの階層と部屋を割り出すんだが……
前回のおさらいだけど
左から１デュエットずつ調べて、一致した分までがその階層
一致している部分を抜き出したのがその階層での部屋っていうことになるね
for文で2ビットずつ抜き出して比較すればいいな
まあ単純に考えればこんな感じだが……効率悪い気がするな 

// 全体の階層をもとに自分のオブジェクトがいる階層を割り出す
let hierNo = 0;
for (let i = this.hierarchyLevel; i > 0; i--) {
	let shiftValue = 0x00000003 << (2*(i-1));
	if((rect.headRoomNo & shiftValue) != (rect.tailRoomNo & shiftValue)) {
		break;
	}
	hierNo++;
}

rect.hierNo = hierNo;
いやまあそうっすね、
というわけでXORを使う方法があるよ
XORは二つのうちどちらかが1なら1、両方同じなら0だったな
例えば左上[10][01][10]（38）と右下[10][11][00]（44）なら
XORすると[00][10][10]
一致するデュエットは[00]になるから
左から調べるときは逆に[00]じゃなくなるところまでを調べる形になるね
これを踏まえてコードを書けば 

// 全体の階層をもとに自分のオブジェクトがいる階層を割り出す
let hierNo = 0;
let xorRoom = rect.headRoomNo ^ rect.tailRoomNo;
for (let i = this.hierarchyLevel; i > 0; i--) {
	let shiftValue = 0x00000003 << (2*(i-1));
	if(xorRoom & shiftValue) {
		break;
	}
	hierNo++;
}
xorRoom & shiftValueの部分は該当の部分が[00]以外ならtrue判定されてループを抜けるってことね
まあ別に変えたからって超スピード！？になるわけではないとは思うけどね
最後に部屋番号の部分行くぞオラァ！
部屋番号に関しては左上の部屋番号から階層番号をもとに抜き出せばいいってだけだよな 

rect.roomNo = rect.headRoomNo >>> ((this.hierarchyLevel - rect.hierNo)*2);
ナイスでーす！
左上の部屋番号から（全体の階層 - 自分の階層）分だけ右にずらせばそのまま取り出せるね
全体、というか毎フレーム処理の部分を振り返ればこうなると 

// 毎フレーム処理
update: function(app) {
	// ここに処理を記述
	let rect = this.rect;
	
	// 左上の部屋番号を割り出す
	let headRoomX = Math.trunc(rect.left / this.unitWidth);
	let headRoomY = Math.trunc(rect.top / this.unitHeight);
	rect.headRoomNo = this.bitSeparate32(headRoomX) | (this.bitSeparate32(headRoomY)<<1);

	// 右下の部屋番号を割り出す
	let tailRoomX = Math.trunc(rect.right / this.unitWidth);
	let tailRoomY = Math.trunc(rect.bottom / this.unitHeight);
	rect.tailRoomNo = this.bitSeparate32(tailRoomX) | (this.bitSeparate32(tailRoomY)<<1);

	// 全体の階層をもとに自分のオブジェクトがいる階層を割り出す
	let hierNo = 0;
	let xorRoom = rect.headRoomNo ^ rect.tailRoomNo;
	for (let i = this.hierarchyLevel; i > 0; i--) {
		let shiftValue = 0x00000003 << (2*(i-1));
		if(xorRoom & shiftValue) {
			break;
		}
		hierNo++;
	}

	rect.hierNo = (this.hierarchyLevel - (xorRoom/2));

	// 部屋番号を割り出す
	rect.roomNo = rect.headRoomNo >>> ((this.hierarchyLevel - rect.hierNo)*2);

	// 階層と部屋を表示
	this.kaisou.text = "階層：" + rect.hierNo;
	this.heya.text = "部屋：" + rect.roomNo;
},
canvas非対応
こうしてオブジェクトの階層番号と部屋番号を導けたわけで
今回はこれで終わりにするね
次は今度こそ別のオブジェクトとの衝突予想リストになるか？
多分そんな感じになるね
じゃ、というわけでまたね～










もうちっとだけ続くんじゃ
なんだ？
オブジェクトの階層と部屋をだすのになんか不足があったか？
そういうわけじゃないけど、この階層を割り出す処理 

// 全体の階層をもとに自分のオブジェクトがいる階層を割り出す
let hierNo = 0;
let xorRoom = rect.headRoomNo ^ rect.tailRoomNo;
for (let i = this.hierarchyLevel; i > 0; i--) {
	let shiftValue = 0x00000003 << (2*(i-1));
	if(xorRoom & shiftValue) {
		break;
	}
	hierNo++;
}
forもifも使わず何とかできないかな～って思ったわけよ
……できるのか？
これがその完成品となります 

// 全体の階層をもとに自分のオブジェクトがいる階層を割り出す
let xorRoom = rect.headRoomNo ^ rect.tailRoomNo;
xorRoom = (xorRoom & 0xaaaaaaaa) | (xorRoom << 1 & 0xaaaaaaaa);
xorRoom |= (xorRoom >>> 1);
xorRoom |= (xorRoom >>> 2);
xorRoom |= (xorRoom >>> 4);
xorRoom |= (xorRoom >>> 8);
xorRoom |= (xorRoom >>> 16);

xorRoom = (xorRoom & 0x55555555) + ((xorRoom >>> 1) & 0x55555555);
xorRoom = (xorRoom & 0x33333333) + ((xorRoom >>> 2) & 0x33333333);
xorRoom = (xorRoom & 0x0f0f0f0f) + ((xorRoom >>> 4) & 0x0f0f0f0f);
xorRoom = (xorRoom & 0x00ff00ff) + ((xorRoom >>> 8) & 0x00ff00ff);
xorRoom = (xorRoom & 0x0000ffff) + ((xorRoom >>> 16) & 0x0000ffff);

rect.hierNo = (this.hierarchyLevel - (xorRoom/2));

// 部屋番号を割り出す
rect.roomNo = rect.headRoomNo >>> xorRoom;
展開が早えよ
３分クッキングか
なんとなくこことかみてたらどうにかならないかな～って思ったわけよ
http://marupeke296.com/TIPS_No17_Bit.html
で、こことかも見るともっと改良とかできるけどまあこんなもんでいっかって感じだね
https://www.nminoru.jp/%7Enminoru/programming/bitcount.html
これを見ると
「最大有効ビット数を取得する処理」 正確にはこの処理の中にビットを数える処理も含まれてるので
「最大有効ビット数を取得する処理の前処理」ですね
と「ビットを数える処理」をやってるみたいだが……？
ループのほうは「左から走査して不一致のデュエットを調べる」で
今回は「右から見て一番左にある不一致のデュエットを調べる」だね
ざっくり言うと
階層が少ないとわかりにくいから8階層でたとえるけど
xorした後のやつ、例えば[00][00][01][10][00][11][01][11]になったとするでしょ？
2階層目（2デュエット目）まで一致してるからH2になるな
逆に[00][00][01][10][00][11][01][11]の一番左にある不一致のデュエットは
右から6番目のやつだね
全体の階層の8から6を引けば目当ての2階層目という答えが出るね
で、最初の xorRoom = (xorRoom & 0xaaaaaaaa) | (xorRoom << 1 & 0xaaaaaaaa);は
「不一致のデュエットの左側に1を立てる処理」になるよ
[00][00][01][10][00][11][01][11]が
[00][00][11][10][00][11][11][11]になるわけか？
何でこんな処理を？
それはまあビットを数えた後でわかるよ
で、その下では「最大有効ビット数を取得する処理」をしてるよ
これは一番左にある1よりも右側全部に1の植え付けを行う処理だね
全部1になるって
ことでいいんだな 1の植え付けを行うってどういう表現なんだ……？

[00][00][11][10][00][11][11][11]が
[00][00][11][11][11][11][11][11]になると
あとは1の数を数えるだけだね
「ビットを数える処理」で1の数は12個
1デュエットに2個1があるから2で割って6
これで答えが導き出せたね
ああ、最初に1をデュエットの左側に立てたのは
0のままだと2で割り切れなくなるからか
そーなんでちゅ
あ、最後の部屋番号を割り出すところは
不一致の部分がそのまま1の数として出てるならそのままその数分右にずらせばいいよね？って感じだね
で、こうしたことでなんかメリットはあるのか？
ないね
たぶん3階層ぐらいなら普通に
ループのほうが速い 普通のループは階層が2倍になれば処理も２倍になりますが
この方法の場合階層が32ビットから64ビットで処理が数個増える、
64ビットから128ビットで処理が数個増える、といった感じに対数的に増えていくので
階層が増えるほどこちらのほうが有利になります
そこまで必要になるかどうかはともかく
んじゃないかな
どっちが速かろうとほぼ誤差みたいなもんだろうしね
じゃあ意味ねえじゃねえか
いやぁすいませーん
まあ頭の体操としてね
というわけで今回はここまでっていうことでまたね～