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.
collisions? n^2 checks?
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.
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..
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.
And if you want to take this idea to the next level, look up quad-trees, octrees, etc..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.
Actually, I'd suggest a sweep prune system as most collision systems use them. They let you "island" out the potential collisions much faster/easier than other variations.
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.
I'm also not fond of Octrees. Often they are the first thing people suggest, without thinking about if they would really help for that one problem of the person asking, and then people generate more work with a complicated datastructure with many pointers to traverse that they dont understand completely and still try to reinvent, where they possibly feed in and maybe duplicate all objects as triangle soup or maybe just end up having many objects at node boundaries and splitting those objects or having them in such a huge node that the Octree cant help much.
Meanwhile they could just test the bounding spheres of all objects first and have most work done, before testing a few triangles from remaining objects. Then if profiling shows there is really a performance problem later it can still be optimized.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
