## 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.

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++)
{
}

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++)
{
}
}``````

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)
{
}
}
``````

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(
Vector2 max = new Vector2(

float width = SceneWidth / CellSize;
//TopLeft
//TopRight
//BottomRight
//BottomLeft

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.

``````
{
int cellPosition = (int)(
(Math.Floor(vector.X / CellSize)) +
(Math.Floor(vector.Y / CellSize)) *
width
);

}
``````

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)
{
}
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

1. #### JeBuSsaid,

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. #### Petersaid,

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.

• #### conkerjosaid,

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.

• #### Johnsaid,

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.

• #### conkerjosaid,

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.

• #### Kallalasaid,

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

3. #### LittleBernardsaid,

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?

• #### conkerjosaid,

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 Gouveiasaid,

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 Gouveiasaid,

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

• #### David Gouveiasaid,

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

5. #### conkerjosaid,

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. #### dp2208said,

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.

• #### conkerjosaid,

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.

• #### Johnsaid,

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. #### dp2208said,

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,

• #### fixitchrissaid,

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. #### Jeffsaid,

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

9. #### shabtronicsaid,

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

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. #### ®iosaid,

Hi,

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

11. #### Glidiassaid,

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 Rootsaid,

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

13. #### mesaid,

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. #### mesaid,

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/