# 2D Collision Management

This topic is 2663 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I'm using a spatial grid index for my 2D game to manage collisions. I've got all my objects successfully adding into the buckets, now I'm trying to figure out the most efficient way to collide objects. For example... if an object exists in 9 grid squares and another object exists in 5 of those same squares... how do I avoid 5 collision checks?

One way I was thinking was having a list for each object that has neighbors, the list populated with the neighbors.

But then I'd have to make sure (5 times in the above example) that I'm not adding in an object that already exists in the collision list as well as making sure there aren't duplicate collision checks if 2 objects have each other in their collision lists.

Anyone with suggestions/links? My ideas seem really inefficient : (

##### Share on other sites
I would intersect the AABB first (see this). Then I would check each cell with no shame (you might also consider AABB trees like this).
There's no absolute evil as "inefficiency" as there's no absolutely "efficient" thing. What you need to to is to have enough efficiency to make the game run on your target hardware. Are you targeting Atom? Portables?
If you are not, then take it easy first, profile, optimize later.
In case you need the optimization, I have to admit I have been fairly impressed by AABB trees.

##### Share on other sites
where is an easy way to skip dublicate checks
In bucket store not pointr to object but whole new helper class:
class
{
objectclass * object; //pointer to object
int startx,starty; //bounding box converted to cell[x][y] start points
}

so if your object ocupy cell[3..6][5..10] than startx=3,starty=5

in collision checks insert code:

for(i=o;i<w;i++)
for(k=0;k<h;++)
{
for(l.....)
for(m....)
{
if(obj[l].startx==i || obj[m].startx==i)
if(obj[l].starty==k || obj[m].starty==k)
if(obj[l].object->box intersects with obj[m].object->box)
do collision obj[l]->object with obj[m]->object
}
}

whats it , no collision checks duplications

##### Share on other sites
You might want to consider increasing your Grid size if objects typically take up more than 1 Grid. It will increase your efficiency to do so.

##### Share on other sites
its not eaven solution
lets take that cell size is allready optimal size = for example 5-10 times as average object size. Edited by serumas

##### Share on other sites
I've found that 2D grid-based collision systems often have "spikey" CPU utilization, for the reasons you describe.

If you're open to it, I would suggest trying a sort/sweep system (http://en.wikipedia.org/wiki/Sweep_and_prune). It can actually be much simpler to implement and maintain, with excellent performance characteristics.

##### Share on other sites

its not eaven solution
lets take that cell size is allready optimal size = for example 5-10 times as average object size.

I didn't offer it up as a solution, but as a consideration to help his efficiency. Let's take that cell size is NOT already optimal, it would improve his performance tremendously.

Your suggestion for solving the (very few) times this should happen sounds good.

##### Share on other sites
i am already checked only single axe sort sweep prune method
and compared with uniform grid and results was better with grid
very expensive sort (quick sort ofcouse was not the best sort algorithm for that case)

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 15
• 21
• 23
• 11
• 25