Jump to content
• Advertisement

# 2D Collision Management

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

If you intended to correct an error in the post then please contact us.

## 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 this post

##### Share on other sites
Advertisement
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 this post

##### 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 this post

##### 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 this post

##### 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 this post

##### 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 this post

##### 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 this post

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

#### Share this post

##### Share on other sites

• Advertisement
• Advertisement

• ### Popular Contributors

1. 1
2. 2
Rutin
19
3. 3
4. 4
khawk
14
5. 5
A4L
13
• Advertisement

• 13
• 26
• 10
• 11
• 44
• ### Forum Statistics

• Total Topics
633743
• Total Posts
3013643
×

## Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!