Collision for rotated bodies. What is most efficient?

[Anderberg]

I am developing a shoot em up where I of course have to detect collisions/overlaps between sprites. Since there will be a lot of bullets on the screen, I need to do really efficient collision detection. No physics such as gravity, friction or the like is necessary.

 

I started out using the Arcade system, but since it cannot handle rotated bodies I have to search for something else (for me it was really confusing that the Arcade physics has several properties that sound like it can actually do rotation, when the bodies cannot be rotated).

 

Anyway, I am trying out P2 instead. First of all, is P2 the best to use? It seems a bit "heavy" for what I want to do.

 

If I need P2, what ways are there to cut down the computations that I do not need?

I have set these properties, are there any more to look into?

game.physics.p2.applyDamping = false;

game.physics.p2.applyGravity = false;

game.physics.p2.applySpringForces = false;

game.physics.p2.solveConstraints = false;

game.physics.p2.setImpactEvents(true);

 

Thankful for any input

[gregmax17]

I don't have any experience with phaser or p2 (I am posting my own experience here), if you really want to improve performance you can do one of 2 things:

 

1 - keep the collisions simple, like circles only, unless you "really" need to have your bodies be the exact outline shape of your sprite

2 - reduce the number of bodies on screen

[lewster32]

P2 is heavy and should be used for situations where you need more advanced physics in general. Oftentimes you don't need the collisions to be totally accurate, and so a common technique is to reduce the size of the sprite's body until it 'mostly covers' the visible area of the sprite.

 

In most games it's usually preferable to have the body smaller than the sprite rather than have invisible corners colliding with things - it's better to let players get away with a near miss that should have been a hit than have them frustrated when something clearly doesn't look like it's colliding with them. If you were applying a body to a triangle for instance, you may want to do it like the below diagram.

 

[Anderberg]

gregmax17: Certainly, I will try to stick mainly to rectangles as hit areas and then work my way upwards in the number of bodies.

 

lewster32: Great idea! This is probably the approach I will use. I will however have to recalculate the boxes as the object rotates, I'll google some mathematics for how to do that.

[InsaneHero]

I had to do this a few years back for a Flash game I was writing and I found quite a few solutions online.

This is my AS3 adaptation of the best one I found, should be easy to convert to JS.

