Spatial hashing implementation for fast 2D collisions

June 13, 2009 at 6:15 pm (Other Stuff, 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.

image

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.

image

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.

SpatialHashing

And what would a sample be without source code?

Enjoy

Link To Sample

About these ads

25 Comments

  1. JeBuS said,

    Now, without having tried myself, wouldn’t you save a little bit of garbage by using the List.Clear method on your individual buckets rather than clearing the big Bucket List and generating a whole new little Lists every update? Something like

    for (int i = 0; i < Cols * Rows; i++)
    {
    Buckets[i].Clear();
    }

  2. Peter said,

    It seems your system can’t handle collision of objects larger than two cells on one axis, since you only use the collision extends to store the object in the corresponding buckets.

    Lets consider this an 1D problem. Imagine a 100px wide object and a grid cell that is 25px wide.

    The object should be located in every cell it overlapps (4 cells), not only in the cells where its extends are located (2 cells). Otherwise it is possible to bypass/tunnel the object in the middle two cells.

    • conkerjo said,

      Very true, i should have made clear, as it does in the linked paper that this system is no good for game objects which are bigger than a cell. It could be extended to resolve that but for my paticular needs it wasnt a requirement.

      • John said,

        Depending on the biggest possible size of your game objects, an easy solution would be to simply make the cells larger.

        In other words, simply scaling up the system you have there so you have more pixels to work with for your game objects.

        If you have a plethora of smaller objects, that might not be ideal, but for many games it could be wonderful.

        The more complex solution is to detect which cells the corners are in and then to do a two dimensional sweep with a nested loop to figure out which cells it’s overlapping.

      • conkerjo said,

        Yeah, you’re right. This is something I’ve implemented since writing this post. I’m going to do a new post once I’ve had a chance to test it some more with the new changes in.

    • Kallala said,

      If your cell is too small, making your objects appear in up to 6 cells, you’re better rethinking your grid size!

  3. LittleBernard said,

    This is really great!
    It really helped to understanding how to make collision detection a load more efficient

    I dont quite understand the importance of the dictionary or why you need a list of buckets.
    Isnt there a certain amount of buckets and each one contains certain objects.
    so if you have a set amount of buckets from the beginning why not make an array?

    • conkerjo said,

      using a hashtable allows for very quick lookup of objects. Give me all objects with id of X. It works a bit like an index in a database table.

      • David Gouveia said,

        I agree with LittleBernard on this. It would make sense if your Dictionary only held non-empty Buckets, and added/removed Buckets dynamically to save space.

        But in this case you’re pre-allocating every bucket from the start and there’s a fixed amount of buckets. So there’s no reason why a simple array wouldn’t be faster:

        var buckets = new List[cols * rows];

        You can access it just the same: buckets[id].

        And surely a simple array lookup by index would be faster looking up a key in a Dictionary?

      • David Gouveia said,

        Correction: var buckets = new List[cols * rows];

      • David Gouveia said,

        Okay, wordpress is stripping out the GameObject template portion of the code as HTML, but you get the point.

  4. Charles Humphrey said,

  5. conkerjo said,

    Charles, Yeah I read your post while doing my research.
    I’ve found some perf issues with my implementation which I’m working on fixing up. I’ll repost when I have better ver :)

  6. dp2208 said,

    Did you think about a resting bodies implementation?
    Something like i did for farseer physics:

    This should be a faster solution and produces less garbage.

    • conkerjo said,

      I now have a new implementation which doesnt produce garbage.I’ll update the post in due course. But no i didnt think too much about many other implementations due to the complexity of them. I had a hard enough time understanding this one :) now i do though, i may revisit other alternatives.
      How does your implementation stack up when you ramp up numbers to beyond 2000 ? thats when mine begins to die.

    • John said,

      Do you mean, that for objects that aren’t moving, for them not to check for collisions?

      I did that a while back when I tried writing my own 2D physics engine. While the overall project was a failure, I did come up with some cool ways to speed up collision detection and some clever makeshift ways to get around some of the problems that become apparent when objects move to fast.

      For example, unless you’re doing multi-threading, objects will move in a specific order. This causes visible problems with higher speeds because the object that gets to update first will be able to “bully” around objects that update later.

      My solution, and though it’s not a perfect one, is to reverse the normal order of objects updating every other frame. That way the “bullying” is averaged out and the system will produce, on average, more believable results.

  7. dp2208 said,

    I don’t know. Farseer will die for sure with this number of geoms.
    But i will implement some sort of resting bodies without a physic engine in the near future. I could tell you the results in the xna irc when i tried it,

    • fixitchris said,

      dp,

      Where did the slowdown happen with farseer? I am using your InactCtrlr, but I’m having trouble fine tuning the MinimumVelocity and ActivityDistance.

  8. Jeff said,

    Hello, the link to sample failed to dowdload the SampleTest.zip, could you please send me the SampleTest.zip to me ? Thanks!

  9. shabtronic said,

    Great Article!

    This looks like it doesn’t handle infinite sized worldspace tho?

    i.e. you have a fixed number of Buckets.

    To do that you need to change the algo to:

    1) Create position space Hash

    2) Find or Create Buckets

    3) Add to Buckets

    4) Collide buckets

    the problem then becomes making the Find or Create Buckets as fast as possible!

    One way to do this is to use a Hash Bit tree dictionary. (you input a 32bit hash and it tells you if it exists or creates one)

  10. ®io said,

    Hi,

    Thank you for a great article!! Would it be possible to get a working link the link for sample? Thanks!

  11. Glidias said,

    If you register an object to more than 1 bucket, wouldn’t, it get checked twice? Also for large objects ,updating buckets would be costlier.

  12. Fondusi’s Dev Blog – Week 5 « System Root said,

    [...] read a bit about spatial hashing and it’s essentially the same way that the tilesets are separated into tiles. The only real [...]

  13. me said,

    this look like an N-tree of depth 2 (with N the size of your map) and has little to none in relation to “spatial hashing collision detection”

    for a simpler implementation of this you may want to merely substitute your hashing funciton with a “modulo” operation on x and y

    just my 2 cents

  14. me said,

    ops, i just realized that you are already using it

    to at least contribute something, may i suggest this: http://www.clusterfaq.org/programming/near-neighbor-search-using-spatial-hashing/

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: