I've written lots of collision detection algorithms using lots of different techniques - however, the Minkowski is one of the best - it's very flexible easy to understand (especially in 2d).
The following gives a tutorial/visualization for working with the Minkowski algorithm.
While the algorithm can work with any 'convex' shapes - this demo focuses on 'boxes'.
Screenshot of the test demo of the minkowski different for collision detection and feature extraction demo.
The demo is interactive and runs in a web-browser - you can drag your mouse around and it displays the minkowski information (and the collision feature data).
Complete Code
<html><head></head>
<body>
<style>
body { min-height: 700px; }
* { margin: 0;
padding: 0;
}
.grid {
height: 100%;
width: 100%;
margin: 0;
}
.grid {
background-image:
repeating-linear-gradient(#ccc 0 1px, transparent 1px 100%),
repeating-linear-gradient(90deg, #ccc 0 1px, transparent 1px 100%);
background-size: 71px 71px;
}
</style>
<div class="grid"></div>
<div id='hit' style="font-size:20pt;position:absolute;left:10px;top:20px;"></div>
<div style="font-size:10pt;position:absolute;width:480px;left:10px;bottom:20px;">
A robust 2D collision detection demo with feature extraction information, such as,
contact points, penetration depth and hit (true/false).
Minkowski difference for 2d boxes and shortest distance algorithms.
Demo shows the Minkowski points (A-B), box A, box B and calculation features (educational purposes). Author: Kenwright (www.xbdev.net)
</div>
<script>
function vec2(x, y)
{
this.x = x;
this.y = y;
this.set = function(x, y)
{
this.x = x;
this.y = y;
}
};
vec2.add = function(v0, v1){ return new vec2(v0.x+v1.x, v0.y+v1.y); }
vec2.sub = function(v0, v1){ return new vec2(v0.x-v1.x, v0.y-v1.y); }
vec2.scale = function(v0, s ){ return new vec2(v0.x*s, v0.y*s); }
vec2.mul = function(v0, v1){ return new vec2(v0.x*v1.x, v0.y*v1.y); }
vec2.cross = function(v0,v1) { return (v0.x*v1.y - v0.y*v1.x); }
vec2.dot = function(v0, v1){ return (v0.x*v1.x + v0.y*v1.y); }
// note you can't use 'length' word
//vec2.length = function(v0 ){ return Math.sqrt( v0.x*v0.x + v0.y*v0.y); }
vec2.dist = function(v0) { return Math.sqrt( v0.x*v0.x + v0.y*v0.y); }
vec2.norm = function(v0 )
{
let ln = Math.sqrt( v0.x*v0.x + v0.y*v0.y);
return vec2.scale( v0, 1.0/ln );
}
vec2.perp = function(n ){ return new vec2(n.y, -n.x); }
let off = new vec2(300,300);
const maxobjs = 1000;
var numobjs2 = 0;
var objs = [];
function cleardraw2()
{
numobjs2 = 0;
for (let i=0; i<objs.length; i++)
{
objs[i].style.left = '-1000px';
}
}
function setupdraw()
{
numobjs2 = 0;
for (let i=0; i<maxobjs; i++)
{
let div = document.createElement('div');
document.body.appendChild( div );
objs.push( div );
}
}
setupdraw();
/*
helper function for drawing lines using 'div'
elements (use a bit of trigonometry to set the size
and orientation to create a line)
*/
function drawLine(s0, s1, col='blue')
{
let ax = s0.x + off.x;
let ay = s0.y + off.y;
let bx = s1.x + off.x;
let by = s1.y + off.y;
//console.log( numobjs2 );
console.assert( numobjs2 < maxobjs );
let div = objs[numobjs2];
numobjs2++;
//if ( div == 0 )
{
//div = document.createElement('div');
//document.body.appendChild( div );
}
div.style.position = 'absolute';
if(ay>by)
{
bx=ax+bx;
ax=bx-ax;
bx=bx-ax;
by=ay+by;
ay=by-ay;
by=by-ay;
}
let calc = Math.atan((ax-bx)/(by-ay));
calc = calc*180.0/Math.PI;
let length = Math.sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by));
div.style.height = length + "px";
div.style.width = 2 + "px";
div.style.left = ax + "px";
div.style.top = ay + "px";
div.style.transform = 'rotate(' + calc + 'deg)';
div.style.transformOrigin="0 0";
div.style.backgroundColor=col;//"blue";
}
function drawCross( v0, s, col='black' )
{
let x = new vec2(s,0);
let y = new vec2(0,s);
drawLine( vec2.sub(v0,x), vec2.add(v0,x), col );
drawLine( vec2.sub(v0,y), vec2.add(v0,y), col );
}
function drawArrow(v0, v1, s, color='blue')
{
drawLine( v0, v1, color );
// Calculate the direction of the line
const direction = vec2.norm( new vec2(v1.x - v0.x, v1.y - v0.y) );
// Perpendicular vectors for the arrowhead
const perp1 = vec2.scale( new vec2(-direction.y, direction.x), s);
const perp2 = vec2.scale( new vec2(direction.y, -direction.x), s);
// Calculate the end points of the arrowhead
const arrowHeadPoint1 = new vec2(v1.x - direction.x * s + perp1.x, v1.y - direction.y * s + perp1.y);
const arrowHeadPoint2 = new vec2(v1.x - direction.x * s + perp2.x, v1.y - direction.y * s + perp2.y);
// Draw the arrowhead
drawLine(v1, arrowHeadPoint1, color);
drawLine(v1, arrowHeadPoint2, color);
}
function drawCircle(s0, r, col='red')
{
let ax = s0.x + off.x;
let ay = s0.y + off.y;
console.assert( numobjs2 < maxobjs );
let div = objs[numobjs2];
numobjs2++;
div.style.position = 'absolute';
div.style.height = r*2 + "px";
div.style.width = r*2 + "px";
div.style.left = (ax-r) + "px";
div.style.top = (ay-r) + "px";
div.style['border-radius'] = '50%';
div.style.backgroundColor=col;
}
function drawBox(p0, s0, angle, col='red')
{
const halfWidth = s0.x;
const halfHeight = s0.y;
// Calculate the rotated corner points
const cos = Math.cos(angle);
const sin = Math.sin(angle);
// Calculate the positions of the four corners
const topLeft = {
x: p0.x + (-halfWidth * cos - -halfHeight * sin),
y: p0.y + (-halfWidth * sin + -halfHeight * cos)
};
const topRight = {
x: p0.x + (halfWidth * cos - -halfHeight * sin),
y: p0.y + (halfWidth * sin + -halfHeight * cos)
};
const bottomRight = {
x: p0.x + (halfWidth * cos - halfHeight * sin),
y: p0.y + (halfWidth * sin + halfHeight * cos)
};
const bottomLeft = {
x: p0.x + (-halfWidth * cos - halfHeight * sin),
y: p0.y + (-halfWidth * sin + halfHeight * cos)
};
// Draw the square
/*
ctx.beginPath();
ctx.moveTo(topLeft.x, topLeft.y);
ctx.lineTo(topRight.x, topRight.y);
ctx.lineTo(bottomRight.x, bottomRight.y);
ctx.lineTo(bottomLeft.x, bottomLeft.y);
ctx.closePath();
ctx.stroke();
*/
drawLine( topLeft, topRight );
drawLine( topRight, bottomRight );
drawLine( bottomRight, bottomLeft );
drawLine( bottomLeft, topLeft );
}
function drawShape( s )
{
for (let i=1; i<s.length; i++)
{
drawLine(s[i-1], s[i]);
drawCircle( s[i-1], 5 );
}
drawLine(s[0], s[s.length-1]);
drawCircle( s[s.length-1], 5 );
}
function shape()
{
this.points = [];
this.addPoint = function( v )
{
this.points.push( new vec2(v.x, v.y) );
}
this.draw = function()
{
drawShape( this.points );
}
/*
this.drawPoints = function()
{
for (let i=1; i<this.points.length; i++)
{
drawCircle( this.points[i-1], 6, 'green' );
}
drawCircle( this.points[this.points.length-1], 6, 'green' );
}
*/
this.getCentroid = function()
{
let v = new vec2(0,0);
for (let i=0; i<this.points.length; i++)
{
v = vec2.add( v, this.points[i] );
}
v = vec2.scale( v, 1/this.points.length );
return v;
}
}
let boxA = { p: new vec2(100,100),
s: new vec2(100, 50),
a: 0.6 };
let boxB = { p: new vec2(200,50),
s: new vec2(60, 120),
a: 1.1 };
function rotatePoint( point, angle )
{
let c = Math.cos(angle);
let s = Math.sin(angle);
return new vec2(
point.x * c - point.y * s,
point.x * s + point.y * c
);
}
function stHit() {
var pen = 0.0;
var normal = new vec2(0,0);
var point = new vec2(0,0);
};
let cur = new vec2(0,0); // mouse position
function closestPoint( pA, pB, pX )
{
let b = vec2.dist( vec2.sub(pB,pA) );
if ( b < 0.0001 )
{
return pA;
}
let n = vec2.norm( vec2.sub(pB,pA) );
let pAX = vec2.sub(pX, pA);
let s = vec2.dot( n, pAX );
let a = vec2.dist( vec2.scale(n,s) );
let t = a/b;
if ( t <= 0 ) return pA;
if ( t >= 1 ) return pB;
let pT = vec2.add( pA, vec2.scale( vec2.sub(pB,pA), t ) );
return pT;
}
// order points for a triangle are in a
// clockwise or counterclockwise direction
function getCW(v1,v2,v3)
{
let n1 = vec2.norm( vec2.sub(v2,v1) );
let n2 = vec2.norm( vec2.sub(v3,v1) );
let d = vec2.cross(n1,n2);
if ( d < 0 ) return -1;
return 1;
}
function MinkowskiBox(boxA, boxB)
{
this.shapeA = [];
this.shapeB = [];
this.shapeBA = [];
let corners = [ new vec2( -1, -1 ),
new vec2( 1, -1 ),
new vec2( 1, 1 ),
new vec2( -1, 1 ) ];
for (let i=0; i<4; i++)
{
this.shapeA.push( vec2.add( rotatePoint( vec2.mul(corners[i], boxA.s) , boxA.a ), boxA.p ) );
this.shapeB.push( vec2.add( rotatePoint( vec2.mul(corners[i], boxB.s) , boxB.a ), boxB.p ) );
}
let c = 0;
for (let i=0; i<this.shapeA.length; i++)
{
let pA = this.shapeA[i];
for (let k=0; k<this.shapeB.length; k++)
{
let pB = this.shapeB[k];
let pBA = vec2.sub( pB, pA );
this.shapeBA.push( { p:pBA, a:pA, i:c, b:pB, ai:i, bi:k } );
c++;
}
}
this.getNumPoints = function()
{
return this.shapeA.length *
this.shapeB.length;
}
this.drawPoints = function()
{
drawShape( this.shapeA );
drawShape( this.shapeB );
for (let i=1; i<this.shapeBA; i++)
{
drawCircle( this.shapeBA[i-1].p, 6, 'green' );
}
drawCircle( this.shapeBA[this.shapeBA.length-1].p, 6, 'green' );
}
this.getSupport = function( dir )
{
let n = vec2.norm( dir );
let d = vec2.dot( this.shapeBA[0].p, n );
let h = 0;
for (let i=0; i<this.shapeBA.length; i++)
{
let t = vec2.dot( this.shapeBA[i].p, n );
if ( t > d )
{
d = t;
h = i;
}
}
return this.shapeBA[h];
}
this.collision = function()
{
let v1 = this.getSupport( new vec2(0, 1) );
let v2 = this.getSupport( new vec2(1, 0) );
let v3 = this.getSupport( new vec2(0,-1) );
if ( v2.i == v1.i || v2.i == v3.i )
{
// swap them around to keep things ordered clockwise
v2 = v3;
v3 = this.getSupport( new vec2(-1, 0) );
}
console.assert( v1.i != v2.i);
console.assert( v2.i != v3.i);
let edges = [];
edges.push( [v1, v2] );
edges.push( [v2, v3] );
edges.push( [v3, v1] );
let hullEdges = [];
let check = 0;
while ( edges.length > 0 )
{
let edge = edges.pop();
let n = vec2.norm( vec2.perp( vec2.sub( edge[0].p, edge[1].p ) ) );
let v4 = this.getSupport( n );
if ( v4.i == edge[0].i ||
v4.i == edge[1].i )
{
// save edge
hullEdges.push( edge );
}
else
{
edges.push( [ edge[0], v4 ] );
edges.push( [ v4 , edge[1] ] );
}
console.assert( edges.length < 100 );
check++;
console.assert(check<100);
}
let sdist = 10000;
let indx = 0;
for (let i=0; i<hullEdges.length; i++)
{
let edge = hullEdges[i];
drawLine( edge[0].p, edge[1].p, 'orange' );
let cp = closestPoint( edge[0].p, edge[1].p, new vec2(0,0) );
//drawCircle( cp, 4, 'yellow' );
let d = vec2.dist( vec2.sub( cp, new vec2(0,0) ) );
if ( d < sdist )
{
sdist = d;
indx = i;
}
}
let inside = getCW( new vec2(0,0),
hullEdges[indx][ 0 ].p,
hullEdges[indx][ 1 ].p );
let best = closestPoint( hullEdges[indx][ 0 ].p,
hullEdges[indx][ 1 ].p,
new vec2(0,0) );
drawCircle( best, 6, 'yellow' );
let df = vec2.dist( vec2.sub(hullEdges[indx][ 0 ].p,
hullEdges[indx][ 1 ].p) );
let d1 = vec2.dist( vec2.sub(hullEdges[indx][ 0 ].p,
best) );
let t = d1/df;
//console.log( 't:' + t + ', df:' + df + ', d1: ' + d1 );
console.assert( t >=0 && t <= 1 );
let a0 = hullEdges[indx][ 0 ].a;
let a1 = hullEdges[indx][ 1 ].a;
let x = vec2.add( a0, vec2.scale(vec2.sub( a1,a0 ), t ) );
drawCross( x, 40, 'orange' );
let b0 = hullEdges[indx][ 0 ].b;
let b1 = hullEdges[indx][ 1 ].b;
let y = vec2.add( b0, vec2.scale(vec2.sub( b1,b0 ), t ) );
drawCross( y, 40, 'orange' );
drawLine( x, y, 'red' );
let pen = vec2.dist( vec2.sub( x, y ) );
let nor = vec2.norm( vec2.sub( x, y ) );
let data = {hit:false,
p: pen,
n: nor };
if ( inside <= 0 )
{
data.hit = true;
}
var hit = new stHit();
hit.pen = pen * (inside<=0 ? -1 : 1);
hit.point = x;
hit.normal = nor;
return hit; // return collision data
}// end collision function
}
document.onmousemove = function(e)
{
cur.x = e.pageX;
cur.y = e.pageY;
cleardraw2();
drawCircle(new vec2(0,0), 8, 'black'); // origin
drawCross( new vec2(0,0), 20 ); // draw origin
//drawBox( boxA.p, boxA.s, boxA.a );
//drawBox( boxB.p, boxB.s, boxB.a );
drawCircle( cur, 3, 'orange' );
boxA.p = vec2.sub(cur,off);
let mink = new MinkowskiBox(boxA, boxB);
mink.drawPoints();
let hit = mink.collision();
/*
// get mouse position and offset the origin - debugging/visualization
// purposes
let cA = shapeA.getCentroid();
let delta = vec2.sub( vec2.sub(cur,off), cA );
for (let i=0; i<shapeA.points.length; i++)
{
shapeA.points[i] = vec2.add( shapeA.points[i], delta );
}
*/
let h0 = hit.point;
let h1 = vec2.add( hit.point, vec2.scale( hit.normal, -50.0 ) );
h0.y += 0;
h1.y += 0;
drawArrow( h0,
h1,
20.0, 'blue' );
let div = document.getElementById('hit');
div.innerHTML = 'Hit: ' + hit.pen.toFixed(2) + ( hit.pen < 0 ? ' <b>(HIT)</b>' : '' );
}
document.onmousemove( {pageX:100, pageY:100} );
</script>
</body>
</html>
The code is actually quiet elegant and compact - the code draws the lines and points using 'pure' html elements (no canvas drawing).
Just manipulates the html elements (div) so they can be used for drawing (of course combined with JavaScript).
