New Superfast broadphase

Topics: Developer Forum
Dec 27, 2007 at 8:17 PM
My friend and I just took a 15 minute break to code up a spatial hashing algorithm for Farseer. The results were much more impressive than I had dreamed. I had been using both my frame-coherent SAP and SelectiveSweep from BioSlayer... but this spatial hashing algorithm has blown them both out of the water.... and by a big margin. I've gotten over 10 times the number of objects at 60fps than I was previously getting... I don't know if this code will perform well for you guys as my game consists of a lot of objects spread apart, but give it a try.... The values you might need to tweak for your own application is the "cellSize" and also the initial capacity of the hashtable... possibly the hashing function.... man, and this was soooooo simple!!!


using System;
using System.Collections.Generic;
using System.Collections;
using System.Text;
 
using FarseerGames.FarseerPhysics.Mathematics;
using FarseerGames.FarseerPhysics.Dynamics;
using FarseerGames.FarseerPhysics.Collisions;
 
namespace FarseerGames.FarseerPhysics.Collisions
{
    public class SpatialHashing : IBroadPhaseCollider
    {
        #region IBroadPhaseCollider Members
        PhysicsSimulator physicsSimulator;
        System.Collections.Generic.Dictionary<long, List<Geom>> spaceHash= null;
        float cellSize = 256.0f;
 
        public SpatialHashing(PhysicsSimulator physicsSimulator)
        {
            this.physicsSimulator = physicsSimulator;
            spaceHash = new Dictionary<long, List<Geom>>(4096);
        }
 
        public void ProcessRemovedGeoms()
        {
        }
 
        public void ProcessDisposedGeoms()
        {
        }
 
        public void Add(Geom geom)
        {
            //if (geom.body.Enabled == false)
            //    return;
        }
 
        public void Update()
        {
            int iCount = physicsSimulator.geomList.Count;
            for (int geomIndex = 0; geomIndex < iCount; geomIndex++)
            {
                Geom geom = physicsSimulator.geomList[geomIndex];
 
                if (geom.body.Enabled == false)
                    continue;
 
                int l = (int)(geom.aabb.Min.X / cellSize);
                int r = (int)(geom.aabb.Max.X / cellSize);
                int t = (int)(geom.aabb.Min.Y / cellSize);
                int b = (int)(geom.aabb.Max.Y / cellSize);
 
                for (int i = l; i <= r; i++)
                {
                    for (int j = t; j <= b; j++)
                    {
                        long key = i * 2185031351 ^ j * 4232417593;
                        if (spaceHash.ContainsKey(key))
                        {
                            List<Geom> theList = null;
                            spaceHash.TryGetValue(key, out theList);
                            theList.Add(geom);
                        }
                        else
                        {
                            List<Geom> theList = new List<Geom>();
                            theList.Add(geom);
                            spaceHash.Add(key, theList);
                        }
                    }
                }
            }
 
            foreach (List<Geom> geomList in spaceHash.Values)
            {
                int iNumGeoms = geomList.Count;
                for (int i = 0; i < iNumGeoms-1; i++)
                {
                    Geom geom1 = geomList[i];
                    for (int j = i + 1; j < iNumGeoms; j++)
                    {
                        Geom geom2 = geomList[j];
                        DoCollision(geom1, geom2);
                    }
                }
 
                geomList.Clear();
            }
        }
 
        Arbiter arbiter;
        private void DoCollision(Geom geometryA, Geom geometryB)
        {
            //possible early exits
            /*if (!geometryA.body.enabled || !geometryB.body.enabled)
            {
                continue;
            }*/
 
            if ((geometryA.collisionGroup == geometryB.collisionGroup) && geometryA.collisionGroup != 0 && geometryB.collisionGroup != 0)
            {
                return;
            }
 
            if (!geometryA.collisionEnabled || !geometryB.collisionEnabled)
            {
                return;
            }
 
            if (geometryA.body.isStatic && geometryB.body.isStatic)
            { //don't collide two static bodies
                return;
            }
 
            if (geometryA.body == geometryB.body)
            { //don't collide two geometries connected to the same body
                return;
            }
 
            if (((geometryA.collisionCategories & geometryB.collidesWith) == Enums.CollisionCategories.None) & ((geometryB.collisionCategories & geometryA.collidesWith) == Enums.CollisionCategories.None))
            {
                return;
            }
 
            bool intersection = true;
            #region INLINE: if (AABB.Intersect(geometryA.aabb, geometryB.aabb)) ....
 
            if (geometryA.aabb.min.X > geometryB.aabb.max.X || geometryB.aabb.min.X > geometryA.aabb.max.X)
            {
                intersection = false;
            }
            else if (geometryA.aabb.min.Y > geometryB.aabb.Max.Y || geometryB.aabb.min.Y > geometryA.aabb.Max.Y)
            {
                intersection = false;
            }
            #endregion
 
 
            if (intersection)
            {
                arbiter = physicsSimulator.arbiterPool.Fetch();
                arbiter.ConstructArbiter(geometryA, geometryB, physicsSimulator);
 
                if (!physicsSimulator.arbiterList.Contains(arbiter))
                {
                    physicsSimulator.arbiterList.Add(arbiter);
                }
                else
                {
                    physicsSimulator.arbiterPool.Release(arbiter);
                }
            }
        }
 
