A Quadtree-Based Collision System in JavaScript

The JavaScript code below, when run, will create a playfield full of small circular bodies, each moving in a random direction. When two circles collide, they will bounce off of each other and move in different directions. To see the code in action, copy it into an .html file and open that file in a web browser that runs JavaScript.

My goal was to optimize the detection of collisions between a large number of objects, with an eye towards using the system in a video game. To do this, I made use of a data structure called a “quadtree”. See the Wikipedia article for details.

Since the name of the game was optimization, I also made some (somewhat uncharacteristic) efforts to limit memory usage and the creation of new objects with the “new” keyword, by storing no-longer-needed object instances for later recycling. Specifically, I was able to mostly prevent the creation of countless new Coords, Collision, and SpaceTreeNode objects after the initial few seconds. Honestly, though, I’m not sure how much good it did. I watched the web browser’s memory usage at runtime–it counted up for a while and then leveled off, but it was doing that before. Garbage collection can be frustratingly hands-off these days.

Also, the physics are a little off, in that, if the particles start off or otherwise get too close to each other, they will stick together and spin or vibrate, rather than bouncing apart. Since the point of this exercise was the collision detection, rather than the collision response, I left that alone for now. I guess I actually kind of like it–it makes the simulation more interesting, at least.

UPDATE 2016/02/28 – I have modified the collision response algorithm so that it adjusts the positions of the colliding bodies in addition their velocities. This prevents the bodies from sticking together, although as I mentioned it was actually kind of more interesting that way.

CollisionQuadtree


<html>
<body>
<div id="divMain" />
<script type="text/javascript">
	
// main

function main()
{
	var worldSize = new Coords(256, 256);

	var world = Demo.worldGenerate(worldSize, 64);

	Globals.Instance.initialize
	(
		new DisplayHelper(world.size),
		world		
	);
}

// extensions

function ArrayExtensions()
{
	// extension class
}
{
	Array.prototype.append = function(other)
	{
		for (var i = 0; i < other.length; i++)
		{
			this.push(other[i]);
		}
	}

	Array.prototype.contains = function(itemToFind)
	{
		return (this.indexOf(itemToFind) != -1);
	}

	Array.prototype.dequeue = function()
	{
		var returnValue = this[0];
		this.removeAt(0);
		return returnValue;
	}

	Array.prototype.insert = function(itemToInsert, indexToInsertAt)
	{
		this.splice(indexToInsertAt, 0, itemToInsert);
	}

	Array.prototype.remove = function(itemToRemove)
	{
		this.removeAt(this.indexOf(itemToRemove));
	}

	Array.prototype.removeAt = function(indexOfItemToRemove)
	{
		if (indexOfItemToRemove >= 0)
		{
			this.splice(indexOfItemToRemove, 1);
		}
	}
}

// classes

function Body(name, color, radius, pos, vel)
{
	this.name = name;
	this.color = color;
	this.radius = radius;
	this.pos = pos;
	this.vel = vel;

	this.sizeHalf = new Coords(this.radius, this.radius);

	this.bounds = new Bounds
	(
		this.pos.clone().subtract(this.sizeHalf),
		this.pos.clone().add(this.sizeHalf)
	);
}
{
	Body.prototype.boundsRecalculate = function()
	{
		this.bounds.min.overwriteWith(this.pos).subtract(this.sizeHalf);
		this.bounds.max.overwriteWith(this.pos).add(this.sizeHalf);
	}
}

function Bounds(min, max)
{
	this.min = min;
	this.max = max;
}
{
	Bounds.prototype.containsPos = function(posToCheck)
	{
		return posToCheck.isWithinRangeMinMax(this.min, this.max);
	}

	Bounds.prototype.minAndMax = function()
	{
		return [ this.min, this.max ];
	}
}