Note however that it's still pretty complex for "rotated rect vs rotated rect" collisions and in most cases you simply don't need that accuracy - lewster's suggestion of making the axis-aligned boxes a bit smaller than the enemy is the way we always did it for 8 bit games (which are kind of the bench-mark for bullet hell gaming!)  Circles are sometimes better than shrunken AABBs depending on the shape of the target, and you can speed that check up by using the square of the radius to avoid a square root (dx = x2 - x1; dy = y2 - y1; distance2 = dx * dx + dy * dy; if (distance2 < radius2) // it hit!)

		// rx, ry are the centre point of the rectangle		public static function IsXYInsideRotatedRect(px:Number, py:Number, rx:Number, ry:Number, rw:Number, rh:Number, rotRad:Number):Boolean		{			// calc offset from rect to point			var dx:Number = px - rx;			var dy:Number = py - ry;			// precalc trig for rect rotation			var sin:Number = Math.sin(rotRad);			var cos:Number = Math.cos(rotRad);			// rotate point offset around rect by -'ve rect's own rotation			var x2:Number = dx * cos + dy * sin;			var y2:Number = -dx * sin + dy * cos;			// precalc half width/height			var hw:Number = rw * 0.5;			var hh:Number = rh * 0.5;			// point vs rect AABB collision detection			return (x2 > -hw && x2 < hw && y2 > -hh && y2 < hh);		}				        // Rotated Rectangles Collision Detection, Oren Becker, 2001        // AS3 conversion Pete Baron, 2010        public static function RotatedRectsCollide(x1:Number, y1:Number, x1width:Number, y1height:Number, rotation1:Number, x2:Number, y2:Number, x2width:Number, y2height:Number, rotation2:Number):Boolean        {            var Ax : Number, Ay : Number, Bx : Number, By : Number;		// vertices of the rotated rr2            var Cx : Number, Cy : Number;								// center of rr2            var BLx : Number, BLy : Number, TRx : Number, TRy : Number;	// vertices of rr2 (bottom-left, top-right)             var ang : Number = rotation1 - rotation2;    // orientation of rotated rr1 relative to rr2            var cosa : Number = Math.cos(ang);           // precalc trig values            var sina : Number = Math.sin(ang);            var cosa2 : Number = Math.cos(rotation2);            var sina2 : Number = Math.sin(rotation2);             var t : Number, t2 : Number, x : Number, a : Number;		// temps            var dx : Number;											// deltaX for linear equations            var ext1 : Number, ext2 : Number;							// min/max vertical values             x1width *= 0.5;            y1height *= 0.5;            x2width *= 0.5;            y2height *= 0.5;             // move rr2 to make rr1 cannonic            t = x2 - x1;            Cy = y2 - y1;             // rotate rr2 clockwise by rr2->ang to make rr2 axis-aligned            BLx = TRx = t * cosa2 + Cy * sina2;            BLy = TRy = -t * sina2 + Cy * cosa2;             // calculate vertices of (moved and axis-aligned := 'ma') rr2            BLx -= x2width;            BLy -= y2height;            TRx += x2width;            TRy += y2height;             // calculate vertices of (rotated := 'r') rr1            Bx = Ax = -y1height * sina;            t = x1width * cosa;            Ax += t;            Bx -= t;             By = Ay = y1height * cosa;            t = x1width * sina;            Ay += t;            By -= t;             t = sina * cosa;             // verify that A is vertical min/max, B is horizontal min/max            if (t < 0)            {				// BUGFIX: this used to mess up 't' which is used later for if (t == 0)                t2 = Ax; Ax = Bx; Bx = t2;                t2 = Ay; Ay = By; By = t2;            }             // verify that B is horizontal minimum (leftest-vertex)            if (sina < 0)            {                Bx = -Bx;                By = -By;            }             // if rr2(ma) isn't in the horizontal range of            // colliding with rr1(r), collision is impossible            if (Bx > TRx || Bx > -BLx)                return false;             // if rr1(r) is axis-aligned, vertical min/max are easy to get            if (t == 0)            {                ext1 = Ay;                ext2 = -ext1;            }            // else, find vertical min/max in the range [BL.x, TR.x]            else            {                x = BLx - Ax;                a = TRx - Ax;                ext1 = Ay;                // if the first vertical min/max isn't in (BL.x, TR.x), then                // find the vertical min/max on BL.x or on TR.x                if (a * x > 0)                {                    dx = Ax;                    if (x < 0)                    {                        dx -= Bx;                        ext1 -= By;                        x = a;                    }                    else                    {                        dx += Bx;                        ext1 += By;                    }                    ext1 *= x;                    ext1 /= dx;                    ext1 += Ay;                }                 x = BLx + Ax;                a = TRx + Ax;                ext2 = -Ay;                 // if the second vertical min/max isn't in (BLx, TRx), then                // find the local vertical min/max on BLx or on TRx                if (a * x > 0)                {                    dx = -Ax;                    if (x < 0)                    {                        dx -= Bx;                        ext2 -= By;                        x = a;                    }                    else                    {                        dx += Bx;                        ext2 += By;                    }                    ext2 *= x;                    ext2 /= dx;                    ext2 -= Ay;                }            }			            // check whether rr2(ma) is in the vertical range of colliding with rr1(r)            // (for the horizontal range of rr2)            return !((ext1 < BLy && ext2 < BLy) || (ext1 > TRy && ext2 > TRy));        }

[Wavertron]

Could you use P2 with only rectangles and/or circles? Perhaps that will still be speedy enough while allowing you to do rotation as well. Wouldn't be too hard to test it out

[Anderberg]

Thanks for the help!

I will start out using the arcade system and have quite quadratic sprites or smaller bounding boxes. Then I might add spheres and perhaps even more advanced like insaneHero's code if it is necessary.

I did try out some P2, but didn't get very far into it. The fps on my mobile dropped almost 20, with only about 20 bullets on screen. But it could probably be improved, for example by turning off impacts and using onBeginContact (as suggested here: http://www.html5gamedevs.com/topic/9931-mobile-performance-tips-tricks/)

While searching I found this page which might help those coming here for answers: http://gamemechanicexplorer.com

Now I will try to create lasers for the game, which will be rotated. So I thought I should try out parts of the raycasting example from the link above.