THE N-BODY PROBLEM (DX11)
UNIVERSITY PROJECT
In physics there exists the "n-body problem". Gravity is a constant force attracting every single body in the universe towards every other single body in the universe. For large amounts of bodies (large values of n), the calculations become very computationally expensive - so how do we calculate the effects of gravity accurately, but also quickly? My dissertation aims to discuss this. I explore two numerical methods, and two "approximation algorithms". One if which I discuss in-depth here.
NUMERICAL METHODS IMPLEMENTED
​
SEMI-IMPLICIT EULER METHOD
One of the most simple ways to represent the movement of a body in a video game, is to use the semi-implicit Euler method. This method updates velocity and position each frame. To calculate the velocity of an object, we update it each frame using the acceleration.
​
4th ORDER RUNGE-KUTTA
A slightly more complex, but accurate way to calculate the forces of gravity, is the 4th order Runge-Kutta method. This method uses 4 iterations for both velocity and position to represent the body. This algorithm is better suited for smaller scale simulations, where a higher degree accuracy is desired. This algorithm was used as the benchmark for accuracy, and was compared with the Euler method to determine the semi-implicit Euler method's accuracy.
​
Both these algorithms are very computationally expensive and time consuming, running with an order of operation of at least O(N^2).
​
​
APPROXIMATION ALGORITHMS IMPLEMENTED
​
BARNES-HUT ALGORITHM
A type of tree-code, this algorithm is a great way to solve large scale n-body problems. This algorithm uses a dynamic octree, and approximates the force of particles that are far away from each other. This simple, powerful algorithm brings the order of operation of the algorithm all the way down to O(N*log(N)).
​
FAST MULTIPOLE METHOD
A much more complex and powerful algorithm. An in-depth discussion of my implementation can be found here. A simple summary: this algorithm breaks the simulation space down into equal sized cell's using a static octree. For each layer of the octree the algorithm approximates the force of far away cells, and on the bottom level the far away cells are approximated but neighbouring cells are not. This algorithm has increased accuracy due to the implementation of a second order Taylor expansion used to create the multipoles of each cell. This multipole is a very accurate representation of a cell's centre of mass. This algorithm has large overhead but great speed and accuracy for huge values of N. This algorithm has an order of operation of O(N).
​
​
OTHER FEATURES
​
TESTING TOOLS
Tools were created so users can choose which algorithm they want to test, how many bodies the simulation will start with, how many it will end with, and the increment of bodies each frame. Then each frame, the calculation time, the accuracy error, and the calculation count will be recorded.
​
PRESETS
Choose some pre set scenarios to look at: There's a demonstration of a regular stable orbit, a body in an elliptical orbit around another body, a pair of equal mass bodies orbiting each other, and more!
​
ALGORITHM DEMONSTRATION
If you don't want to do any testing there is an option to just view the different algorithms in action. Set how many bodies you want, and these bodies will be spread out in a disc around a galactic centre, and given sufficient velocity to orbit the centre.
​