Detecting collisions

Apr 10, 2010 at 9:38 AM

Great library... many thanks!

I've had good luck getting the proper physical behaviors out of my objects but I can figure out how to tell when objects collide from my application.  For example when something hits a bomb... destroy the object.  When something hits a target... award a powerup.  I've been looking for some kind of OnCollision event, override, or delegate that I could provide such that the engine would call me on collisions and let me intervine.  Seams like a common enough task in a game but I can't figure out how to do it.  Am I missing something?

thanks

Coordinator
Apr 12, 2010 at 8:48 PM

Good point, I may have overlooked this. There was a time when the Contacts property of the RigidBody class was public, and then I made it internal, intending to expose another way to read the list of current contacts, but I must have forgotten to do that.

I'll make a note to add something like this to the next release. In the meantime, you can change "internal" to "public" on the Contacts property in RigidBody.cs, and you'll be able to access the list of currently touching objects in each frame. The property returns a list of Constraint objects, via which the BodyA and BodyB properties will tell you the two objects that are in contact.

Hope this helps, and thanks for pointing it out!

Coordinator
Apr 12, 2010 at 8:55 PM

Oh, also - if you have any suggestions on the most friendly way to expose this information, please let me know. I have yet to produce any actual games with XNA, so feedback from those who do is always welcome. 

An OnCollision event could probably occur at either the object level or at the world level, although I think some benchmarking would have to be done in the latter case. The system can generate a LOT of collisions, and that many delegate calls could have a negative effect on performance. Also, I wasn't sure how to best treat the event--should it fire for every frame where two objects are touching, or only when they are touching for the first time? If the latter, there could be some issues with objects that separate briefly and then come back into contact with each other (e.g. due to "jitter" that is too small to see). 

That line of thinking made me wonder if just exposing a list that can be checked each frame by the game was a better idea... I'll think about it some more.

 

Apr 13, 2010 at 4:58 PM

Thanks, I'll try making the contacts list public and see how far I get with that.

I think implementing an OnCollision delegate onto the RigidBody would probably be the right thing.  Then you don't incure the perf cost of calling a global handler for every object... just the objects you care to treat special.  I would prefer that it is only called once per collision.  Perhaps you have a MinimumSepperation setting which controls when they are considered apart and dictate when OnCollision would get called again to remove the jitter.  I don't quite remember but I think the Farseer physics engine had a OnSepperation handler as well.  I also don't know what it does to deal with jitter.

Not to call on Farseer too much... but one thing that was handy in that implementation was to be able to say wether or not you want the collision to happen as the return value of the OnCollision handler.  One concrete example of when this is needed is when an object launches projectiles.  You could remember a projectile came from a certain object and tell it not to collide until the projectile was sufficiently launched away from the launcher.  Another scenario is with character animation.  I want to attach RigidBodies to a character's parts to use as collision detection with an environment... but I will still want to control the characters movement through animations and direct control.  I would just use those RigidBodies to tell me if there was a collision but tell the system to ignore the collision and then I'd manually manipulate the RigidBodies to make them conform and react the way I want them to.

BTW... I'm just getting into using the content pipeline integration you have provided.  I love it... good job.

Coordinator
Apr 13, 2010 at 6:57 PM

Great feedback, thanks. 

I think I'll end up going with your suggestion to have a Collision event in RigidBody. I like the idea of being able to cancel a collision via the event. It would have to take place after the collision phase but before the response phase so that the event subscribers aren't being called on multiple threads.

Regarding characters and animations, I believe it should be possible to use the collision detection portion of the library separate from the physics portion by copying what PhysicsManager does, only without the RigidBody objects. The collision system should take any composition of shapes. If you try this, let me know if you run into any roadblocks. I'm also open to adding any new functionality to RigidBody needed to support the scenario.

 

Apr 13, 2010 at 8:42 PM

Using just the collision side of the engine is an interesting thought for certain things.  But for my character animation... I still want the physics to function for other objects in my scene... just not the character components.  I would listen for OnCollision and cancel the collision for character components, but still want doors to hinge, boxes to fall, etc.  When my character is killed I'd also want it to just ragdoll it, so I'd let the physics on those components taker over again.  For bumping into a wall I would just alter the animation such that the character conformed, but if a crate falls on his head I would ragdoll him and make his limp body interact with the box and rest of the scene.

Apr 21, 2010 at 5:17 PM

Do you have a timeframe for a next release?  I need some form of collision notification (and suppresion) so I was thinking about taking a crack at adding an OnCollision delegate to RigidBody.  If you have something in progress that you'd release soon I might wait... but otherwise I might put something in even if temporary until you add it (or build on what I do).  Perhaps I could at least synch with you on the signature of the callback.

