How to Optimize Object Collision Check in games?

Question

in my game, ObjectManager class is manage my game's all objects and it has a list of Objects.

and i use 2 for statement when i check the each object's collision.

for(int i = 0; i < objectnum; ++i )
{
  for(int j = 0; j < objectnum; ++j)
  {
    AABB_CollisionCheck()
  }
}

but if there is many objects in the game, the FPS is get lower. (80 Objects == 40frame) maybe this is because that my collision check method is inefficient. (if the object num is n , then my method operate n^2 times)

can you give me some tips about this Collision Check Optimizing?

i want to reduce my for loop to check each Object collision.

what is different about using Callback Fucntion or not? for Collision Check. is there have any operate speed adventage about Callback?

p.s thanks a lot for read my question. and please excuse for my english skill...

You don't have to check whether B collides with A if you already checked whether A collides with B. — Blutkoete, Nov 10 '14 at 10:08
possible duplicate of [What technique should be used to prune 2d collision checks?](http://stackoverflow.com/questions/414553/what-technique-should-be-used-to-prune-2d-collision-checks) — slaphappy, Nov 10 '14 at 10:08
The most obvious improvement would be running the second loop from `i + 1`. After that, you probably want to look at the collision code, and when that doesn't help, some space-partitioning scheme. A profiler is a good help. — molbdnilo, Nov 10 '14 at 10:11
@Blutkoete, I would also suggest such a code: `for (int i = 0; i < objectnum - 1; ++i) for (int j = i + 1; j < objectnum; ++j)` — Dmitry Ginzburg, Nov 10 '14 at 10:19

score 1 · Answer 1 · edited May 23 '17 at 12:05

As is often the case, knowing an extra bit of vocabulary does wonders here for finding a wealth of information. What you are looking for is called the broad phase of collision detection, which is any method that prevents you from having to look at each pair of objects and thus hopefully avoid the n^2 complexity.

One popular method is spatial hashing, where you subdivide your space into a grid of cells and assign each object to the cells which contains it. Then you only check objects in each cell against other objects from that one and the neighboring cells.

Another method is called Sweep and Prune, which uses the fact that objects usually don't move much from one frame to the next.

You can find more information in this question: Broad-phase collision detection methods?

score 0 · Answer 2 · answered Nov 10 '14 at 10:09

can you give me some tips about this Collision Check Optimizing?

Well firstly you could try to optimize your second loop making that way :

for (int i = 0; i < objectnum; i++)
{
  for (int j = i+1; j < objectnum; j++)
  {
    AABB_collisioncheck();
  }
}

This will only check collisions in one way, say A collided B, then you won't trigger B collided A.

How to Optimize Object Collision Check in games?

2 Answers2