Collision detection of a huge number of circles

Question

What is the best way to check for collisions in a huge number of circles?
It is very easy to detect a collision between two circles, but if we check each combination, then it is O (n ² ) , which is definitely not the optimal solution.

We can assume that the circle object has the following properties:

• Coordinates
• Radius
• Speed
• Direction

The speed is constant, but the direction may change.

I came up with two solutions, but maybe there are some better solutions.

Solution 1
Divide the entire space into overlapping squares and check for collision only with circles that are in the same square. The squares must intersect, so there will be no problem when the circle moves from one square to another.

Decision 2
First you need to calculate the distance between each pair of circles.
If the distance is small, these pairs are stored in some list, and we need to check for conflicts in each update.
If the distance is large, then we save, after which the update can be a collision (it can be calculated because we know the distance and speed). It should be stored in a priority queue. After the pre-calculated number of update intervals needs to be checked again, and then we perform the same procedure - put it in the list or again in the priority queue.

Answers to Mark Bayer questions

• Is this for the game?
  This is for modeling, but it can also be considered as a game.
• Do you want to recount a new position every n milliseconds and also check for conflicts at this time?
  Yes, the time between updates is constant.
• Do you want to find the time at which the first / any collision occurs?
  No, I want to find every collision and do something when it happens.
• How important is accuracy?
  It depends on what you mean by precision. I need to detect all collisions.
• Is it a big problem if very small, fast-moving circles can sometimes pass with each other?
  It can be assumed that the speed is so low that this will not happen.

Answer 1

I assume that you are doing a simple molecular dynamic simulation, right? I came to the same problem many times in Monte Carlo and molecular dynamics modeling. Both of your decisions are often mentioned in the simulation literature. Personnel I prefer solution 1 , but slightly modified.

Solution 1
Divide your space into rectangular cells that do not overlap. Therefore, when you check one circle for a collision, you look at all the circles inside the cell that your first circle is in, and look at the X-cells in each direction. I tried many X values ​​and found that X = 1 is the fastest solution. Thus, you must divide the space by the cell size in each direction equal to:

Divisor = SimulationBoxSize / MaximumCircleDiameter; CellSize = SimulationBoxSize / Divisor; 

The divisor must be greater than 3, otherwise it will cause errors (if it is too small, you should increase the simulation window).
Then your algorithm will look like this:

• Put all the circles inside the box
• Create a cell structure and save indexes or pointers to circles inside a cell (in an array or in a list)
• Take a step in time (move everything) and update the position of the circles inside the cells
• Look around each circle for a collision. You must check one cell in all directions.
• If there is a collision, do something.
• Go to 3.

If you write it correctly, you will get something about O (N) complexity, because the maximum number of circles inside 9 cells (in 2D) or 27 cells (in 3D) is constant for any total number of circles.

Decision 2
Ususaly does this as follows:

• For each circle, create a list of circles at a distance of R < R_max , calculate the time after which we must update the lists (something about T_update = R_max / V_max , where V_max is the maximum current speed)
• Take it step by step
• Check the distance of each circle with circles in its list
• If there is a collision, do something.
• If the current time is longer than T_update , go to 1.
• It remains to go to 2.

This solution with lists is often improved by adding another list with R_max_2 > R_max and with its own expiration time T_2 . In this solution, this second list is used to update the first list. Of course, after T_2 you need to update all lists that are O (N ^ 2) . Also be careful with these T and T_2 times, because if a collision could change speed, then these times would change. In addition, if you enter some tricks into your system, this will also lead to a change in speed.

Solution 1 + 2 You can use lists to detect conflicts and cells to update lists. In one book it was written that this is the best solution, but I think that if you create small cells (as in my example), then solution 1 is better. But this is my opinion.

Other things
You can also do other things to improve simulation speed:

• When you calculate the distance r = sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) + ...) , you do not need to perform the square root operation. You can compare r^2 with some value - this is normal. Also you do not need to perform all operations (x1-x2)*(x1-x2) (I mean, for all values), because if x*x larger than some r_collision^2 , then all the rest are y*y and etc., Summarized, will be more.
• The molecular dynamics method is very easy to parallelize. You can do this using threads or even on the GPU. You can calculate each distance in different streams. On a GPU, you can easily create thousands of threads at virtually no cost.

For hard areas, there is also an efficient algorithm that does not perform time steps, but instead, it searches for the nearest time collision and moves on to this time and updates all positions. This can be useful for non-dense systems where collisions are not very likely.

Answer 2

