Collisions

Collisions is a JavaScript library for quickly and accurately detecting collisions between Polygons, Circles, and Points. It combines the efficiency of a Bounding Volume Hierarchy (BVH) for broad-phase searching and the accuracy of the Separating Axis Theorem (SAT) for narrow-phase collision testing.

• Installation
• Documentation
• Demos
• Usage
• Getting Started
  1. Creating a Collision System
  2. Creating, Inserting, Updating, and Removing Bodies
  3. Updating the Collision System
  4. Testing for Collisions
  5. Getting Detailed Collision Information
  6. Negating Overlap
• Lines
• Concave Polygons
• Rendering
• Bounding Volume Padding
• Only using SAT
• FAQ

<a name="anchor-installation"></a> Installation

npm install collisions

Note: This library uses the native ECMAScript Module syntax. Most environments support native modules, but the following exceptions apply:

• Node.js (9.2.0) requires the --experimental-modules flag
• Firefox (54) requires the dom.moduleScripts.enabled setting

Bundling solutions such as Webpack or Rollup.js make native modules compatible with all environments.

<a name="anchor-documentation"></a> Documentation

View the documentation (this README is also there).

<a name="anchor-demos"></a> Demos

• Tank
• Stress Test

<a name="anchor-usage"></a> Usage

import Collisions from 'collisions';

// Create the collision system
const system = new Collisions();

// Create a Result object for collecting information about the collisions
const result = system.createResult();

// Create the player (represented by a Circle)
const player = system.createCircle(100, 100, 10);

// Create some walls (represented by Polygons)
const wall1 = system.createPolygon(400, 500, [[-60, -20], [60, -20], [60, 20], [-60, 20]], 1.7);
const wall2 = system.createPolygon(200, 100, [[-60, -20], [60, -20], [60, 20], [-60, 20]], 2.2);
const wall3 = system.createPolygon(400, 50, [[-60, -20], [60, -20], [60, 20], [-60, 20]], 0.7);

// Update the collision system
system.update();

// Get any potential collisions (this quickly rules out walls that have no chance of colliding with the player)
const potentials = player.potentials();

// Loop through the potential wall collisions
for(const wall of potentials) {
	// Test if the player collides with the wall
	if(player.collides(wall, result)) {
		// Push the player out of the wall
		player.x -= result.overlap * result.overlap_x;
		player.y -= result.overlap * result.overlap_y;
	}
}

<a name="anchor-getting-started"></a> Getting Started

<a name="anchor-step-1"></a>

1. Creating a Collision System

Collisions provides functions for performing both broad-phase and narrow-phase collision tests. In order to take full advantage of both phases, bodies need to be tracked within a collision system.

Call the Collisions constructor to create a collision system.

import Collisions from 'collisions';

const system = new Collisions();

<a name="anchor-step-2"></a>

2. Creating, Inserting, Updating, and Removing Bodies

Collisions supports the following body types:

• Circle: A shape with infinite sides equidistant from a single point
• Polygon: A shape made up of line segments
• Point: A single coordinate

To use them, import the desired body class, call its constructor, and insert it into the collision system using insert().

import {Collisions, Circle, Polygon, Point} from 'collisions';

const system = new Collisions();

const circle  = new Circle(100, 100, 10);
const polygon = new Polygon(50, 50, [[0, 0], [20, 20], [-10, 10]]);
const line    = new Polygon(200, 5, [[-30, 0], [10, 20]]);
const point   = new Point(10, 10);

system.insert(circle)
system.insert(polygon, line, point);

Collision systems expose several convenience functions for creating bodies and inserting them into the system in one step. This also avoids having to import the different body classes.

import Collisions from 'collisions';

const system = new Collisions();

const circle  = system.createCircle(100, 100, 10);
const polygon = system.createPolygon(50, 50, [[0, 0], [20, 20], [-10, 10]]);
const line    = system.createPolygon(200, 5, [[-30, 0], [10, 20]]);
const point   = system.createPoint(10, 10);

All bodies have x and y properties that can be manipulated. Additionally, Circle bodies have a scale property that can be used to scale their overall size. Polygon bodies have scale_x and scale_y properties to scale their points along a particular axis and an angle property to rotate their points around their current position (using radians).

circle.x     = 20;
circle.y     = 30;
circle.scale = 1.5;

polygon.x       = 40;
polygon.y       = 100;
polygon.scale_x = 1.2;
polygon.scale_y = 3.4;
polygon.angle   = 1.2;

And, of course, bodies can be removed when they are no longer needed.

system.remove(polygon, point);
circle.remove();

<a name="anchor-step-3"></a>

3. Updating the Collision System

Collision systems need to be updated when the bodies within them change. This includes when bodies are inserted, removed, or when their properties change (e.g. position, angle, scaling, etc.). Updating a collision system is done by calling update() and should typically occur once per frame.

system.update();

The optimal time for updating a collision system is after its bodies have changed and before collisions are tested. For example, a game loop might use the following order of events:

function gameLoop() {
	handleInput();
	processGameLogic();

	system.update();

	handleCollisions();
	render();
}

<a name="anchor-step-4"></a>

4. Testing for Collisions

When testing for collisions on a body, it is generally recommended that a broad-phase search be performed first by calling potentials() in order to quickly rule out bodies that are too far away to collide. Collisions uses a Bounding Volume Hierarchy (BVH) for its broad-phase search. Calling potentials() on a body traverses the BVH and builds a list of potential collision candidates.

const potentials = polygon.potentials();

Once a list of potential collisions is acquired, loop through them and perform a narrow-phase collision test using collides(). Collisions uses the Separating Axis Theorem (SAT) for its narrow-phase collision tests.

const potentials = polygon.potentials();

for(const body of potentials) {
	if(polygon.collides(body)) {
		console.log('Collision detected!');
	}
}

It is also possible to skip the broad-phase search entirely and call collides() directly on two bodies.

Note: Skipping the broad-phase search is not recommended. When testing for collisions against large numbers of bodies, performing a broad-phase search using a BVH is much more efficient.

if(polygon.collides(line)) {
	console.log('Collision detected!');
}

<a name="anchor-step-5"></a>

5. Getting Detailed Collision Information

There is often a need for detailed information about a collision in order to react to it appropriately. This information is stored using a Result object. Result objects have several properties set on them when a collision occurs, all of which are described in the documentation.

For convenience, there are several ways to create a Result object. Result objects do not belong to any particular collision system, so any of the following methods for creating one can be used interchangeably. This also means the same Result object can be used for collisions across multiple systems.

Note: It is highly recommended that Result objects be recycled when performing multiple collision tests in order to save memory. The following example creates multiple Result objects strictly as a demonstration.

import {Collisions, Result, Polygon} from 'collisions';

const system     = new Collisions();
const my_polygon = new Polygon(100, 100, 10);

const result1 = new Result();
const result2 = Collisions.createResult();
const result3 = system.createResult();
const result4 = Polygon.createResult();
const result5 = my_polygon.createResult();

To use a Result object, pass it into collides(). If a collision occurs, it will be populated with information about the collision. Take note in the following example that the same Result object is being reused each iteration.

const result     = system.createResult();
con