Optimization in collision detection

Question

I'm searching for information about optimization for collision detection.

There is an object (circle) which is moving from point a to point b. This object has radius r, and there are many obstacles (circle) in field too.

I have an algorithm (function) that checks collision between a circle and a capsule, and I currently call this function for every obstacle:

for-each (o : obstacles)
  if collide(o, Capsule(a,b,r))
    return true;

return false;

Many obstacles are very far away from the moving object and they can be ignored from checking with the collision detection function.

My question is:

Is there a solution to ignore checking all obstacles with collision detection function? Something like Nearest neighbor search or KD trees?

EDIT : All obstacles have same radius.

Answer 1

As a first step, you can ignore all obstacles not beeing in a certain frame/box.

E.g. all obstacles with y - coordinate (the y- lowest point of the shape of the obstacle) bigger then the maximum y coordinate of a and b + same distance for the radius of the moving object can be ignored. Similar for lower y-border and the x borders. Instead of one box, you could further branch similar into two (ore more) boxes. For example buy splitting the distance of a-b into two distances and doing the above procedure for each of (a, (b-a)/2), /(b-a)/2, b).

But it all depends on how efficient you can compare these values in comparison to you collision procedure.

Answer 2

You can simply use a grid, where each cell holds all the obstacles touching that cell. Now only check the cells for collision that your capsule touches. Also you could use a quadtree as well, but from my experience a grid suffices usually and also has the advantage of being easily and quickly updatable in case your obstacles move.