There is a “ spatial index ” of the data structure for storing your circles for quick comparison later; Examples: Quadtree, r-tree and kd-tree.

Solution 1 seems to be a spatial index, and solution 2 would benefit from the spatial index every time you recalculate your pairs.

To complicate the situation, your objects move - they have speed.

It is normal to use spatial indexes for objects in games and simulations, but mainly for stationary objects and usually objects that do not respond to a collision while moving.

normal in games and such that you calculate everything at given time intervals (discrete), so it may be that two objects pass through but you did not notice, because they moved so fast. Many games do not even really evaluate collisions in strict chronological order. They have a spatial index for fixed objects, for example. walls and lists for all moving objects that they check exhaustively (albeit with relaxed discrete checks, as I set out).

Accurate continuous collision detection and when objects respond to collisions in simulations are usually much more demanding.

The pairing approaches you have outlined sound promising. You can save pairs sorted after the next collision and reinsert them when they collide in the corresponding new positions. You only need to sort the new generated collision (O (n lg n)) for two objects, and then combine the two lists (new collisions for each object and the existing collision list, insert new collisions, delete these obsolete collisions that list two objects, which collided) which is O (n).

Another solution is to adapt your spatial index to store objects not strictly in one sector, but in each one that it has passed since the last calculation, and do things discretely. This means storing fast moving objects in your spatial structure, and you will need to optimize it for this case.

Remember that linked lists or pointer lists are very bad for caching on modern processors. I would recommend that you keep copies of your circles - their important properties for collision detection in any case - in an array (sequential memory) in each sector of any spatial index or in pairs that you indicated above.

As Mark points out in the comments, it would be pretty simple to parallelize the calculations.

Answer 3

One possible way is to use Delaunay triangulation in the center of your circles.

consider the center of each circle and apply delaunay triangulation. this will result in surface loss in triangles. this allows you to create a graph where each node stores the center of the triangle, and each edge connects to the center of a neighboring circle. tessellation, operated above, will limit the number of neighbors to a reasonable value (on average 6 neighbors)

Now that the circle is moving, you have a limited set of circles to consider in a collision. you need to apply tessellation again to the set of circles that the movement affects, but this operation includes only a very small subset of the circles (neighbors of the moving circle and some neighbors of the neighbors)

the critical part is the first tessellation, which will take some time to complete, and then tessellation is not a problem. and, of course, you need an effective implementation of the graph in terms of time and space ...

Answer 4

Divide your space into regions and keep a list of circles centered in each region.

Even if you use a very simple scheme, such as placing all the circles in a list sorted by center.x, then you can quickly speed up the process. To test a given circle, you only need to test it against the circles on either side of it in the list, exiting until you reach the one with the x coordinate greater than the radius.

Answer 5

You can make a two-dimensional version of the "tree sphere", which is a special (and really easy to implement) case of the "spatial index" to be proposed. The idea is to "combine" the circles into a "containing" circle until you have one circle that "contains" a huge number of circles.

Just to indicate the simplicity of calculating the “containing circle” (top-of-my-head): 1) Add the central locations of the two circles (as vectors) and scale by 1/2, that is, the center of the containing circle 2) Subtract the central locations of the two circles (as vectors), add the radii and scale to 1/2, i.e. the radius of the containing circle

Answer 6

Which answer is most effective will to some extent depend on the density of the circles. If the density is low, then placing a low-resolution grid on the map and labeling these grid elements that contain a circle are likely to be most effective. This will take approximately O(N*m*k) per update, where N is the total number of circles, m is the average number of circles for each grid point, and k is the average number of grid points covered by one circle. If one circle moves more than one grid point per turn, then you need to change m to include the number of projected grid points.

On the other hand, if the density is extremely high, you should try to get closer to the chart. Let each circle contain all neighbors at a distance R ( R > r_i for each circle radius r_i ). Then, if you move, you request all the circles in the forward direction for the neighbors that they have, and grab everything that will be within D; then you will forget all those that are in the opposite direction, which are now further than D. Now a full update will take O(N*n^2) , where N is the average number of circles in the radius R For something like a closely spaced hexagonal grid, this will give you much better results than the grid method above.

Answer 7

Suggestion - I'm not a game developer

Why not predict when collisions will occur?

as you indicate

We can assume that the circle object has the following properties:

-coordinates

-radius

-Velocity

-direction

The speed is constant, but the direction may change.

Then, when the direction of one object changes, recount the pairs that are affected. This method is effective if the directions do not change too often.

Answer 8

As mentioned in his answer, spatial partition trees are a common solution to this problem. These algorithms sometimes require some tweaking to effectively control moving objects. You want to use a free rule for installation in the basket so that most of the movement steps do not require changing objects.

