Detecting Collisions of Shapes in JavaScript

The JavaScript program below, when run, displays a wraparound playfield filled with squares moving in random directions at random speeds and rotating at random rates. When two squares overlap, the collisions between them are highlighted with small circles.

The program performs no collision response except for highlighting the collisions themselves. The purpose of this program is to serve as a relatively simple basis for further work along these lines.

SquaresColliding


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

// main

function main()
{
	var viewSize = new Coords(200, 200);

	var world = Demo.worldRandom
	(
		viewSize, // worldSize
		10, // bodyDimension
		32 // numberOfBodies
	);

	Globals.Instance.initialize
	(
		new Display(viewSize),
		world
	);
}

// extensions

function ArrayExtensions()
{
	// extension class
}
{
	Array.prototype.clone = function()
	{
		var returnValues = [];

		for (var i = 0; i < this.length; i++)
		{
			var element = this[i];
			var elementCloned = element.clone();
			returnValues.push(elementCloned);
		}

		return returnValues;
	}

	Array.prototype.overwriteWith = function(other)
	{
		for (var i = 0; i < this.length; i++)
		{
			var elementThis = this[i];
			var elementOther = other[i];
			elementThis.overwriteWith(elementOther);
		}

		return this;
	}
}

// classes

function Body(defn, pos, vel, orientation, angVel)
{
	this.defn = defn;
	this.pos = pos;
	this.vel = vel;
	this.orientation = orientation;
	this.angVel = angVel;

	this.accel = new Coords(0, 0);
	this.force = new Coords(0, 0);

	this.angAccel = 0;
	this.torque = 0;

	this.shapeTransformed = this.defn.shape.clone();
	this.transformForShape = new TransformMultiple
	([
		new TransformOrient(this.orientation),
		new TransformTranslate(this.pos),
	]);
}
{
	Body.prototype.updateForTimerTick = function(world)
	{
		this.pos.add
		(
			this.vel
		).wrapToRangeMax
		(
			world.size
		);
		this.vel.add(this.accel);
		this.accel.add
		(
			this.force.divideScalar
			(
				this.defn.mass
			)
		);
		this.force.clear();

		this.angAccel += 
			this.torque
			/
			(
				this.defn.mass 
				* this.defn.angularInertiaFactor
			);
		this.torque = 0;
		this.angVel += this.angAccel;
		this.angAccel = 0;
		var forwardAsPolar = Polar.fromCoords
		(
			this.orientation.forward
		);
		forwardAsPolar.angle += this.angVel;
		forwardAsPolar.angle = NumberHelper.wrapValueToRangeMax
		(
			forwardAsPolar.angle, 1	
		);			
		this.orientation.forwardSet
		(
			forwardAsPolar.toCoords()
		);

		this.shapeTransformed.overwriteWith
		(
			this.defn.shape
		).transform
		(
			this.transformForShape
		);
	}
}

function BodyDefn(name, mass, angularInertiaFactor, shape)
{
	this.name = name;
	this.angularInertiaFactor = angularInertiaFactor;
	this.mass = mass;
	this.shape = shape;
}

