How do you check collision against 1000x1000 objects?

Danny Chu · 2012-12-04T18:26:16

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 So, i just want to know if thats how you do it... cant see any other way of doing this so far

For Beginners

Started by Assassinbeast December 02, 2012 10:16 PM

12 comments, last by Burnt_Fyr 11 years, 4 months ago

landagen

376

December 03, 2012 03:43 PM

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.

iMalc

2,466

December 04, 2012 07: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.

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.

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

pTymN

464

December 04, 2012 06: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.