ArbiterList getting larger when removing objects in SelectiveSweep

Topics: Developer Forum, User Forum
Dec 7, 2009 at 3:04 PM

Hey! First of all thanks for the great work on this very impressive physics engine. I'm working on a game where I originally had my own collision detection and physics but as I wanted more and more complex stuff I decided it's better to get yours which already had everything I needed. It was some work to change the entire game to the new system, but I've got most everything working now.

A problem I've run into is that when I remove objects from the simulator the arbiter count goes up about 10-15 for every object removed, and they stay there indefinitely, which means that if I remove say 100 items I'll have about invalid 1000-1500 arbiters. I've tried looking through my own code as I assume the problem is my own fault, but I can't seem to find any errors.

I'm using SAT for narrow and SS for broad and the error only seems to exist when using SelectiveSweep for narrow. The broad phase doesn't make any difference but when running S&P or Bruteforce the extra arbiters aren't created.

The item removal happens when my player object collides with the target item, if that makes any difference.

This happens when using both Simulator.Remove() and Geom.Dispose() / Body.Dispose()

My game object currently is the container for a Body and a Geom. My code for removing my gameobject from my world is:

        public virtual void Dispose()
        {
            if (IsDisposed) return;
            IsDisposed = true;
            World.Active.Assets.Remove(this);
            //this.Geom.Dispose();
            //this.Body.Dispose();
            World.Active.Simulator.Remove(this.Geom);
            World.Active.Simulator.Remove(this.Body);
        }
The removal gets called all the way into the SelectiveSweep.ProcessRemovedGeoms() and it does remove objects from it's _wrapper list. However the arbiter list still increases.

One idea is that the problem lies in removing arbiters associated with the removed geoms, since the check for this (in PhysicsSimulator.ProcessRemovedItems()) never returns true. However it never returns true when using other narrow colliders either so that might not be the source of the problem either.

 

I apologize beforehand as I'm assuming that the fault here is still mine, but maybe you could give me a hint at what I'm doing wrong so I can find a solution for this error, or possibly locate a new error within the SS collider. SAT+SS seems to be the most efficient approach for me at the moment so I wouldn't really like to change.

 

2. On a side note I'm not pro in any way at optimizing code, but looking at code for removing arbiters associated with removed geoms I think there might be a faster solution. I might be dead wrong though, but it's just an idea as I would think it reduces the amount of checks when removing several items at a time, also the check itself may be cheaper? The code also removes any arbiters associated with objects not currently in the simulation instead of just the recently removed items, which may clean up old misses. (The old code is commented away for comparison)

            for (int i = 0; i < _tempCount; i++)
            {
                _geomRemoveList[i].InSimulation = false;
                GeomList.Remove(_geomRemoveList[i]);

                // ORIGINAL CODE
                ////Remove any arbiters associated with the geometries being removed
                //for (int j = ArbiterList.Count; j > 0; j--)
                //{
                //    if (ArbiterList[j - 1].GeometryA == _geomRemoveList[i] ||
                //        ArbiterList[j - 1].GeometryB == _geomRemoveList[i])
                //    {
                //        //TODO: Should we create a RemoveComplete method and remove all Contacts associated
                //        //with the arbiter?
                //        arbiterPool.Insert(ArbiterList[j - 1]);
                //        ArbiterList.Remove(ArbiterList[j - 1]);
                //    }
                //}
            }

            // NEW CODE
            //Remove any arbiters associated with inactive geometries
            if (_geomRemoveList.Count > 0)
            {
                for (int j = ArbiterList.Count; j > 0; j--)
                {
                    if (!ArbiterList[j - 1].GeometryA.InSimulation ||
                        !ArbiterList[j - 1].GeometryB.InSimulation)
                    {
                        //TODO: Should we create a RemoveComplete method and remove all Contacts associated
                        //with the arbiter?
                        arbiterPool.Insert(ArbiterList[j - 1]);
                        ArbiterList.Remove(ArbiterList[j - 1]);
                    }
                }
            }

Dec 9, 2009 at 1:16 PM

Been looking more into this and I've located the problem, but I'm not sure my code is causing the problem or if it's the the SelectiveSweep collider. Could you possibly ask BioSlayer to check over this post genbox?

It seems that when an object is removed the next iteration of SelectiveSweep.DetectInternal() will generate a new (copy-invalid) arbiter for every (valid) arbiter already in the arbiterlist. Naturally copy arbiter will be removed when the connection is lost between the two geoms, but as long as the connection is held, the arbiter will stay there. This means if I have 25 objects colliding which each generates an arbiter, and I delete 10 other objects, I will have my original 25 arbiters, and an additional 25x10 copy arbiters in my list.

So if I have a single player object moving around my scene, and I go pickup some of my items (so that they are removed from the simulator) each pickup will add a new copy arbiter into my list, as soon as my player looses contact with a surface all it's arbiters are lost ofcourse. If this was the case I probably wouldn't have noticed this, but since I've got a bunch of other objects laying around the scene, a bunch of copy arbiters are created that won't dissapear immediately.

The objects I'm removing are static, I don't know if this makes a difference.

I've come up with a workaround for this, but it's a very expensive check since the loop amount increases exponentially with the amount of arbiters. (ArbiterCount^2) I simply run a check when SelectiveSweep decides to create an arbiter to see if an arbiter between those two geometries already exist. If I got a better understanding of SelectiveSweep I may be able to find a much cheaper solution, an alternative solution that is cheaper than my current one would be to add references within each Geom of any connected Arbiters, that way we'd only have to loop that geom's arbiters (which probably is only one) and it would be much cheaper, but I don't think you'd want to add those potentially expensive references to the geom class just for this.

Place this inside SelectiveSweep.DetectInternal(), after the wrapper decides that the objects are colliding and after it checks all other voiding cases.

bool cont = false;
foreach (var item in _physicsSimulator.ArbiterList)
    if ((item.GeometryA == geometryA && item.GeometryB == geometryB) ||
        (item.GeometryA == geometryB && item.GeometryB == geometryA))
    {
        cont = true;
        break;
    }
if (cont)
    continue;

// This line is original code, place the above code right above this
_physicsSimulator.ArbiterList.AddArbiterForGeomPair(_physicsSimulator, geometryA, geometryB);

PS. Does anyone know of a better way to "double break" or "break and continue" on two loops at once? the cont flag could be removed if I could just say breakandcontinue inside the loop. I find myself needing this quite often but don't have a decent solution. I know I can use the goto command but that is ugly and probably more expensive than a simple flag?

Dec 14, 2009 at 3:50 PM

Any idea on this genbox? Or is there a way I could contact BioSlayer and see if he has any ideas? My hack works, but it's expensive so I don't want to leave it as it is.

Coordinator
Dec 14, 2009 at 5:32 PM

Hi jsmars,

I've been too busy to answer all posts on the forum. Sorry for the delay.

I'm no expert in the selective sweep algorithm, if it indeed does have a problem with stale arbiters, I would recommend switching to another broadphase. I have had some problems with arbiters not getting removed when you remove a geometry right after a collision, it might be related to that.