O(n^log n) algorithm for collision detection

Question

I'm building a game engine and I was wondering: are there any algorithms out there for Collision Detection that have time complexity of O(N^log N)?

I haven't written any coding yet, but I can only think of a O(N^2) algorithm (ie: 2 for-loops looping through a list of object to see if there's collision).

Any advice and help will be appreciated.

Thanks

Answer 1

Spatial partitioning can create O(n log(n)) solutions. Depending on the exact structure and nature of your objects, you'll want a different spatial partitioning algorithm, but the most common are octrees and BSP.

Basically, the idea of spatial partitioning is to group objects by the space they occupy. An object in node Y can never collide with an object in node X (unless X is a subnode of Y or vice versa). Then you partition the objects by which go in which nodes. I implemented an octree myself.

Answer 2

You can minimize the number of checks by sorting the objects into areas of space. ( There is no point in checking for a collision between an object near 0,0 and one near 1000,1000 )

The obvious solution would be to succesively divide your space in half and use a tree (BSP) structure. Although this works best for sparse clouds of objects, otherwise you spend all the time checking if an object near a boundary hits an object just on the other side of the boundary