Jump to content
  • Advertisement
Sign in to follow this  
reaperrar

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


Link to 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


Link to 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


Link to 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


Link to 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


Link to 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


Link to 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


Link to 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


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

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!