Spatial hashing implementation for fast 2D collisions

June 13, 2009 at 6:15 pm (Other Stuff, XNA) (2D, C#, COlLISION DETECTION, SPATIAL HASHING, XNA)

This is a sample prototype I wrote to fix a performance limitation with collision checking in SBARG. So what is spatial hashing? Here is a good 1 liner I will borrow from the source material i used.

“Spatial hashing is a process by which a 3D or 2D domain space is projected into a 1D hash table.” Optimization of Large-Scale, Real-Time Simulations by Spatial Hashing

So why do we need it?

Well, for me it was a problem in my collision code and my A.I code which was trying to find nearby objects to check collisions for. Due to my brute force nature if I had 10 monsters in the world there would be 10*10 = 100 collision checks in every update. Now ramp the number up to 100 to be a bit excessive and we end up with 100*100=10,000 collision checks. This makes the cpu cry like a little baby as I’m sure you can imagine. To rectify this we need to reduce the amount of collision checks we need to do in the first place. This is where spatial hashing comes in handy.

Imagine the game world in a flat 2d grid. 100 by 100 pixels and each cell was 25 by 25 pixels. Now number the cells from left to right, top to bottom 0 onwards. You will end up with something like this. The orange circles are the game objects, in my case, monsters.

Each cell is a bucket of game objects and a unique hash id. If we imagine the bucket as a list of 16 buckets, 0-15 cells and placed the game objects in that bucket. It might look something like this.

This is our 1D grid mentioned in the introduction.

It’s a simple premise really, any item in bucket 3 for example, cannot possibly collide with something in bucket 9. This reduces the amount of times we need to cycle the nearby objects but also dramatically reduce the amount of times we need to check if a collision is happening.

Ok, so the above implementation is fine as long as a game object only ever exists in 1 bucket. But what if it crosses a line and exists in more than 1 bucket. To resolve this I imagined a box around each game object, and I calculated the hash id for each corner of the box. I then populate a List<GameObject> going through each bucket the game object is in. Sounds simple ?

Let me show you some of this theory in code.

First we need a game object. For this sample all we need is a position and a radius.

    public class GameObject
    {
        public Vector2 Position { get; set; }
        public float Radius { get; set; }
    }

We create a new class to store the grid data in including the buckets. I’m terrible at naming classes so I called it SpatialManager. I gave this class a Setup method which takes a full scenewidth, height and a cellsize. In our example this would be 100,100,25

    public void Setup(int scenewidth, int sceneheight, int cellsize)
    {

We can work out how many buckets we need by first calculating the rows and cols then simply create a new Dictionary of buckets to the tune of Rows*Cols. I also store these variables passed in for future use.

    Cols= scenewidth / cellsize;
    Rows= sceneheight / cellsize;
    Buckets = new Dictionary<int  , list><gameobject>(Cols * Rows);

    for (int i = 0; i < Cols*Rows; i++)
    {
        Buckets.Add(i, new List());
    }

    SceneWidth = scenewidth;
    SceneHeight = sceneheight;
    CellSize = cellsize;
}

Each update, we need to clear out the buckets and re calculate the buckets each game object are in. I created a method called ClearBuckets to start fresh.

   internal void ClearBuckets()  
   {
       Buckets.Clear();
       for (int i = 0; i < Cols * Rows; i++)
       {
           Buckets.Add(i, new List());   
       }
   }

We now need a method to register a game object into the buckets it sits in.

    internal void RegisterObject(GameObject obj)
    {
        List cellIds= GetIdForObj(obj);
        foreach (var item in cellIds)
        {
            Buckets[item].Add(obj);
        }
    }

As you can see, the code retrieves a list of cellids to add the game object to.

In the GetIdForObj method it calculates the cell id for each corner of the game object.

If we were just checking the position of the game object the calculation would be.

float width = SceneWidth / CellSize; // 100 / 25

int hashid=(int)(

    (Math.Floor(position.X / CellSize)) +

    (Math.Floor(position.Y / CellSize)) * width);

We need to do this for each corner and add our game to each bucket.

The GetIdForObj method looks like this.

    private List GetIdForObj(GameObject obj)
    {
        List bucketsObjIsIn = new List();
           
        Vector2 min = new Vector2(
            obj.Position.X - (obj.Radius),
            obj.Position.Y - (obj.Radius));   
        Vector2 max = new Vector2(
            obj.Position.X + (obj.Radius),
            obj.Position.Y + (obj.Radius));

        float width = SceneWidth / CellSize;   
        //TopLeft
        AddBucket(min,width,bucketsObjIsIn);
        //TopRight
        AddBucket(new Vector2(max.X, min.Y), width, bucketsObjIsIn);
        //BottomRight
        AddBucket(new Vector2(max.X, max.Y), width, bucketsObjIsIn);
        //BottomLeft
        AddBucket(new Vector2(min.X, max.Y), width, bucketsObjIsIn);

	return bucketsObjIsIn;    
    }

And here is the AddBucket method which uses the calculation described above and adds it to the list of bucket id’s to add to.

    private void AddBucket(Vector2 vector,float width,List buckettoaddto)
    {  
        int cellPosition = (int)(
                   (Math.Floor(vector.X / CellSize)) +
                   (Math.Floor(vector.Y / CellSize)) *
                   width   
        );
        if(!buckettoaddto.Contains(cellPosition))
            buckettoaddto.Add(cellPosition);
            
    }

Now that we have our grid of buckets. It’s a very simple retrieval process. I added a method to get the nearby objects of a given object. This uses the GetIdForObj method and populates a list of GameObject’s and returns once complete. This is the key part to this solution, you only now need to check items which are actually nearby and not items the other side of the theoretical world.

    internal List GetNearby(GameObject obj)
    {
        List objects = new List();
        List bucketIds = GetIdForObj(obj);
        foreach (var item in bucketIds)
        {
            objects.AddRange(Buckets[item]);
        }
        return objects;   
    }

So that’s it. Now you can do your normal collision checking by retrieving nearby GameObjects. And here’s a screenshot to prove it.

I’ve placed my mouse over one of the GameObjects and it’s highlighted all nearby items. Notice how they cross over cells. This is because the item i hover over is on the line and exists in multiple cells. Also notice the amount of checks it has to do. For brute force it has to do 250,000 bounding box collision checks. For spatial hashing, it checks only 4840 times. Wicked.

And what would a sample be without source code?

Enjoy

Link To Sample