LOCKYOUで学ぶ

パラフドーム後日談

戻る
ハロ～　パッ☆
というわけで今回も4分木空間分割によるオブジェクトの衝突判定の効率化講座やってくよ！
今回は衝突予想リストを作るんだな
いやまぁそうっすね
その前に二個やっておきたいことがあるんだよね
一個目は前回やったこの左上と右下の部屋番号を割り出すところ 

// ここに処理を記述
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);
これだとちょっと不十分だからちょっと付け加えるね 

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


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

// 右下の部屋番号を割り出す
let tailRoomX = Math.trunc(colObj.right / this.unitWidth);
tailRoomX = Math.clamp(tailRoomX, 0, this.unitCount-1);
let tailRoomY = Math.trunc(colObj.bottom / this.unitHeight);
tailRoomY = Math.clamp(tailRoomY, 0, this.unitCount-1);
colObj.tailRoomNo = this.bitSeparate32(tailRoomX) | (this.bitSeparate32(tailRoomY)<<1);
unitCountはコメントに書いてある通り一番下の階層の横（もしくは縦）の部屋の数だな
今回は3階まであるから8個になる
Math.clampってやつに使われてるようだがこの関数はいったいなんだ？
このMath.clampっていうのは
phina.js独自の 今(2023/7/30)のところjavascriptには標準装備されてないっぽいです
されててもいいと思うんですけどねぇ……
関数で
Math.clamp(val, 0, 7)で、valが0より小さかったら0を、7より大きかったら7を、範囲内ならそのままvalを返す関数だね
範囲内に丸めるってことだな
画面外に出ても大丈夫にするっていうことか
これは前回にやっとけよ……
段取りがわるくてすみませーんごめんなさーい
あともう一つは、オブジェクトが今のところ一個しかないからたくさん作るように改良しよう 

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

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

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

		省略

		// ラベル（画面に表示するテキスト）を生成
		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.colObjList = [];
		this.colObjCount = 0;
		// 四角を複数個作成
		for(; this.colObjCount<31; this.colObjCount++) {
			let rect = RectangleShape().addChildTo(this);
			rect.setPosition(Math.randint(0, 600),Math.randint(0, 600)); // 位置はランダムにする
			rect.setSize(30,30);
			rect.draggable;

			rect.id = this.colObjCount; // ID
			rect.headRoomNo = 0; // 左上の部屋番号（最下層）
			rect.tailRoomNo = 0; // 右下の部屋番号（最下層）
			rect.hierNo = 0; // 階層番号
			rect.roomNo = 0; // 部屋番号
			
			// それぞれの四角にIDを表示
			let label = Label(rect.id).addChildTo(rect);
			label.fill = 'white'; // 塗りつぶし色

			this.colObjList[rect.id] = rect;
		}
		
	},

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

			// 右下の部屋番号を割り出す
			let tailRoomX = Math.trunc(colObj.right / this.unitWidth);
			let tailRoomY = Math.trunc(colObj.bottom / this.unitHeight);
			colObj.tailRoomNo = this.bitSeparate32(tailRoomX) | (this.bitSeparate32(tailRoomY)<<1);
			
			// 全体の階層をもとに自分のオブジェクトがいる階層を割り出す
			let xorRoom = colObj.headRoomNo ^ colObj.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);
			
			colObj.hierNo = (this.hierarchyLevel - (xorRoom/2));

			// 部屋番号を割り出す
			colObj.roomNo = colObj.headRoomNo >>> xorRoom;

		}
		
		// 階層と部屋を表示
		this.kaisou.text = "階層：" + colObjList[0].hierNo;
		this.heya.text = "部屋：" + colObjList[0].roomNo;
	}, 
	
	bitSeparate32: function(n) {
		n = (n|(n<<8)) & 0x00ff00ff;
		n = (n|(n<<4)) & 0x0f0f0f0f;
		n = (n|(n<<2)) & 0x33333333;
		return (n|(n<<1)) & 0x55555555;
	},

});

省略
複数になったから
ID オブジェクトのリスト（colObjList）の添え字をIDとしているので
colObjList[ID]でそのオブジェクトが取得できます
上記コードのcolObjList[0].hierNoがその例
をつけるようにしたよ
さて、「オブジェクトがどの部屋に入っているか？」はわかったけど
「この部屋にはどのオブジェクトが入っているか？」はまだわからない
これの下の
画像 上の画像は第二回の講座の画像から持ってきています
15のオブジェクトの色が変ですがめんどくさかったので直してません
のほうの４分木データが必要になってくるね
４分木ってjavascriptでどうやって表現？するんだ？
そういう専用のデータ型があるとかか……？
その必要はない
配列だけで表現できるよ
初期化はこんな感じ 

// オブジェクトの衝突の木をSetで埋める
this.colObjBelongTree = new Array(this.hierarchyLevel + 1);
for (let i=0; i < this.colObjBelongTree.length; i++) {
	this.colObjBelongTree[i] = new Array(Math.pow(4, i));
	for(let j=0; j < this.colObjBelongTree[i].length; j++) {
		this.colObjBelongTree[i][j] = new Set();
	}
}
二次元配列を使うんだな
まあ一次元配列でもつくれるけどね
javascriptだとnew Arrayの引数に
ただの数ひと Arrayのコンストラクターの引数に各値を入れた時の動作は
let a1 = new Array(5); // [ <5 empty slots> ]（空の要素が5個の配列）
let a2 = new Array('5'); // ['5'] （'5'（文字列）という要素が1個の配列）
let a3 = new Array(5,0); // [5,0] （5と0、要素が2個の配列）
let a4 = new Array(5.1); // error
となり、通常は与えられた引数を配列にしますが
引数が数値(自然数)一つだけの場合はその数分の空の配列を作る処理となります
驚きました
つだけを入れるとその数分要素がある配列ができるから
一次元目には階層、二次元目にはその階層分の部屋の個数分だけ入れてるよ
その階層の部屋の個数は「4の「階層」乗」だな
0階層には部屋が1つ、1階層には4つというように
そしてその部屋一つ一つに
Set 様々な値を格納できるオブジェクト
配列（List）との違いは「順番はとくに気にされない（ので添え字がない）」「重複した値は格納できない」こと
addメソッドで値を格納、hasメソッドで値があるかの確認、deleteメソッドで値を取り除くのが基本動作
を入れてやると
このcolObjBelongTreeという二次元配列では[]を使って
colObjBelongTree[階層][部屋]ってやればその部屋のSetが取得できるから
こんな感じで部屋にIDを入れることができるね 