        #endregion
    }
}
Dec 27, 2007 at 8:31 PM
Just a quick note - the cellSize is probably going to be about the average size of your objects (I think).... And I haven't tested this with stacked bodies and what not yet.... I think the current implementation might be calling multiple pairs more than once, so probably the code needs to be changed slightly to store the geometry pair once in a map and that can be iterated over all at once.... any - lots of coolness!
Dec 28, 2007 at 3:18 AM
I've put up a test / demo using spatial hashing...
In this demo, I have about 5,000 objects (though, at any given time, probably only about 1200-1500 are enabled) and getting between 30-60fps.
http://www.youtube.com/watch?v=cstUpsoCwhY

Its probably the case that this demo is especially well suited for the spatial hashing algorithm: Lots of space, objects spread apart, and no universe boundaries. I'll be interested in hearing if it works well for others - the downside of the algorithm is that you need to tweek values and it looks like its memory hungry (haven't look to what extent yet). One change that I've made since posting is that the line:
if (!physicsSimulator.arbiterList.Contains(arbiter);
had so many objects in the arbiterList (more than 300 entries!), that I modified the code so that an arbiter hash table was used instead of a list. So instead of searching through a list of more than 300 entries, I used a key like {geom.id + geom2.id * largeNum} and can more quickly find if the arbiter had already been added....

Andy
Coordinator
Dec 28, 2007 at 4:29 PM
Edited Dec 28, 2007 at 4:31 PM
Looks interesting. I'll try it out and maybe add it as an option in the next release.

Is the change you made to the arbiter list something you think would be universally better than what is currently there? Do you have some more details on the changes you made?

btw, very cool demo!
Jan 2, 2008 at 6:25 PM
I don't know if the change I made would be beneficial in the general case. I don't have the code in front of me, but what I did was handle it entirely inside the spatialHash. At the beginning of the update, I iterated over the current arbiter list and hashed each entry. Then in the OnCollision, before even constructing the arbiter, I would check to see if it was already in the hash - the theory being a hash look up would be faster then a search in the lists of the sizes I was working with. In all actuality, I didn't crunch any numbers - but it "seemed" faster. I'll have to go back and see exactly what kind of difference it made.

I've played with the algorithm a little more. I'm a sold believer of it - though I don't think it would work as a default broadphase or as a canned solution. It seems more of an algorithm to tweak or use in a large broadphase scheme. Here are some of the interesting things I found:

  • Works best if objects are relatively the same size as each other.
  • Objects larger or around the same size as the gridcell will cause multiple "paints" of the object to multiple grids. You don't want multiple paints per object.
  • Grid-cells too small can also cause lots of "lists" with only 1 or 2 objects. This can be inefficient too because you have to reserve memory for those list. And you have to iterate over them.
  • Grid-cells too large causes lots of objects in a list. Since we use brute force in a list, you don't want that.

So, you sort of have to tweak the algorithm to your game. Here are some other ideas:

If you have large and small objects - create a hiearchial spatial-hash solution. Have the big objects hash using larger grid-sizes and the smaller objects hash to smaller gridsizes. Search the net, there are some ideas on this.

When creating your broad-phase solution, tailor it to your specific app. For example, in the broadphase stress-test demo (demo8) - if this was a real app, you could cheat majorly. Since none of the balls collide with each other, you could have them in one "special" spatial-hash that doesn't test collisions at all. But, you would use the hashed contents by grabbing the hashkeys/list that the user-controlled-spinning-X was over and "just" test those lists against that object. For the outer walls - since those are static, you could precompute their hash values and avoid touching them again - except to do the same similiar trick as with the user-controlled object.

I guess my point is - I'm now tending to think of the broad-phase as a very application and custimizable sort of thing. I think the SelectiveSweep is probably a good default as it makes few assumptions. But if someone wants to role in their own thing, they might be able to make use of this spatial-hash thing - potentially could get some really nice results.

Andy