|
|
|
|
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 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 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. 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:
and execute withjavac NBody.java
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.java NBody < input.txt
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 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.
|
|
These are purely suggestions for how you might make progress. You do not have to follow these steps.
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().
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.
|
|