function Collision(pos, edges)
{
	this.pos = pos;
	this.edges = edges;
}
{
	// static methods

	Collision.ofBodies = function(bodies)
	{
		var returnValues = [];

		var numberOfBodies = bodies.length;
		for (var i = 0; i < numberOfBodies; i++)
		{
			bodyThis = bodies[i];
			
			for (var j = i + 1; j < numberOfBodies; j++)
			{
				bodyOther = bodies[j];

				var collisionsOfShapes = Collision.ofShapes
				([
					bodyThis.shapeTransformed,
					bodyOther.shapeTransformed
				]);

				if (collisionsOfShapes.length > 0)
				{
					for (var c = 0; c < collisionsOfShapes.length; c++)
					{
						var collision = collisionsOfShapes[c];

						collision.bodies = 
						[ 
							bodyThis, bodyOther 
						];
	
						returnValues.push(collision);
					}
				}
			}
		}

		return returnValues;
	}

	Collision.ofEdges = function(edges)
	{
		var returnValue = null;

		var edge0 = edges[0];
		var edge1 = edges[1];

		var edgeProjected = edge1.clone().projectOnto(edge0);
		var edgeProjectedStart = edgeProjected.vertices[0];
		var edgeProjectedDirection = edgeProjected.direction;		

		var distanceAlongEdgeProjectedToXAxis = 
			0 - edgeProjectedStart.y
			/ edgeProjectedDirection.y

		if 
		(
			distanceAlongEdgeProjectedToXAxis > 0 
			&& distanceAlongEdgeProjectedToXAxis < edgeProjected.length
		)
		{
			var distanceAlongEdge0ToIntersection =
				edgeProjectedStart.x 
				+ (edgeProjectedDirection.x * distanceAlongEdgeProjectedToXAxis);

			if 
			(
				distanceAlongEdge0ToIntersection > 0
				&& distanceAlongEdge0ToIntersection < edge0.length
			)
			{
				var collisionPos = edge0.direction.clone().multiplyScalar
				(
					distanceAlongEdge0ToIntersection
				).add
				(
					edge0.vertices[0]
				);

				returnValue = new Collision
				(
					collisionPos,
					edges
				);
			}
		}

		return returnValue;
	}

	Collision.ofShapes = function(shapes)
	{
		var returnValues = [];

		var shape0Edges = shapes[0].edges;
		var shape1Edges = shapes[1].edges;

		for (var i = 0; i < shape0Edges.length; i++)
		{
			var shape0Edge = shape0Edges[i];

			for (var j = 0; j < shape1Edges.length; j++)
			{
				var shape1Edge = shape1Edges[j];
			
				var collision = Collision.ofEdges
				(
					[shape0Edge, shape1Edge]
				);

				if (collision != null)
				{
					collision.shapes = shapes;
					returnValues.push(collision);
				}
			}
		}

		return returnValues;
	}

	// instance methods

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

			// todo - Collision response.
		}
	}
}

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.magnitude = function(other)
	{
		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.overwriteWithXY = function(x, y)
	{
		this.x = x;
		this.y = y;
		return this;
	}

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

	Coords.prototype.right = function()
	{
		var yPrev = this.y;
		this.y = this.x;
		this.x = 0 - yPrev;
		return this;
	}

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

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

	Coords.prototype.wrapToRangeMax = function(max)
	{
		while (this.x < 0)
		{
			this.x += max.x;
		}
		while (this.x > max.x)
		{
			this.x -= max.x;
		}

		while (this.y < 0)
		{
			this.y += max.y;
		}
		while (this.y > max.y)
		{
			this.y -= max.y;
		}

		return this;
	}
}

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

	this.colorBack = "White";
	this.colorFore = "LightGray";

	this.zeroes = new Coords(0, 0);
}
{
	// methods

	Display.prototype.clear = function()
	{
		this.drawRectangle
		(
			this.zeroes, this.viewSize, 
			this.colorFore, this.colorBack
		);
	}

	Display.prototype.drawBody = function(body)
	{
		this.drawShape(body.shapeTransformed);
	}

	Display.prototype.drawCollision = function(collision)
	{
		var collisionPos = collision.pos;

		this.graphics.beginPath();
		this.graphics.arc
		(
			collisionPos.x, collisionPos.y,
			4, // radius
			0, Polar.RadiansPerCycle
		);
		this.graphics.stroke();	
	}

	Display.prototype.drawRectangle = function
	(
		pos, size, colorBorder, colorFill
	)
	{
		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
		);
	}

	Display.prototype.drawShape = function(shape)
	{
		this.graphics.beginPath();

		var vertices = shape.vertices;

		this.graphics.moveTo(vertices[0].x, vertices[0].y);

		for (var i = 1; i < vertices.length; i++)
		{
			var vertex = vertices[i];
			this.graphics.lineTo(vertex.x, vertex.y);
		}

		this.graphics.closePath();
		this.graphics.stroke();
	}

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

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

		this.graphics = canvas.getContext("2d");

		var divMain = document.getElementById("divMain");
		divMain.appendChild(canvas);
	}
}