function Collision(body0, body1)
{
	this.bodies = [];
	this.initialize(body0, body1);
}
{
	// static helper variables

	Collision.BodyVelsAfterCollision = [ new Coords(), new Coords() ];
	Collision.CollisionsDeallocated = [];
	Collision.Displacement = new Coords();	
	Collision.VelocityRelative = new Coords();

	// static methods

	Collision.allocate = function(body0, body1)
	{
		var collisionsDeallocated = Collision.CollisionsDeallocated;
		if (collisionsDeallocated.length > 0)
		{
			returnValue = collisionsDeallocated.dequeue();
			returnValue.initialize(body0, body1);
		}
		else
		{
			returnValue = new Collision(body0, body1);
		}

		return returnValue;		
	}

	Collision.collisionsOfBodiesAddToList = function(bodiesToCheck, collisionsSoFar)
	{	
		var displacement = Collision.Displacement;

		for (var i = 0; i < bodiesToCheck.length; i++)
		{
			var bodyThis = bodiesToCheck[i];

			for (var j = i + 1; j < bodiesToCheck.length; j++)
			{
				var bodyOther = bodiesToCheck[j];

				var distanceBetweenBodyCenters = displacement.overwriteWith
				(
					bodyOther.pos
				).subtract
				(
					bodyThis.pos
				).magnitude();

				var sumOfBodyRadii = bodyThis.radius + bodyOther.radius;

				if (distanceBetweenBodyCenters < sumOfBodyRadii)
				{
					var collision = Collision.allocate
					(
						bodyThis, 
						bodyOther
					);
					collisionsSoFar.push(collision);
				}				
			}
		}	

		return collisionsSoFar;
	}

	Collision.deallocateMany = function(collisions)
	{
		for (var i = 0; i < collisions.length; i++)
		{
			var collision = collisions[i];
			collision.deallocate();
		}	
		collisions.length = 0;
	}

	// instance methods

	Collision.prototype.applyEffectsToBodies = function()
	{
		var bodyPositionsAfterCollision = Collision.BodyPositionsAfterCollision;
		var bodyVelsAfterCollision = Collision.BodyVelsAfterCollision;
		var displacement = Collision.Displacement;
		var velocityRelative = Collision.VelocityRelative;

		var body0 = this.bodies[0];
		var body1 = this.bodies[1];

		var sumOfBodyRadii = 
			body0.radius + body1.radius; 

		velocityRelative.overwriteWith
		(
			body0.vel
		).subtract
		(
			body1.vel
		);
 
		displacement.overwriteWith
		(
			body0.pos
		).subtract
		(
			body1.pos
		);

		var distanceBetweenBodyCenters = displacement.magnitude();
		var overlap = sumOfBodyRadii - distanceBetweenBodyCenters;
		var overlapHalf = overlap / 2;

		var normalAtCollision = displacement.divideScalar
		(
			distanceBetweenBodyCenters
		);

		var velocityAlongNormal = normalAtCollision.multiplyScalar
		(
			velocityRelative.dotProduct
			(
				normalAtCollision
			)
		);

		velocityRelative.subtract
		(
			velocityAlongNormal
		).multiplyScalar
		(
			-1
		);

		for (var i = 0; i < this.bodies.length; i++)
		{
			var bodyThis = this.bodies[i];
			var bodyOther = this.bodies[1 - i];
		
			var bodyPosAfterCollision = bodyPositionsAfterCollision[i];
			var bodyVelAfterCollision = bodyVelsAfterCollision[i];

			var multiplier = (i == 0 ? -1 : 1);

			bodyPosAfterCollision.overwriteWith
			(
				normalAtCollision
			).multiplyScalar
			(
				multiplier * overlapHalf
			).add
			(
				bodyThis.pos
			);
 
			bodyVelAfterCollision.overwriteWith
			(
				velocityRelative
			).multiplyScalar
			(
				multiplier
			).add
			(
				bodyOther.vel
			);
		}

		for (var i = 0; i < this.bodies.length; i++)
		{
			var bodyThis = this.bodies[i];
			var bodyPosAfterCollision = bodyPositionsAfterCollision[i];
			var bodyVelAfterCollision = bodyVelsAfterCollision[i];

			bodyThis.pos.overwriteWith
			(
				bodyPosAfterCollision
			);
			bodyThis.vel.overwriteWith
			(
				bodyVelAfterCollision
			);
		}
	}

	Collision.prototype.deallocate = function()
	{
		Collision.CollisionsDeallocated.push(this);
	}

	Collision.prototype.initialize = function(body0, body1)
	{
		this.bodies[0] = body0;
		this.bodies[1] = body1;
	}
}

