### Programming Assignment Checklist: Barnes-Hut

 Goals

• Learn about quadtrees. This data structure is also widely used in computer graphics games.

• Apply many topics from the semester (loops, arrays, graphics, recursion, linked structures, object oriented programming, and analysis of algorithms) to solve a significant problem in scientific computing.

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 NBody.java calls StdDraw.setXscale() and StdDraw.setYscale() 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 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 NBody.java 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 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.

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()
```

 Submission

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.

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 `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, print out the initial tree and see if bodies are where you expect. After you write your updateForce() method, you can modify your NBody.java 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.

 Enrichment

• Here's some information about our solar system.

• Here's a wealth of information on N-body simulation.

• Here's some of the N-body physics.

• To avoid excessive accelerations, astrophysicists often use a softened potential which adds an ε2 term to the denominator of Gm1m2 / r2. This prevents binary stars from forming with r < ε.

• In real N-body simulations particles move at different timescales, so it is desirable computationally to simulate particles on different timescales. Nearby particles might need to be simulated more accurately, so a short timescale may be required, whereas points that are far away can be updated less frequently to save computation.

Kevin Wayne