Just to confirm... there is only a single ContactConstraint that gets created for each collision between two RigidBodies... correct?  You don't get multiple of them if multiple parts of the RigidBodies come in contact (points just get added to the existing contact).

What I was thinking of doing is walking the contacts for each unique RigidBody pair (that are in contact) and call an optional OnCollision delegate on each RigidBody.  If either delegate decides to supress a collision then under the covers the ContactContraint gets marked as suppressed but kept around for tracking.  The physics response is avoided for supressed ContactConstraints.  There is already a flag on Contstraint called IsCollisionEnabled.  This property looks like its used so that if I constrain two objects together (like a joint) then I could set this property to false and collisions would be avoided between those two objects.   Of course it doesn't work on the ContactConstraint itself because the flag currently just keeps a ContactConstraint from being generated. What I was thinking was to reuse this property on the ContactConstraint and supress it's own behavior when it is set.  Does this sound reasonable?

Coordinator
Apr 21, 2010 at 8:40 PM

I've been waiting for the XNA4 update to fix support for VS2010 before doing another release; their announcements suggest that it should be coming very soon.

A pair of rigid bodies could actually have more than one ContactConstraint between them if two different parts of their compositions are touching. The constraints might have different elasticity/friction properties, so they're solved separately. Each individual ContactConstraint can also have multiple points; those are really just used for "support" in the contact resolution. For example, if an "L" shaped block is resting on its side so that both ends are touching a plane, there might be two ContactConstraints, with two contact points each.

One way to go might be to just have a dummy constraint, like NoCollisionConstraint that does nothing but tells the collision functor to still check for collisions (unlike IsCollisionEnabled = false) but produce CollisionConstraints that don't get processed. The NoCollisionConstraint could be automatically produced if the event handler suppresses the collision, and then automatically removed when the collision system finds that the objects are separated. This might be preferrable to adding a new data structure or list.

If a NoCollisionConstraint exists between two bodies, but at the end of the frame, there are no shared ContactConstraints, then the objects could be considered separated, and the constraint is removed.

For the delegate signatures, I'm all ears - you might know better than me what information would be useful to the game itself. My initial thought was just a struct event args that holds a reference to the other body in the collision, with "sender" of course being the body on which the event lives. There's the possibility of including some contact data in there, but I'm not really sure how useful it would be in practice; since contact points are generated to support collision response, and not necessarily to represent a complete contact manifold.

Apr 22, 2010 at 12:33 AM

There was the recent MIX release that supports VS2010 (RC, I believe), but none for RTM yet.  We haven't announced a release date for the final GS4, but I wouldn't classify it as "very soon".

Apr 22, 2010 at 6:05 AM

So regardless if I go the route of a NoCollisionConstraint or extra flag to denote that collisions are supressed... let me run how I get get the collisions suppressed by you.  I think I just go to Island.Add(RigidBody a) and skip adding ContactConstraints to the Island when they should be suppressed.  This will keep them from getting processed but keep them around for later... correct? Islands are always cleared and rebuilt between update loops... correct?

The thing I'm not liking about the NoCollisionConstraint approach is that while contacts are processed it takes an order N walk through the constraints for each M contacts to determine if they should be suppressed on each update loop.  If there was an extra flag on the ContactConstraints then it could be swept on once and kept in sync.  It does serve as a good indicator for a potential sepperated event to fire.  Any thoughts on avoiding the NxM search for detecting the suppression of the contact with the NoCollisionConstraint approach?

Coordinator
Apr 22, 2010 at 7:18 AM

@mitchwalker,

I think it was an announcement on the Creator's Club forums said there would be a new CTP that supported VS2010 out soon-ish, should have stated that I was referring to that and not necessarily an RTM. But if not, then I may look to do another release under 3.1.

@dongi,

My thought was to put the check for NoCollisionConstraint in the already existing loop in BodyCollisionFunctor that checks for the IsCollisionEnabled = false condition. The number of non-contact constraints that an object contains should always be very low, so I don't think the additional if would be that bad. Essentially, a flag would be set on the ContactConstraint at that time to tell Island to just ignore it while processing. Then it would still get recycled at the end of the frame.

NoCollisionConstraint could also hold a value indicating whether it was actually used to suppress a collision on the current frame. In this way, Separation events could be fired for any NoCollisionConstraint that is not flagged, and they would be removed too.

I think your idea would work too, but I was concerned about the housekeeping. The extra ContactConstraints would have to be stored somewhere and then recycled at some future time. It could just be that I haven't fully wrapped my head around your approach yet. But I am open to trying pretty much anything.

 

Apr 22, 2010 at 9:08 AM