function Coords(x, y)
{
	this.x = x;
	this.y = y;
}
{
	Coords.prototype.add = function(other)
	{
		this.x += other.x;
		this.y += other.y;
		return this;
	}

	Coords.prototype.clear = function()
	{
		this.x = 0;
		this.y = 0;
		return this;
	}

	Coords.prototype.clone = function()
	{
		return new Coords(this.x, this.y);
	}

	Coords.prototype.divide = function(other)
	{
		this.x /= other.x;
		this.y /= other.y;
		return this;
	}

	Coords.prototype.divideScalar = function(scalar)
	{
		this.x /= scalar;
		this.y /= scalar;
		return this;
	}

	Coords.prototype.dotProduct = function(other)
	{
		return this.x * other.x + this.y * other.y;
	}

	Coords.prototype.floor = function()
	{
		this.x = Math.floor(this.x);
		this.y = Math.floor(this.y);
		return this;
	}

	Coords.prototype.magnitude = function()
	{
		return Math.sqrt(this.x * this.x + this.y * this.y);
	}

	Coords.prototype.multiply = function(other)
	{
		this.x *= other.x;
		this.y *= other.y;
		return this;
	}

	Coords.prototype.multiplyScalar = function(scalar)
	{
		this.x *= scalar;
		this.y *= scalar;
		return this;
	}

	Coords.prototype.normalize = function()
	{
		return this.divideScalar(this.magnitude());
	}

	Coords.prototype.overwriteWith = function(other)
	{
		this.x = other.x;
		this.y = other.y;
		return this;
	}

	Coords.prototype.randomize = function()
	{
		this.x = Math.random();
		this.y = Math.random();
		return this;
	}

	Coords.prototype.subtract = function(other)
	{
		this.x -= other.x;
		this.y -= other.y;
		return this;
	}

	Coords.prototype.trimToRangeMax = function(rangeMax)
	{
		if (this.x < 0)
		{
			this.x = 0;
		}
		else if (this.x > rangeMax.x)
		{
			this.x = rangeMax.x;
		}

		if (this.y < 0)
		{
			this.y = 0;
		}
		else if (this.y > rangeMax.y)
		{
			this.y = rangeMax.y;
		}

		return this; 
	}

	Coords.prototype.wrapToRangeMax = function(rangeMax)
	{
		if (this.x < 0)
		{
			this.x += rangeMax.x;		
		}
		else if (this.x > rangeMax.x)
		{
			this.x -= rangeMax.x;
		}

		if (this.y < 0)
		{
			this.y += rangeMax.y;		
		}
		else if (this.y > rangeMax.y)
		{
			this.y -= rangeMax.y;
		}

		return this;
	}
}

