Jump to content
  • Advertisement
Sign in to follow this  

collisions? n^2 checks?

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

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
Advertisement

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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!