Programming Assignment Checklist: Barnes-Hut


Frequently Asked Questions

How do I tell if a tree node is internal or external? Check if all four children are null. Consider writing a helper method isExternal() to check this.

How do I calculate center-of-mass of a body with an aggregate body? Just treat the aggregate body like any other body - the center of mass formula works even if one body is already the center of mass of several other bodies.

What should the velocity and color of a center-of-mass object be? One reasonable approach would be to set the velocity equal to the velocity of the center-of-mass. However, since you will never use this quantity, it's fine to set the velocity to 0. If you set the color to null or StdDraw.RED you can identify any (inadvertent) attempts to draw such an object.

None of the particles appear on the screen. What could I be doing wrong? Make sure that your particles are not being drawn in the same color as your background. Check that your client program calls StdDraw.setXscale() and StdDraw.setYscale() in a similar manner as Make sure that your NW(), NE(), SW(), and SE() methods are setting up the proper subquadrants. It could also be that a bug in your program introduces infinite forces, and your particle (x, y) coordinates leave the universe.

When computing the net force acting on body b, do I need a special case to prevent calculating the force between b and an aggregate body that happens to contain b? No, but excellent question. If an aggregate body representing a quad of size s contains b, then the distance d from b to the center of mass will be at most sqrt(2) × s. But in this case θ = s / d > 1/2, so the algorithm would need to expand the aggregate body anyway.

Does Quad need to pass all of the tests in QuadTester? No, but it will help you identify how your program handles border cases.

Does a point on the border of the universe need to be considered inside the universe? No, that's up to you. You can think of the universe as being an open or closed region (or open on one side and closed on the other).

What value of dt should I use? Please use 0.1 for the file that you turn in. When testing some of the bigger data files, use a bigger value (e.g., 1.0) or be prepared to wait for a while to see movement.

Who discovered the first efficient algorithm for N-Body simulation? Andrew Appel discovered the first N log N algorithm while at Princeton University working on his senior thesis in the Department of Physics. He's now a professor of computer science at Princeton.

When was the Barnes-Hut algorithm discovered? It was developed in 1986 by two astrophysicists at Princeton's Institute for Advanced Study.

Can the Barnes-Hut algorithm be extended to three dimensions? Yes. You can use an oct-tree instead of a quad-tree, although there are more wasted links. Another spatial partitioning data structure called a k-d tree is also useful for two and higher dimensional problems.

Is the Barnes-Hut algorithm less accurate than the direct sum approach taken in Assignment 2? Yes, although it is still the method of choice in many scientific applications. There are some applications (e.g., tracking the orbit of the solar system over billions of years) that require very accurate calculations, and in these cases, Barnes-Hut is inappropriate.

Should I worry about collisions? No. The softening parameter keeps the forces from getting unreasonably large upon a close encounter. (This parameter has already been included in the addForce() method in the Body class.)

Input, Output, and Testing

Input. Copy the files from the directory barnes-hut into your working directory. The file test2.txt is the 5 node example from the assignment. Please note that none of the test[1-5].txt files are intended to be animated. They are simple data sets to test your Quad and BHTree methods. The files results[1-5].txt contain string representations of the universe and of the BHTree after one iteration. Note that the order of your points on the tree may vary from ours, depending upon how you dealt with border points (points exactly on a quadrant boundary line).

Compilation and execution.  The main() function must be in the file We will compile your program with:

and execute with
java NBody < input.txt
We will also be compiling your BHTree, Body, and Quad files with our own version of NBody that prints out the string representation of the universe Quad and the BHTree, so make sure you include the toString() methods for both of these classes. This also means that the following methods must agree with the ones described in the assignment or existing in the template files.

For Body

public boolean in(Quad q) public void resetForce() public void update(double dt) public void draw()

For BHTree

public void insert(Body b) public void updateForce(Body b) public String toString()


readme.txt. Use the following readme file template and answer any questions.

Submission.  Submit and all of the files needed to run your program. Don't forget to hit the "Run Script" button on the submission system to test that it compiles cleanly.

Possible Progress Steps

These are purely suggestions for how you might make progress. You do not have to follow these steps.

  1. Download the directory barnes-hut to your system. It contains sample data files and the brute force implementation.

  2. Create the data type for representing quadrants. Use as a template. After you have filled in the constructor and methods for, use to test it. QuadTester creates a 20-by-20 square universe quadrant and its NW, NE, SW, and SE quadrants. It prints out representations of each of these quadrants. To test the draw() method, QuadTester further subdivides the NW quadrant, and draws each quadrant and sub-quadrant. It then tests the contains method using interior and border points. Be sure that if a quadrant q contains (x, y), then exactly one of the following quadrants also contains (x, y): q.NW(), q.NE(), q.SW(), and q.SE(). Do not even think about continuing until your Quad data type is thoroughly tested and debugged.

  3. Body data type. Make sure that you understand the Body data type provided - we'll talk about this in precept. Write the two methods in and plus. The second method returns a new object so you must use the keyword new to create it. Test and debug your code before continuing.

  4. insert(Body b). Carefully follow the recursive strategy outlined in the assignment. This is the trickiest part of the program, although it should only be around 20 lines of code. To represent a null branch coming from an internal node, we suggest creating a BHTree object whose body field is set to null. This way, you can recursively call the BHTree methods on this external node without getting a null pointer exception. This will also simplify the methods insert() and updateForce().

  5. Testing. To confirm that the tree is being constructed correctly, write a method draw() for BHTree that does a preorder traversal of the Barnes-Hut tree and plots each of the quads whose children are all null. (If the children are all null, then either there is an external point in that quad, or there is an external point in at least one of its sister quads.) Use this method after inserting points into the initial tree. For test1.txt and test2.txt, these pictures should match the drawings of the two examples in the assignment instructions.

    Also write a method to print out the contents of the tree in preorder notation (i.e., print its root, then recursively print all its subtrees). To do this, write a toString() method in Mark internal nodes with an asterisk. If you implement null branches as suggested above, this code would look something like this:

    public String toString() {
        if (isExternal()) return " " + body + "\n";
        else              return "*" + body + "\n" + NW + NE + SW + SE;
    For testing, print out the initial tree and see if bodies are where you expect. After you write your updateForce() method, you can modify your so that it prints out the results after the first iteration of the simulation. Using test[1-5].txt as input, compare results[1-5].txt with your output. Remember - these test files are not intended to be animated.

  6. updateForce(b). Think of this method as a kind of preorder traversal of the tree. When you hit an external node during the traversal, calculate the pairwise force between it and b, and update the net force acting on b. When you hit an internal node, calculate the ratio s/d. Depending on the ratio either (i) recursively invoke updateForce() on its children or (ii) calculate the force between the aggregate body stored in the internal node and b, and update the net force acting on b.


Kevin Wayne