Detect-Collisions

Introduction

Detect-Collisions is a robust TypeScript library for detecting collisions among varied entities. It uses Bounding Volume Hierarchy (BVH) and the Separating Axis Theorem (SAT) for efficient collision detection. Uniquely, it manages rotation, scale of bodies, and supports decomposing concave polygons into convex ones. It also optimizes detection with body padding. Ideal for gaming, simulations, or projects needing advanced collision detection, Detect-Collisions offers customization and fast performance.

Demos

• Tank
• Stress Test
• Stackblitz

Installation

$ npm install detect-collisions

API Documentation

For detailed documentation on the library's API, refer to the following link:

https://prozi.github.io/detect-collisions/modules.html

Usage

Step 1: Initialize Collision System

Detect-Collisions extends functionalities from RBush. To begin, establish a unique collision system.

const { System } = require("detect-collisions");
const system = new System();

Step 2: Understand Body Attributes

Bodies have various properties:

• Position Attributes: pos: Vector, x: number, y: number. Setting body.pos.x or body.pos.y doesn't update the bounding box while setting body.x or body.y directly does. To set both at the same time, use setPosition(x, y).

• Scale, Offset: Bodies have scale: number shorthand property and setScale(x, y) method for scaling. The offset: Vector property and setOffset({ x, y }: Vector) method are for offset from body center for rotation purposes.

• AABB Bounding Box: You can get the bounding box even on non-inserted bodies with getAABBAsBBox(): BBox method.

Bodies contain additional properties (BodyOptions) that can be set in runtime or during creation:

• angle: number: Use setAngle(angle: number) to change it during runtime.
• isStatic: boolean: If set to true, the body won't move during system.separare(). For walls.
• isTrigger: boolean: If set to true, the body won't move during system.separate(). For projectiles.
• isCentered: boolean: If set to true, offset is set to center for rotation purposes.
• padding: number: Bounding box padding, optimizes costly updates.

Use isConvex: boolean and convexPolygons: Vector[][] to check if the Polygon is convex.

Each body type has specific properties, for example, a Box has width & height properties.

Step 3: Create and Manage Bodies

Use BodyOptions as the last optional parameter during body creation.

const { deg2rad } = require("detect-collisions");
const options = {
  angle: deg2rad(90),
  isStatic: false,
  isTrigger: false,
  isCentered: false,
  padding: 0,
};

Create body of various types using:

const {
  Box,
  Circle,
  Ellipse,
  Line,
  Point,
  Polygon,
} = require("detect-collisions");

// create with options, without insert
const box = new Box(position, width, height, options);
const circle = new Circle(position, radius, options);
const ellipse = new Ellipse(position, radiusX, radiusY, step, options);
const line = new Line(start, end, options);
const point = new Point(position, options);
const polygon = new Polygon(position, points, options);

Insert a body into the system:

// insert any of the above
system.insert(body);

Create and insert body in one step:

// create with options, and insert
const box = system.createBox(position, width, height, options);
const circle = system.createCircle(position, radius, options);
const ellipse = system.createEllipse(position, radiusX, radiusY, step, options);
const line = system.createLine(start, end, options);
const point = system.createPoint(position, options);
const polygon = system.createPolygon(position, points, options);

Step 4: Manipulate Bodies

Notice the last parameter of each of the below 4 functions defaults to true if omitted.

• setPosition(x: number, y: number, update = true):

  • Sets the position of the body to the specified (x, y) coordinates in the 2D space.

• setScale(x: number, y = x, update = true):

  • Sets the scale of the body along the x-axis and y-axis (optional).
  • Allows resizing the body.

• setAngle(angle: number, update = true):

  • Sets the rotation angle of the body to the specified value.
  • Used for rotating the body around its center.
  • Angle in radians, use deg2rad(degrees: number) for conversion.

• setOffset(offset: { x: number, y: number }, update = true):

  • Sets the offset of the body from its center.
  • Used to position the body's collision shape more accurately.

