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 : (
2D Collision Management
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.
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.
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
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
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.
its not eaven solution
lets take that cell size is allready optimal size = for example 5-10 times as average object size.
lets take that cell size is allready optimal size = for example 5-10 times as average object size.
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.
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.
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.
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)
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)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