function DisplayHelper(viewSize)
{
	this.viewSize = viewSize;

	this.colorBack = "White";
	this.colorFore = "Gray";
	this.fontHeight = 10;

	// helper variables
	this.zeroes = new Coords(0, 0);
	//this.drawPos = new Coords();
}
{
	DisplayHelper.prototype.clear = function()
	{
		this.drawRectangle
		(
			this.zeroes, 
			this.viewSize, 
			this.colorFore, 
			this.colorBack
		);
	}

	DisplayHelper.prototype.drawRectangle = function(pos, size, colorBorder, colorFill)
	{
		if (colorFill != null)
		{
			this.graphics.fillStyle = colorFill;
			this.graphics.fillRect
			(
				pos.x, pos.y, size.x, size.y
			);
		}

		this.graphics.strokeStyle = colorBorder;
		this.graphics.strokeRect
		(
			pos.x, pos.y, size.x, size.y
		);
	}

	DisplayHelper.prototype.drawBody = function(body)
	{
		this.drawCircle(body.pos, body.radius, body.color);
	}

	DisplayHelper.prototype.drawCircle = function(center, radius, color)
	{
		this.graphics.beginPath();
		this.graphics.arc
		(
			center.x, center.y,
			radius,
			0, Math.PI * 2
		);
		this.graphics.strokeStyle = color;
		this.graphics.stroke();
	}

	DisplayHelper.prototype.drawSpaceTree = function(spaceTree)
	{
		this.drawSpaceTreeNode(spaceTree.nodeRoot);
	}

	DisplayHelper.prototype.drawSpaceTreeNode = function(spaceTreeNode)
	{
		this.drawRectangle
		(
			spaceTreeNode.pos, 
			spaceTreeNode.size(), 
			"LightGreen"
		);

		var children = spaceTreeNode.children;
		
		if (children.length > 0)
		{
			for (var i = 0; i < children.length; i++)
			{
				var child = children[i];
				this.drawSpaceTreeNode(child);
			}
		}
	}

	DisplayHelper.prototype.drawWorld = function(world)
	{
		this.clear();

		this.drawSpaceTree(world.collisionTree);

		var bodies = world.bodies;
		for (var i = 0; i < bodies.length; i++)
		{
			var body = bodies[i];
			this.drawBody(body);
		}
	}

	DisplayHelper.prototype.initialize = function()
	{
		var canvas = document.createElement("canvas");
		canvas.width = this.viewSize.x;
		canvas.height = this.viewSize.y;

		var divMain = document.getElementById("divMain");
		divMain.appendChild(canvas);
		
		this.graphics = canvas.getContext("2d");
	}
}

function Globals()
{
	// do nothing
}
{
	// instance

	Globals.Instance = new Globals();
	
	// methods

	Globals.prototype.initialize = function(displayHelper, world)
	{
		this.displayHelper = displayHelper;
		this.displayHelper.initialize();

		this.world = world;	
		
		this.timer = setInterval
		(
			this.handleEventTimerTick.bind(this),
			100 // millisecondsPerTimerTick
		);
	}

	// events

	Globals.prototype.handleEventTimerTick = function()
	{
		this.world.updateForTimerTick();
		this.displayHelper.drawWorld(this.world);
	}
}