• updateBody():

  • Updates body AABB in collision tree, please call this after all manipulations are done

Depending on your use case:

• If you use only position updates stick to setPosition(x, y) and don't use system.update() or body.updateBody(). Since the last parameter of each manipulation function (update) defaults to true, this way will make that body bounding box update after that setPosition call,

• If you use 2 or more manipulation methods, like position plus any other aspect like scale/angle/offset, you should call manipulation functions with last parameter set to false (for example: setPosition(x, y, false))

  • After all of those manipulations are done, call once body.updateBody() to update the bounding box once. This method is most efficient.
  • Alternatively, after all updates of bodies in this frame are finished, call once system.update() which will iterate over all bodies and update their bounding box. This method is slightly less efficient.

Step 5: Collision Detection and Resolution

Check collisions for all bodies or a single body:

// all bodies
const collided = system.checkAll((response: Response) => {
  // if you want to end after first collision
  return true;
});

// check for one `body`
const collided = system.checkOne(body, (response: Response) => {
  // if you want to end after first collision
  return true;
});

For a direct collision check without broad-phase search, use system.checkCollision(body1, body2). However, this isn't recommended due to efficiency loss.

Access detailed collision information in the system.response object, which includes properties like a, b, overlap, overlapN, overlapV, aInB, and bInA.

In case of overlap during collision, subtract the overlap vector from the position of the body to eliminate the collision. This can be achieved as follows:

if (system.checkCollision(player, wall)) {
  const { overlapV } = system.response;
  player.setPosition(player.x - overlapV.x, player.y - overlapV.y);
}

Step 6: Collision Response

After detecting a collision, you may want to respond or "react" to it in some way. This could be as simple as stopping a character from moving through a wall, or as complex as calculating the resulting velocities of a multi-object collision in a physics simulation.

Here's a simple example:

system.checkAll((response: Response) => {
  if (response.a.isPlayer && response.b.isWall) {
    // Player can't move through walls
    const { overlapV } = response;
    response.a.setPosition(
      response.a.x - overlapV.x,
      response.a.y - overlapV.y
    );
  } else if (response.a.isBullet && response.b.isEnemy) {
    // Bullet hits enemy
    system.remove(response.a); // Remove bullet
    response.b.takeDamage(); // Damage enemy
  }
});

Step 7: System Separation

There is an easy way to handle overlap and separation of bodies during collisions. Use system.separate() after updating the system. This function takes into account isTrigger and isStatic flags on bodies.

system.separate();

This function provides a simple way to handle collisions without needing to manually calculate and negate overlap.

Step 8: Cleaning Up

When you're done with a body, you should remove it from the system to free up memory and keep the collision checks efficient. You can do this with the remove method:

system.remove(body);

This will remove the body from the system's internal data structures, preventing it from being included in future collision checks. If you keep a reference to the body, you can insert it again later with system.insert(body).

Remember to always keep your collision system as clean as possible. This means removing bodies when they're not needed, and avoiding unnecessary updates. Following these guidelines will help ensure your project runs smoothly and efficiently.

And that's it! You're now ready to use the Detect-Collisions library in your project. Whether you're making a game, a simulation, or any other kind of interactive experience, Detect-Collisions provides a robust, efficient, and easy-to-use solution for collision detection. Happy coding!

Detecting collision after insertion

// create self-destructing collider
const testCollision = ({ x, y }, radius = 10) => {
  // create and add to tree
  const circle = system.createCircle({ x, y }, radius);
  // init as false
  const collided = system.checkOne(circle, () => {
    // ends iterating after first collision
    return true;
  });

  // remove from tree
  system.remove(circle);

  return collided ? system.response : null;
};

Handling Concave Polygons

As of version 6.8.0, Detect-Collisions fully supports non-convex or hollow polygons*, provided they are valid. Learn more about this feature from GitHub Issue #45 or experiment with it on Stackblitz.

Visual Debugging with Rendering

