The fastest way to calculate the gravitational forces experienced between a large set of particles?

Question

Given a set of n particles in two-dimensional space, where each particle experiences an attractive force with respect to all other particles in the set, proportional to the inverse square of the distances between them, can you imagine any clever methods for calculating the net force experienced by each particle without performing distance computations n ^ 2?

From the Particle class of my program:

public void calculateAttractions(List<Particle> entities) { foreach (Particle p in entities) { if (!p.Equals(this)) { Vector2 dx = this.Position - p.Position; this.ApplyForce(-dx / dx.LengthSquared()); } } } 

The brute force method can only simulate ~ 150 particles in my program (using the XNA infrastructure and the Farseer physics engine) before running into performance issues.

If there is no other way, how can I optimize this code, or how can I cheat? I tried to randomize the call to compute Attractions () based on particles with particles, so that at any given time, only about 1/3 of the particles are actually updated. This led to some performance improvements, but of course, at the cost of accuracy.

What I'm trying to do is like calculating the gravitational force. Someone from this topic suggested working with complex numbers and using the equation:

 (z-z')/abs(z-z')**3 

However, I do not know what z refers to, and I cannot find a link to this equation anywhere else.

EDIT: although I accepted the answer below, I ended up using a solution that no one mentioned: lookup table. In principle, I pre-calculate the force acting on one particle by another particle at all distances (with a resolution of 1 pixel) up to 2000 pixels in any direction. The forces can then be determined without any calculation of the distance at run time. Although this is not an exact solution, the distortion is not perceived, and this allowed me to increase the number of simulation particles by a factor of three (until the moment when the number is now limited by the physical engine, and not by the n-body problem.)

Answer 1

• First, the force is symmetrical, so you only need a square n divided by two calculations.

• Secondly, the force drops with the square of the distance, so you can get closer to this by setting a threshold beyond which there is no need to calculate. You only need to check it in 1 dimension. As in the case where x - x 't and y - y' t are calculated, otherwise not.

• You can use two employment trees to put particles in small squares or buckets, and only square k divided by two distance calculations for pairs in each bucket in one tree. Another tree moves up and to the left to take care of any pairs at the borders of adjacent squares. For the second tree, just do not repeat the distance calculations you made in the first tree.

• Between updates, it is possible that some particles cannot change their position, so you do not need to calculate again the forces that are associated with two stationary particles after the last update.

• It can be assumed that the masses also contribute. Further optimization is that the mass is too small, then the threshold t, for which is not calculated, can also decrease.

• You can also quantize particle translations so that any movement below the minimum is not recorded as a change in coordinates.

Hope this helps!

Answer 2

To calculate the forces between all N particles accurately, you must determine the particle-particle distance O(N^2) . There is no way to do this better than O(N^2) , although you can achieve (1/2)N^2 by noting symmetry (i.e., dist(i,j) == dist(j,i) ).

To do almost the same thing, by deceiving, you can instead calculate only the “close” particle interactions (in any case, these are the largest quantities) and use spatial indexing structures.

One idea is to use quadtrees ( octtrees in 3d) so that you can efficiently identify a small set of particles M that are “close” to a specific particle. When calculating the forces of a particle, you consider only this reduced set. You will need to experiment with the threshold value used to determine if the set M is large enough - it is obvious that small sets will be very fast but inaccurate, large sets will be accurate but slow.

The spatial index also needs to be updated as particles move. One way to do this with quadrants is to set the upper and lower particle counts on a sheet and refine the tree when these restrictions are violated.

In general, based on fairly well-distributed sets of particles, the tree height will be O(log(N)) , and you should expect O(N*log(N)) performance from the tree method.

Answer 3

Since you mention that deception is okay, you can probably fake things by calculating the attraction between one particle and the center of mass of the whole group (including the particle itself). This would be an O (2N) problem (N for the center of mass, plus another N for each force particle tested). This may differ significantly from the actual laws of motion for certain particle devices, but it may be a reasonable approximation for most (random) initial arrangements.