Jump to content
  • Advertisement
Sign in to follow this  
Assassinbeast

How do you check collision against 1000x1000 objects?

This topic is 2145 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

Hey, i just need some information on how to check collision if theres 1000 objects on the field.
And all 1000 objects are enemies to eachother.

So, do i for example have to make two for loops like this?:

[source lang="cpp"]
for(int i = 0; i < objects.size(); ++i) //objects.size is the size of the vector(if i use that)
for(int j = 0; j < objects.size(); ++i)
collision(objects, objects[j]);
[/source]
But thats 1000x1000 = a million loops in a single statement wacko.png

So, i just want to know if thats how you do it... cant see any other way of doing this so far huh.png Edited by Assassinbeast

Share this post


Link to post
Share on other sites
Advertisement
Yep, subdivide the problem!!!

It's a little more complicated that JUST dividing into regions (i.e. players on the boundaries of two different regions might be able to collide, or a bullet/player might cross from one region into another in one time-step). You'll need to handle these edge cases in addition to what ultramailman suggests.

Octrees/quadtrees are common ways to hierarchically subdivide your world although depending on your requirements you can optimize this in different ways.

Share this post


Link to post
Share on other sites
in addition to what was said,ie: using some form of broad phase culling of objects that can't possibly collide, your loops are naive in that they check each item with each other item... twice. Better would be to change the second loop to:


for(int i=0; i< objects.size() ; i++)
{
for(int j=0; j<i; j++)
{
// check collisions
}
}


Your implementation results in n^2 tests, the above in a little over 1/2 that.

Share this post


Link to post
Share on other sites
Stroppy Katamari already said that, and the j = i+1 method saves checking i == j as well.

You can also sort the coordinates in each axis and check 1 dimension at a time, if something is at x = 1 and moving with an x velocity of +2, it's never going to collide with anything that isn't in the interval [1, 3] in the x coordinate (need to account for the width of both objects in the x axis as well, of course). You need to have a system for reoordering the objects when they move which doesn't involve sorting the whole lot though. Space partitioning systems are just more advanced versions of that kind of thing.

Share this post


Link to post
Share on other sites
hehe
1000 * 1000 == BOOOM biggrin.png

The first solution ::


class Object
{
bool receiveCollision;
};
//player.receiveCollision = true;
//block.receiveCollision = false;
//items.receiveCollision = false;
for(int i = 0; i < objects.size(); ++i)
{
Object* obj = objects;
if(obj->receiveCollision)
{
for(int j = 0; j < objects.size(); ++i)
{
collisionCheck(obj, objects[j])
}
}
}


The second solution ::


enum Tags { TagPlayer, TagEnemy, TagBlock, TagWeapons};
class Object
{
Tags tag;
std::vector<Tags> collisionTags;
};
for(int i = 0; i < objects.size(); ++i)
{
Object* obj = objects;
for(int j = 0; j < obj->collisionTags.size(); ++i)
{
for(int k = 0; k < objects.size(); ++k)
{
if(obj->collisionTags[j] == objects[k].tag )
{
collisionCheck(obj, objects[k]);
}
}
}
}


happy.png

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!