Jun 18, 2010 at 12:10 PM
Edited Oct 27, 2010 at 7: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 5: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 10:14 PM
Edited Jun 18, 2010 at 10: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 8:38 PM

Can we get a video Pnikosis?



Jun 21, 2010 at 7:58 AM
Edited Jun 21, 2010 at 8: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 :$




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




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 1:15 PM

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




Absolutely, I'll do it this afternoon :)



Oct 26, 2010 at 8:01 AM
Edited Oct 26, 2010 at 8: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.




Thank you.
I will use it well.




Can you give the fixed version?




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




aha, I understand.
Thank you



Coordinator
Oct 27, 2010 at 9: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?




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




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




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 1:25 PM
Edited Nov 28, 2010 at 1: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 5:03 PM

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