function SpaceTree(nodeSizeInChildren, depthMax, sizeOfNodeRoot)
{
	this.nodeSizeInChildren = nodeSizeInChildren;
	this.depthMax = depthMax;

	this.nodeSizeInChildrenMinusOnes = this.nodeSizeInChildren.clone().subtract
	(
		new Coords(1, 1)
	);

	var sizeAtDepth = sizeOfNodeRoot.clone();
	this.sizesAtDepths = [];
	this.childOffsetsForDepths = []; 
	this.startAndEndOffsetsForDepths = []; 
	for (var i = 0; i <= this.depthMax; i++)
	{
		this.sizesAtDepths.push(sizeAtDepth.clone());
		sizeAtDepth.divide(this.nodeSizeInChildren);

		this.childOffsetsForDepths.push(new Coords());

		this.startAndEndOffsetsForDepths.push([ new Coords(), new Coords() ]);
	}

	this.offsetsWithinSiblings = [];
	var offsetWithinSiblings = new Coords();
	for (var y = 0; y < this.nodeSizeInChildren.y; y++)
	{
		offsetWithinSiblings.y = y;

		for (var x = 0; x < this.nodeSizeInChildren.x; x++)
		{
			offsetWithinSiblings.x = x;

			this.offsetsWithinSiblings.push
			(
				offsetWithinSiblings.clone()
			);
		}
	}

	this.bodies = [];
	this.bodyNameToNodesOccupiedLookup = [];
	this.leafNodesOccupiedByMultipleBodies = [];

	this.nodeRoot = new SpaceTreeNode
	(
		this, 
		null, // parent
		new Coords(0, 0) // offsetsWithinSiblings
	);

	this.nodesDeallocated = [];
}
{
	// static helper variables

	SpaceTree.BodyPairsPotentiallyCollidingLookup = {};
	SpaceTree.Collisions = [];

	// instance methods

	SpaceTree.prototype.bodiesAddMany = function(bodiesToAdd)
	{
		for (var i = 0; i < bodiesToAdd.length; i++)
		{
			var body = bodiesToAdd[i];
			this.bodyAdd(body);
		}

		var nodesToCheck = this.leafNodesOccupiedByMultipleBodies;

		this.nodeRoot.leafNodesSharedAddToList
		(
			nodesToCheck
		);
		
		var bodyPairsPotentiallyCollidingLookup = 
			SpaceTree.BodyPairsPotentiallyCollidingLookup;
			
		for (var i = 0; i < nodesToCheck.length; i++)
		{
			var node = nodesToCheck[i];
			var nodeBodies = node.bodies;

			for (var j = 0; j < nodeBodies.length; j++)
			{
				var bodyThis = nodeBodies[j];
				var bodyThisName = bodyThis.name;

				for (var k = j + 1; k < nodeBodies.length; k++)
				{
					var bodyOther = nodeBodies[k];
					var bodyOtherName = bodyOther.name;

					// hack - ID is not satisfactorily unique.
					var bodyPairID;
					if (bodyThisName < bodyOtherName)
					{
						bodyPairID = bodyThisName + bodyOtherName;
					}
					else
					{
						bodyPairID = bodyOtherName + bodyThisName;	
					}

					if (bodyPairsPotentiallyCollidingLookup[bodyPairID] == null)
					{
						var bodyPair = [ bodyThis, bodyOther ];
						bodyPairsPotentiallyCollidingLookup[bodyPairID] = bodyPair;
					}
				}
			}
		}

		var collisions = SpaceTree.Collisions;

		for (var bodyPairID in bodyPairsPotentiallyCollidingLookup)
		{
			var bodyPair = bodyPairsPotentiallyCollidingLookup[bodyPairID];

			Collision.deallocateMany(collisions);

			Collision.collisionsOfBodiesAddToList
			(
				bodyPair, collisions
			);

			for (var j = 0; j < collisions.length; j++)
			{
				var collision = collisions[j];
				collision.applyEffectsToBodies();
			}

			delete bodyPairsPotentiallyCollidingLookup[bodyPairID];
		}
	}

	SpaceTree.prototype.bodiesRemoveAll = function()
	{
		while (this.bodies.length > 0)
		{
			var body = this.bodies[0];
			this.bodyRemove(body);
		}

		this.leafNodesOccupiedByMultipleBodies.length = 0;
	}

	SpaceTree.prototype.bodyAdd = function(bodyToAdd)
	{
		this.bodies.push(bodyToAdd);

		var bodyName = bodyToAdd.name;
		var nodesOccupiedByBody = this.bodyNameToNodesOccupiedLookup[bodyName];
		if (nodesOccupiedByBody == null)
		{
			nodesOccupiedByBody = [];
			this.bodyNameToNodesOccupiedLookup[bodyName] = nodesOccupiedByBody;
		}

		this.nodeRoot.bodyAdd(bodyToAdd, nodesOccupiedByBody);
	}

	SpaceTree.prototype.bodyRemove = function(bodyToRemove)
	{
		this.bodies.remove(bodyToRemove);

		var nodesOccupiedByBody = this.bodyNameToNodesOccupiedLookup[bodyToRemove.name];
		if (nodesOccupiedByBody != null)
		{
			for (var i = nodesOccupiedByBody.length - 1; i >= 0; i--)
			{
				var nodeOccupied = nodesOccupiedByBody[i];
				nodeOccupied.bodies.remove(bodyToRemove);
				nodeOccupied.childrenDeallocateIfEmpty();
			}				
			nodesOccupiedByBody.length = 0; 
		}	
	}

	SpaceTree.prototype.nodeAllocate = function(parent, offsetWithinSiblings)
	{
		var returnValue;

		if (this.nodesDeallocated.length > 0)
		{
			returnValue = this.nodesDeallocated.dequeue();
			returnValue.initialize(this, parent, offsetWithinSiblings);
		}
		else
		{
			returnValue = new SpaceTreeNode
			(
				this, parent, offsetWithinSiblings
			);
		}

		return returnValue;
	}
}

