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
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