Simulating galaxies, sounds complicated? It is, but let's try understanding how it works!

So, let's suppose that you've got an awful lot of bodies (or a galaxy) and want to calculate the forces acting inbetween all of them (using Newton's law of univeral gravitation).

All in all, you need to calculate the forces between two objects about \( n \cdot n-1 \) times. We can express this using the Big O notation as \(O(n) = n^2\). So for an input amount of \(n\) stars, we need \(n^2\) calculations to calculate the forces acting inbetween all the stars.

Generally Speaking, \(O(n^2)\) is bad. We want to achieve something much faster. But how?

The method I used (and am recommending to you right now) is the Barnes-Hut Simulation. So what is that? Well, the two great people Josh Barnes and Piet Hut one day thought about not calculating the forces acting inbetween all the stars, but only between the stars that are in direct proximity to the original star. You might (and should) ask yourself how this works: subdividing.

By subdividing the galaxy into multiple subcells, we can construct a tree containing a subsection of the original galaxy. Calculating the force between a star and another star can be abstracted by calculating the force between our star and the cell the other star is inside.

Barnes and Hut formulated a rule deciding what cell should be used (or not). This rule can be written in the following way:

$$ \theta = \frac{s}{d} $$

Well that looks simple, doesn't it? It actually is really simple but insanely genius: \(\theta\) is some kind of threshold we can set, let's just say that it is set to \(0.5\). \(s\) is the distance to the midpoint of the region of star \(B\) and \(d\) is the width of the cell \(B\) is in.

So if the distance inbetween \(A\) and \(B\) is really big, and the cell in which \(B\) is inside of is really small, the complete fraction gets really small. Using this knowledge, we can manipulate \(\theta\) in the following way: if we set \(\theta\) to a really small value, the distance inbetween the stars must be really big until we begin to group stars. On the other hand, if we set \(\theta\) to a really big value, we alsmost directly start to group the stars.

By implementing this, we can acchieve an O-notation of \(O(n \cdot \log(n))\)... ... alot better than \(O(n^2)\)!