boku2d.js

window.Boku2D = (function() {
	/*
		Recursive Dimensional Clustering
		http://lab.polygonal.de/articles/recursive-dimensional-clustering/
	*/
	var RDC = function (collide) {
		this.collide = collide;
	};
	// RDC.SUBDIVISION_THRESHOLD = 4;
	// RDC.CONTACT_THRESHOLD = 0.1;

	RDC.prototype.bruteForce = function (group) {
		var collde = this.collide;
		for (var i=0,l=group.length; i<l; i++) {
			for (var j=i+1; j<l; j++) {
				collde(group[i], group[j]);
			}
		}
	};
	RDC.prototype.recursiveClustering = function (group, axis1, axis2) {
		// if (axis1 === -1 || group.length < RDC.SUBDIVISION_THRESHOLD) {
		if (axis1 === -1 || group.length < 4) {
			this.bruteForce(group);
		} else {
			var boundaries = this.getOpenCloseBounds(group, axis1);		
			boundaries.sort(function (a, b) {
				return a.pos - b.pos;
			});
			
			var newAxis1 = axis2,
				newAxis2 = -1,
				groupSubdivided = false,
				subgroup = [],
				count = 0,
				l = boundaries.length;
			for (var i=0; i<l; i++)
			{
				var b = boundaries[i];
				if (b.type === 1) {
					count++;
					subgroup.push(b.obj);
				} else {
					count--;
					if (count === 0) {
						if (i !== (l - 1)) {
							groupSubdivided = true;
						}
						
						if (groupSubdivided) {
							if (axis1 === 0) {
								newAxis1 = 1;
							} else if (axis1 === 1) {
								newAxis1 = 0;
							}
						}
						
						this.recursiveClustering(subgroup, newAxis1, newAxis2);
						subgroup = [];
					}
				}
			}
		}
	};
	RDC.prototype.getOpenCloseBounds = function (group, axis) {
		var l = group.length;
		var boundaries = [];
		
		switch(axis)
		{
			case 0:
				for (var i=0; i<l; i++) {
					var o = group[i];
					var center = o.center.x;
					var size = o.size.x;
					boundaries.push({
						type: 1, 
						// pos: o.center.x - o.size.x + RDC.CONTACT_THRESHOLD,
						pos: center - size + 0.1,
						obj: o
					});
					boundaries.push({
						type: 0, 
						// pos: o.center.x + o.size.x - RDC.CONTACT_THRESHOLD,
						pos: center + size - 0.1,
						obj: o
					});
				}
				break;
			case 1:
				for (var i=0; i<l; i++) {
					var o = group[i];
					var center = o.center.y;
					var size = o.size.y;
					boundaries.push({
						type: 1, 
						// pos: o.center.y - o.size.y + RDC.CONTACT_THRESHOLD,
						pos: center - size + 0.1,
						obj: o
					});
					boundaries.push({
						type: 0, 
						// pos: o.center.y + o.size.y - RDC.CONTACT_THRESHOLD,
						pos: center + size - 0.1,
						obj: o
					});
				}
		}
		return boundaries;
	};
	
	var IsNumber = function(num) {
		return typeof num === "number";
	};
	
	var Extend = function(obj, option) {
		if (!option) {
			return;
		}
		 
		var key;
		for (key in option) {
			if (option.hasOwnProperty(key)) {
				obj[key] = option[key];
			}
		}
	};
	
	var Vec = function(x, y) {
		this.x = x || 0;
		this.y = y || 0;
	};
	Vec.prototype = {
		copy: function() {
			return new Vec(this.x, this.y);
		},
		add: function(v, y) {
			if (y !== undefined) {
				v = new Vec(v, y);
			}
			
			var x = this.x + v.x,
				y = this.y + v.y;
			return new Vec(x, y);
		},
		subtract: function(v, y) {
			if (y !== undefined) {
				v = new Vec(v, y);
			}
			
			var x = this.x - v.x,
				y = this.y - v.y;
			return new Vec(x, y);
		},
		multiply: function(i) {
			var x = this.x * i,
				y = this.y * i;
			return new Vec(x, y);
		},
		divide: function(i) {
			var x = this.x / i,
				y = this.y / i;
			return new Vec(x, y);
		},
		dot: function(v) {
			return this.x * v.x + this.y * v.y;
		},
		length: function() {
			return Math.sqrt(this.x*this.x + this.y*this.y);
		},
		normalize: function() {
			var length = this.length();
			return this.divide(length);
		}
	};
	
	var Manifold = function(object, opponent) {
		this.object = object;
		this.opponent = opponent;
		this.normal = new Vec();
	};
	Manifold.prototype = {
		solve: function() {
			var move = this.object,
				fixed = this.opponent;
			
			if (move.fixed) {
				return false;
			}
			
			var friction = Math.sqrt(move.friction * fixed.friction);
			var spring = Math.sqrt(move.elastic * fixed.elastic);
			var damp = Math.sqrt(move.viscosity * fixed.viscosity);
			// var relSpeed = move.speed.subtract(fixed.speed);
			var relSpeed = {
				x: move.speed.x - fixed.speed.x,
				y: move.speed.y - fixed.speed.y
			};
			
			// 衝突ソルバー
			// this.normal = new Vec();
			this.normal.x = 0;
			this.normal.y = 0;
			if (this.direction.x < 0) {
				var diff = move._maxPos.x - fixed._minPos.x;
				var adj = spring * diff + damp * relSpeed.x;
				// this.normal = this.normal.add(-adj, 0);
				this.normal.x += -adj;
			} else if (this.direction.x > 0) {
				var diff = fixed._maxPos.x - move._minPos.x;
				var adj = spring * diff - damp * relSpeed.x;
				// this.normal = this.normal.add(adj, 0);
				this.normal.x += adj;
			}
			if (this.direction.y < 0) {
				var diff = move._maxPos.y - fixed._minPos.y;
				var adj = spring * diff + damp * relSpeed.y;
				// this.normal = this.normal.add(0, -adj);
				this.normal.y += -adj;
			} else if (this.direction.y > 0) {
				var diff = fixed._maxPos.y - move._minPos.y;
				var adj = spring * diff - damp * relSpeed.y;
				// this.normal = this.normal.add(0, adj);
				this.normal.y += adj;
			}
			var l = move.contacts.length;
			move.applyForce({
				x: this.normal.x / l,
				y: this.normal.y / l
			});
			
			// 摩擦
			var n = this.normal.length(),
				force = new Vec(n, n).multiply(friction);
			if (force.x > Math.abs(move.force.x)) {
				force.x = Math.abs(move.force.x);
			}
			if (force.y > Math.abs(move.force.y)) {
				force.y = Math.abs(move.force.y);
			}
			if (this.direction.y !== 0) {
				if (relSpeed.x > 0) {
					force.x = -force.x;
				}
			} else {
				force.x = 0;
			}
			if (this.direction.x !== 0) {
				if (relSpeed.y > 0) {
					force.y = -force.y;
				}
			} else {
				force.y = 0;
			}
			move.applyForce(force);
			// !fixed.fixed && fixed.applyForce(force.multiply(-1));
			!fixed.fixed && fixed.applyForce({
				x: force.x * -1,
				y: force.y * -1
			});
		}
	};
	
	var Contact = function(object1, object2) {
		var direction1 = new Vec(),
			direction2 = new Vec();
		
		// 前回の位置から衝突方向を調べる
		if (object1._maxTmpPos.x < object2._minTmpPos.x && 
			object1._maxPos.x > object2._minPos.x) {
			// direction1 = direction1.add(-1, 0);
			direction1.x += -1;
		}
		if (object1._minTmpPos.x > object2._maxTmpPos.x && 
			object1._minPos.x < object2._maxPos.x) {
			// direction1 = direction1.add(1, 0);
			direction1.x += 1;
		}
		if (object1._maxTmpPos.y < object2._minTmpPos.y &&
			object1._maxPos.y > object2._minPos.y) {
			// direction1 = direction1.add(0, -1);
			direction1.y += -1;
		}
		if (object1._minTmpPos.y > object2._maxTmpPos.y && 
			object1._minPos.y < object2._maxPos.y) {
			// direction1 = direction1.add(0, 1);
			direction1.y += 1;
		}
		
		if (direction1.x === 0 && direction1.y === 0) {
			// 最小分離距離を計る
			var normals = [];
			
			if ((object2._minPos.x <= object1._minPos.x && 
				object1._minPos.x <= object2._maxPos.x) || 
				(object1._minPos.x <= object2._maxPos.x && 
				object2._maxPos.x <= object1._maxPos.x)) {
				// 左衝突
				var d = object2._maxPos.x - object1._minPos.x;
				// normal = new Vec(d, 0);
				// normal.direction = new Vec(1, 0);
				var normal = {
					length: d,
					direction: {
						x: 1,
						y: 0
					}
				};
				normals.push(normal);
			}
			if ((object2._minPos.x <= object1._maxPos.x && 
				object1._maxPos.x <= object2._maxPos.x) || 
				(object1._minPos.x <= object2._minPos.x && 
				object2._minPos.x <= object1._maxPos.x)) {
				// 右衝突
				var d = object1._maxPos.x - object2._minPos.x;
				// normal = new Vec(d, 0);
				// normal.direction = new Vec(-1, 0);
				var normal = {
					length: d,
					direction: {
						x: -1,
						y: 0
					}
				};
				normals.push(normal);
			}
			if ((object2._minPos.y <= object1._minPos.y && 
				object1._minPos.y <= object2._maxPos.y) || 
				(object1._minPos.y <= object2._maxPos.y && 
				object2._maxPos.y <= object1._maxPos.y)) {
				// 上衝突
				var d = object2._maxPos.y - object1._minPos.y;
				// normal = new Vec(0, d);
				// normal.direction = new Vec(0, 1);
				var normal = {
					length: d,
					direction: {
						x: 0,
						y: 1
					}
				};
				normals.push(normal);
			}
			if ((object2._minPos.y <= object1._maxPos.y && 
				object1._maxPos.y <= object2._maxPos.y) || 
				(object1._minPos.y <= object2._minPos.y && 
				object2._minPos.y <= object1._maxPos.y)) {
				// 下衝突
				var d = object1._maxPos.y - object2._minPos.y;
				// normal = new Vec(0, d);
				// normal.direction = new Vec(0, -1);
				var normal = {
					length: d,
					direction: {
						x: 0,
						y: -1
					}
				};
				normals.push(normal);
			}
			
			var normal = normals[0];
			for (var i=0,l=normals.length;i<l;i++) {
				// normal = normal.length() > normals[i].length() ? 
				normal = normal.length > normals[i].length ? 
					normals[i] : 
					normal;
			}
			if (normal) {
				// direction1 = normal.direction;
				direction1.x = normal.direction.x;
				direction1.y = normal.direction.y;
			}
		}
		
		// direction2 = direction1.multiply(-1);
		direction2.x = direction1.x * -1;
		direction2.y = direction1.y * -1;
		
		var manifold1 = new Manifold(object1, object2),
			manifold2 = new Manifold(object2, object1);
		manifold1.direction = direction1;
		manifold2.direction = direction2;
		
		this.manifolds = [manifold1, manifold2];
		this.stepCount = 0;
		this.world = object1.world;
		this.object1 = object1;
		this.object2 = object2;
		this.update();
		
		var manifolds = this.manifolds;
		for (var i=0,l=manifolds.length;i<l;i++) {
			var manifold = manifolds[i];
			manifold.object.createContact(this, manifold);
		}
	};
	Contact.prototype = {
		update: function() {
			this.stepCount = this.world.stepCount;
			
			var manifolds = this.manifolds;
			for (var i=0,l=manifolds.length;i<l;i++) {
				var manifold = manifolds[i];
				manifold.object.updateContact(this, manifold);
			}
		},
		solve: function() {
			var manifolds = this.manifolds;
			for (var i=0,l=manifolds.length;i<l;i++) {
				var manifold = manifolds[i];
				manifold.object.beforeSolve(this, manifold);
				manifold.solve();
				manifold.object.afterSolve(this, manifold);
			}
		},
		destroy: function() {
			this._removeFromList(this.world.contacts);
			this._removeFromList(this.object1.contacts);
			this._removeFromList(this.object2.contacts);
			
			var manifolds = this.manifolds;
			for (var i=0,l=manifolds.length;i<l;i++) {
				var manifold = manifolds[i];
				manifold.object.destroyContact(this, manifold);
			}
		},
		_removeFromList: function(contacts) {
			for (var i=0,l=contacts.length;i<l;i++) {
				if (contacts[i] == this) {
					delete contacts[i];
					contacts.splice(i, 1);
				}
			}
		}
	};
	
	var Collide = function(object1, object2) {
		if (!CheckContact(object1, object2)) {
			return;
		}
		
		var list = object1.contacts,
			contact = null;
		for (var i=0,l=list.length;i<l;i++) {
			var c = list[i];
			if (c.manifolds[0].opponent === object2 || 
				c.manifolds[1].opponent === object2) {
				contact = c;
				break;
			}
		}
		
		if (contact) {
			contact.update();
		} else {
			contact = new Contact(object1, object2);
			object1.contacts.push(contact);
			object2.contacts.push(contact);
			object1.world.contacts.push(contact);
		}
	};
	
	var CheckContact = function(object1, object2) {
		return object1._maxPos.x >= object2._minPos.x && 
			object1._minPos.x <= object2._maxPos.x &&
			object1._maxPos.y >= object2._minPos.y && 
			object1._minPos.y <= object2._maxPos.y;
	};
	
	var Model = function() {
		var newObject = function(option) {
			this._init(option);
		};
		
		/*
			object <- object.prototype 
				<- object.prototype.prototype( = Model.prototype)
		*/
		var newModel = function() {};
		newModel.prototype = Model.defaults;
		newObject.prototype = new newModel();
		
		return newObject;
	};
	Model.defaults = {
		speed: new Vec(),
		force: new Vec(),
		accel: new Vec(),
		center: new Vec(),
		centerTmp: new Vec(),
		size: new Vec(0, 0),
		gravity: new Vec(0, 10),
		weight: 1, // 質量
		elastic: 7, // 反発係数　→　バネ定数 （侵入量が減る）
		viscosity: 3, // 粘性係数　→　ダンパ係数 （速度が落ちる）
		friction: 0.1, // 摩擦係数
		fixed: false,
		contacts: [],
		init: function(option) {},
		beforeStep: function(time) {},
		afterStep: function(time) {},
		createContact: function(contact, manifold) {},
		destroyContact: function(contact, manifold) {},
		updateContact: function(contact, manifold) {},
		beforeSolve: function(contact, manifold) {},
		afterSolve: function(contact, manifold) {},
		_init: function(option) {
			this.speed = this.speed.copy();
			this.force = this.force.copy();
			this.accel = this.accel.copy();
			this.center = this.center.copy();
			this.centerTmp = this.center.copy();
			this.size = this.size.copy();
			this.gravity = this.gravity.copy();
			this.contacts = [];
			Extend(this, option);
			
			this.init(option);
		},
		_makeCache: function() {
			this._maxTmpPos = this.maxTmpPos();
			this._minTmpPos = this.minTmpPos();
			this._maxPos = this.maxPos();
			this._minPos = this.minPos();
		},
		_step: function(time) {
			this.beforeStep(time);
			
			// this.applyForce(this.gravity.multiply(this.weight));
			this.applyForce({
				x: this.gravity.x * this.weight,
				y: this.gravity.y * this.weight
			});
			// this.speed = this.speed.add(this.accel.multiply(time));
			this.speed.x += this.accel.x * time;
			this.speed.y += this.accel.y * time;
			//this.centerTmp = this.center.copy();
			this.centerTmp.x = this.center.x;
			this.centerTmp.y = this.center.y;
			//this.center = this.center.add(this.speed.multiply(time));
			this.center.x += this.speed.x * time;
			this.center.y += this.speed.y * time;
			this._makeCache();
			
			this.afterStep(time);
			
			this.resetForce();
		},
		maxTmpPos: function() {
			// return this.centerTmp.add(this.size.divide(2));
			return {
				x: this.centerTmp.x + this.size.x/2,
				y: this.centerTmp.y + this.size.y/2
			};
		},
		minTmpPos: function() {
			// return this.centerTmp.subtract(this.size.divide(2));
			return {
				x: this.centerTmp.x - this.size.x/2,
				y: this.centerTmp.y - this.size.y/2
			};
		},
		maxPos: function() {
			// return this.center.add(this.size.divide(2));
			return {
				x: this.center.x + this.size.x/2,
				y: this.center.y + this.size.y/2
			};
		},
		minPos: function() {
			// return this.center.subtract(this.size.divide(2));
			return {
				x: this.center.x - this.size.x/2,
				y: this.center.y - this.size.y/2
			};
		},
		applyForce: function(force) {
			// this.force = this.force.add(force);
			this.force.x += force.x;
			this.force.y += force.y;
			// this.accel = this.accel.add(force.divide(this.weight));
			this.accel.x += force.x/this.weight;
			this.accel.y += force.y/this.weight;
		},
		resetForce: function() {
			// this.accel = new Vec();
			this.accel.x = 0;
			this.accel.y = 0;
		}
	};
	
	var Rdc = new RDC(Collide);
	
	var World = function(option) {
		this.objects = [];
		this.size = new Vec(0, 0);
		this.stepCount = 0;
		this.contacts = [];
		
		Extend(this, option);
		
		this.init(option);
	};
	World.prototype = {
		step: function(time) {
			this._createObject();
			
			this.beforeStep(time);
			
			this.stepCount++;
			
			// 衝突情報取得
			if (this.objects < 100)  {
				Rdc.bruteForce(this.objects);
			} else {
				Rdc.recursiveClustering(this.objects, 0, 1);
			}
			
			// 衝突処理
			var contacts = this.contacts;
			for (var i=0;i<contacts.length;i++) {
				var contact = contacts[i];
				if (contact.stepCount !== this.stepCount) {
					contact.destroy();
					i--;
				} else {
					contact.solve();
				}
			}
			
			// 各アイテムの進行
			for (var i=0,l=this.objects.length;i<l;i++) {
				var object = this.objects[i];
				if (object) {
					object._step(time);
				}
			}
			
			this.afterStep(time);
			
			return this;
		},
		_createObject: function() {
			var objects = this._stackObjects;
			for (var i=0,l=objects.length;i<l;i++) {
				var object = objects[i];
				object.world = this;
				this.objects.push(object);
				object.centerTmp.x = object.center.x;
				object.centerTmp.y = object.center.y;
				object._makeCache();
			}
			this._stackObjects = [];
		},
		createObject: function(object) {
			this._stackObjects.push(object);
		},
		destroyObject: function(object) {
			if (object) {
				for (var i=0,l=object.contacts.length;i<l;i++) {
					var contact = object.contacts[i];
					if (contact) {
						contact.destroy();
					}
				}
				for (i=0,l=this.objects.length;i<l;i++) {
					if (this.objects[i] === object) {
						delete this.objects[i];
						this.objects.splice(i, 1);
					}
				}
			}
		},
		destroy: function() {
			for (var i=0,l=this.objects.length;i<l;i++) {
				this.destroyObject(this.objects[i]);
			}
		},
		init: function(option) {},
		beforeStep: function(time) {},
		afterStep: function(time) {},
		_stackObjects: []
	};
	
	return {
		Vec: Vec,
		World: World,
		Model: Model
	};
})();