• Stars
    star
    128
  • Rank 281,044 (Top 6 %)
  • Language
    JavaScript
  • License
    MIT License
  • Created over 4 years ago
  • Updated 2 months ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

2d collision routines

collision-2d

There are many javascript collision routines and libraries for 2d. None satisifed all of these criteria:

  • consistent API interface
  • doesn't generate memory garbage
  • consistent vector/matrix/line representation
  • is data-oriented
  • is purely functional
  • collisions only - no gravity, rigid body handling, or complex solvers
  • pure es modules

so here we are!

Note: If you're looking for higher-level 2d collision handling routine for ellipsoids vs line segments, check out https://github.com/mreinstein/collide-and-slide-2d

available collision checks

aabb-aabb overlap

alt text

const collided = aabbAABBOverlap(aabb, aabb2, contact)

aabb-aabb contain

// true when aabb1 fully contains aabb2 (2 is fully inside the bounds of 1)
const contains = aabbAABBContain(aabb1, aabb2)

aabb-aabb sweep 1

alt text

const collided = aabbAABBSweep1(aabb, aabb2, delta, contact)

aabb-aabb sweep 2

alt text

const collided = aabbAABBSweep2(aabb, delta, aabb2, delta2, contact)

aabb-segment sweep

alt text

const collided = aabbSegmentSweep(line, aabb, delta, contact)

aabb-segments sweep-indexed

alt text

const collided = aabbSegmentsSweep1Indexed(segments, indices, segmentCount, aabb, delta, contact)

if there is a collision, contact.collider will be an integer indicating the index of which segment in the segments array collided.

aabb-point overlap

alt text

const collided = aabbPointOverlap(aabb, point, contact)

aabb-segment overlap

alt text

const collided = aabbSegmentOverlap(aabb, pos, delta, paddingX, paddingY, contact)

ray-plane-distance

alt text

import plane from 'plane.js'


const p = plane.create()
plane.fromPlane(p, planeOrigin, planeNormal)
const distance = plane.rayDistance(p, rayOrigin, rayVector)

ray-sphere overlap

alt text

import raySphereOverlap from 'ray-sphere-overlap.js'


// declare 2 points that lie on an infinite ray
const p1 = [ 100, 100 ]
const p2 = [ 200, 100 ]

const sphereCenter: [ 250, 100 ]
const sphereRadius: 50
const contact = { mu1: NaN, mu2: NaN }
const overlaps = raySphereOverlap(p1, p2, sphereCenter, sphereRadius, contact)

// mu1 and mu2 are the points along the line segment from p1 to p2 where the sphere intersection occurs:
//   intersection1 = p1 + contact.mu1  * (p2 - p1)
//   intersection2 = p1 + contact.mu2  * (p2 - p1)
if (overlaps) {
    console.log('sphere intersection time 1:', contact.mu1)
    console.log('sphere intersection time 2', contact.mu2)
}

segment-sphere overlap

alt text

import segmentSphereOverlap from 'segment-sphere-overlap.js'


// declare 2 points that lie on a line segment
const p1 = [ 100, 100 ]
const p2 = [ 200, 100 ]

const sphereCenter: [ 250, 100 ]
const sphereRadius: 50
const contact = { intersectionCount: 0, mu1: NaN, mu2: NaN }
const overlaps = segmentSphereOverlap(p1, p2, sphereCenter, sphereRadius, contact)

// mu1 and mu2 are the points along the line segment from p1 to p2 where the sphere intersection occurs:
//   intersection1 = p1 + contact.mu1  * (p2 - p1)
//   intersection2 = p1 + contact.mu2  * (p2 - p1)
if (overlaps) {
    // the segment interesects the sphere, intersectionCount is 1 or 2
    // either mu1 or mu2 will be NaN if there's not 2 intersections
    console.log('intersection count:', contact.intersectionCount)
    console.log('sphere intersection time 1:', contact.mu1)
    console.log('sphere intersection time 2', contact.mu2)
} else {
    // no overlap, contact.intersectionCount is 0
}

