Sign in to follow this  
ms75214

collisions? n^2 checks?

Recommended Posts

If you have 100 objects on screen and want to see about collisions...
 
Do you just check all 100 objects with the 99 others? (thus doing 9900 collision checks)
 
 
Is there a better way?
 
Thanks.
 

Share this post


Link to post
Share on other sites

A better way is to split your map into smaller pieces, and do the collision checks of one object against every other object that is in the same piece of map. For example, a 2d rectangular map can be split into a grid.

And if you want to take this idea to the next level, look up quad-trees, octrees, etc..

Share this post


Link to post
Share on other sites

Try using O(n^2). In this question it doesn't matter much, however using proper notation later on will be important. Consider:

 

Trivial cases.

 

And other stuff I can't really remember. What if you have 0 or 1 objects? Then its a trivial problem because its either Theta(0) or Theta(1). Obviously it's not important now, but it's good to get into the habit of proper notation so when you're doing something which is really important you don't slip up and confuse your peers.

Share this post


Link to post
Share on other sites

with 100 objects any method will be fine.

I will suggest not to use quadtrees or octrees ever becouse it cant be faster than uniform grid (depends on concept), Quadtrees principles are the same as simple grid but you will face recursion. Even layered grid is better.

In your situation I will chouse 1axis sweep and prune algorithm (most simple case) and will end up with 0.1ms performace.

Edited by serumas

Share this post


Link to post
Share on other sites

If you avoid double-checking then you only have 4,950 checks rather than 9,900.

 

Apart from that, some simple broad-phase tests can cut down on work if your collisions are complex. Just don't do more work eliminating work than the work that it eliminates.

 

Er...

 

You know what I mean.

Share this post


Link to post
Share on other sites

Keep it simple, if the checks aren't too many for 100 objects, it's fine. Obviously this depends on hardware speed and the difficulty of the check.

 

Normally you don't actually want to test 100 objects against all others, some collisions are "deliberately ignored", for example, you might group them into "player objects", "enemy objects", "player missiles" and "enemy missiles". It's likely that only some combinations of these groups need to be tested, so you can dramatically cut down the checking by only checking "interesting" types against each other.

 

If most of the objects aren't doing anything interesting (e.g. they're outside the screen AND not moving) then you could also ignore them somehow.

 

There are a variety of optimisations which are not as "cool" as world-partitioning or something else clever (e.g. some kind of spatial index), which are much easier to implement and work nearly as well for relatively small numbers of objects. Keep it simple.

Share this post


Link to post
Share on other sites

Hello

You can also integrate a state (isSleeping) to your entities. If an entity is not moving for a given (short) elapsed time, you can set isSleeping to true, so that you can avoid collision detections between sleeping entities. (And if a sleeping entity is involved in a collision then set isSleeping to false).

 

Hope it can help

 

smile.png

Share this post


Link to post
Share on other sites


If you have 100 objects on screen and want to see about collisions...
 
Do you just check all 100 objects with the 99 others? (thus doing 9900 collision checks)
 
 
Is there a better way?

 

not only is there no better way,   there is no other way - period. 

 

all collision detection schemes and strategies are a form of "divide and conquer" to deal with this fact.

 

all seek to reduce that 100 objects somehow, by dividing up the scene into smaller sets of objects, by dividing up the object types and skipping the collisions you don't need to check (like my bullets colliding with each other), by culling objects you don't need to check from the list (asleep, etc), by storing history of past checks and positions, and so on.

 

but in the end, if you need to check a given pair-wise collision, you have to break down and do a collision check (of some sort).

 

that's where the second way to speed things up comes into play...

 

you ramp-up the complexity of the checks.

 

you start with fast inaccurate, and go to slower more accurate checks. the fast checks trivially reject anything that's not close to being a collision. the slower more accurate checks are performed only on those object pairs that pass the first check.

 

unfortunately in the end, a lot of how fast the actual checks are usually has a lot to do with:

1. how anal-retentive one is about collision check accuracy. most folks go way overkill.

2. how poor an algo choice one makes. less than optimal choices are all too common. most geometry problems can be solved in more than one way. many times folks seem to know of a number of possible (usually complex) methods, but somehow don't know of the the best one (hit or miss learning i suspect, or perhaps the "i have a hammer [oct-tree for example], so everything looks like a nail" mentality).

3. how obtusely one implements the ill-suited overkill algo chosen. overly complicated code on top of poor algo choice is also very common.

 

avoid these pitfalls, divide and conquer, and ramp up check complexity, and you'll be fine, even with 100,000 dynamic objects.

Share this post


Link to post
Share on other sites

 

not only is there no better way,   there is no other way - period. 

 

I only slightly agree with this statement. Worst case most solutions to pruning collision detections have a degenerate case which ends up comparing everything against everything else anyways. However, this generally isn't typical or in most systems (with some form of broad-phase implementation) possible, so finding a means to take advantage of such spatial coherence is actually very beneficial and actually does reduce the number of collision checks (simple or complex).

 

@ms75124 I would recommend reading / getting a copy of Christer Ericson's book "Real-Time Collision Detection". In it he outlines several different methods for reducing the number of collision checks upfront (generally in what he calls "Spatial Partitioning" and most call "broad-phase" collision detection; simple checks to that reduce which objects get checked for collision). To list a few of the *types* of methods he mentions (within each there are a few algorithms): uniform grids, hierarchical grids, trees, and sort and sweep. He also offers some insight on the benefits performance-wise of most.

Share this post


Link to post
Share on other sites


I only slightly agree with this statement.

 

ah, you misunderstand!

 

my only point is  that after you've divided and conquered as much at possible, whatever's left you end up pair-wise checking.  THEN you can apply progressively more accurate and slower checks, until you reach the level of accuracy desired.

Share this post


Link to post
Share on other sites
In short explanation: Using a variety of different techniques you basically just bundle together objects so that you -know- they can not possibly be colliding and then use that to narrow down how many collision checks you need to do.
 
You can't really get rid of the checking but you can try to eliminate as many redundant ones as possible. Edited by Satharis

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this