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](https://en.wikipedia.org/wiki/Bounding_volume_hierarchy) (BVH) for broad-phase searching and the accuracy of the [Separating Axis Theorem](https://en.wikipedia.org/wiki/Separating_axis_theorem) (SAT) for narrow-phase collision testing.
* [Installation](#anchor-installation)
* [Documentation](#anchor-documentation)
* [Demos](#anchor-demos)
* [Usage](#anchor-usage)
* [Getting Started](#anchor-getting-started)
1. [Creating a Collision System](#anchor-step-1)
2. [Creating, Inserting, Updating, and Removing Bodies](#anchor-step-2)
3. [Updating the Collision System](#anchor-step-3)
4. [Testing for Collisions](#anchor-step-4)
5. [Getting Detailed Collision Information](#anchor-step-5)
6. [Negating Overlap](#anchor-step-6)
* [Lines](#anchor-lines)
* [Concave Polygons](#anchor-concave-polygons)
* [Rendering](#anchor-rendering)
* [Bounding Volume Padding](#anchor-bounding-volume-padding)
* [Only using SAT](#anchor-only-using-sat)
* [FAQ](#anchor-faq)
Installation
===============================================================================
```bash
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](https://nodejs.org/api/esm.html) flag
> * Firefox (54) requires the [dom.moduleScripts.enabled](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/import#Browser_compatibility) setting
>
> Bundling solutions such as [Webpack](https://webpack.js.org/) or [Rollup.js](https://rollupjs.org/) make native modules compatible with all environments.
Documentation
===============================================================================
View the [documentation](https://sinova.github.com/Collisions/) (this README is also there).
Demos
===============================================================================
* [Tank](https://sinova.github.com/Collisions/demo/)
* [Stress Test](https://sinova.github.com/Collisions/demo/?stress)
Usage
===============================================================================
```JavaScript
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;
}
}
```
Getting Started
===============================================================================
## 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.
```JavaScript
import Collisions from 'collisions';
const system = new Collisions();
```
## 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()`.
```JavaScript
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.
```JavaScript
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).
```JavaScript
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.
```JavaScript
system.remove(polygon, point);
circle.remove();
```
## 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.
```JavaScript
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:
```JavaScript
function gameLoop() {
handleInput();
processGameLogic();
system.update();
handleCollisions();
render();
}
```
## 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](https://en.wikipedia.org/wiki/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.
```JavaScript
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](https://en.wikipedia.org/wiki/Separating_axis_theorem) (SAT) for its narrow-phase collision tests.
```JavaScript
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.
```JavaScript
if(polygon.collides(line)) {
console.log('Collision detected!');
}
```
## 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](https://sinova.github.com/Collisions/).
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.
```JavaScript
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.
```JavaScript
const result = system.createResult();
const potentials = point.potentials();
for(const body of potentials) {
if(point.collides(body, result)) {
console.log(result);
}
}
```
## 6. Negating Overlap
A common use-case in collision detection is negating overlap when a collision occurs (such as when a player hits a wall). This can be done using the collision information in a `Result` object (see [Getting Detailed Collision Information](#anchor-getting-detailed-collision-information)).
The three most useful properties on a `Result` object are `overlap`, `overlap_x`, and `overlap_y`. Together, these values describe how much and in what direction the source body is overlapping the target body. More specifically, `overlap_x` and `overlap_y` describe the direction vector, and `overlap` describes the magnitude of that vector.
These values can be used to "push" one body out of another using the minimum distance required. More simply, subtracting this vector from the source body's position will cause the bodies to no longer collide. Here's an example:
```JavaScript
if(player.collides(wall, result)) {
player.x -= result.overlap * result.overlap_x;
player.y -= result.overlap * result.overlap_y;
}
```
Lines
===============================================================================
Creating a line is simply a matter of creating a single-sided polygon (i.e. a polygon with only two coordinate pairs).
```JavaScript
const line = new Polygon(200, 5, [[-30, 0], [10, 20]]);
```
Concave Polygons
===============================================================================
**Collisions** uses the [Separating Axis Theorem](https://en.wikipedia.org/wiki/Separating_axis_theorem) (SAT) for its narrow-phase collision tests. One caveat to SAT is that it only works properly on convex bodies. However, concave polygons can be "faked" by using a series of [Lines](#anchor-lines). Keep in mind that a polygon drawn using [Lines](#anchor-lines) is "hollow".
Handling true concave polygons requires breaking them down into their component convex polygons (Convex Decomposition) and testing them for collisions individually. There are plans to integrate this functionality into the library in the future, but for now, check out [poly-decomp.js](https://github.com/schteppe/poly-decomp.js).
Rendering
===============================================================================
For debugging, it is often useful to be able to visualize the collision bodies. All of the bodies in a Collision system can be drawn to a `