Jump to content

  • Log In with Google      Sign In   
  • Create Account

Interested in a FREE copy of HTML5 game maker Construct 2?

We'll be giving away three Personal Edition licences in next Tuesday's GDNet Direct email newsletter!

Sign up from the right-hand sidebar on our homepage and read Tuesday's newsletter for details!


We're also offering banner ads on our site from just $5! 1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


How do you check collision against 1000x1000 objects?


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
13 replies to this topic

#1 Assassinbeast   Members   -  Reputation: 271

Like
1Likes
Like

Posted 02 December 2012 - 04:16 PM

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[i], objects[j]);[/source]
But thats 1000x1000 = a million loops in a single statement Posted Image

So, i just want to know if thats how you do it... cant see any other way of doing this so far Posted Image

Edited by Assassinbeast, 02 December 2012 - 04:19 PM.


Sponsor:

#2 ultramailman   Prime Members   -  Reputation: 1581

Like
8Likes
Like

Posted 02 December 2012 - 04:24 PM

The idea is to seperate the map into several regions. An object in region B cannot possibly be colliding with an object in region C. So if your 1000 objects are evenly distributed in four regions, you only need to do 4 * (1000 / 4)^2 = 250000 checks. Even less if you split the map into more regions.

#3 C0lumbo   Crossbones+   -  Reputation: 2343

Like
6Likes
Like

Posted 02 December 2012 - 04:27 PM

Broadphase collision detection is the general term you need to be googling.

Common solutions are spatial partitioning and sweep-and-prune.

#4 Cornstalks   Crossbones+   -  Reputation: 6991

Like
10Likes
Like

Posted 02 December 2012 - 04:27 PM

There are usually two steps in collision detection: broad phase and narrow phase. The first one, broad phase, is basically going through the objects and creating "groups" of objects that might be colliding. In the narrow phase, each group is individually processed and the actual collisions are detected and resolved. The broad phase is really important, as it allows you to avoid N2 comparisons.

As for what broad phase algorithm to use... that depends. You could create a spatial hash (works pretty well if you fine tune it and have lots of objects all of about the same size), binary space partitioning (BSP) trees, sweep and prune, axis-aligned bounding box (AABB) trees, etc. Bullet has a nice page on a couple of broad-phase algorithms.

I don't know what's easiest, but I've found dynamic AABB trees seems to work pretty well (which Chipmunk physics uses by default, albeit it's a little tweaked/fine tuned).
[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

#5 Yrjö P.   Crossbones+   -  Reputation: 1412

Like
7Likes
Like

Posted 02 December 2012 - 04:32 PM

Before doing anything else, you'll probably want to prevent 500000 useless comparisons by switching the "j=0" in your code into "j=i+1"...

#6 cardinal   Members   -  Reputation: 898

Like
1Likes
Like

Posted 02 December 2012 - 04:33 PM

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.

#7 Assassinbeast   Members   -  Reputation: 271

Like
1Likes
Like

Posted 02 December 2012 - 04:40 PM

ahh ok, thanks for all the help and suggestions Posted Image

#8 Burnt_Fyr   Members   -  Reputation: 1245

Like
2Likes
Like

Posted 02 December 2012 - 04:53 PM

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.

#9 Paradigm Shifter   Crossbones+   -  Reputation: 5406

Like
1Likes
Like

Posted 02 December 2012 - 05:06 PM

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.
"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

#10 __UFNHGGI_H__   Members   -  Reputation: 305

Like
-3Likes
Like

Posted 03 December 2012 - 01:24 AM

hehe
1000 * 1000 == BOOOM Posted Image

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[i];
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[i];
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]);
   }
  }
}
}

Posted Image

#11 landagen   Members   -  Reputation: 376

Like
5Likes
Like

Posted 03 December 2012 - 09:43 AM

Also, I would say that in order for a collision to take place, one of the colliding objects must have moved. No need to test 2 objects together if neither of them moved.



#12 iMalc   Crossbones+   -  Reputation: 2313

Like
1Likes
Like

Posted 04 December 2012 - 01:44 AM

Also, I would say that in order for a collision to take place, one of the colliding objects must have moved. No need to test 2 objects together if neither of them moved.

Unless of course you have a more advanced physics system where objects can change size. Posted Image Posted Image

But yeah, identifying objects that have not changed in any way and skipping those pairs, is a very useful optimisation to use at some stage in the collision detection process. It likely doesn't matter too much at what point you do it.

Edited by iMalc, 04 December 2012 - 01:44 AM.

"In order to understand recursion, you must first understand recursion."
My website dedicated to sorting algorithms

#13 pTymN   Members   -  Reputation: 464

Like
0Likes
Like

Posted 04 December 2012 - 12:11 PM

In situations where you need to actually update that many objects each and every frame, well tuned spatial hashing will handily beat all other broadphase methods for large amounts (1000s) of uniformly sized objects - where the largest are within 4-8 times the radius of the smallest objects. If you can get away with only updating a subrect of your game world, that's another optimization you should consider.

 


#14 Burnt_Fyr   Members   -  Reputation: 1245

Like
0Likes
Like

Posted 04 December 2012 - 12:26 PM

Stroppy Katamari already said that, and the j = i+1 method saves checking i == j as well.

I was ninja'd! (i was interrupted mid post at work, and didn't get to finish until after many follow up posts)

+1 on the j=i+i solution though.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS