CODEWITHSUNDEEP
algorithmoptimizationcollision-detection
masoud
masoud

Reputation: 56479

Optimization in collision detection

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.

enter image description here

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.

Upvotes: 4

Views: 6286

Answers (6)

masoud
masoud

Reputation: 56479

A comment on Martin's answer:

I made a box like Box(a.x-R, a.y-R, b.x+R, b.y+R) where R is ObjectRadius + ObstacleRadius, then drop every obstacle which is not inside this box. In the figure, only obstacles with yellow dot will be checked:

enter image description here

Upvotes: 2

NiTuRen
NiTuRen

Reputation: 57

You can try implementing spatial partitioning in your code. By partitioning each object/obstacle into each boxes covering the entire space or map. By doing so you are grouping the obstacle into sections. So you can reduce the collision check by a huge amount by just checking for collision within a small section. If your obstacle are not moving you only need to do this partitioning only once for each obstacle. If they are moving, you have to update the partitioning [Regrouping] for each obstacle every time.

Spatial Partitioning techniques have been around for quite some time, here is a link to help you out with the implementation.

http://gameprogrammingpatterns.com/spatial-partition.html

Upvotes: 0

maxim1000
maxim1000

Reputation: 6365

  1. Put centres of obstacles into KD-tree.
  2. Find the nearest centre.
  3. Check if it's closer than ObstacleRadius.

Upvotes: 0

Cybercartel
Cybercartel

Reputation: 12592

I can recommend a monster curve, for example a hilbert curve. It's a quadtree or kd tree like data structure and it reduces the 2d complexity to a 1d problem. At each frame you can just build the monster curve from start and such spare the deleting or inserting in a quadtree or kd tree. It has also some better 2d tiling properties but that may be unwanted in your case.

Upvotes: 1

stryba
stryba

Reputation: 2027

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.

Upvotes: 3

Martin
Martin

Reputation: 336

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.

Upvotes: 5

Related Questions