I have a solution that worked pretty well.  I used a new constraint but NoCollisionConstraint was not enough.  The reason a constraint works well is because it is data stored per pair of objects.  But we not only need the info that says to ignore the collision for a pair of objects... but we also need to keep the fact that OnCollision was already called for a give pair of objects... even if the collision is not ignored.  So I made a CollisionConstraint that keeps track of all the info for a given collison between two bodies.  I originally had a bool on it saying if OnCollision had been called for the collision... but later removed the property as the existence of the CollisionConstraint designates that it has been called.  It may make sense to add it back just to be more explicit.

    public class CollisionConstraint : Constraint
    {
        public CollisionConstraint(RigidBody bodyA, RigidBody bodyB)
            : base(bodyA, bodyB) {        }

        public bool IsCollisionSuppressed { get; set; }
    }

I added the following to RigidBody

        public delegate bool CollisionEventHandler(RigidBody bodyA, RigidBody bodyB);
        public delegate void SeparationEventHandler(RigidBody bodyA, RigidBody bodyB);

        /// <summary>
        /// Fires when a collision occurs with another RigidBody
        /// </summary>
        public CollisionEventHandler OnCollision;

        /// <summary>
        /// Fires when a seperation occurs with another RigidBody
        /// </summary>
        public SeparationEventHandler OnSeparation;

I modified BodyCollisionFunctor.PropogateContacts to add a CollisionConstraint for each collision that does not have a CollisionConstraint yet AND that has OnCollision or OnSeperation handlers set up for it.  This is also where OnCollision gets called.

In Island.Add(RigidBody a) I skip adding contacts to the Island for processing if it detects a CollisionConstraint with IsCollisionSuppressed that matches the contact.

After processing islands I walk through and elliminate CollisionConstraints that don't have matching ContactConstraints... and call OnSeparate handlers if needed.

This all works really well, gets the callbacks to the right thread... and doesn't appear to break any of the multi-threading constructs.

Coordinator
Apr 22, 2010 at 9:38 AM

OK, I think I get your approach and it looks great so far. I think I'll implement it pretty much the way you did. Do you think there might ever be a need to have multiple subscribers to those events? That might create issues with the return value of the CollisionEventHandler delegate, since multicast delegates only return the last value. I suppose I could enumerate those delegates and suppress the collision if any handlers return true.

Did you end up allocating CollisionConstraints via the Pool<T> class or do you think the frequency will be low enough to not create problems with the CF GC?

Thanks so much for your work on this, it's all extremely helpful.

 

Apr 22, 2010 at 4:05 PM

My thinking is that there is a cost with doing a multicast delegate that I wanted to avoid.  Someone could override RigidBody or encapsulate it and provide an event at a higher level.

I didn't allocate CollisionConstraint via the Pool<T> class... good catch.  I absolutely should have. 

Here are the 3 other function of relevance if you want them for reference


In BodyCollisionFunctor.cs

  public void PropagateContacts()
  {
   for (int i = 0; i < _items.Length; i++)
   {
    for (int j = 0; j < _items[i].Count; j++)
    {
     var c = _items[i][j];
     c.BodyA.Contacts.Add(c);
     c.BodyB.Contacts.Add(c);
     if (c.BodyA.IsActive && !c.BodyB.IsActive && c.BodyB.IsMovable) Activate(c.BodyB);
     if (!c.BodyA.IsActive && c.BodyA.IsMovable && c.BodyB.IsActive) Activate(c.BodyA);
                    
                    // see if we need to add a CollisionConstraint for this contact
                    // we need one if there is anyone listening for notifications on the two RigidBodies in contact
                    // and we don't already have one for this pair of objects
                    if ((c.BodyA.OnCollision != null || c.BodyB.OnCollision != null || c.BodyA.OnSeparation != null || c.BodyB.OnSeparation != null)
                            && !c.BodyA.Constraints.Any(cc => cc is CollisionConstraint && (cc.BodyA == c.BodyB || cc.BodyB == c.BodyB)))
                    {
                        var cc = new CollisionConstraint(c.BodyA, c.BodyB);

                        bool wantCollision = true;
                        if (cc.BodyA.OnCollision != null)
                            wantCollision = c.BodyA.OnCollision(cc.BodyA, cc.BodyB);
                        if (cc.BodyB.OnCollision != null)
                            wantCollision &= c.BodyB.OnCollision(cc.BodyA, cc.BodyB);
                        cc.IsCollisionSuppressed = !wantCollision;

                        _manager.Add(cc);
                    }
    }
   }
  }}

In Island.cs

