Programming Assignment Checklist: Barnes-Hut

Goals

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.

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. Don't forget to call StdDraw.pause. Check that your client program NBody.java calls StdDraw.setScale in a similar manner as NBodyBrute.java. 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 my Quad need to pass all of the tests in QuadTester? No this is not a requirement, but it will help you identify how your program handles border cases.

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.

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.

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

javac NBody.java
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. (If you want to modify one of these methods, remember that in java it is OK to have more than one method with the same name as long as they have different arguments.)

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)

Submission

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

Submission.  Submit NBody.java 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 Quad.java as a template. After you have filled in the constructor and methods for Quad.java, use QuadTester.java 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 15 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 that does a preorder traversal of the Barnes-Hut tree and plots each of the quads. 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 BHTree.java. 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, modify your NBody.java so that it prints out the results after the first iteration of the simulation.

  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.

Enrichment


Kevin Wayne