Avoiding duplicates in grid based collision detection?

Question

Here is my problem.

My game, for efficient rendering and collision is divided into regions. There will be many objects in each region that will dynamically move. When they move, I determine which regions they are in.

This means and object can be in multiple regions.

If I know object A is in region 1 and 2 and object B is also in 1 and 2, then what would happen is I would do:

for each object in region 1 and 2
if A collides with B...

I would effectively be checking the same pair twice.

What could I do to only check them once? Is there a data structure or algorithm I should be using?

Answer 1

If you can impose an ordering on the objects, then you only need to check the pairs where a < b by the ordering. Could be anything: index in an array, pointer (yay for languages that do allow pointer value access).

for(Object a : list) {
    for(Object b : list) {
        if (a.compare(b) < 0) {

is very simple and will actually solve the problem.

If you have integer indexed storage, you can just do

for(int i = 0; i < list.length; i++) {
    for(int j = i + 1; j < list.length; j++) {

and you won't get duplicates. This will work for ArrayList but probably not for arbitary types. You might be able to clone some iterators, but I wouldn't bet on that...

for(Iterator<Object> iter = list.iterator(); iter.hasNext(); ) {
    Object a = iter.next();
    Iterator<Object> iter2 = iter.clone();
    for(;iter2.hasNext();) {
        Object b = iter.next();

But seriously, that is a hack. I would be surprised if it works for all the java collections. A more reliable but just as hackish workaround with Java iterators:

for(Object a : list) {
    Iterator<Object> biter = list.iter();
    while(biter.next() != a) { };
    for(; biter.hasNext(); ) {
        Object b = biter.next();

In general, the java foreach syntax for(Clazz object : iterable) { is "cute", but much less powerful than Iterators. And in fact, the old integer for loop above works like a charm, too.

Answer 2

Why not store the results from previous computations?

Effectively, it would become:

for each object in region 1 and 2
    if results doesn't contain (A collides with B)
       ...
       results = result of (A collides with B)

Answer 3

No. It can be that your grid is too small. Also bounding box isn't very good at collision detection, you avoid empty region at the cost of inserts and deleting.

Answer 4

Instead of a regular spaced grid you could use a quadtree ( http://en.wikipedia.org/wiki/Quadtree ), which lends itself better to index objects of varying size. Instead of having to pick a single cell size (which might be too big for some objects and too small for others), you can let the quadtree determine the appropriate cell size.

However, even then you can't prevent a single object from occuring in multiple tree nodes, but this shouldn't be a goal that you should try to achieve - the only thing you should prevent is that every object occurs in tens or hundreds of cells or Quadtree nodes, because that does hurt performance.

Hence, if all your objects are about the same size, a regular grid might still be the best choice as long as the cells are at least as large (or maybe twice as large?) as your objects.