function Edge(vertices)
{
	this.vertices = vertices;

	this.displacement = new Coords();
	this.direction = new Coords();
	this.right = new Coords();
	this.recalculate();
}
{
	// static methods

	Edge.manyFromVertices = function(vertices)
	{
		var returnValues = [];

		var numberOfVertices = vertices.length;
		for (var i = 0; i < numberOfVertices; i++)
		{
			var iNext = NumberHelper.wrapValueToRangeMax
			(
				i + 1, 
				numberOfVertices
			);

			var vertex = vertices[i];
			var vertexNext = vertices[iNext];

			var edge = new Edge([vertex, vertexNext]);

			returnValues.push(edge);
			
		}

		return returnValues;
	}

	// instance methods

	Edge.prototype.clone = function()
	{
		return new Edge(this.vertices.clone());
	}

	Edge.prototype.projectOnto = function(other)
	{
		for (var i = 0; i < this.vertices.length; i++)
		{
			var vertexThis = this.vertices[i];

			vertexThis.subtract
			(
				other.vertices[0]
			).overwriteWithXY
			(
				vertexThis.dotProduct(other.direction),
				vertexThis.dotProduct(other.right)
			);
		}

		this.recalculate();

		return this;
	}

	Edge.prototype.recalculate = function()
	{
		this.displacement.overwriteWith
		(
			this.vertices[1]
		).subtract
		(
			this.vertices[0]
		);

		this.length = this.displacement.magnitude();

		this.direction.overwriteWith
		(
			this.displacement
		).divideScalar
		(
			this.length
		);

		this.right.overwriteWith
		(
			this.direction
		).right();		
	}
}

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

	Globals.Instance = new Globals();

	// methods

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

		this.display.initialize();		

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

	// events

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

function NumberHelper()
{
	// static class
}
{
	NumberHelper.wrapValueToRangeMax = function(value, max)
	{
		while (value < 0)
		{
			value += max;
		}

		while (value >= max)
		{
			value -= max;
		}

		return value;
	}
}

function Orientation(forward)
{
	this.forward = forward;
	this.right = new Coords();
	this.recalculate();
}
{
	Orientation.prototype.forwardSet = function(value)
	{
		this.forward.overwriteWith(value);
		this.recalculate();
	}

	Orientation.prototype.recalculate = function()
	{
		this.right.overwriteWith(this.forward).right();
	}
}

function Polar(angle, distance)
{
	this.angle = angle; // in cycles
	this.distance = distance;
}
{
	Polar.RadiansPerCycle = Math.PI * 2;	

	Polar.fromCoords = function(coordsToConvert)
	{
		var distance = coordsToConvert.magnitude();

		var angle = NumberHelper.wrapValueToRangeMax
		(
			Math.atan2
			(
				coordsToConvert.y,
				coordsToConvert.x
			) / Polar.RadiansPerCycle,
			1
		);

		var returnValue = new Polar
		(
			angle,
			distance
		);

		return returnValue;
	}

	Polar.prototype.toCoords = function()
	{
		var angleInRadians = 
			this.angle * Polar.RadiansPerCycle;

		var returnValue = new Coords
		(
			Math.cos(angleInRadians),
			Math.sin(angleInRadians)
		).multiplyScalar
		(
			this.distance
		);

		return returnValue;
	}
}

function Shape(vertices)
{
	this.vertices = vertices;
	this.edges = Edge.manyFromVertices(this.vertices);
}
{
	Shape.prototype.clone = function()
	{
		return new Shape
		(
			this.vertices.clone()
		);
	}

	Shape.prototype.overwriteWith = function(other)
	{
		this.vertices.overwriteWith(other.vertices);
		return this;
	}

	Shape.prototype.recalculate = function()
	{
		for (var i = 0; i < this.edges.length; i++)
		{
			var edge = this.edges[i];
			edge.recalculate();
		}
	}

	Shape.prototype.transform = function(transformToApply)
	{
		for (var i = 0; i < this.vertices.length; i++)
		{
			transformToApply.applyToCoords
			(
				this.vertices[i]
			)
		}

		this.recalculate();

		return this;
	}
}