public void Add(RigidBody a)
  {
   if (a.Island != null || !a.IsMovable) return;

   _bodies.Add(a);
   a.Island = this;

   for (int i = 0; i < a.Constraints.Count; i++)
   {
    var constraint = a.Constraints[i];
    if (constraint.Island == null)
    {
     _constraints.Add(constraint);
     constraint.Island = this;
     var other = constraint.BodyA == a ? constraint.BodyB : constraint.BodyA;
     if (other != null && other.Island == null && other.IsMovable)
      this.Add(other);
    }
   }
   for (int i = 0; i < a.Contacts.Count; i++)
   {
    var contact = a.Contacts[i];
    var collision = contact.BodyA.Constraints.FirstOrDefault(cc => cc is CollisionConstraint && (cc.BodyA == contact.BodyB || cc.BodyB == contact.BodyB)) as CollisionConstraint;
    if (contact.Island == null && (collision == null || !collision.IsCollisionSuppressed))
    {
     _constraints.Add(contact);
     contact.Island = this;
     var other = contact.BodyA == a ? contact.BodyB : contact.BodyA;
     if (other != null && other.Island == null && other.IsMovable)
      this.Add(other);
    }
   }
  }

In PhysicsManager.cs

       /// <summary>
        /// Removes CollisionConstraints when there are no more contacts
        /// </summary>
        private void ProcessSeparations()
        {
            for (int i = 0; i < _bodies.Count; i++)
            {
                var body = _bodies[i];
                for (int j = 0; j < body.Constraints.Count; j++)
                {
                    var cc = body.Constraints[j] as CollisionConstraint;
                    if (cc != null)
                    {
                        var other = cc.BodyA == body ? cc.BodyB : cc.BodyA;
                        if (!body.Contacts.Any(c => c.BodyA == other || c.BodyB == other))
                        {
                            if (cc.BodyA.OnSeparation != null)
                                cc.BodyA.OnSeparation(cc.BodyA, cc.BodyB);
                            if (cc.BodyA.OnSeparation != null)
                                cc.BodyA.OnSeparation(cc.BodyA, cc.BodyB);
                            Remove(cc);
                        }
                    }
                }
            }
        }

Apr 22, 2010 at 6:03 PM

You know as much as I like this approach and it works well.  It really wouldn't have hurt to make a sepperate Collisions collection off of the RigidBody and have Collision (not a Constraint) rather than CollisionConstraint. It would only change a few lines of code. The nice thing about this is it makes it easier to enumerate and doesn't pollute the 'real' constraints.  As of now I think that because it is a constraint it would force an object to get pulled into an Island with another object even if the object is avoiding collisions with it.  I could also see a Collision having much more utility and surfacing it as it's own entity might be nice.  Just a thought.

Coordinator
Apr 22, 2010 at 9:28 PM

Yeah, I'm starting to think that might be best too. I wonder if that new collection could just contain structs, with three fields: BodyA, BodyB, and IsCollisionSuppressed. The advantage to the struct would be that another pool wouldn't be needed, but of course the downside would be that BodyCollisionFunctor would have to check the list on both colliding bodies to see if either one generated a suppression. Or....maybe not; maybe the act of suppressing would set the flag on both sides, and then only one has to be checked.

In fact, maybe only the "other" body needs to be stored in the struct, since the first body is obviuosly known.

I'm thinking:

struct CollisionStatus
{
    public RigidBody OtherBody;
    public bool IsSuppressed;
}

...and then a List<CollisionStatus> on each body pointing to each other.

Of course, if we really wanted to micro-optimize, this could be a Dictionary<RigidBody, int>with bit flags:

0x01 = collided on last frame
0x02 = colliding on this frame
0x04 = collision suppressed

The "this frame" flag could be set by the collision functor when any CollisionConstraint is created, and then that flag would be copied to "last frame" when collision processing is done and "this frame" reset to zero. Then all that is required to check for separation is flags & 1 > 0 && flags & 2 == 0.

Oh, BTW, I'd have to check with reflector and I could be wrong, but I think the use of LINQ extensions (.Any() and .FirstOrDefault()) will create garbage via the enumerators.

I'll play around with these different approaches and try to have another alpha release this weekend.

Apr 23, 2010 at 4:47 PM

These approaches sound great. 

I thought that in general when the LINQ extensions came up with a templated versions they didn't allocate their enumerator... but I was being lazy and didn't check first... I should have put a review comment in.

I don't think Dictionary will actually be an optimization for small data sets (linear search) but it would certainly be handier to call into and maybe avoid some accidental GC issues.

Coordinator
Apr 25, 2010 at 1:24 AM

I put up a new release today that includes a mix of the approaches above. I think I'm pretty happy with it. It can be a little wonky and report a separation sometimes when you don't think there should be one, which is a side effect of doing the check every frame. A distance threshold is possible, but having the collision system track that info could be quite a chore. I used the handler signatures you created, so it shouldn't require much in the way of changes to your game code. I look forward to hearing your feedback.

Beer time!

 

Apr 27, 2010 at 4:02 AM

Thanks for the new release!  The collision tracking works great and the pipeline changes are also much appreciated.  I haven't encountered any issues with the separation reporting when I haven't expected it yet.  Perhaps this should just be handled up in the app logic if it does become an issue.  Again... many thanks.