segment-normal

const normal = segmentNormal(vec2.create(), pos1, pos2)

segment-point-overlap

alt text

const collided = segmentPointOverlap(p, segPoint0, segPoint1) // true or false

segment-segment-overlap

alt text

const intersectionPoint = vec2.create()
if (segmentSegmentOverlap(seg1Point1, seg1Point2, seg2Point1, seg2Point2, intersectionPoint)) {
    // if we get here, intersectionPoint is filled in with where the 2 segments overlap
}

segments-segment-overlap

alt text

const collided = segmentsSegmentOverlap(segments, start, delta, contact)

if there is a collision, contact.collider will be an integer indicating the index of which segment in the segments array collided.

segments-segment-overlap-indexed

const segs = [
    [ p0, p1 ],
    [ p2, p3 ],
    [ p4, p5 ]
]
const indices = [ 0, 2 ]  // indices into the segs array

const segmentCount = 2    // numer of indices to include. only run the segmentsSegment intersection tests on [ p0, p1 ] and [ p4, p5]

const collided = segmentsSegmentOverlapIndexed(segments, indices, segmentCount, start, delta, contact)

if there is a collision, contact.collider will be an integer indicating the index of which segment in the segments array collided.

segments-sphere-sweep 1

alt text

const collided = segmentsSphereSweep1(segments, position, radius, delta, contact)

if there is a collision, contact.collider will be an integer indicating the index of which segment in the segments array collided.

segments-sphere-sweep-1-indexed

const segs = [
    [ p0, p1 ],
    [ p2, p3 ],
    [ p4, p5 ]
]
const indices = [ 0, 2 ]  // indices into the segs array

const segmentCount = 2    // only run the segmentsSphereSweep tests on [ p0, p1 ] and [ p4, p5 ]

const collided = segmentsSphereSweep1(segments, indices, segmentCount, position, radius, delta, contact)

if there is a collision, contact.collider will be an integer indicating the index of which segment in the segments array collided.

sphere-sphere-overlap

alt text

const collided = sphereSphereOverlap(centerA, radiusA, centerB, radiusB) // collided is true or false

cone-point-overlap

alt text

const collided = conePointOverlap(conePosition, coneRotation, coneFieldOfView, coneMinDistance, coneMaxDistance, point) // collided is true or false

tri-point-overlap

alt text

const collided = triPointOverlap(v0, v1, v2, point) // collided is true or false

entities

The collision routines all use these entity definitions

point

a point is a 2d vector, which is represented as an array with 2 values:

const position = [ 200, 150 ] // x: 200, y: 150

We use the fantastic gl-matrix vec2 for representing these.

aabb

an axially aligned bounding box

const aabb = {
    position: [ 200, 100 ],  // center point of the AABB
    width: 50,
    height: 50
}

segment

a line segment consists of 2 points

const segment = [
    [ 0, 0 ],   // starting point of line
    [ 100, 0 ]  // ending point of line
]

plane

a 2d plane

{
    origin: vec2.create(),
    normal: vec2.create(),
    D: 0,
}

contact

The data structure populated when a collision occurs

{
    // for segments-segment-overlap and segments-sphere-sweep1 this is set to the index
    // in the array of line segments passed into the collision routine
    // for all other routines, collider is a reference to the colliding object itself
    collider : null,

    position : [ 0, 0 ], // the exact position of the collision
    delta    : [ 0, 0 ], // a vector that can be applied to get out of the colliding state
    normal   : [ 0, 0 ], // the collision normal vector
    time     : 0         // the time of the collision, from 0..1
}

conventions

All collision checking functions return a boolean indicating if there was a collision. They also accept an optional contact argument, which gets filled in if there is an actual collision.

"sweep" tests indicate at least 1 of the objects is moving. the number indicates how many objects are moving. e.g., aabb-aabb-sweep2 means we are comparing 2 aabbs, both of which are moving.