function TransformMultiple(transforms)
{
	this.transforms = transforms;
}
{
	TransformMultiple.prototype.applyToCoords = function(coordsToTransform)
	{
		for (var i = 0; i < this.transforms.length; i++)
		{
			var transform = this.transforms[i];
			transform.applyToCoords(coordsToTransform);
		}
	}
}

function TransformOrient(orientation)
{
	this.orientation = orientation;
}
{
	TransformOrient.prototype.applyToCoords = function(coordsToTransform)
	{
		coordsToTransform.overwriteWithXY
		(
			coordsToTransform.dotProduct
			(
				this.orientation.forward
			),
			coordsToTransform.dotProduct
			(
				this.orientation.right
			)
		);
	}
}

function TransformTranslate(offset)
{
	this.offset = offset;
}
{
	TransformTranslate.prototype.applyToCoords = function(coordsToTransform)
	{
		coordsToTransform.add(this.offset);
	}
}

function World(size, bodies)
{
	this.size = size;
	this.bodies = bodies;		
}
{
	World.prototype.updateForTimerTick = function()
	{
		for (var i = 0; i < this.bodies.length; i++)
		{
			var body = this.bodies[i];
			body.updateForTimerTick(this);
		}

		var collisions = Collision.ofBodies(this.bodies);

		for (var i = 0; i < collisions.length; i++)
		{
			var collision = collisions[i];
			collision.applyEffectsToBodies();
			Globals.Instance.display.drawCollision(collision)
		}

	}
}

// demo

function Demo()
{
	// static class
}
{
	Demo.worldRandom = function(worldSize, dimensionOfBodies, numberOfBodies)
	{
		var bodyDefn = new BodyDefn
		(
			"BodyDefn0",
			1, // mass
			1, // angularInertiaFactor
			new Shape
			([
				new Coords(-dimensionOfBodies, -dimensionOfBodies),
				new Coords(dimensionOfBodies, -dimensionOfBodies),
				new Coords(dimensionOfBodies, dimensionOfBodies),
				new Coords(-dimensionOfBodies, dimensionOfBodies),
			])
		);

		var bodies = [];

		for (var i = 0; i < numberOfBodies; i++)
		{
			var body = new Body
			(
				bodyDefn,
				new Coords().randomize().multiply(worldSize), // pos
				
				// vel
				new Coords().randomize().multiplyScalar
				(
					2
				).subtract
				(
					new Coords(1, 1)
				).multiplyScalar
				(
					2
				), 

				new Orientation(new Coords(1, 0)),
				Math.random() / 32 // angVel				
			);

			bodies.push(body);
		}

		var world = new World
		(
			worldSize,
			bodies
		);

		return world;
	}

	Demo.worldSimple = function(size)
	{
		// A simpler world for testing.

		var bodyDefns = 
		[
			new BodyDefn
			(
				"BodyDefn0",
				1, // mass
				1, // angularInertiaFactor
				new Shape
				([
					new Coords(0, -8),
					new Coords(4, 8),
					new Coords(-4, 8),
				])
			),

			new BodyDefn
			(
				"BodyDefn1",
				1000000, // mass
				1, // angularInertiaFactor
				new Shape
				([
					new Coords(-5, -40),
					new Coords(5, -40),
					new Coords(5, 40),
					new Coords(-5, 40),
				])
			),
		];

		var world = new World
		(
			size,
			// bodies
			[
				new Body
				(
					bodyDefns[0],
					new Coords(25, 10), // pos
					new Coords(1, 1), // vel
					new Orientation(new Coords(1, 0)),
					.02 // angVel
				),
	
				new Body
				(
					bodyDefns[1],
					new Coords(75, 50), // pos
					new Coords(0, 0), // vel
					new Orientation(new Coords(1, 0)),
					0 // angVel
				),
	
			]
		);

		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