Skip to content

Instantly share code, notes, and snippets.

@szolotykh
Last active May 30, 2019 02:48
Show Gist options
  • Save szolotykh/9374110 to your computer and use it in GitHub Desktop.
Save szolotykh/9374110 to your computer and use it in GitHub Desktop.
JavaScript collision library
/* File comments updated: Sunday, March 25, 2012 at 12:38 AM
*
* COLLISION SYSTEM: provides functions to create collision objects
* and detect collisions between objects and points.
* Used by most animated objects on the canvas to detect collisions.
*/
// POINT: contains an x and y position
function Point(x, y){
this.x = x;
this.y = y;
}
// VECTOR: contains an x and y direction
function Vector(x, y){
this.x = x;
this.y = y;
}
// TRIANGLE: described by three points p1, p2 and p3
// which together form the verticies of the triangle.
function Triangle(p1, p2, p3){
this.p1 = p1;
this.p2 = p2;
this.p3 = p3;
}
// CIRCLE: described by an x and y position as the circle's
// center, and a radius.
function Circle(center, radius){
this.c = center;
this.r = radius;
}
// DOT PRODUCT OF TWO VECTORS
function dotProduct(v1, v2){
return v1.x*v2.x + v1.y*v2.y;
}
// TRIANGLE-TO-POINT COLLISION FUNCTION
// Returns TRUE if the given point and triangle intersect;
// that is, if they collide on a 2D x-y plane.
// See Triangle object above for details on triangles.
function triangle2point(tr, p0){
var area0 = Math.abs((tr.p2.x-tr.p1.x)*(tr.p3.y-tr.p1.y)-(tr.p3.x-tr.p1.x)*(tr.p2.y-tr.p1.y));
var area1 = Math.abs((tr.p1.x-p0.x)*(tr.p2.y-p0.y)-(tr.p2.x-p0.x)*(tr.p1.y-p0.y));
var area2 = Math.abs((tr.p2.x-p0.x)*(tr.p3.y-p0.y)-(tr.p3.x-p0.x)*(tr.p2.y-p0.y));
var area3 = Math.abs((tr.p3.x-p0.x)*(tr.p1.y-p0.y)-(tr.p1.x-p0.x)*(tr.p3.y-p0.y));
return (Math.abs(area1+area2+area3-area0) <= 0.0001);
}
// SEGMENT-TO-SEGMENT COLLISION FUNCTION
// Returns TRUE if the two given lines intersect;
// that is, if they collide on a 2D x-y plane.
// Lines are given as two points.
// PARAMETERS line #1 as (p11, p12) and line #2 as (p21, p22)
function segment2segment(p11, p12, p21, p22){
var a1 = p12.y - p11.y;
var b1 = p11.x - p12.x;
var c1 = a1*p11.x + b1*p11.y;
var a2 = p22.y - p21.y;
var b2 = p21.x - p22.x;
var c2 = a2*p21.x + b2*p21.y;
var det = a1*b2 - a2*b1;
if(det == 0){
//Lines are parallel
return false;
}else{
var xi = (b2*c1 - b1*c2)/det;
var yi = (a1*c2 - a2*c1)/det;
if(((p11.x<=xi && xi<=p12.x)||(p12.x<=xi && xi<=p11.x))&&
((p11.y<=yi && yi<=p12.y)||(p12.y<=yi && yi<=p11.y))&&
((p21.x<=xi && xi<=p22.x)||(p22.x<=xi && xi<=p21.x))&&
((p21.y<=yi && yi<=p22.y)||(p22.y<=yi && yi<=p21.y))){
return true;
}
else{
return false;
}
}
}
// TRIANGLE-TO-TRIANGLE COLLISION FUNCTION
// Returns TRUE if the two given triangles intersect;
// that is, if they collide on a 2D x-y plane.
// See Triangle object above for details on triangles.
function triangle2triangle(tr1, tr2){
if(segment2segment(tr1.p1, tr1.p2, tr2.p1, tr2.p2))
return true;
if(segment2segment(tr1.p1, tr1.p2, tr2.p2, tr2.p3))
return true;
if(segment2segment(tr1.p1, tr1.p2, tr2.p3, tr2.p1))
return true;
if(segment2segment(tr1.p2, tr1.p3, tr2.p1, tr2.p2))
return true;
if(segment2segment(tr1.p2, tr1.p3, tr2.p2, tr2.p3))
return true;
if(segment2segment(tr1.p2, tr1.p3, tr2.p3, tr2.p1))
return true;
if(segment2segment(tr1.p3, tr1.p1, tr2.p1, tr2.p2))
return true;
if(segment2segment(tr1.p3, tr1.p1, tr2.p2, tr2.p3))
return true;
if(segment2segment(tr1.p3, tr1.p1, tr2.p3, tr2.p1))
return true;
if(triangle2point(tr1,tr2.p1))
return true;
if(triangle2point(tr1,tr2.p2))
return true;
if(triangle2point(tr1,tr2.p3))
return true;
if(triangle2point(tr2,tr1.p1))
return true;
if(triangle2point(tr2,tr1.p2))
return true;
if(triangle2point(tr2,tr1.p3))
return true;
}
// CIRCLE-TO-CIRCLE COLLISION FUNCTION
// Returns TRUE if the two given circles intersect;
// that is, if they collide on a 2D x-y plane.
// This function takes two circles defined by x,y center and r radius.
function circle2circle(cir1, cir2){
var d = (cir1.c.x - cir2.c.x)*(cir1.c.x - cir2.c.x)+(cir1.c.y - cir2.c.y)*(cir1.c.y - cir2.c.y);
var r = (cir1.r + cir2.r)*(cir1.r + cir2.r);
return (d <= r);
}
// CIRCLE-TO-POINT COLLISION FUNCTION
// Returns TRUE if the given circle and point intersect;
// that is, if they collide on a 2D x-y plane.
// This function takes a circle defined by an x,y center and r radius,
// and a point defined as an x,y coordinate.
// PARAMETERS: point as (x1, y1) and circle as (x2, y2, r)
function circle2point(cir, p){
var d = (cir.c.x - p.x)*(cir.c.x - p.x)+(cir.c.y - p.y)*(cir.c.y - p.y);
return (d <= cir.r*cir.r);
}
// CREATE CIRCLE FROM TRIANGE
// Given a triangle object, this function returns a circle object based
// on the triangle. Essentially, it encircles the traingle and returns
// the circle such that the triangle is entirely encompassed by it.
// See functions at top of page for details on triangle and circle objects.
function circleByTriangle(tr){
var midP1 = new Point((tr.p1.x + tr.p2.x)/2, (tr.p1.y + tr.p2.y)/2);
var midP2 = new Point((tr.p2.x + tr.p3.x)/2, (tr.p2.y + tr.p3.y)/2);
var A1 = tr.p2.y - tr.p1.y;
var B1 = tr.p1.x - tr.p2.x;
var D1 = -B1*midP1.x + A1*midP1.y;
var A2 = tr.p3.y - tr.p2.y;
var B2 = tr.p2.x - tr.p3.x;
var D2 = -B2*midP2.x + A2*midP2.y;
var det = B2*A1 - B1*A2;
var x = (A2*D1 - A1*D2)/det;
var y = (B2*D1 - B1*D2)/det;
var r = Math.sqrt((x - tr.p1.x)*(x - tr.p1.x) + (y - tr.p1.y)*(y - tr.p1.y));
return (new Circle(new Point(x, y), r));
}
// CIRCLE-TO-TRIANGLE COLLISION FUNCTION
function circle2triangle(cir, tr){
// Check if one of vertex of triangle inside of circle
if(circle2point(cir, tr.p1))
return true;
if(circle2point(cir, tr.p2))
return true;
if(circle2point(cir, tr.p3))
return true;
// Check if center of circle inside of triangle
if(triangle2point(tr,cir.c))
return true;
// Check if circle intersect one of edges of triangle
//Edge p1-p2
var v1 = new Vector(tr.p2.x - tr.p1.x, tr.p2.y - tr.p1.y);
var v0 = new Vector(cir.c.x - tr.p1.x, cir.c.y - tr.p1.y);
var dotV10 = dotProduct(v1, v0);
if(dotV10>0){
var lengthV1 = dotProduct(v1, v1);//squared length
var lengthProection = dotV10*dotV10/lengthV1;//squared length of proection v0 on v1
if(lengthProection<lengthV1){
var lengthV0 = dotProduct(v0, v0);//squared length
if(lengthV0-lengthProection < cir.r*cir.r){
return true;
}
}
}
//Edge p2-p3
v1 = new Vector(tr.p3.x - tr.p2.x, tr.p3.y - tr.p2.y);
v0 = new Vector(cir.c.x - tr.p2.x, cir.c.y - tr.p2.y);
dotV10 = dotProduct(v1, v0);
if(dotV10>0){
var lengthV1 = dotProduct(v1, v1);//squared length
var lengthProection = dotV10*dotV10/lengthV1;//squared length of proection v0 on v1
if(lengthProection<lengthV1){
var lengthV0 = dotProduct(v0, v0);//squared length
if(lengthV0-lengthProection < cir.r*cir.r){
return true;
}
}
}
//Edge p3-p1
v1 = new Vector(tr.p1.x - tr.p3.x, tr.p1.y - tr.p3.y);
v0 = new Vector(cir.c.x - tr.p3.x, cir.c.y - tr.p3.y);
dotV10 = dotProduct(v1, v0);
if(dotV10>0){
var lengthV1 = dotProduct(v1, v1);//squared length
var lengthProection = dotV10*dotV10/lengthV1;//squared length of proection v0 on v1
if(lengthProection<lengthV1){
var lengthV0 = dotProduct(v0, v0);//squared length
if(lengthV0-lengthProection < cir.r*cir.r){
return true;
}
}
}
return false;
}
// Function return actual distance between point p and line p1, p2.
// It use sqrt function and don't recommended for frequent usage
function point2lineDistance(p,p1,p2){
//http://mathworld.wolfram.com/Point-LineDistance2-Dimensional.html
return Math.abs((p2.x-p1.x)*(p1.y-p.y)-(p1.x-p.x)*(p2.y-p1.y))
/Math.sqrt((p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y));
}
// Transformations
//Rotate on angle 'angle'
function rotatePoint(p, angle){
var x = p.x;
p.x = Math.cos(angle)*x - Math.sin(angle)*p.y;
p.y = Math.sin(angle)*x + Math.cos(angle)*p.y;
return p;
}
// Translate point on dx, dy
function translatePoint(p, dx, dy){
p.x += dx;
p.y += dy;
}
// Create point from existent point
function createPoint(p){
return {x:p.x, y:p.y};
}
// Copy point p2 to p1
function copyPoint(p1, p2){
p1.x = p2.x;
p1.y = p2.y;
}
// === Collision objects ====
function standardCollision(r){
// if 'r = 0' or undefined, then standardCollision object become point
// if 'r != 0', then standardCollision is circle with radius 'r'
r = typeof r !== 'undefined' ? r : 0;
this.x = 0;
this.y = 0;
this.angle = 0;
this.r = r;
this.parent;
this.cObjects = new Array();
// Add collision object to collision
this.addObject = function(newOb){
this.cObjects.push(newOb);
return this;
}
// Update collision position
this.updatePosition = function(){
this.x = this.parent.getX();
this.y = this.parent.getY();
return this;
}
// Update collision angle
this.updateAngle = function(){
this.angle = this.parent.angle;
return this;
}
}
// === Collision objects ===
// Triangle collision object
// p1, p2, p3 are three points of triangle
function cTriangle(p1, p2, p3){
// Temporary points
this.p1 = p1;
this.p2 = p2;
this.p3 = p3;
// Original points
this.orP1 = createPoint(p1);
this.orP2 = createPoint(p2);
this.orP3 = createPoint(p3);
// Rotare triangle on angle 'angle' from current position
this.rotate = function(angle){
rotatePoint(this.p1, angle);
rotatePoint(this.p2, angle);
rotatePoint(this.p3, angle);
return this;
}
// Reset triangle on original position
this.reset = function(){
copyPoint(this.p1, this.orP1);
copyPoint(this.p2, this.orP2);
copyPoint(this.p3, this.orP3);
return this;
}
// Rotate triangle on specific angle 'angle' from original position
this.setOrientation = function(angle){
this.reset();
this.rotate(angle);
return this;
}
// Translate triangle on dx, dy from current position
this.translate = function(dx, dy){
translatePoint(this.p1, dx, dy);
translatePoint(this.p2, dx, dy);
translatePoint(this.p3, dx, dy);
return this;
}
}
// Circle collision object
// 'center' is a center of collision circle (point object)
// 'radius' is a radius of collision object
function cCircle(center, radius){
// Temporary center
this.c = center;
// Original center
this.orC = createPoint(center);
// Radius
this.r = radius;
// Rotate center of circle on 'angle' from current position
this.rotate = function(angle){
rotatePoint(this.c, angle);
return this;
}
// Reset circle on original position
this.reset = function(){
copyPoint(this.c, this.orC);
return this;
}
// Rotate center of circle on 'angle' from original position
this.setOrientation = function(angle){
this.reset();
this.rotate(angle);
return this;
}
// Translate circle on dx, dy
this.translate = function(dx, dy){
translatePoint(this.c, dx, dy);
return this;
}
}
// isCollide check if two collision collide with each other
// 'cObje1', 'cObje2' are collisions, objects of type "standardCollision"
isCollide = function(cObje1, cObje2){
var d2 = (cObje1.x-cObje2.x)*(cObje1.x-cObje2.x)+(cObje1.y-cObje2.y)*(cObje1.y-cObje2.y);
if(d2<((cObje1.r+cObje2.r)*(cObje1.r+cObje2.r))){
// if one of the objects is a point?
if(cObje1.r*cObje2.r == 0){
// Who is a point?
var pObject; // Point object
var sObject; // Some object
if(cObje1.r == 0){
pObject = cObje1;
sObject = cObje2;
}else{
pObject = cObje2;
sObject = cObje1;
}
// sObject is a just a circle?
if(sObject.cObjects.length == 0){
// Yes
return true;
}else{
// No, and we have to check it children
var objPoint = new Point(pObject.x, pObject.y);
for(var i=0; i<sObject.cObjects.length; i++){
sObject.cObjects[i].reset().rotate(sObject.angle).translate(sObject.x, sObject.y);
if(sObject.cObjects[i] instanceof cTriangle)
if(triangle2point(sObject.cObjects[i], objPoint))
return true;
if(sObject.cObjects[i] instanceof cCircle)
if(circle2point(sObject.cObjects[i], objPoint))
return true;
}
return false;
}
}else{
// One or both objects just a circle?
if(cObje1.cObjects.length*cObje2.cObjects.length == 0){
if(cObje1.cObjects.length + cObje2.cObjects.length == 0 ){
// They are both circles
return true;
}
// One object is circle another some thing else
var cirObject;
var sObject;
if(cObje1.cObjects.length == 0){
cirObject = cObje1;
sObject = cObje2;
}else{
cirObject = cObje2;
sObject = cObje1;
}
var objCircle = new Circle(new Point(cirObject.x, cirObject.y), cirObject.r);
for(var i=0; i<sObject.cObjects.length; i++){
sObject.cObjects[i].reset().rotate(sObject.angle).translate(sObject.x, sObject.y);
// Triangle?
if(sObject.cObjects[i] instanceof cTriangle)
if(circle2triangle(objCircle, sObject.cObjects[i]))
return true;
// Circle?
if(sObject.cObjects[i] instanceof cCircle)
if(circle2circle(objCircle, sObject.cObjects[i]))
return true;
}
return false;
}else{
// Each object has complecs structure
for(var i=0; i<cObje1.cObjects.length; i++){
cObje1.cObjects[i].reset().rotate(cObje1.angle).translate(cObje1.x, cObje1.y);
for(var j=0; j<cObje2.cObjects.length; j++){
cObje2.cObjects[j].reset().rotate(cObje2.angle).translate(cObje2.x, cObje2.y);
// First object is triangle?
if(cObje1.cObjects[i] instanceof cTriangle){
// Triangle to Triangle
if(cObje2.cObjects[j] instanceof cTriangle)
if(triangle2triangle(cObje1.cObjects[i], cObje2.cObjects[j]))
return true;
//Triangle to Circle
if(cObje2.cObjects[j] instanceof cCircle)
if(circle2triangle(cObje2.cObjects[j], cObje1.cObjects[i]))
return true;
}
// First object is Circle?
if(cObje1.cObjects[i] instanceof cCircle){
// Circle to Triangle
if(cObje2.cObjects[j] instanceof cTriangle)
if(circle2triangle(cObje1.cObjects[i], cObje2.cObjects[j]))
return true;
if(cObje2.cObjects[j] instanceof cCircle)
if(circle2circle(cObje1.cObjects[i], cObje2.cObjects[j]))
return true;
}
}
}
return false;
}
}
}else{
return false
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment