• # DIY 2D Vector Physics

Math and Physics

2D physics libraries like Box2D and Chipmunk are fine things, but not for every game. Sometimes they're total overkill. Other times, technical constraints force you to go your own way. Sometimes you just want to avoid the well-worn path trod by countless Limbo and Angry Birds knock-offs. Whatever the reason, here are some algorithms to get you started should you opt to do it yourself. BACKGROUND Having worked on a physics-library-based space shooter, I was acutely aware of the difficulties. First of all, you need concave polygons. Our spaceships weren't, so we had to divide them into a bunch of little triangles using a fancy algorithm. When the ships collided, the triangles would fly apart and snap back together as if held together with elastic, sometimes with part of the other ship wedged in between - not the effect we had in mind. And then there were issues with "bullet tunneling", and the general pain of storing part of our objects' state in a black box - even if it is an open-source black box. If I had to do it all over again, I'd use simple bounding-circle collisions. That's exactly what the MARS guys did. After that ordeal, and with HTML5 coming into vogue a few years back, I decided to make a nice, simple, slow-paced, sailing ship battle game... in JavaScript. I tried a JS port of the Chipmunk physics engine, but it was just too slow. So, I looked up the algorithms I really needed, and implemented them in about 100 lines of JavaScript. And when HTML5 soured on me and I switched to C++ for my next game, porting the code was a piece of cake. I love working this way. DESIGN There are three kinds of objects in my naval combat game: 1. Ships - a few slow-moving convex polygons 2. Cannonballs - many fast-moving point particles 3. Land masses - a few large static polygons I only need to check for ship-vs-ship, ship-vs-cannonball, and ship-vs-land collisions. What are the algorithms for those? 1. Ship vs Cannonball - polygon vs line segment. 2. Ship vs Land - point vs polygon. Shorelines are fuzzy and imprecise, so for this purpose I treat ships as point particles. 3. Ship vs Ship - polygon vs polygon, specifically convex hulls (literally!) There's no need for joints, polygon stacking, or polygon-vs-polygon continuous collision detection (Box2D creator Erin Catto wrote some great papers about that; it's rather advanced for DIYers but definitely worth reading). I also use bounding boxes for first-pass collision detection. That's just an optimization, and it's easy, so I'll leave it as an exercise to the reader. Potentially I might need a spatial partitioning scheme (e.g. quadtrees) if I create an MMO with huge sprawling maps. I haven't done that, and it could get complicated, so I'll leave it at that and move on. ALGORITHMS A few notes on the following code: - This is working JavaScript code from my game, with only minor edits for clarity. - Porting to C, C++, and similar languages should be very direct in most cases. - Polygons are stored as flat interleaved arrays: [x1,y1, x2,y2, ...] - Points are stored as [x,y] arrays for consistency with polygons. (Yes, p[0] is a little harder to type than p.x but I got used to it and I prefer it now. And anyway, it'll be a moot point if/when array-oriented languages come back into vogue.) One piece of advice: if you intend to roll your own physics engine, allow yourself a few weeks to iron it out (maybe months, if you have ambitious goals). Study the algorithms. Code up some demos. Step through the algorithms in a debugger. Get comfortable with the math. Look for other algorithms that might suit your particular needs better than these ones. LINE VS LINE This is the standard line intersection formula, useful for all kinds of things.  function lineIntersection(a,b, c,d){ var v,u,d,r,s; v= [ d[0]-c[0], d[1]-c[1] ]; u= [ b[0]-a[0], b[1]-a[1] ]; d= u[0]*v[1] - u[1]*v[0]; r= ((a[1]-c[1])*v[0] - (a[0]-c[0])*v[1]) / d; s= ((a[1]-c[1])*u[0] - (a[0]-c[0])*u[1]) / d; return (0<=r && r<=1 && 0<=s && s<=1); }  LINE VS POLYGON To detect when a cannonball hits a ship, trace a line from the cannonball's previous position (last frame) to its current position, and test to see if it crossed any line segment of the ship's hull. This is reasonably accurate even if the framerate drops to a miserable 10 fps. This is an easy form of Continuous Collision Detection that's ideal for CCD's main use cases: bullets and beam weapons.  // a, b = [x,y] // edges = [x1,y1, x2,y2, ...] // function linePolygonIntersection(a,b, edges){ var c,d,i; d= edges.slice(edges.length-2); for(i=0; i POINT VS POLYGON This is one of the many elegant "even-odd rule" algorithms. Starting at the point in question, trace a line in any direction and count how many times it crosses the polygon. If it's an odd number, the point is inside the polygon. It's really just a Line-vs-Polygon algorithm, optimized for a horizontal line. // point = [x,y] // polygon = [x1,y1, x2,y2, ...] // function isPointInPolygon(point, polygon){ var tx= point[0], ty=point[1]; var a; var b= polygon.slice(polygon.length-2); var yflag0= (b[1] >= ty); var yflag1; var inside_flag=false; for(var j=0; j= ty); if(yflag0 != yflag1){ // vertexes straddle our point's Y-coord: potential hit. // LERP to check X-coord... if(yflag1 == ((b[1]-ty) * (a[0]-b[0]) >= (b[0]-tx) * (a[1]-b[1]))) inside_flag= !inside_flag; } yflag0= yflag1; } return inside_flag; } POLYGON VS POLYGON I'm using the Separating Axis Theorem (SAT) algorithm. It's not "the best" but it's relatively simple and fast enough for most purposes. Right: if we project along every line of both ship polygons, we always get an overlap (no separation), so the ships have collided. The axis with the smallest overlap (red) provides the 'separation vector' which tells us exactly how far we must move one ship to resolve the collision state. We could also move each ship half that amount, or whatever makes sense. Left: there is at least one separating axis, therefore the ships have not collided. // Algorithm: // For each side, compute its "axis" (normal vector), B. Normalize it. // Project each vertex, of both polygons, onto the axis. // Note: dot(A,B) is an adequate approximation of proj(A,B) for this purpose. // Keep track of min and max values for each polygon. // If there's an axis with no overlap - a SEPARATING AXIS - we can stop. // If the min/max values overlap on all sides, we have a collision. // Use the smallest overlap to separate the shapes. // // P1,P2 = two *convex* polygons in [x,y, x,y, ...] format // cx = canvas context for debug drawing (optional) // function collidePolyPoly(P1, P2, cx){ var collision= true; var dmin= -Infinity; var collaxis= null; function _projectVerts(P1, P2, flip){ var A=P1, B=P2; var v1; var v2= A.slice(A.length-2); for(var i=0; imaxA) maxA=t; } var minB= vdot(axis, B.slice(0,2)); var maxB= minB; for(var j=2; jmaxB) maxB=t; } var d0= minA-maxB; var d1= minB-maxA; var d= Math.max(d0,d1); if(d>0){ collision=false; return null; } if(d>dmin){ // keep track of minimum separation vector dmin=d; collaxis={ vector: axis, dist: d, midpt: midpt, poly: (d0d1)^flip, }; } } } _projectVerts(P1,P2,false); if(!collision) return null; _projectVerts(P2,P1,true); if(!collision) return null; var sep= vscale(collaxis.vector, collaxis.dist); if(cx) drawLine(cx, collaxis.midpt, vadd(collaxis.midpt, sep), 'red', 0.2); return { vector: sep, poly: collaxis.poly, flip: collaxis.flip, }; } // vector math helpers function vadd(a,b){ return [a[0]+b[0], a[1]+b[1]]; } function vsub(a,b){ return [a[0]-b[0], a[1]-b[1]]; } function vscale(v,s){ return [v[0]*s, v[1]*s]; } function vdot(a,b) { return a[0] * b[0] + a[1] * b[1]; } function vcross(a,b) { return a[0] * b[1] - a[1] * b[0]; } function vlerp(a, b, lerp) { return [a[0] + lerp * (b[0] - a[0]), a[1] + lerp * (b[1] - a[1])]; } function vnormal(v){ // return a perpendicular unit vector var mag = Math.sqrt(v[0]*v[0] + v[1]*v[1]); return [-v[1]/mag, v[0]/mag]; // normalize & perpendicularize } // debug-draw helper function drawLine(cx, p1, p2, color, weight){ if(!cx) return; cx.strokeStyle=color; cx.lineWidth=weight; cx.beginPath(); cx.moveTo(p1[0],p1[1]); cx.lineTo(p2[0],p2[1]); cx.stroke(); } NOTES I mentioned that I'm using similar algorithms in my current C++ sidescroller project. One advantage over physics libraries is that I'm able to use the same structure-of-arrays data for collisions, skeleton animation, and rendering. These old algorithms are heavy on Structures-of-Arrays, a staple of modern CPU/GPU/cache optimization and Data Oriented Design. That was a happy accident. The code felt questionable to me at first, I hadn't heard of DOD, and optimization would have been premature at the time. It was only when I started porting to C++/OpenGL that I realized how well these algorithms fit today's hardware. While backporting recent improvements from C++ to JS, I used interleaved arrays to overcome JS's lack of pointers. For example, by storing splines as flat arrays (ax1,ay1, ax2,ay2, ax3,ay3, ...) I can refer to any spline node, point, or x/y value by an array index, which eliminates a bit of slow/cumbersome indirection. SOURCES Line Intersection formula from the comp.graphics.algorithms FAQ (section 1.03) Point vs Polygon ptinpoly.c (by Eric Haines, in Graphic Gems IV) (I used the last algorithm, "CrossingsMultiplyTest") SAT visual explanation + Flash demo SAT tutorial with formulas + VB code Related article on gamedev.net: Shooting At Stuff (how to aim at moving targets) ARTICLE UPDATE LOG 29 Nov 2015: Initial release 2 Dec 2015: Formatting fixes

 
 0   Report Article 
 Sign in to follow this   Followers 0 Go to articles Math and Physics 
 User Feedback 6 Comments 0 Reviews Randy Gaul 2792 Posted December 2, 2015 Cool article, I enjoyed reading. Despite me sounding nit-picky it still might a good idea to change the article title; there's no physics here. You've written good content about collision detection, which is a different topic than physics. Physics implies forces, equations, motion, simulation, etc. Share this comment Link to comment Share on other sites tnovelli 1190 Posted December 2, 2015 Thanks! You're right, this is 90% collision detection, but I'm presenting it as an alternative to shrink-wrapped physics libraries, so I'll leave "physics" in the title. Kinematics and forces are relatively straightforward (unless you're making a sailing sim...) and there are already some good articles on that subject here. Share this comment Link to comment Share on other sites lede 591 Posted December 2, 2015 Thanks for the great collision info.  The only thing I found hard to follow is your magic numbers in the array stacks.  It just makes your code harder to follow.  You could just assign a local variable the values o and 1 to help clarify what each array index represents.   Other then that great work! Share this comment Link to comment Share on other sites tookie 396 Posted December 10, 2015 Great article! It would be nice if you can add the C++ code I always had problems with the minimal separation vector in my SAT implementations :( Share this comment Link to comment Share on other sites tnovelli 1190 Posted December 13, 2015 Allright @TookieToon @lede, here's the first function in C++, with alias vars... untested :D bool lineIntersection(     double ax, double ay, double bx, double by,     double cx, double cy, double dx, double dy) { double vx,vy, ux,uy, dd,r,s; vx = dx-cx; vy = dy-cy; ux = bx-ax; uy = by-ay; dd = ux*vy - uy*vx; r = ((ay-cy)*vx - (ax-cx)*vy) / dd; s = ((ay-cy)*ux - (ax-cx)*uy) / dd; return (0<=r && r<=1 && 0<=s && s<=1); } Yeah, it figures that my C++ game code is nothing like a direct port of the JS. Sometime I'll do a direct port of that SAT code and upload it to Github. The main difference, the vector functions take a destination first argument instead of returning it. So for example var edge = vsub(v2,v1); becomes double edge; vsub(edge,v2,v1); ...and actually, I've inlined most of that stuff.   I've never found a great notation for vector components. There's "vector swizzling" in GLSL (also possible in Lua) where you can declare vec2 v and then refer to v.x, v.y, but I think it's almost as cluttered as v[0], v[1]. I think I'd prefer automatic suffix generation (vx, vy or v0, v1) even if the declaration is a bit magical. You could probably do it with C++ macros, something like this... #define vectorize(v) double &v#x = v[0], &v#y = v[1] #define vector(v) double v[2]; vectorize(v) bool lineIntersection(double a[2], .....){ vectorize(a); vectorize(b); vectorize(c); vectorize(d); vector(u); vector(v); double dd,r,s;    vx = dx-cx; vy = dy-cy; .... Meh... maybe I'll try it. Share this comment Link to comment Share on other sites ccuccherini 352 Posted July 29, 2016 Very informative article.  Once I get to this point in my game developments (and get some of this math under my belt) this is definitely something I will keep in mind. Share this comment Link to comment Share on other sites Create an account or sign in to comment You need to be a member in order to leave a comment Create an account Sign up for a new account in our community. It's easy! Register a new account Sign in Already have an account? Sign in here. Sign In Now 
•  
 
 Advertisement 
 Advertisement Categories 29Audio 29Music and Sound FX 200Business 125Business and Law 36Career Development 39Production and Management 191Game Design 185Game Design and Theory 3Writing for Games 3UX for Games 233Industry 172Interviews 61Event Coverage 1165Programming 55Artificial Intelligence 616General and Gameplay Programming 322Graphics and GPU Programming 56Engines and Middleware (and 2 more) 65Visual Arts 34Archive Show all categories   Advertisement GameDev.net GameDev.net Articles GameDev.net Event Coverage GameDev.net Forums GameDev.net Blogs GameDev.net Gallery GameDev.net News GameDev.net Projects GDNet Chat All Activity Search In Everywhere This Category This Article More options... Find results that contain... All of my search term words Any of my search term words Find results in... Content titles and body Content titles only Home Articles Programming Math and Physics DIY 2D Vector Physics 
 
 
 × Existing user? Sign In Sign Up Browse Back Articles & Tutorials Back All Categories Audio Business Game Design Industry Programming Visual Arts Columns Back GameDev Unboxed Event Coverage Back All Events Game Developers Conference Power Up Digital Games Conference GameDev.Market Links News Podcasts Back All Podcasts Game Dev Loadout Archive Community Back Beginners Back Beginners Group Beginners Forum Beginners Resources Blogs Calendar Chat Forums Back All Forums Audio Business Game Design Programming Visual Arts Community GameDev Challenges Affiliates Topical Workshops Gallery Groups Back For Beginners GameDev Challenges All Groups Projects Back All Projects Games Game Assets Game Mods Developer Tools Store Careers Back Contractors Hobby Projects Game Jobs Back Browse on GameDev.Jobs Post a Job Members Back Chat GDNet+ Membership Guidelines Leaderboard Online Users Awards Search Back All Activity My Activity Streams Back Latest Topics Featured Blogs Search var ipsDebug=false;var CKEDITOR_BASEPATH='//www.gamedev.net/applications/core/interface/ckeditor/ckeditor/';var ipsSettings={cookie_path:"/",cookie_prefix:"ips4_",cookie_ssl:true,upload_imgURL:"",message_imgURL:"",notification_imgURL:"",baseURL:"//www.gamedev.net/",jsURL:"//www.gamedev.net/applications/core/interface/js/js.php",csrfKey:"207d83473d5d650892f75dbce37f764d",antiCache:"2a361a8a02",disableNotificationSounds:false,useCompiledFiles:true,links_external:true,memberID:0,analyticsProvider:"ga",viewProfiles:true,mapProvider:'google',mapApiKey:"AIzaSyAeT7tk3vnWWmbgVISkLpbhkQvekG19rHM",}; ips.setSetting('date_format',jQuery.parseJSON('"mm\/dd\/yy"'));ips.setSetting('date_first_day',jQuery.parseJSON('0'));ips.setSetting('remote_image_proxy',jQuery.parseJSON('1'));ips.setSetting('ipb_url_filter_option',jQuery.parseJSON('"none"'));ips.setSetting('url_filter_any_action',jQuery.parseJSON('"allow"'));ips.setSetting('bypass_profanity',jQuery.parseJSON('0'));ips.setSetting('emoji_style',jQuery.parseJSON('"native"'));ips.setSetting('emoji_shortcodes',jQuery.parseJSON('"1"'));ips.setSetting('emoji_ascii',jQuery.parseJSON('"1"'));ips.setSetting('emoji_cache',jQuery.parseJSON('"1"'));ips.setSetting('quickSearchDefault',jQuery.parseJSON('"all"'));ips.setSetting('quickSearchMinimum',jQuery.parseJSON('3'));ips.setSetting('quickSearchShowAdv',jQuery.parseJSON('true'));ips.setSetting('quickSearchIn',jQuery.parseJSON('"title"')); { "@context": "http://schema.org", "@type": "Article", "url": "https://www.gamedev.net/articles/programming/math-and-physics/diy-2d-vector-physics-r4106/", "discussionUrl": "https://www.gamedev.net/articles/programming/math-and-physics/diy-2d-vector-physics-r4106/", "mainEntityOfPage": "https://www.gamedev.net/articles/programming/math-and-physics/diy-2d-vector-physics-r4106/", "name": "DIY 2D Vector Physics", "headline": "DIY 2D Vector Physics", "text": "2D physics libraries like Box2D and Chipmunk are fine things, but not for every game. Sometimes they\u0027re total overkill. Other times, technical constraints force you to go your own way. Sometimes you just want to avoid the well-worn path trod by countless Limbo and Angry Birds knock-offs. Whatever the reason, here are some algorithms to get you started should you opt to do it yourself.\n\n\nBACKGROUND\n\nHaving worked on a physics-library-based space shooter, I was acutely aware of the difficulties. First of all, you need concave polygons. Our spaceships weren\u0027t, so we had to divide them into a bunch of little triangles using a fancy algorithm. When the ships collided, the triangles would fly apart and snap back together as if held together with elastic, sometimes with part of the other ship wedged in between - not the effect we had in mind. And then there were issues with \"bullet tunneling\", and the general pain of storing part of our objects\u0027 state in a black box - even if it is an open-source black box.\n\nIf I had to do it all over again, I\u0027d use simple bounding-circle collisions. That\u0027s exactly what the MARS guys did.\n\nAfter that ordeal, and with HTML5 coming into vogue a few years back, I decided to make a nice, simple, slow-paced, sailing ship battle game... in JavaScript. I tried a JS port of the Chipmunk physics engine, but it was just too slow. So, I looked up the algorithms I really needed, and implemented them in about 100 lines of JavaScript. And when HTML5 soured on me and I switched to C++ for my next game, porting the code was a piece of cake. I love working this way.\n\n\nDESIGN\n\nThere are three kinds of objects in my naval combat game:\n\n 1. Ships - a few slow-moving convex polygons\n 2. Cannonballs - many fast-moving point particles\n 3. Land masses - a few large static polygons\n\nI only need to check for ship-vs-ship, ship-vs-cannonball, and ship-vs-land collisions. What are the algorithms for those?\n\n\t1. Ship vs Cannonball - polygon vs line segment.\n\t2. Ship vs Land - point vs polygon. Shorelines are fuzzy and imprecise, so for this purpose I treat ships as point particles.\n\t3. Ship vs Ship - polygon vs polygon, specifically convex hulls (literally!)\n\nThere\u0027s no need for joints, polygon stacking, or polygon-vs-polygon continuous collision detection (Box2D creator Erin Catto wrote some great papers about that; it\u0027s rather advanced for DIYers but definitely worth reading).\n\nI also use bounding boxes for first-pass collision detection. That\u0027s just an optimization, and it\u0027s easy, so I\u0027ll leave it as an exercise to the reader.\n\nPotentially I might need a spatial partitioning scheme (e.g. quadtrees) if I create an MMO with huge sprawling maps. I haven\u0027t done that, and it could get complicated, so I\u0027ll leave it at that and move on.\n\n\nALGORITHMS\n\nA few notes on the following code:\n\n\t- This is working JavaScript code from my game, with only minor edits for clarity.\n\t- Porting to C, C++, and similar languages should be very direct in most cases.\n\t- Polygons are stored as flat interleaved arrays: [x1,y1, x2,y2, ...]\n\t- Points are stored as [x,y] arrays for consistency with polygons. (Yes, p[0] is a little harder to type than p.x but I got used to it and I prefer it now. And anyway, it\u0027ll be a moot point if/when array-oriented languages come back into vogue.)\n\nOne piece of advice: if you intend to roll your own physics engine, allow yourself a few weeks to iron it out (maybe months, if you have ambitious goals). Study the algorithms. Code up some demos. Step through the algorithms in a debugger. Get comfortable with the math. Look for other algorithms that might suit your particular needs better than these ones.\n\n\nLINE VS LINE\n\n\n\nThis is the standard line intersection formula, useful for all kinds of things.\n\n\nfunction lineIntersection(a,b, c,d){\n var v,u,d,r,s;\n\tv= [ d[0]-c[0], d[1]-c[1] ];\n\tu= [ b[0]-a[0], b[1]-a[1] ];\n\n\td= u[0]*v[1] - u[1]*v[0];\n\tr= ((a[1]-c[1])*v[0] - (a[0]-c[0])*v[1]) / d;\n\ts= ((a[1]-c[1])*u[0] - (a[0]-c[0])*u[1]) / d;\n\n\treturn (0\n\n\nLINE VS POLYGON\n\n\n\nTo detect when a cannonball hits a ship, trace a line from the cannonball\u0027s previous position (last frame) to its current position, and test to see if it crossed any line segment of the ship\u0027s hull. This is reasonably accurate even if the framerate drops to a miserable 10 fps. This is an easy form of Continuous Collision Detection that\u0027s ideal for CCD\u0027s main use cases: bullets and beam weapons.\n\n\n// a, b = [x,y]\n// edges = [x1,y1, x2,y2, ...]\n//\nfunction linePolygonIntersection(a,b, edges){\n\tvar c,d,i;\n d= edges.slice(edges.length-2);\n\tfor(i=0; i\n\n\nPOINT VS POLYGON\n\n\n\nThis is one of the many elegant \"even-odd rule\" algorithms. Starting at the point in question, trace a line in any direction and count how many times it crosses the polygon. If it\u0027s an odd number, the point is inside the polygon.\n\nIt\u0027s really just a Line-vs-Polygon algorithm, optimized for a horizontal line.\n\n\n// point = [x,y]\n// polygon = [x1,y1, x2,y2, ...]\n//\nfunction isPointInPolygon(point, polygon){\n\tvar tx= point[0], ty=point[1];\n\tvar a;\n var b= polygon.slice(polygon.length-2);\n\tvar yflag0= (b[1] \u0026gt;= ty);\n\tvar yflag1;\n\tvar inside_flag=false;\n\n\tfor(var j=0; j= ty);\n\t\tif(yflag0 != yflag1){\n\t\t\t// vertexes straddle our point\u0027s Y-coord: potential hit.\n\t\t\t// LERP to check X-coord...\n\t\t\tif(yflag1 == ((b[1]-ty) * (a[0]-b[0]) \u0026gt;=\n\t\t\t\t\t\t (b[0]-tx) * (a[1]-b[1])))\n\t\t\t\tinside_flag= !inside_flag;\n\t\t}\n\t\tyflag0= yflag1;\n\t}\n\treturn inside_flag;\n}\n\n\n\nPOLYGON VS POLYGON\n\nI\u0027m using the Separating Axis Theorem (SAT) algorithm. It\u0027s not \"the best\" but it\u0027s relatively simple and fast enough for most purposes.\n\n\n\nRight: if we project along every line of both ship polygons, we always get an overlap (no separation), so the ships have collided. The axis with the smallest overlap (red) provides the \u0027separation vector\u0027 which tells us exactly how far we must move one ship to resolve the collision state. We could also move each ship half that amount, or whatever makes sense.\n\nLeft: there is at least one separating axis, therefore the ships have not collided.\n\n\n// Algorithm:\n// For each side, compute its \"axis\" (normal vector), B. Normalize it.\n// Project each vertex, of both polygons, onto the axis.\n// Note: dot(A,B) is an adequate approximation of proj(A,B) for this purpose.\n// Keep track of min and max values for each polygon.\n// If there\u0027s an axis with no overlap - a SEPARATING AXIS - we can stop.\n// If the min/max values overlap on all sides, we have a collision.\n// Use the smallest overlap to separate the shapes.\n//\n// P1,P2 = two *convex* polygons in [x,y, x,y, ...] format\n// cx = canvas context for debug drawing (optional)\n//\nfunction collidePolyPoly(P1, P2, cx){\n\tvar collision= true;\n\tvar dmin= -Infinity;\n\tvar collaxis= null;\n\n\tfunction _projectVerts(P1, P2, flip){\n\t\tvar A=P1, B=P2;\n\n\t\tvar v1;\n var v2= A.slice(A.length-2);\n\t\tfor(var i=0; imaxA) maxA=t;\n\t\t\t}\n\n\t\t\tvar minB= vdot(axis, B.slice(0,2));\n\t\t\tvar maxB= minB;\n\t\t\tfor(var j=2; jmaxB) maxB=t;\n\t\t\t}\n\n\t\t\tvar d0= minA-maxB;\n\t\t\tvar d1= minB-maxA;\n\t\t\tvar d= Math.max(d0,d1);\n\t\t\tif(d\u0026gt;0){\n\t\t\t\tcollision=false;\n\t\t\t\treturn null;\n\t\t\t}\n\t\t\tif(d\u0026gt;dmin){\n\t\t\t\t// keep track of minimum separation vector\n\t\t\t\tdmin=d;\n\t\t\t\tcollaxis={\n\t\t\t\t\tvector: axis,\n\t\t\t\t\tdist: d,\n\t\t\t\t\tmidpt: midpt,\n\t\t\t\t\tpoly: (d0d1)^flip,\n\t\t\t\t};\n\t\t\t}\n\t\t}\n\t}\n\n\t_projectVerts(P1,P2,false);\n\tif(!collision) return null;\n\n\t_projectVerts(P2,P1,true);\n\tif(!collision) return null;\n\n\tvar sep= vscale(collaxis.vector, collaxis.dist);\n\n\tif(cx) drawLine(cx, collaxis.midpt,\n\t\t\tvadd(collaxis.midpt, sep),\n\t\t\t\u0027red\u0027, 0.2);\n\n\treturn {\n\t\tvector: sep,\n\t\tpoly: collaxis.poly,\n\t\tflip: collaxis.flip,\n\t};\n}\n\n// vector math helpers\nfunction vadd(a,b){ return [a[0]+b[0], a[1]+b[1]]; }\nfunction vsub(a,b){ return [a[0]-b[0], a[1]-b[1]]; }\nfunction vscale(v,s){ return [v[0]*s, v[1]*s]; }\nfunction vdot(a,b) { return a[0] * b[0] + a[1] * b[1]; }\nfunction vcross(a,b) { return a[0] * b[1] - a[1] * b[0]; }\nfunction vlerp(a, b, lerp) {\n\treturn [a[0] + lerp * (b[0] - a[0]),\n\t\t\ta[1] + lerp * (b[1] - a[1])];\n}\nfunction vnormal(v){\n\t// return a perpendicular unit vector\n\tvar mag = Math.sqrt(v[0]*v[0] + v[1]*v[1]);\n\treturn [-v[1]/mag, v[0]/mag]; // normalize \u0026amp; perpendicularize\n}\n\n// debug-draw helper\nfunction drawLine(cx, p1, p2, color, weight){\n\tif(!cx) return;\n\tcx.strokeStyle=color;\n\tcx.lineWidth=weight;\n\tcx.beginPath();\n\tcx.moveTo(p1[0],p1[1]);\n\tcx.lineTo(p2[0],p2[1]);\n\tcx.stroke();\n}\n\n\n\nNOTES\n\nI mentioned that I\u0027m using similar algorithms in my current C++ sidescroller project. One advantage over physics libraries is that I\u0027m able to use the same structure-of-arrays data for collisions, skeleton animation, and rendering.\n\nThese old algorithms are heavy on Structures-of-Arrays, a staple of modern CPU/GPU/cache optimization and Data Oriented Design. That was a happy accident. The code felt questionable to me at first, I hadn\u0027t heard of DOD, and optimization would have been premature at the time. It was only when I started porting to C++/OpenGL that I realized how well these algorithms fit today\u0027s hardware.\n\nWhile backporting recent improvements from C++ to JS, I used interleaved arrays to overcome JS\u0027s lack of pointers. For example, by storing splines as flat arrays (ax1,ay1, ax2,ay2, ax3,ay3, ...) I can refer to any spline node, point, or x/y value by an array index, which eliminates a bit of slow/cumbersome indirection.\n\n\nSOURCES\n\nLine Intersection formula from the comp.graphics.algorithms FAQ (section 1.03)\nPoint vs Polygon\nptinpoly.c (by Eric Haines, in Graphic Gems IV) (I used the last algorithm, \"CrossingsMultiplyTest\")\nSAT visual explanation + Flash demo\nSAT tutorial with formulas + VB code\n\nRelated article on gamedev.net: Shooting At Stuff (how to aim at moving targets)\n\n\nARTICLE UPDATE LOG\n\n29 Nov 2015: Initial release\n2 Dec 2015: Formatting fixes", "articleBody": "2D physics libraries like Box2D and Chipmunk are fine things, but not for every game. Sometimes they\u0027re total overkill. Other times, technical constraints force you to go your own way. Sometimes you just want to avoid the well-worn path trod by countless Limbo and Angry Birds knock-offs. Whatever the reason, here are some algorithms to get you started should you opt to do it yourself.\n\n\nBACKGROUND\n\nHaving worked on a physics-library-based space shooter, I was acutely aware of the difficulties. First of all, you need concave polygons. Our spaceships weren\u0027t, so we had to divide them into a bunch of little triangles using a fancy algorithm. When the ships collided, the triangles would fly apart and snap back together as if held together with elastic, sometimes with part of the other ship wedged in between - not the effect we had in mind. And then there were issues with \"bullet tunneling\", and the general pain of storing part of our objects\u0027 state in a black box - even if it is an open-source black box.\n\nIf I had to do it all over again, I\u0027d use simple bounding-circle collisions. That\u0027s exactly what the MARS guys did.\n\nAfter that ordeal, and with HTML5 coming into vogue a few years back, I decided to make a nice, simple, slow-paced, sailing ship battle game... in JavaScript. I tried a JS port of the Chipmunk physics engine, but it was just too slow. So, I looked up the algorithms I really needed, and implemented them in about 100 lines of JavaScript. And when HTML5 soured on me and I switched to C++ for my next game, porting the code was a piece of cake. I love working this way.\n\n\nDESIGN\n\nThere are three kinds of objects in my naval combat game:\n\n 1. Ships - a few slow-moving convex polygons\n 2. Cannonballs - many fast-moving point particles\n 3. Land masses - a few large static polygons\n\nI only need to check for ship-vs-ship, ship-vs-cannonball, and ship-vs-land collisions. What are the algorithms for those?\n\n\t1. Ship vs Cannonball - polygon vs line segment.\n\t2. Ship vs Land - point vs polygon. Shorelines are fuzzy and imprecise, so for this purpose I treat ships as point particles.\n\t3. Ship vs Ship - polygon vs polygon, specifically convex hulls (literally!)\n\nThere\u0027s no need for joints, polygon stacking, or polygon-vs-polygon continuous collision detection (Box2D creator Erin Catto wrote some great papers about that; it\u0027s rather advanced for DIYers but definitely worth reading).\n\nI also use bounding boxes for first-pass collision detection. That\u0027s just an optimization, and it\u0027s easy, so I\u0027ll leave it as an exercise to the reader.\n\nPotentially I might need a spatial partitioning scheme (e.g. quadtrees) if I create an MMO with huge sprawling maps. I haven\u0027t done that, and it could get complicated, so I\u0027ll leave it at that and move on.\n\n\nALGORITHMS\n\nA few notes on the following code:\n\n\t- This is working JavaScript code from my game, with only minor edits for clarity.\n\t- Porting to C, C++, and similar languages should be very direct in most cases.\n\t- Polygons are stored as flat interleaved arrays: [x1,y1, x2,y2, ...]\n\t- Points are stored as [x,y] arrays for consistency with polygons. (Yes, p[0] is a little harder to type than p.x but I got used to it and I prefer it now. And anyway, it\u0027ll be a moot point if/when array-oriented languages come back into vogue.)\n\nOne piece of advice: if you intend to roll your own physics engine, allow yourself a few weeks to iron it out (maybe months, if you have ambitious goals). Study the algorithms. Code up some demos. Step through the algorithms in a debugger. Get comfortable with the math. Look for other algorithms that might suit your particular needs better than these ones.\n\n\nLINE VS LINE\n\n\n\nThis is the standard line intersection formula, useful for all kinds of things.\n\n\nfunction lineIntersection(a,b, c,d){\n var v,u,d,r,s;\n\tv= [ d[0]-c[0], d[1]-c[1] ];\n\tu= [ b[0]-a[0], b[1]-a[1] ];\n\n\td= u[0]*v[1] - u[1]*v[0];\n\tr= ((a[1]-c[1])*v[0] - (a[0]-c[0])*v[1]) / d;\n\ts= ((a[1]-c[1])*u[0] - (a[0]-c[0])*u[1]) / d;\n\n\treturn (0\n\n\nLINE VS POLYGON\n\n\n\nTo detect when a cannonball hits a ship, trace a line from the cannonball\u0027s previous position (last frame) to its current position, and test to see if it crossed any line segment of the ship\u0027s hull. This is reasonably accurate even if the framerate drops to a miserable 10 fps. This is an easy form of Continuous Collision Detection that\u0027s ideal for CCD\u0027s main use cases: bullets and beam weapons.\n\n\n// a, b = [x,y]\n// edges = [x1,y1, x2,y2, ...]\n//\nfunction linePolygonIntersection(a,b, edges){\n\tvar c,d,i;\n d= edges.slice(edges.length-2);\n\tfor(i=0; i\n\n\nPOINT VS POLYGON\n\n\n\nThis is one of the many elegant \"even-odd rule\" algorithms. Starting at the point in question, trace a line in any direction and count how many times it crosses the polygon. If it\u0027s an odd number, the point is inside the polygon.\n\nIt\u0027s really just a Line-vs-Polygon algorithm, optimized for a horizontal line.\n\n\n// point = [x,y]\n// polygon = [x1,y1, x2,y2, ...]\n//\nfunction isPointInPolygon(point, polygon){\n\tvar tx= point[0], ty=point[1];\n\tvar a;\n var b= polygon.slice(polygon.length-2);\n\tvar yflag0= (b[1] \u0026gt;= ty);\n\tvar yflag1;\n\tvar inside_flag=false;\n\n\tfor(var j=0; j= ty);\n\t\tif(yflag0 != yflag1){\n\t\t\t// vertexes straddle our point\u0027s Y-coord: potential hit.\n\t\t\t// LERP to check X-coord...\n\t\t\tif(yflag1 == ((b[1]-ty) * (a[0]-b[0]) \u0026gt;=\n\t\t\t\t\t\t (b[0]-tx) * (a[1]-b[1])))\n\t\t\t\tinside_flag= !inside_flag;\n\t\t}\n\t\tyflag0= yflag1;\n\t}\n\treturn inside_flag;\n}\n\n\n\nPOLYGON VS POLYGON\n\nI\u0027m using the Separating Axis Theorem (SAT) algorithm. It\u0027s not \"the best\" but it\u0027s relatively simple and fast enough for most purposes.\n\n\n\nRight: if we project along every line of both ship polygons, we always get an overlap (no separation), so the ships have collided. The axis with the smallest overlap (red) provides the \u0027separation vector\u0027 which tells us exactly how far we must move one ship to resolve the collision state. We could also move each ship half that amount, or whatever makes sense.\n\nLeft: there is at least one separating axis, therefore the ships have not collided.\n\n\n// Algorithm:\n// For each side, compute its \"axis\" (normal vector), B. Normalize it.\n// Project each vertex, of both polygons, onto the axis.\n// Note: dot(A,B) is an adequate approximation of proj(A,B) for this purpose.\n// Keep track of min and max values for each polygon.\n// If there\u0027s an axis with no overlap - a SEPARATING AXIS - we can stop.\n// If the min/max values overlap on all sides, we have a collision.\n// Use the smallest overlap to separate the shapes.\n//\n// P1,P2 = two *convex* polygons in [x,y, x,y, ...] format\n// cx = canvas context for debug drawing (optional)\n//\nfunction collidePolyPoly(P1, P2, cx){\n\tvar collision= true;\n\tvar dmin= -Infinity;\n\tvar collaxis= null;\n\n\tfunction _projectVerts(P1, P2, flip){\n\t\tvar A=P1, B=P2;\n\n\t\tvar v1;\n var v2= A.slice(A.length-2);\n\t\tfor(var i=0; imaxA) maxA=t;\n\t\t\t}\n\n\t\t\tvar minB= vdot(axis, B.slice(0,2));\n\t\t\tvar maxB= minB;\n\t\t\tfor(var j=2; jmaxB) maxB=t;\n\t\t\t}\n\n\t\t\tvar d0= minA-maxB;\n\t\t\tvar d1= minB-maxA;\n\t\t\tvar d= Math.max(d0,d1);\n\t\t\tif(d\u0026gt;0){\n\t\t\t\tcollision=false;\n\t\t\t\treturn null;\n\t\t\t}\n\t\t\tif(d\u0026gt;dmin){\n\t\t\t\t// keep track of minimum separation vector\n\t\t\t\tdmin=d;\n\t\t\t\tcollaxis={\n\t\t\t\t\tvector: axis,\n\t\t\t\t\tdist: d,\n\t\t\t\t\tmidpt: midpt,\n\t\t\t\t\tpoly: (d0d1)^flip,\n\t\t\t\t};\n\t\t\t}\n\t\t}\n\t}\n\n\t_projectVerts(P1,P2,false);\n\tif(!collision) return null;\n\n\t_projectVerts(P2,P1,true);\n\tif(!collision) return null;\n\n\tvar sep= vscale(collaxis.vector, collaxis.dist);\n\n\tif(cx) drawLine(cx, collaxis.midpt,\n\t\t\tvadd(collaxis.midpt, sep),\n\t\t\t\u0027red\u0027, 0.2);\n\n\treturn {\n\t\tvector: sep,\n\t\tpoly: collaxis.poly,\n\t\tflip: collaxis.flip,\n\t};\n}\n\n// vector math helpers\nfunction vadd(a,b){ return [a[0]+b[0], a[1]+b[1]]; }\nfunction vsub(a,b){ return [a[0]-b[0], a[1]-b[1]]; }\nfunction vscale(v,s){ return [v[0]*s, v[1]*s]; }\nfunction vdot(a,b) { return a[0] * b[0] + a[1] * b[1]; }\nfunction vcross(a,b) { return a[0] * b[1] - a[1] * b[0]; }\nfunction vlerp(a, b, lerp) {\n\treturn [a[0] + lerp * (b[0] - a[0]),\n\t\t\ta[1] + lerp * (b[1] - a[1])];\n}\nfunction vnormal(v){\n\t// return a perpendicular unit vector\n\tvar mag = Math.sqrt(v[0]*v[0] + v[1]*v[1]);\n\treturn [-v[1]/mag, v[0]/mag]; // normalize \u0026amp; perpendicularize\n}\n\n// debug-draw helper\nfunction drawLine(cx, p1, p2, color, weight){\n\tif(!cx) return;\n\tcx.strokeStyle=color;\n\tcx.lineWidth=weight;\n\tcx.beginPath();\n\tcx.moveTo(p1[0],p1[1]);\n\tcx.lineTo(p2[0],p2[1]);\n\tcx.stroke();\n}\n\n\n\nNOTES\n\nI mentioned that I\u0027m using similar algorithms in my current C++ sidescroller project. One advantage over physics libraries is that I\u0027m able to use the same structure-of-arrays data for collisions, skeleton animation, and rendering.\n\nThese old algorithms are heavy on Structures-of-Arrays, a staple of modern CPU/GPU/cache optimization and Data Oriented Design. That was a happy accident. The code felt questionable to me at first, I hadn\u0027t heard of DOD, and optimization would have been premature at the time. It was only when I started porting to C++/OpenGL that I realized how well these algorithms fit today\u0027s hardware.\n\nWhile backporting recent improvements from C++ to JS, I used interleaved arrays to overcome JS\u0027s lack of pointers. For example, by storing splines as flat arrays (ax1,ay1, ax2,ay2, ax3,ay3, ...) I can refer to any spline node, point, or x/y value by an array index, which eliminates a bit of slow/cumbersome indirection.\n\n\nSOURCES\n\nLine Intersection formula from the comp.graphics.algorithms FAQ (section 1.03)\nPoint vs Polygon\nptinpoly.c (by Eric Haines, in Graphic Gems IV) (I used the last algorithm, \"CrossingsMultiplyTest\")\nSAT visual explanation + Flash demo\nSAT tutorial with formulas + VB code\n\nRelated article on gamedev.net: Shooting At Stuff (how to aim at moving targets)\n\n\nARTICLE UPDATE LOG\n\n29 Nov 2015: Initial release\n2 Dec 2015: Formatting fixes", "dateCreated": "2015-06-27T18:02:12+0000", "datePublished": "2015-12-02T01:32:00+0000", "dateModified": "2015-12-02T01:32:00+0000", "pageStart": 1, "pageEnd": 1, "author": { "@type": "Person", "name": "tnovelli", "image": "https://www.gamedev.net/uploads/profile/photo-216081.png", "url": "https://www.gamedev.net/profile/216081-tnovelli/" }, "publisher": { "@type": "Organization", "name": "tnovelli", "image": "https://www.gamedev.net/uploads/profile/photo-216081.png", "logo": { "@type": "ImageObject", "url": "https://www.gamedev.net/uploads/profile/photo-216081.png" }, "url": "https://www.gamedev.net/profile/216081-tnovelli/" }, "interactionStatistic": [ { "@type": "InteractionCounter", "interactionType": "http://schema.org/ViewAction", "userInteractionCount": 15668 }, { "@type": "InteractionCounter", "interactionType": "http://schema.org/FollowAction", "userInteractionCount": 3 }, { "@type": "InteractionCounter", "interactionType": "http://schema.org/ReviewAction", "userInteractionCount": 0 }, { "@type": "InteractionCounter", "interactionType": "http://schema.org/CommentAction", "userInteractionCount": 6 } ], "image": { "@type": "ImageObject", "url": "https://www.gamedev.net/uploads/fd1050f4d0f96ea55bd1e8efec42a773.png", "width": 250, "height": 150 }, "aggregateRating": { "@type": "AggregateRating", "ratingValue": 4.5, "ratingCount": 11, "reviewCount": 0, "bestRating": "5" }, "commentCount": 6 } { "@context": "http://www.schema.org", "@type": "WebSite", "name": "GameDev.net", "url": "https://www.gamedev.net/", "potentialAction": { "type": "SearchAction", "query-input": "required name=query", "target": "https://www.gamedev.net/search/?q={query}" }, "inLanguage": [ { "@type": "Language", "name": "English (USA)", "alternateName": "en-US" } ] } { "@context": "http://www.schema.org", "@type": "Organization", "name": "GameDev.net", "url": "https://www.gamedev.net/", "logo": "https://www.gamedev.net/uploads/themes/monthly_2017_04/gamedev-logo-2017-368x76.png.e986e41d566ff6c90485a5304985ed5f.png", "address": { "@type": "PostalAddress", "streetAddress": "", "addressLocality": null, "addressRegion": null, "postalCode": null, "addressCountry": null } } { "@context": "http://schema.org", "@type": "BreadcrumbList", "itemListElement": [ { "@type": "ListItem", "position": 1, "item": { "@id": "https://www.gamedev.net/articles/", "name": "Articles" } }, { "@type": "ListItem", "position": 2, "item": { "@id": "https://www.gamedev.net/articles/programming/", "name": "Programming" } }, { "@type": "ListItem", "position": 3, "item": { "@id": "https://www.gamedev.net/articles/programming/math-and-physics/", "name": "Math and Physics" } } ] } { "@context": "http://schema.org", "@type": "ContactPage", "url": "https://www.gamedev.net/contact/" } Important Information By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.   I accept We are the game development community. Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up! Sign me up!