Skip to main content

A simple implementation of the Barnes-Hut algorithm for N-body simulations in python 3.7

Project description

The N-Body Problem

what is it
    Newton tried to use analytical geometry to predict the planets' motions from its orbital properties (position, orbital diameter, period and orbital velocity) and failed
    realised that there is a gravitational interaction between the planets that is affecting their orbits
    In the solar system, every planet is gravitationally affected by all the other planets to some degree.
    This is also true for other bodies inside and outside the solar system
    it is easy to calculate the gravitationally interactive forces between two bodies using newtonian physics
    as soon as there are more than two bodies involved, things get harder to predict
    This technique is pretty close to reality -- the moon landings used newtonian mechanics to calculate their orbits -- but it has to be said that einstein showed that there are small micro-interactions between bodies that newtonian physics cannot predict

why is it hard
    This is because every body's gravity influences all the other bodies orbital parameters, which in turn influence all OTHER bodies
    for n bodies, there are n^2 interactions to calculate
    you have to take all bodies into account, or your result will be very imprecise
    You can use this to find bodies you don't know about: Plug all bodies you know about into the equations, calculate, and if the result differs from reality, Boom, you know where to look for your new dark moon

approximation using Barnes-Hut
    organise all bodies into an octo-tree (or quad-tree for 2d), ordered by their distance from each other
    each Body is a leaf on the end of the tree, and saves its mass, plus its orbital parameters
    save the combined mass of the attached bodies for each node
    for far away bodies, do not calculate every body's mass and gravitational interaction individually -- instead, with increasing distance, retreat further and further up the tree and use the mass information in the upper nodes
    it can be proven that due to the inverse square root relation of gravity to mass over distance, this only gives us very small errors as opposed to calculating every individual body
    However, the complexity sinks from O(n^2) to O(n log n)

Reference Code (java)


J. Barnes & P. Hut (December 1986). "A hierarchical O(N log N) force-calculation algorithm". Nature. 324 (4): 446–449. Bibcode:1986Natur.324..446B. doi:10.1038/324446a0.


Project details

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for CrudeBHT, version 1.0.7
Filename, size File type Python version Upload date Hashes
Filename, size CrudeBHT-1.0.7-py3-none-any.whl (17.5 kB) File type Wheel Python version py3 Upload date Hashes View
Filename, size CrudeBHT-1.0.7.tar.gz (7.6 kB) File type Source Python version None Upload date Hashes View

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page