Programming Assignment Checklist: N-Body Simulation

Goals

Frequently Asked Questions (Operating System and Configuration)

I used the auto-installer, but when I compile in Terminal/Command Prompt, the Java compiler reports that it cannot resolve symbol StdDraw. Why is this? Be sure to use the commands javac-introcs and java-introcs (instead of javac and java); these wrapper commands tell Java where to find our standard libraries. If you are using the wrapper commands, try re-rerunning the autoinstaller; this should fix situations where you moved files that the auto-installer added. Otherwise, check with a lab TA.

I used the auto-installer. I can compile my program in DrJava, but when I try to run it in Terminal/Command Prompt using java-introcs, it complains. A common reason is that DrJava is using one version of Java and your Terminal/Command Prompt is using a different version. See a lab TA. In the meantime, try compiling and executing in Terminal/Command Prompt (instead of compiling in DrJava and executing in Terminal/Command Prompt).

I did not use the auto-installer. How do I access stdlib.jar? We highly recommend using the auto-installer. If you are unable to use the auto-installer, here are a few alternatives.

I am using an OIT cluster machine. How can I access stdlib.jar? It may work automatically. If not, here are a few alternatives. The simplest is to copy StdIn.java, StdOut.java, StdAudio.java and StdDraw.java into the same folder as NBody.java (but you'll have to do this for each assignment). The lab TAs can help you with this.

DrJava doesn't let me redirect standard input. What should I do instead? Sorry, DrJava does not support redirection or piping; use the Terminal/Command Prompt.

What is the best way to download the helper files associated with this assignment? See the programming assignment FAQ.

Frequently Asked Questions (Programming)

What preparation do I need before beginning this assignment? Read Sections 1.4 and 1.5 of the textbook. Also, you should familiarize yourslef with the command line.

Any advice on completing this programming assignment? This program is more involved than the previous ones, so you should budget more time accordingly. The best advice we can give you is to carefully test, debug, and re-test your code as you write it. Do not attempt to write the whole program at once—if you do, then you will have no idea where to find the errors when the program doesn't work. Proactive testing will save you enormous amounts of time in the long run. Trust us!

Do I have to follow the assignment specifications for reading input from command-line arguments and standard input, and writing output to standard drawing and standard output? Yes, or you will lose a substantial number of points.

Checkstyle complains about the variable I named T because it begins with an uppercase letter. Which name should I use instead? By convention, a variable in Java should begin with a lowercase letter and use camel case, such as isLeapYear. A constant variable (a variable whose value does not change during the execution of a program, or from one execution of the program to the next) should begin with an uppercase letter and use underscores to separate any word boundaries, such as GRAVITATIONAL_CONSTANT. So, a Java variable name might not always perfect align with the corresponding domain-specific mathematical notation. In this case, tao or stoppingTime would be fine choices.

Where can I find the APIs for StdIn, StdOut, StdDraw, and StdAudio? They are on pp. 1140–1141 of the textbook. They also appear in this Java cheatsheet.

Why do I get an InputMismatchException or a NoSuchElementException when I try to read data using StdIn?

How do I draw an image to standard drawing? The command StdDraw.picture(x, y, filename) reads the image (either JPEG, GIF, or PNG format) from the specified file and draws it to standard drawing, centered at (x, y).

My computer doesn't display the animation smoothly. Is there anything I can do? Be sure to follow the template in BouncingBall.java. In particular, call StdDraw.enableDoubleBuffering() once at the beginning of your program; and call StdDraw.show() and StdDraw.pause(20) at the end of each time step (frame), not after each call to StdDraw.picture().

Can I combine Steps 1, 2, and 3 for each body? No, as indicated in the assignment, you must separate Step 1 (compute all of the forces) from Step 2 (update the positions); otherwise, you will be computing the forces at time t using the positions of some of bodies at time t and others at time t + Δt.

My animation looks fine, but the numbers are off a little bit when I follow the tests below, what could be causing this? Read the question just above — this is the most common cause. Double-check that you followed the assignment instructions exactly in the order of how positions and velocities are updated.

I draw the bodies, but they do not appear on the screen. Why? Did you use StdDraw.setXscale() and StdDraw.setYscale() to change the x- and y-coordinate systems to use the physics coordinates instead of the unit box? Since you want it centered on the origin with a "square radius" of radius, the minimum of each axis should be –radius and the maximum should be +radius.

My bodies repel each other. Why don't they attract each other? Make sure that you get the sign right when you apply Newton's law of gravitation: (x[j] - x[i]) vs. (x[i] - x[j]). Note that Δx and Δy can be positive or negative so do not use Math.abs(). Do not consider changing the universal gravitational constant G to patch your code!

What is Δx? It's the change in x-coordinate between two bodies (not between a body at time t and at time t + Δt).

How many steps should my program simulate if Τ is not a multiple of Δt? Simulate the universe as long as t < Τ. For example, if Τ is 50,000 and Δt is 25,000, you should simulate the system for two steps (t = 0 and 25,000). If Τ is 60,000 and Δt is 25,000, you should simulate the system for three steps (t = 0, 25,000 and 50,000).

Does my program need to plot anything if T equals 0? No.

Testing and Debugging

Inserting print statements is a good way to trace what your program is doing. Our input files were created with the following StdOut.printf() statements. 

StdOut.printf("%d\n", n);
StdOut.printf("%.2e\n", radius);
for (int i = 0; i < n; i++) {
    StdOut.printf("%11.4e %11.4e %11.4e %11.4e %11.4e %12s\n",
                   px[i], py[i], vx[i], vy[i], mass[i], image[i]);
}

As indicated in the collaboration policy, you may not copy or adapt code (except from the course materials). Moreover, you need to cite any code that you copy or adapt (except for code provided with the assignment). So, you are free to copy or adapt this code, with or without citation.

Here are our results for a few sample inputs. 

% java-introcs NBody 0.0 25000.0 < planets.txt           // zero steps
5
2.50e+11
 1.4960e+11  0.0000e+00  0.0000e+00  2.9800e+04  5.9740e+24    earth.gif
 2.2790e+11  0.0000e+00  0.0000e+00  2.4100e+04  6.4190e+23     mars.gif
 5.7900e+10  0.0000e+00  0.0000e+00  4.7900e+04  3.3020e+23  mercury.gif
 0.0000e+00  0.0000e+00  0.0000e+00  0.0000e+00  1.9890e+30      sun.gif
 1.0820e+11  0.0000e+00  0.0000e+00  3.5000e+04  4.8690e+24    venus.gif

% java-introcs NBody 25000.0 25000.0 < planets.txt       // one step
5
2.50e+11
 1.4960e+11  7.4500e+08 -1.4820e+02  2.9800e+04  5.9740e+24    earth.gif
 2.2790e+11  6.0250e+08 -6.3860e+01  2.4100e+04  6.4190e+23     mars.gif
 5.7875e+10  1.1975e+09 -9.8933e+02  4.7900e+04  3.3020e+23  mercury.gif
 3.3087e+01  0.0000e+00  1.3235e-03  0.0000e+00  1.9890e+30      sun.gif
 1.0819e+11  8.7500e+08 -2.8329e+02  3.5000e+04  4.8690e+24    venus.gif

% java-introcs NBody 50000.0 25000.0 < planets.txt       // two steps
5
2.50e+11
 1.4959e+11  1.4900e+09 -2.9640e+02  2.9799e+04  5.9740e+24    earth.gif
 2.2790e+11  1.2050e+09 -1.2772e+02  2.4100e+04  6.4190e+23     mars.gif
 5.7826e+10  2.3945e+09 -1.9789e+03  4.7880e+04  3.3020e+23  mercury.gif
 9.9262e+01  2.8198e-01  2.6470e-03  1.1279e-05  1.9890e+30      sun.gif
 1.0818e+11  1.7499e+09 -5.6660e+02  3.4998e+04  4.8690e+24    venus.gif

% java-introcs NBody 60000.0 25000.0 < planets.txt       // three steps
5
2.50e+11
 1.4958e+11  2.2349e+09 -4.4460e+02  2.9798e+04  5.9740e+24    earth.gif
 2.2789e+11  1.8075e+09 -1.9158e+02  2.4099e+04  6.4190e+23     mars.gif
 5.7752e+10  3.5905e+09 -2.9682e+03  4.7839e+04  3.3020e+23  mercury.gif
 1.9852e+02  1.1280e+00  3.9705e-03  3.3841e-05  1.9890e+30      sun.gif
 1.0816e+11  2.6248e+09 -8.4989e+02  3.4993e+04  4.8690e+24    venus.gif


% java-introcs NBody 31557600.0 25000.0 < planets.txt    // one year
5
2.50e+11
 1.4959e+11 -1.6531e+09  3.2949e+02  2.9798e+04  5.9740e+24    earth.gif
-2.2153e+11 -4.9263e+10  5.1805e+03 -2.3640e+04  6.4190e+23     mars.gif
 3.4771e+10  4.5752e+10 -3.8269e+04  2.9415e+04  3.3020e+23  mercury.gif
 5.9426e+05  6.2357e+06 -5.8569e-02  1.6285e-01  1.9890e+30      sun.gif
-7.3731e+10 -7.9391e+10  2.5433e+04 -2.3973e+04  4.8690e+24    venus.gif

// this test should take only a few seconds. 4.294E9 is bigger than the largest int
% java-introcs NBody 4.294E9 2.147E9 < 3body.txt       
3
1.25e+11
 2.1470e+12 -7.8082e-03  5.0000e+02 -3.6368e-12  5.9740e+24    earth.gif
 1.2882e+14 -1.5100e+17  3.0000e+04 -3.5165e+07  1.9890e+30      sun.gif
-1.2882e+14  1.5100e+17 -3.0000e+04  3.5165e+07  1.9890e+30      sun.gif

Possible Progress Steps

These are purely suggestions for how you might make progress. You do not have to follow these steps. If you get stumped or frustrated on some portion of the assignment, you should not hesitate to consult a preceptor.

Enrichment

I'm a physicist. Why should I use the leapfrog method instead of the formula I derived in high school? In other words, why does the position update formula use the velocity at the updated time step rather than the previous one? Why not use the 1/2 a t^2 formula? The leapfrog method is more stable for integrating Hamiltonian systems than conventional numerical methods like Euler's method or Runge–Kutta. The leapfrog method is symplectic, which means it preserves properties specific to Hamiltonian systems (conservation of linear and angular momentum, time-reversibility, and conservation of energy of the discrete Hamiltonian). In contrast, ordinary numerical methods become dissipative and exhibit qualitatively different long-term behavior. For example, the earth would slowly spiral into (or away from) the sun. For these reasons, symplectic methods are extremely popular for n-body calculations in practice. You asked!

Here's a more complete explanation of how you should interpret the variables. The classic Euler method updates the position uses the velocity at time t instead of using the updated velocity at time t + Δt. A better idea is to use the velocity at the midpoint t + Δt / 2. The leapfrog method does this in a clever way. It maintains the position and velocity one-half time step out of phase: At the beginning of an iteration, (px, py) represents the position at time t and (vx, vy) represents the velocity at time t − Δt / 2. Interpreting the position and velocity in this way, the updated position (px + Δt vx, py + Δt vy). uses the velocity at time t + Δt / 2. Almost magically, the only special care needed to deal with the half time-steps is to initialize the system's velocity at time t = −Δt / 2 (instead of t = 0.0), and you can assume that we have already done this for you. Note also that the acceleration is computed at time t so that when we update the velocity, we are using the acceleration at the midpoint of the interval under consideration.

Are there analytic solutions known for n-body systems? Yes, Sundman and Wang developed global analytical solutions using convergent power series. However, the series converge so slowly that they are not useful in practice. See The Solution of the N-body Problem for a brief history of the problem.

Who uses n-body simulation? N-body simulations play a crucial role in our understanding of the universe. Astrophysicists use it to study stellar dynamics at the galactic center, stellar dynamics in a globular cluster, colliding galaxies, and the formation of the structure of the Universe. The strongest evidence we have for the belief that there is a black hole in the center of the Milky Way comes from very accurate n-body simulations. Many of the problems that astrophysicists want to solve have millions or billions of particles. More sophisticated computational techniques are needed.

The same methods are also widely used in molecular dynamics, except that the heavenly bodies are replaced by atoms, gravity is replaced by some other force, and the leapfrog method is called Verlet's method. With van der Waals forces, the interaction energy may decay as 1/R6 instead of an inverse square law. Occasionally, 3-way interactions must be taken into account, e.g., to account for the covalent bonds in diamond crystals.

Kepler's Orrery uses an n-body simulator to compose and play music.

What techniques are used to do n-body simulation in practice? Here's a wealth of information on n-body simulation.

Any ideas for creating my own universe? Here are some interesting two-body systems. Here is beautiful 21-body system in a figure-8 —reproducing this system (in a data file in our format) will earn you a small amount extra credit.