I saw your “solution 1” used for this problem before and called the “collision hash”. It can work well if the space you are dealing with is small enough to be manageable and you expect your objects to be at least vaguely close to evenly distributed. If your objects can be grouped, then obviously this is causing the problem. Using a hybrid approach for some type of partition tree within each hash box can help with this and can transform a clean tree approach into something that is easier to scale at the same time.

Overlapping areas are one way to deal with objects that cross the boundaries of trees or hash blocks. A more common solution is to check for any object that crosses the edge with respect to all objects in the adjacent field, or to insert the object in both fields (although additional processing is required to prevent the interruption of the crawl).

Answer 9

If your code depends on the checkmark (and tests to determine if the objects on the checkmark overlap), then:

• when objects move "too fast", they pass each other without colliding

• when several objects collide in the same tick, the final result (for example, how they bounce, what damage they receive, ...) depends on the order that you check for collisions, and not on the order in which collisions can / must happen. In rare cases, this can lead to a game blocking (for example, 3 objects collide in the same tick; object1 and object2 are set to collide with them, then object2 and object3 are set to collide with them, causing object2 to collide again with object1, so that the collision is between object1 and object2 should be redone, but this causes object2 to collide with object3 again, so ...).

Note. Theoretically, this second problem can be solved using "recursive tick division" (if more than two objects collide, divide the tick length in half and try again until only two objects collide in this "sub-tick"), It can also lead to blocking and / or abnormal termination of games (when 3 or more objects collide at the same moment, when you end up with a “forever disappear” script).

Besides; sometimes when game developers use "ticks", they also say "1 fixed tick length = 1 / variable frame rate", which is absurd because what needs to be a fixed length cannot depend on any variable (for example, when the graphics processor in the absence of speed of 60 frames per second, all the simulation is in slow mode); and if they don’t do this and instead have “ticks of variable length”, then both problems with “ticks” become much worse (especially at a low frame rate), and the simulation becomes non-deterministic (which can be problematic for several players, and can lead to to other behavior when the player saves, loads or pauses the game).

The only correct way is to add a dimension (time) and give each object a segment described as “initial coordinates and final coordinates”, plus “trajectory after final coordinates”. When an object changes its trajectory (either because the unexpected happened, or because it has reached its “final coordinates”), you will find the “fastest” collision by going through the “distance between two lines” (object1.radius + object2 .radius) "calculation for an object that has changed for every other object; then change the" final coordinates "and" trajectory after the final coordinates "for both objects.

An external “game loop” would look something like this:

  while(running) { frame_time = estimate_when_frame_will_be_visible(); // Note: Likely to be many milliseconds after you start drawing the frame while(soonest_object_end_time < frame_time) { update_path_of_object_with_soonest_end_time(); } for each object { calculate_object_position_at_time(frame_time); } render(); } 

Please note that there are several ways to optimize this, including:

• divide the world into "zones" - for example, so if you know that object1 will go through zones 1 and 2, it will not be able to collide with any other object that also will not go through zone 1 or zone 2

• store objects in the segments "end_time% bucket_size" to minimize the time taken to find the "next closest end time"

• use multiple threads to execute "Calculate_object_position_at_time (frame_time);" for each object in parallel

• do all the work "simulation state until next frame time" in parallel with "render ()" (especially if most of the rendering is done using the GPU, leaving the processors free).

For execution:

• When collisions occur infrequently, they can be significantly faster than ticks (you can hardly do work for a relatively long period of time); and when you have free time (for any reason - for example, due to the fact that the player paused the game), you can timely calculate the future (effectively smooth out the overhead over time to avoid sudden jumps in productivity )

• If collisions happen often, this will give you the right results, but it can be slower than a broken joke that gives the wrong results under the same conditions.

It also simplifies the arbitrary relationship between “simulation time” and “real time” - things like fast forward and slow motion won't crash (even if the simulation runs at the speed that the hardware can run, or so slow it’s hard to say if anything is moving at all); and (in the absence of unpredictability), you can pre-calculate arbitrary time in the future, and (if you save the old information about the “segment of the line of the object” instead of discarding it after the expiration date), you can go to an arbitrary time in the past and ( if you store old information only at certain points in time to minimize storage costs), you can return to the time described by the stored information, and then calculate the transfer to an arbitrary time. Together, these things also make it easy to do things like "instant slow motion playback."

Finally; , , " " .

, - , / (, , ), ( , ) (, /angular, )./) , , , ; "" , , N .