# Is this Broad phase Collision Detection Algorithm correct?

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

## Recommended Posts

Quote:
 A more general, elegant system, which is useful in simulation-type environments where all objects must collide with each other, is to iterate over all moving objects, and test them against: . any objects after them in the current cell's list . any objects in the lists of 4 cells which neighbor the current cell. You can use any contiguous set of 4 cells, for instance, [right, right-down, down, left-down], [up, up-left, left, left-down], etc. It might seem like this technique will miss some collisions, but if you work it out on paper you'll see that every possible collision between objects is found. This lets us reduce the number of per-object cell-list tests to 5 (from 9), without resorting to flags or any other awkward solution.
It was on http://www.metanetsoftware.com/technique/tutorialB.html. I intend to use it literally. Just want to make sure.

##### Share on other sites
That algorithm restricts you to a grid size of at least the size of your largest object. That sounds pretty wasteful unless you were making geometry wars or N+.

It all depends on your game.

I more generic solution would be a loose quadtree.

##### Share on other sites
Yeah, that's if you object size is less or equal to the cell size.

If your objects vary in size, you can use a multi-resolution map (fine level cells of size X, coarser level of size X*2, and so on). Or use a loose kd-tree / quad-tree, or use bucket lists of objects overlapping cells, or some other algorithms (sweep and prune).

##### Share on other sites
It's a Soccer Game. The Objects (Players) are Circles of the same Size.

##### Share on other sites
Quote:
 Original post by hiigaraIt's a Soccer Game. The Objects (Players) are Circles of the same Size.

Then it should be fine. If you think about the algorithm a bit, you should be able to convince yourself that it is correct...

1. 1
Rutin
24
2. 2
3. 3
JoeJ
18
4. 4
5. 5

• 38
• 23
• 13
• 13
• 17
• ### Forum Statistics

• Total Topics
631708
• Total Posts
3001839
×