Fast way to check collisions between multiple balls every frame

user_5348875 0
Viewed 508

Suppose I have N moving balls of radius r in a 2D space. For simplicity, N < 30.

I want to know the fastest way to check if these balls are colliding every frame.

I could obviously do something like this:

for(int i = 0; i < N - 1; i++){
    for(int j = i + 1; j < N; j++){
        if (dist(ball[i], ball[j]) <= r) CollisionList.Add(i, j);
    }
}

But as this is O(N²) and I want to do this every frame, I'd like to ask if there is a faster way. Every frame I want to be able to deal with every collision and compute its consequences.

unity3d game-physics physics math
2 Answers

What you seem to be asking is the optimal solution to verifying collision between bodies in a simulation (video game). Here is the long answer.

It's actually a whole discipline to try to find this efficiently and the ball problem is a simpler subset of this kind of problem.

By seeing that your algorithm is O(N²) you saw the actual problem which is choosing the right bodies to test for collision. It's not that simple to implement efficiently, Unity has that built-in I think it would be worth checking out (I'm not good with Unity so I can't help you too much with that).

Also, if you're pretty adamant about doing it by yourself I think a good starting point would be to divide your space and check collision only in those small subspaces. There is a C coded version of that algorithm maybe it could guide you or you can use it directly.

Hope that helps!

user_134784980

Alongside the answer of vdere, maybe you could modify and adapt the closest pair of points algorithm. Instead of using it to find the pair of points closest to each other, you can try to find all pairs of centers whose distances are less or equal to the sum of the corresponding radii.

Another thing that comes to mind is to keep and update the Delaunay triangulation of the centers of the balls, or maybe another version of it, called the weighted Delaunay triangulation of the centers, where the weights are the radii of the balls. There are different algorithms for generating the (weighted) Delaunay triangulation or its dual version, the Voronoi Diagram. See for example Fortune's algorithm.

user_99114400
Related