// 毎フレーム処理
update: function(app) {
	// ここに処理を記述
	let colObjList = this.colObjList;
	for(let colObj of colObjList) {
			
		// 旧番号を保持
		let oldHierNo = colObj.hierNo;
		let oldRoomNo = colObj.roomNo;
			
		中略
		
		colObj.hierNo = (this.hierarchyLevel - (xorRoom/2));

		// 部屋番号を割り出す
		colObj.roomNo = colObj.headRoomNo >>> xorRoom;

		// 旧番号と異なる場合は部屋を移し替える
		if (oldHierNo != colObj.hierNo || oldRoomNo != colObj.roomNo) {
			this.colObjBelongTree[oldHierNo][oldRoomNo].delete(colObj.id);
			this.colObjBelongTree[colObj.hierNo][colObj.roomNo].add(colObj.id);
		}
	}
canvas非対応
なんにせよこれで四分木にオブジェクトは登録できたな
次はようやく衝突予想ペアのリストを作る処理か
どうしようかな……
何がだよ
衝突予想のペアのリストをつくるのはちょ～っと長くなりそうなんだよね
だからまあ次回に回したいなーって
でも今回の講座結構短くねえか？
これで終わるのか？
まあ、来週までのフラグをということで
二つの関数をあらかじめ用意しておこう
まず一個目はこれ、一つのリストの要素の中から二つの組み合わせを全部作り出す処理だね 

makeCombiList: function(paramList) {
	let result = [];
	for (let i=0; i < paramList.length-1; i++){
		for(let j=i+1; j < paramList.length; j++) {
			result.push([paramList[i], paramList[j]]);
		}
	}
	return result;
},
入れる値が[1,2,3,4]なら
出力されるのは[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
4C2の6個のペアになると
もう一個は二つのリストから一つずつ要素を取り出した場合のすべての組み合わせを作り出す処理だよ
数学的にいえば直積ってやつだね 

makeCrossJoinList: function(list1, list2) {
	let result = [];
	for (let i=0; i < list1.length; i++){
		for(let j=0; j < list2.length; j++) {
			result.push([list1[i], list2[j]]);
		}
	}
	return result;
},
（関数名は
それでいいのか 直積の英名はdirect product
ただしSQLでの直積の操作はCROSS JOINとなるのでこっちにしました
どうしてかって？まあ何となく
？）
[1,2,3]と[4,5]なら
[[1,4],[1,5],[2,4],[2,5],[3,4],[3,5]]
3×2の6通りになるな
そういうこと
この二つの関数はさっきも言った通り衝突予想ペアを作るために使うから記憶の片隅に置いといてね
今回はここまで
またね～










あ、そうそう
またなんかあんのか……
今度は何だ？
今回オブジェクトの数を増やして、ツリーに登録できるようにしたわけだけど
実は今回のコードの中にバグがあるんだよね
なんでだよ
バグのあるコードを教えるなよ
グダグダになっちゃってすみませーんごめんなさーい
このバグこの講座書いてるときに気づいたんだよね
というわけで
直し方の一例 本当は初期処理時点でちゃんと階層と部屋を割り出してセットしてあげたほうがいいと思います
割り出す処理をサブルーチン化する必要がありますが
はこんな感じ 

		// 四角を複数個作成
		for(; this.colObjCount<31; this.colObjCount++) {
			let rect = RectangleShape().addChildTo(this);
			rect.setPosition(Math.randint(0, 600),Math.randint(0, 600)); // 位置はランダムにする
			rect.setSize(30,30);
			rect.draggable;

			rect.id = this.colObjCount; // ID
			rect.headRoomNo = 0; // 左上の部屋番号（最下層）
			rect.tailRoomNo = 0; // 右下の部屋番号（最下層）
			rect.hierNo = -1; // 階層番号
			rect.roomNo = 0; // 部屋番号
			
			// それぞれの四角にIDを表示
			let label = Label(rect.id).addChildTo(rect);
			label.fill = 'white'; // 塗りつぶし色

			this.colObjList[rect.id] = rect;
		}


// オブジェクトの衝突の木をSetで埋める
this.colObjBelongTree = new Array(this.hierarchyLevel + 1);
for (let i=0; i < this.colObjBelongTree.length; i++) {
	this.colObjBelongTree[i] = new Array(Math.pow(4, i));
	for(let j=0; j < this.colObjBelongTree[i].length; j++) {
		this.colObjBelongTree[i][j] = new Set();
	}
}
this.colObjBelongTree[-1] = [new Set()];
どんなバグがあったかは詳しく書くの面倒正直この講座の本質じゃないし
詳しくは書かないからまあ、考えてみてね
直し方がヒントになってるし、さらに言えば初期処理で階層番号と部屋番号に0を入れるのは不都合って感じだね
最後の最後に適当な感じだな……
作者だらしねぇし……
というわけで今回はここまでだね　じゃあまたね～