function SpaceTreeNode(tree, parent, offsetWithinSiblings)
{
	this.pos = new Coords();
	this.bounds = new Bounds(new Coords(), new Coords());
	this.children = [];
	this.bodies = [];

	this.initialize(tree, parent, offsetWithinSiblings);
}
{
	// static helper variables

	SpaceTreeNode.AncestorPos = new Coords();

	// instance methods

	SpaceTreeNode.prototype.ancestorsAndSelf = function()
	{
		var returnValues = [];

		var nodeCurrent = this;

		while (nodeCurrent != null)
		{
			returnValues.insert(nodeCurrent, 0);
			nodeCurrent = nodeCurrent.parent;
		}

		return returnValues;
	}

	SpaceTreeNode.prototype.bodyAdd = function
	(
		bodyToAdd, 
		nodesOccupiedByBodySoFar
	)
	{
		this.bodies.push(bodyToAdd);

		nodesOccupiedByBodySoFar.push(this);

		var depth = this.depth();
		var depthNext = depth + 1;

		if (depthNext >= this.tree.depthMax)
		{
			return;
		}

		this.childrenCreateIfNecessary();

		var childOffsetsStartAndEnd = this.startAndEndOffsetsForChildrenInBounds
		(
			bodyToAdd.bounds
		);

		var childOffsetStart = childOffsetsStartAndEnd[0];
		var childOffsetEnd = childOffsetsStartAndEnd[1];

		var childOffset = this.tree.childOffsetsForDepths[depth];
 
		for (var y = childOffsetStart.y; y <= childOffsetEnd.y; y++)	
		{
			childOffset.y = y;

			for (var x = childOffsetStart.x; x <= childOffsetEnd.x; x++)
			{
				childOffset.x = x;
	
				var child = this.childAtOffset(childOffset);

				child.bodyAdd
				(
					bodyToAdd, 
					nodesOccupiedByBodySoFar
				);
			}
		}
	}

	SpaceTreeNode.prototype.childAtOffset = function(childOffset)
	{
		return this.children[this.childIndicesFlatten(childOffset)];
	}

	SpaceTreeNode.prototype.childIndicesFlatten = function(childOffset)
	{
		return childOffset.y * this.tree.nodeSizeInChildren.x + childOffset.x;
	}

	SpaceTreeNode.prototype.childrenCreate = function()
	{
		var offsetsWithinSiblings = this.tree.offsetsWithinSiblings;

		for (var i = 0; i < offsetsWithinSiblings.length; i++)
		{
			var offsetWithinSiblings = offsetsWithinSiblings[i];

			var child = this.tree.nodeAllocate
			(
				this, // parent
				offsetWithinSiblings
			);

			this.children.push(child);
		}

		return this.children;
	}

	SpaceTreeNode.prototype.childrenDeallocateIfEmpty = function()
	{
		if (this.children.length > 0)
		{
			if (this.bodies.length == 0)
			{
				for (var i = 0; i < this.children.length; i++)
				{
					var child = this.children[i];
					child.deallocate();				
				}
				this.children.length = 0;				
			}
		}
	}

	SpaceTreeNode.prototype.childrenCreateIfNecessary = function()
	{
		if (this.children.length == 0)
		{
			this.childrenCreate();
		}

		return this.children;
	}

	SpaceTreeNode.prototype.deallocate = function()
	{
		this.tree.nodesDeallocated.push(this);

		if (this.children.length > 0)
		{
			for (var i = 0; i < this.children.length; i++)
			{
				var child = this.children[i];
				child.deallocate();
			}

			this.children.length = 0;
		}		
	}

	SpaceTreeNode.prototype.depth = function()
	{
		var returnValue = 0;

		var nodeCurrent = this.parent;

		while (nodeCurrent != null)
		{
			returnValue++;
			nodeCurrent = nodeCurrent.parent;
		}

		return returnValue;
	}

	SpaceTreeNode.prototype.initialize = function(tree, parent, offsetWithinSiblings)
	{
		this.tree = tree;
		this.parent = parent;
		this.offsetWithinSiblings = offsetWithinSiblings;

		this.posRecalculate();

		this.bounds.min.overwriteWith(this.pos);
		this.bounds.max.overwriteWith(this.pos).add(this.size());
	}

	SpaceTreeNode.prototype.leafNodesSharedAddToList = function(leafNodesSharedSoFar)
	{
		if (this.children.length == 0)
		{
			if (this.bodies.length > 1)
			{
				leafNodesSharedSoFar.push(this);
			}
		}
		else
		{
			for (var i = 0; i < this.children.length; i++)
			{
				var child = this.children[i];
				child.leafNodesSharedAddToList(leafNodesSharedSoFar);
			}
		}

		return leafNodesSharedSoFar;
	}

	SpaceTreeNode.prototype.posRecalculate = function()
	{
		var returnValue = this.pos.clear();

		var ancestorPos = SpaceTreeNode.AncestorPos;

		var ancestors = this.ancestorsAndSelf();
		for (var i = 0; i < ancestors.length; i++)
		{
			var ancestor = ancestors[i];
			returnValue.add
			(
				ancestorPos.overwriteWith
				(
					ancestor.size()
				).multiply
				(
					ancestor.offsetWithinSiblings
				)
			);
		}

		return returnValue;
	}

	SpaceTreeNode.prototype.startAndEndOffsetsForChildrenInBounds = function(bounds)
	{
		var depth = this.depth();

		var returnValues = this.tree.startAndEndOffsetsForDepths[depth];
		var offset = this.tree.childOffsetsForDepths[depth];

		var sizeInChildrenMinusOnes = this.tree.nodeSizeInChildrenMinusOnes;
		var sizeOfChildren = this.tree.sizesAtDepths[depth + 1];

		var boundsMinAndMax = bounds.minAndMax();


		for (var i = 0; i < boundsMinAndMax.length; i++)
		{
			var boundsExtreme = boundsMinAndMax[i];

			offset.overwriteWith
			(
				boundsExtreme
			).subtract
			(
				this.pos
			).divide
			(
				sizeOfChildren
			).floor().trimToRangeMax
			(
				sizeInChildrenMinusOnes
			);

			returnValues[i].overwriteWith(offset);
		}

		return returnValues;
	}

	SpaceTreeNode.prototype.size = function()
	{
		return this.tree.sizesAtDepths[this.depth()];
	}
}


