Collision Detection with Many Objects

[XianForce]

I have many objects that will be in motion, but I only have up to 5 that would need to have collision checks for. How do I check for collisions for these objects, while not having to check for collisions between it and every other object?

[MarauderIIC]

Put them in a special list?

[Bludklok]

I've thought about this as well but I never came to a conclusion.

My idea is that you could split the screen into decent size sections (If you had a 100 x 100 screen you split it into 50 x 50 sections so you have 4 sections). Number the sections and label the object according to what section they are in. Then just do a check for which ever section you want.

Thats the best I could come up with.

[Bakkon]

Have them hold a hasCollision flag and check for that before checking collision.

[avansc]

mar had the best solution. just make a specialy list that only contain object that will collide.
if you have 100 object that wont collide and 5 that will. and you check for a collision flag on all of them you are wasting alot of cpu cycles.
and the splitscreen is not your idea. its called quad tree decomposition.

[RyanPridgeon]

Do you mean they dont collide because they're not supposed to, or because they're not near each other?

To optimise so that only nearby objects are tested, you can use a quad/oct tree

[hurstshifter]

A quad-tree would probably be a good idea if you had many objects that could collide, but with a small number like 5 or so Marauder's idea of a special list of collision-specific objects is probably your best bet.

[XianForce]

Put them in a special list?

Yeah, but that's not what I was talking about exactly. It's like I have a bunch of Enemy NPCs that don't collide with each other, but the player can can collide with them. So I don't want to check for every enemy there is. So I'm looking for something like the quad tree composition thing avansc was talking about.

Thanks guys =D

[AerisAndMe]

I'm working on implementing a quad tree for ES coarse-collision resolutions right now too. In our case, a quad tree is the way to go because of its flexibility and its dynamics.

If there aren't going to be vast numbers of collisions happening at a time, a grid is FAR easier to implement and functions similarly.

The biggest difference between something like a quad tree (oct for 3D of course), or binary partitioning even, and a grid is that a grids cells are static and a tree's cells can be programmed to adjust based on the density of collidables in that area.

For example, if you set your grid's cells to be 256x256, and your average object is 32x32, then there can be several collisions happening in every grid, each of which must now be resolved using the brute force (check every object with every other object) method. If your grid's cells are 64x64 and there are very few objects in the grid, you may lose efficiency because the number of cells ends up being huge.

After all, it depends on your purpose. Trees are, of course, heavier and harder to implement.