Public Group

# collisions? n^2 checks?

This topic is 2142 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 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 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 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 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 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.

• 9
• 17
• 10
• 11
• 18