function World(size, bodies)
{
	this.size = size;
	this.bodies = bodies;

	this.collisionTree = new SpaceTree
	(
		new Coords(2, 2), // nodeSizeInChildren,
		6, // depthMax
		this.size.clone()
	);
}
{
	World.prototype.updateForTimerTick = function()
	{
		this.collisionTree.bodiesRemoveAll();

		for (var i = 0; i < this.bodies.length; i++)
		{
			var body = this.bodies[i];

			body.pos.add
			(
				body.vel
			).wrapToRangeMax
			(
				this.size
			);
			body.boundsRecalculate();
		}

		this.collisionTree.bodiesAddMany(this.bodies);
	
	}
}

// demo

function Demo()
{
	// static class
}
{
	Demo.worldGenerate = function(worldSize, numberOfBodiesToGenerate)
	{
		var bodiesGenerated = [];

		var ones = new Coords(1, 1);

		for (var i = 0; i < numberOfBodiesToGenerate; i++)
		{
			var body = new Body
			(
				"Body" + i,
				"Blue", // color
				4, // radius
				// pos
				new Coords().randomize().multiply
				(
					worldSize
				),
				// vel
				new Coords().randomize().multiplyScalar
				(
					2
				).subtract
				(
					ones
				).normalize()
			);

			bodiesGenerated.push(body);
		}

		var world = new World
		(
			worldSize,	
			bodiesGenerated
		);

		return world;
	}
}

// run

main();
	
</script>
</body>
</html>

Advertisements
This entry was posted in Uncategorized and tagged , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s