Sign in to follow this  
hiigara

Is this Broad phase Collision Detection Algorithm correct?

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by hiigara
It'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...

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this