COS 126

N-Body Simulation
Programming Assignment

Checklist

Assignment Overview. In 1687, Isaac Newton formulated the principles governing the motion of two particles under the influence of their mutual gravitational attraction in his famous Principia. However, Newton was unable to solve the problem for three particles. Indeed, in general, solutions to systems of three or more particles must be approximated via numerical simulations.

Your challenge is to write a program to simulate the motion of n particles in the plane, mutually affected by gravitational forces, and animate the results. Such methods are widely used in cosmology, semiconductors, and fluid dynamics to study complex physical systems. Scientists also apply the same techniques to other pairwise interactions including Coulombic, Biot–Savart, and van der Waals.

Program specification. Write a program NBody.java that:

Input format. The input format is a text file that contains the information for a particular universe (in SI units). The first value is an integer n which represents the number of particles. The second value is a real number radius which represents the radius of the universe; it is used to determine the scaling of the drawing window (which displays particles with x- and y-coordinates between −radius and +radius). Next, there are n lines (one for each particle), with each line containing 6 values. The first two values are the x- and y-coordinates of the initial position; the next pair of values are the x- and y-components of the initial velocity; the fifth value is the mass; the last value is a String that is the name of an image file used to display the particle. The remainder of the file (optionally) contains a description of the universe, which your program must ignore. As an example, planets.txt contains real data from part of our Solar System.

Input Format

Simulating the universe: the physics. We review the equations governing the motion of the particles, according to Newton's laws of motion and gravitation. Don't worry if your physics is a bit rusty; all of the necessary formulas are included below. We'll assume for now that the position (px, py) and velocity (vx, vy) of each particle is known. In order to model the dynamics of the system, we must know the net force exerted on each particle.

Simulating the universe: the numerics.  We use the leapfrog finite difference approximation scheme to numerically integrate the above equations: this is the basis for most astrophysical simulations of gravitational systems. In the leapfrog scheme, we discretize time, and update the time variable t in increments of the time quantum Δt (measured in seconds). We maintain the position (px, py) and velocity (vx, vy) of each particle at each time step. The steps below illustrate how to evolve the positions and velocities of the particles.

Do not interleave steps A and B; otherwise, you will be computing the forces at time t using the positions of some of the particles at time t and others at time t + Δt. The simulation is more accurate when Δt is very small, but this comes at the price of more computation.

Creating an animation. Draw each particle at its current position to standard drawing, and repeat this process at each time step until the designated stopping time. By displaying this sequence of snapshots (or frames) in rapid succession, you will create the illusion of movement. After each time step, draw the background image starfield.jpg; redraw all the particles in their new positions; and control the animation speed (about 40 frames per second looks good). You will call several methods from the StdDraw library.

Optional finishing touch. For a finishing touch, play the theme to 2001: A Space Odyssey using the StdAudio library and the audio file 2001.wav. It's a one-liner using the method StdAudio.play().

Compiling and executing your program. If you used our autoinstaller, you will use the commands java-introcs and javac-introcs (instead of java and javac) to compile and execute your programs. These versions provide access to the standard libraries.

To compile your program from the command line, type the following in your terminal application (Command Prompt or Terminal):

% javac-introcs NBody.java

To execute your program from the command line, redirecting from the file planets.txt to standard input, type:

% java-introcs NBody 157788000.0 25000.0 < planets.txt

Your browser can not display this movie.
Be sure that Javascript is enabled and that you have Flash 9.0.124 or better.

After the animation stops, your program must output the final state of the universe in the same format as the input, e.g.:
5
2.50e11
 1.4925e+11 -1.0467e+10  2.0872e+03  2.9723e+04  5.9740e+24    earth.gif
-1.1055e+11 -1.9868e+11  2.1060e+04 -1.1827e+04  6.4190e+23     mars.gif
-1.1708e+10 -5.7384e+10  4.6276e+04 -9.9541e+03  3.3020e+23  mercury.gif
 2.1709e+05  3.0029e+07  4.5087e-02  5.1823e-02  1.9890e+30      sun.gif
 6.9283e+10  8.2658e+10 -2.6894e+04  2.2585e+04  4.8690e+24    venus.gif


Getting started. Before you begin coding, do the following:

Submission. Submit NBody.java and a completed readme.txt file.

Challenge for the bored. There are limitless opportunities for additional excitement and discovery here. Create an alternate universe (using the same input format). Try adding other features, such as supporting elastic or inelastic collisions. Or, make the simulation three-dimensional by doing calculations for x-, y-, and z-coordinates, then using the z-coordinate to vary the sizes of the planets. Add a rocket ship that launches from one planet and has to land on another. Allow the rocket ship to exert force with the consumption of fuel.

Copyright © 1999–2010, Robert Sedgewick and Kevin Wayne.