To facilitate debugging, Detect-Collisions allows you to visually represent the collision bodies. By invoking the draw() method and supplying a 2D context of a <canvas> element, you can draw all the bodies within a collision system.

const canvas = document.createElement("canvas");
const context = canvas.getContext("2d");

context.strokeStyle = "#FFFFFF";
context.beginPath();
system.draw(context);
context.stroke();

You can also opt to draw individual bodies.

context.strokeStyle = "#FFFFFF";
context.beginPath();
// draw specific body
body.draw(context);
// draw whole system
system.draw(context);
context.stroke();

To assess the Bounding Volume Hierarchy, you can draw the BVH.

context.strokeStyle = "#FFFFFF";
context.beginPath();
// draw specific body bounding box
body.drawBVH(context);
// draw bounding volume hierarchy of the system
system.drawBVH(context);
context.stroke();

Raycasting

Detect-Collisions provides the functionality to gather raycast data. Here's how:

const start = { x: 0, y: 0 };
const end = { x: 0, y: -10 };
const hit = system.raycast(start, end);

if (hit) {
  const { point, body } = hit;

  console.log({ point, body });
}

In this example, point is a Vector with the coordinates of the nearest intersection, and body is a reference to the closest body.

Contributing to the Project

We welcome contributions! Feel free to open a merge request. When doing so, please adhere to the following code style guidelines:

• Execute the npm run precommit script prior to submitting your merge request
• Follow the conventional commits standard
• Refrain from using the any type

Additional Considerations

Why not use a physics engine?

While physics engines like Matter-js or Planck.js are recommended for projects that need comprehensive physics simulation, not all projects require such complexity. In fact, using a physics engine solely for collision detection can lead to unnecessary overhead and complications due to built-in assumptions (gravity, velocity, friction, etc.). Detect-Collisions is purpose-built for efficient and robust collision detection, making it an excellent choice for projects that primarily require this functionality. It can also serve as the foundation for a custom physics engine.

Benchmark

$ git clone https://github.com/Prozi/detect-collisions.git
$ cd detect-collisions
$ yarn
$ yarn benchmark [milliseconds=1000]

will show you the Stress Demo results without drawing, only using Detect-Collisions and with different N amounts of dynamic, moving bodies

typical output:

┌─────────┬────────────────────────────┬─────────┬────────────────────┬──────────┬─────────┐
│ (index) │         Task Name          │ ops/sec │ Average Time (ns)  │  Margin  │ Samples │
├─────────┼────────────────────────────┼─────────┼────────────────────┼──────────┼─────────┤
│    0    │ 'stress test, items=1000'  │  '295'  │ 3385692.610933974  │ '±2.87%' │   296   │
│    1    │ 'stress test, items=2000'  │  '141'  │ 7059932.731406789  │ '±2.69%' │   142   │
│    2    │ 'stress test, items=3000'  │  '80'   │ 12414747.956358356 │ '±2.22%' │   81    │
│    3    │ 'stress test, items=4000'  │  '57'   │ 17436071.825438533 │ '±4.02%' │   58    │
│    4    │ 'stress test, items=5000'  │  '39'   │ 25130633.383989334 │ '±2.94%' │   40    │
│    5    │ 'stress test, items=6000'  │  '30'   │ 32609690.800789863 │ '±2.89%' │   31    │
│    6    │ 'stress test, items=7000'  │  '21'   │ 46937344.686551526 │ '±2.27%' │   22    │
│    7    │ 'stress test, items=8000'  │  '15'   │ 63767726.480960846 │ '±3.27%' │   16    │
│    8    │ 'stress test, items=9000'  │  '13'   │ 74750863.00713675  │ '±3.77%' │   14    │
│    9    │ 'stress test, items=10000' │  '12'   │ 81232352.54104322  │ '±5.38%' │   13    │
└─────────┴────────────────────────────┴─────────┴────────────────────┴──────────┴─────────┘
✨  Done in 12.21s.