"overlap" tests don't take movement into account, and this is a static check to see if the 2 entities overlap.

plural forms imply a collection. e.g., segments-segment-ovelap checks one line segment against a set of line segments. If there is more than one collision, the closest collision is set in the contact argument.

"indexed" tests are the same as their non-indexed forms, except they take in an array of segment indices to use. These are nice in that you can avoid having to build large arrays of line segments every frame, if you have things like dynamic line segments (platforms) or have a spatial culling algorithm that selects line segments to include.

credits

Most of these collision checks were adapted from existing open source modules:

More Repositories

1

snabby

Use HTML template strings with snabbdom.
JavaScript
93
star
2

ecs

data oriented, functional entity component system
JavaScript
85
star
3

alexa-verifier

βœ“ Verify HTTP requests sent to an Alexa skill are sent from Amazon
JavaScript
76
star
4

node-gearman

βš™ Gearman client and worker for node
JavaScript
75
star
5

remove-array-items

βͺ½ remove items from a javascript array without generating garbage
JavaScript
34
star
6

constraint-solver

a constraint solver based on kiwi.js with better API ergonomics
JavaScript
20
star
7

collide-and-slide-2d

slide an ellipse/sphere along a series of line segments in 2d
JavaScript
17
star
8

text-animate

✍ beautiful, animated, HTML typographic UI effects
JavaScript
16
star
9

aws-transcription-to-vtt

convert an AWS transcribe JSON body into a .vtt file
JavaScript
14
star
10

ascii-diagrams

no bullshit ascii diagramming
JavaScript
10
star
11

level-generator

✣ Randomly generate 2d levels in closed environments, as found in many roguelike games.
JavaScript
8
star
12

cobalt

WebGpu 2D renderer
JavaScript
7
star
13

node-red-contrib-alexa-verifier

node-red packaged node that verifies HTTP requests sent to an Alexa skill are sent from Amazon
JavaScript
6
star
14

wag

☍ web asset graph
JavaScript
6
star
15

priority-queue

functional, data oriented priority queue that doesn't suck
JavaScript
6
star
16

home-automation

🏠 Notes, links, and prototypes related to my home automation experiments
JavaScript
5
star
17

attenuate

general purpose attenuation functions (linear, quadratic, etc.)
JavaScript
3
star
18

visualizer

An HTML5 audio visualizer for mic/line-in input
JavaScript
3
star
19

nexkey

node sdk for nexkey's awesome lock product
JavaScript
3
star
20

snabbdom-test-content-editor

a full app based on snabby, written for learning purposes
JavaScript
3
star
21

substrate

literate programming with javascript, markdown, and explorables
JavaScript
3
star
22

boids

functional, data-oriented steering behaviors
JavaScript
2
star
23

game-input

tiny, pollable input singleton for web games and simulations
JavaScript
2
star
24

home-movie

LAN based movie streaming
JavaScript
2
star
25

round-half-up-symmetric

symmetric half-up rounding for javascript
JavaScript
2
star
26

universal-translator

enable people from multiple native languages to communicate seamlessly with automatic translation
HTML
2
star
27

upsocket

transactional connection queue for websockets
JavaScript
1
star
28

hierarchical-fsm

data-oriented hierarchical finite state machines
JavaScript
1
star
29

snabbdom-timeline

an interactive timeline component implemented in snabbdom
JavaScript
1
star
30

standing-desk

The source code and plans for my homegrown standing desk
JavaScript
1
star
31

padolsey

generate padolsey patterns
JavaScript
1
star
32

ev-pubsub

asynchronous publish/subscribe
JavaScript
1
star
33

is-not-twelve

sure, why not.
JavaScript
1
star
34

is-media-playing

🎧 determine if an html mediaelement is currently playing
JavaScript
1
star
35

extract

a command line tool to extract a sub rectangle from a series of image frames
JavaScript
1
star