Explosions in Farseer (port from Box2D)

Topics: Developer Forum, User Forum
Jun 18, 2010 at 11:10 AM
Edited Oct 27, 2010 at 6:26 AM

I ported to Farseer 3.0 an implementation found in the Box2D forums for explosions. Maybe this will be useful for someone else besides me :)

As far as now, it works, but it does some weird stuff sometimes, it needs a lot of optimization too.

For a deep explanation in the logic behind, look at this thread. At the last page is the C++ code if you want to take a look to it.

 

    // Some useful structs
    struct shapeData
    {
        public Body body;
        public float min; // absolute angles
        public float max;
    }

    struct rayData
    {
        public float angle;
        public Vector2 pos;
    }

    /// <summary>
    /// This is a comprarer used for 
    /// detecting angle difference between rays
    /// </summary>
    class rayDataComparer : IComparer<rayData>
    {
        int IComparer<rayData>.Compare(rayData a, rayData b)
        {
            float diff = (a.angle - b.angle);
            if (diff > 0)
                return 1;
            else if (diff < 0)
                return -1;
            return 0;
        }
    }

    /// <summary>
    /// This is an explosive... it explodes.
    /// Original Code by Steven Lu
    /// (see http://www.box2d.org/forum/viewtopic.php?f=3&t=1688)
    /// Ported to Farseer 3.0
    /// </summary>
    public abstract class Explosive
    {
        const int MAX_SHAPES = 100;
        Dictionary<Fixture, List<Vector2>> exploded;
        rayDataComparer rdc;
        List<shapeData> data = new List<shapeData>();
        World world;

        public Explosive(World farseerWorld)
        {
            exploded = new Dictionary<Fixture, List<Vector2>>();
            rdc = new rayDataComparer();
            data = new List<shapeData>();
            world = farseerWorld;
        }

        /// <summary>
        /// This makes the explosive explode
        /// <param name="pos">
        /// The position where the explosion happens
        /// </param>
        /// <param name="radius">
        /// The explosion radius
        /// </param>
        /// <param name="maxForce">
        /// The explosion force at the explosion point
        /// (then is inversely proportional to the square of the distance)
        /// </param>
        /// <returns>
        /// A dictionnary containing all the "exploded" fixtures
        /// with a list of the applied impulses
        /// </returns>
        /// </summary>
        public virtual Dictionary<Fixture, List<Vector2>> Explode(Vector2 pos, float radius, float maxForce)
        {
            exploded.Clear();

            AABB aabb;
            aabb.LowerBound = pos + new Vector2(-radius, -radius);
            aabb.UpperBound = pos + new Vector2(radius, radius);
            Fixture[] shapes = new Fixture[MAX_SHAPES];

            int shapeCount = 0;
            // Query the world for overlapping shapes.
            world.QueryAABB(
                fixture =>
                {
                    shapes[shapeCount++] = fixture.Fixture;

                    // Continue the query.
                    return true;
                }, ref aabb);

            // check if the explosion point is contained inside of a shape
            bool isInsideSomething = false;
            for (int i = 0; i < shapeCount; ++i)
            {
                if (shapes[i].TestPoint(ref pos))
                {
                    isInsideSomething = true;
                    break;
                }
            }

            if (!isInsideSomething)
            {
                // per shape max/min angles for now
                rayData[] vals = new rayData[shapeCount * 2];
                int valIndex = 0;
                for (int i = 0; i < shapeCount; ++i)
                {
                    PolygonShape ps;
                    CircleShape cs = shapes[i].Shape as CircleShape;
					
					// If it is a circle, we create a diamond from it
                    if (cs != null)
                    {
                        Vertices v = new Vertices();
                        Vector2 vec = Vector2.Zero + new Vector2(cs.Radius, 0);
                        v.Add(vec);
                        vec = Vector2.Zero + new Vector2(0, cs.Radius);
                        v.Add(vec);
                        vec = Vector2.Zero + new Vector2(-cs.Radius, cs.Radius);
                        v.Add(vec);
                        vec = Vector2.Zero + new Vector2(0, -cs.Radius);
                        v.Add(vec);
                        ps = new PolygonShape(v);
                    }
                    else
                        ps = shapes[i].Shape as PolygonShape;

                    if ((shapes[i].Body.BodyType == BodyType.Dynamic) && ps != null)
                    {
                        Vector2 toCentroid = shapes[i].Body.GetWorldPoint(ps.Centroid) - pos;
                        float angleToCentroid = (float)Math.Atan2(toCentroid.Y, toCentroid.X);
                        float min = float.MaxValue;
                        float max = float.MinValue;
                        float minAbsolute = 0.0f;
                        float maxAbsolute = 0.0f;
                        Vector2 minPt = new Vector2(-1, -1);
                        Vector2 maxPt = new Vector2(1, 1);

                        for (int j = 0; j < (ps.Vertices.Count()); ++j)
                        {
                            Vector2 toVertex = (shapes[i].Body.GetWorldPoint(ps.Vertices[j]) - pos);
                            float newAngle = (float)Math.Atan2(toVertex.Y, toVertex.X);
                            float diff = (newAngle - angleToCentroid);

                            diff = (diff - MathHelper.Pi) % (2 * MathHelper.Pi); // the minus pi is important.
// It means cutoff for going other
// direction is at 180 deg where it
// needs to be
if (diff < 0.0f) diff += 2 * MathHelper.Pi; // correction for not handling negs diff -= MathHelper.Pi; if (Math.Abs(diff) > MathHelper.Pi) throw new ArgumentException("OMG!"); // Something's wrong,
// point not in shape but
// exists angle diff > 180
if (diff > max) { max = diff; maxAbsolute = newAngle; maxPt = shapes[i].Body.GetWorldPoint(ps.Vertices[j]); } if (diff < min) { min = diff; minAbsolute = newAngle; minPt = shapes[i].Body.GetWorldPoint(ps.Vertices[j]); } } vals[valIndex].angle = minAbsolute; vals[valIndex].pos = minPt; ++valIndex; vals[valIndex].angle = maxAbsolute; vals[valIndex].pos = maxPt; ++valIndex; } } Array.Sort(vals, 0, valIndex, rdc); data.Clear(); bool rayMissed = true; for (int i = 0; i < valIndex; ++i) { Fixture shape = null; float midpt; int iplus = (i == valIndex - 1 ? 0 : i + 1); if (vals[i].angle == vals[iplus].angle) continue; if (i == valIndex - 1) { // the single edgecase midpt = (vals[0].angle + MathHelper.Pi * 2 + vals[i].angle); } else { midpt = (vals[i + 1].angle + vals[i].angle); } midpt = midpt / 2; Vector2 p1 = pos; Vector2 p2 = radius * new Vector2((float)Math.Cos(midpt), (float)Math.Sin(midpt)) + pos; float fraction = 0; // RaycastOne bool hitClosest = false; world.RayCast((f, p, n, fr) => { Body body = f.Body; if (body.UserData != null) { int index = (int)body.UserData; if (index == 0) { // filter return -1.0f; } } hitClosest = true; shape = f; fraction = fr; return fr; }, p1, p2); //draws radius points if ((hitClosest) && (shape.Body.BodyType == BodyType.Dynamic)) { if ((data.Count() > 0) && (data.Last().body == shape.Body) && (!rayMissed)) { int laPos = data.Count - 1; shapeData la = data[laPos]; la.max = vals[iplus].angle; data[laPos] = la; } else { // make new shapeData d; d.body = shape.Body; d.min = vals[i].angle; d.max = vals[iplus].angle; data.Add(d); } if ((data.Count() > 1) && (i == valIndex - 1) && (data.Last().body == data.First().body) && (data.Last().max == data.First().min)) { shapeData fi = data[0]; fi.min = data.Last().min; data.RemoveAt(data.Count() - 1); data[0] = fi; while (data.First().min >= data.First().max) { fi.min -= MathHelper.Pi * 2; data[0] = fi; } } int lastPos = data.Count - 1; shapeData last = data[lastPos]; while ((data.Count() > 0) && (data.Last().min >= data.Last().max)) // just making sure min<max { last.min = data.Last().min - 2 * MathHelper.Pi; data[lastPos] = last; } rayMissed = false; } else { // add entry to data with body = NULL to indicate a lack of objects in this range.
// Useful for drawing/graphical/other purposes.
if (data.Count() > 0 && rayMissed && data.Last().body == null) { int laPos = data.Count - 1; shapeData la = data[laPos]; la.max = vals[iplus].angle; data[laPos] = la; } else { shapeData d; d.body = null; d.min = vals[i].angle; d.max = vals[iplus].angle; data.Add(d); } if ((data.Count() > 1) && (i == valIndex - 1) && (data.First().body == null) && (data.Last().max == data.First().min)) { shapeData fi = data[0]; fi.min = data.Last().min; data.RemoveAt(data.Count() - 1); while (data.First().min >= data.First().max) { fi.min -= MathHelper.Pi * 2; data[0] = fi; } } int lastPos = data.Count - 1; shapeData last = data[lastPos]; while ((data.Count() > 0) && (data.Last().min >= data.Last().max)) // just making sure min<max { last.min = data.Last().min - 2 * MathHelper.Pi; data[lastPos] = last; } rayMissed = true; // raycast did not find a shape } } for (int i = 0; i < data.Count(); ++i) { const int min_rays = 5; // for small arcs -- how many rays per shape/body/segment const float max_angle = MathHelper.Pi / 15; // max angle between rays (used when segment is large) const float edge_ratio = 1.0f / 40.0f; // ratio of arc length to angle from edges to first ray tested const float max_edge_offset = MathHelper.Pi / 90; // two degrees: maximum angle
// from edges to first ray tested
float arclen = data[i].max - data[i].min; if (data[i].body == null) { for (float j = data[i].min; j <= data[i].max; j += max_angle) { // Draw Debug stuff... if you want to. // Nothing found } continue; } float first = MathHelper.Min(max_edge_offset, edge_ratio * arclen); int inserted_rays = (int)Math.Ceiling((double)(((arclen - 2.0f * first) - (min_rays - 1) * max_angle) / max_angle)); if (inserted_rays < 0) inserted_rays = 0; float offset = (arclen - first * 2.0f) / ((float)min_rays + inserted_rays - 1); int jj = 0; for (float j = data[i].min + first; j <= data[i].max; j += offset) { Vector2 p1 = pos; Vector2 p2 = pos + radius * new Vector2((float)Math.Cos(j), (float)Math.Sin(j)); Vector2 hitpoint = Vector2.Zero; float minlambda = float.MaxValue; List<Fixture> fl = data[i].body.FixtureList; for (int x = 0; x < fl.Count; x++) { Fixture f = fl[x]; RayCastInput ri; ri.Point1 = p1; ri.Point2 = p2; ri.MaxFraction = 50f; RayCastOutput ro; if (f.RayCast(out ro, ref ri, 0)) { if (minlambda > ro.Fraction) { minlambda = ro.Fraction; hitpoint = ro.Fraction * p2 + (1 - ro.Fraction) * p1; } } // the force that is to be applied for this particular ray. // offset is angular coverage. lambda*length of segment is distance. float impulse = (arclen / (float)(min_rays + inserted_rays))
* maxForce * 180.0f / MathHelper.Pi * (1.0f - Math.Min(1.0f, minlambda)); // We Apply the impulse!!! Vector2 vectImp = Vector2.Dot(impulse * new Vector2((float)Math.Cos(j), (float)Math.Sin(j)), -ro.Normal) * new Vector2((float)Math.Cos(j), (float)Math.Sin(j)); data[i].body.ApplyLinearImpulse(vectImp, hitpoint); // We gather the fixtures for returning them Vector2 val = Vector2.Zero; List<Vector2> vectorList; if (exploded.TryGetValue(f, out vectorList)) { val.X += Math.Abs(vectImp.X); val.Y += Math.Abs(vectImp.Y); vectorList.Add(val); } else { vectorList = new List<Vector2>(); val.X = Math.Abs(vectImp.X); val.Y = Math.Abs(vectImp.Y); vectorList.Add(val); exploded.Add(f, vectorList); } if (minlambda > 1.0f) { hitpoint = p2; } ++jj; } } } } return exploded; } }

 

 

Any feedback would be welcome too :)

Edit: Updated the code solving a couple of bugs

Coordinator
Jun 18, 2010 at 4:20 PM

Very good Pnikosis. I'm considering adding stuff like that into the engine. Most games would probably be fine with just a simple explosion approximation. I could implement several different explosion strategies , this being the more advanced one.

What kind if weird stuff are we talking about here?

Jun 18, 2010 at 9:14 PM
Edited Jun 18, 2010 at 9:16 PM

Hi Genbox, now it's working fine. The weird stuff was because I used a bad implementation of the Dot product between two vectors, I changed it for Vector2.Dot() and now works like a charm :) (the code above already should do it). I'll try to improve it a little in case you want to add it to the engine.

Is very nice to see it working, in my game I can hide my character under a table for covering from the explosion, and then see how the table flies away xD

Developer
Jun 19, 2010 at 7:38 PM

Can we get a video Pnikosis?

 

Jun 21, 2010 at 6:58 AM
Edited Jun 21, 2010 at 7:03 AM

Hi Matt, here it is, the video is in slow motion :)

In the demo, I release a "misile" (the flying circle) that follows the main character. I placed two "towers" of tables so the misile collides (and thus, explodes) before reaching the character. Notice that the character is not affected by the explosion, as he is "protected" behind the tables. Notice too how depending on the explosion angle, the tables rotate differently.

Video

(The table legs don't collide with the character intentionally so he can slide under them)

It is drawn using the debug view as I haven't figured out how to draw sprites using the camera yet :$

Oct 24, 2010 at 12:21 PM

Thank you , Pnikosis and matt who gave me a sample like this.

I will try .

Oct 25, 2010 at 9:43 AM

I've found a couple of bugs in the code above, I'll update it as soon as I convert it from my game's code to a more "easy to port" one.

Coordinator
Oct 25, 2010 at 12:15 PM

When you have cleaned up the code and fix the bugs, could you upload the code here?

Oct 25, 2010 at 12:17 PM

Absolutely, I'll do it this afternoon :)

Oct 26, 2010 at 7:01 AM
Edited Oct 26, 2010 at 7:04 AM

Done :), I hope the port is ok (the original code uses a lot of custom classes from my own game that I had to clean up)

Also, I asked permission to the original author to add its (slightly modified and ported from C++) algorithm to the engine, and he kindly agreed. I credited him in the code as a comment.

Oct 26, 2010 at 4:45 PM
Thank you.
I will use it well.
Oct 27, 2010 at 2:05 AM

Can you give the fixed version?

Oct 27, 2010 at 6:27 AM

Done, blackdragon. You can use the code from the first post, which I just updated.

Oct 27, 2010 at 6:40 AM
aha, I understand.
Thank you
Coordinator
Oct 27, 2010 at 8:15 PM

I've just added this code to change set 79020.

Pnikosis: Could you take a look at the code? it is inside Common/PhysicsLogic/Explosion.cs. I commented out a few lines of code that seems to be unnecessary, could you see if they should be used or not? Another thing; do you have a good test of the code? A testbed sample perhaps?

Oct 28, 2010 at 7:37 AM

Ooops, I forgot to remove some lines that I used for drawing debug stuff. I'll take a look to teh code and add a sample using the same current sample structure. It will take a while though, as next week I'll be out :)

Oct 28, 2010 at 10:15 AM

Hi GenBox, I uploaded a new patch containing an updated explosion class (more commented code, I haven't removed it just in case), and a ExplosionTest class which can be added safely in the Farseer testbed (I tested it and works fine).

Nov 11, 2010 at 12:03 PM

By the way, the last version I uploaded (with the sampletest) returns a list of all the fixtures and the impulses applied using a dictionary (Dictionary<Fixture, List<Vector2>>), I'm not sure if this could result on a performance issue or not. Also I tried to reduce as much as possible the new object creation during the explosion.

Plus, there are a couple (well, 4) of values (stored as a constant) that can be changed in order to improve performance, but I wasn't sure if to add them as an option. These values are:

int minRays = 5; // for small arcs -- how many rays per shape/body/segment
float maxAngle = MathHelper.Pi / 15; // max angle between rays (used when segment is large)
float edgeRatio = 1.0f / 40.0f; // ratio of arc length to angle from edges to first ray tested
float maxEdgeOffset = MathHelper.Pi / 90; // two degrees: maximum angle from edges to first ray tested

Cheers.

Nov 28, 2010 at 12:25 PM
Edited Nov 28, 2010 at 12:27 PM

Hey Pnikosis,

they video looks pretty sweet, however i am getting the following error

Error    2    'FarseerPhysics.Dynamics.Fixture' does not contain a definition for 'Fixture' and no extension method 'Fixture' accepting a first argument of type 'FarseerPhysics.Dynamics.Fixture' could be found (are you missing a using directive or an assembly reference?)

 

on the following line:

 

_world.QueryAABB(
    fixture =>
     {
	shapes[shapeCount++] = fixture.Fixture;
        
// Continue the query.
return true; }, ref aabb);

Regards

 

Coordinator
Nov 28, 2010 at 4:03 PM

I've changed the API of the query. Simply remove ".Fixture" and it should work.