For this assignment the different branches separate completely. For some of the options that means things start to get interesting.
Data Structures - For this assignment you will put your graph code on the back burner for a bit and instead work on a more advanced tree structure, an AVL tree.
We have talked about binary search trees in class and how they can allow us to have O(log n) operations for search, insert, and remove. We largely glossed over the fact that this only happens if the tree is well balanced and that a normal BST can become completely unbalanced so it is basically a linked list with the O(n) performance of that data structure. For this reason, most true binary tree data structures use balanced binary trees instead of just a plain BST. An AVL tree is an example of a balanced binary tree. Red-black trees are another form of balanced BSTs, but are a bit more complex.
The idea behind an AVL tree is that for every node in the tree, the height of the left child and the height of the right child can't differ by more than one. For our purposes here, the height of a node is the maximum number of vertices between it and a leaf below it including the leaf itself. This definition makes the height of an empty node be zero while the height of a leaf is one. To implement this efficiently, we add an extra int to all of our nodes and that int stores the height of the node.
The way an AVL tree works, is that every time you make a change, as the recursion comes back up, the code checks if things are still balanced. If they aren't it performs a "rotation" to get things back to balanced. Depending on where things were added, either single or double rotations are performed. If you want further references on AVL tree, just let me know.
As you might guess, the data for this will come from an XML file. You will have a root element called avltree that contains mutiple elements of type data. Each of those elements will have an attribute called key. The string value of key should be used as the key for your AVL tree. The full element will be the data.
read fileName - returns an AVL tree with all the elements inside the root element from the given XML file
add tree ElementNode - returns a new AVL tree with this node added using the key in it
search tree key - returns the ElementNode that matches the given key string
preorderPrint - prints the keys of the tree in a preorder traversal
inorderPrint - prints the keys of the tree in an inorder traversal
The functions should be placed in a structure named AVLTree. Remove is extra credit.
Text Game - For this assignment you will start to turn your graph into a game. The objective of the assignment is quite simple. You will put a text interface on this so that it loads in a graph, with room descriptions attached to the vertices, and allows the user to navigate through the rooms.
There is really only one function that you have to write, startGame(). Obviously you will write lots of others, but this is the only one I will explicitly call. This function will take no arguments (technically it takes one argument that is unit, but the call looks like it takes no arguments). It should load in your rooms and then print out the description of the starting room and wait for the user to input something. There are two commands that your game has to have. The obvious one is quit. When the user types in quit, the function should end. The other one is help. When the user types in help, you should provide the user with a description of how to play your game. For this assignment, that basically means you will tell me how to move around in your game.
You should maximize your use of the XML. Don't put long strings for stuff like help in your ML code. Instead, put that in the XML file and have it so that commands in the game print that out. You can use the XML format from assignment #8 as a foundation. You'll need to add to it descriptions for vertices at the very least. I recommend having the first element in a vertex be a <descritpion> element that contains a TextNode with the description. You can also allow a <help> element that contains the help description and goes either before or after the <vertex> elements. When you submit, remember to submit all of the .sml files that you are using and the .xml file that your map is in.
Physics - For this assignment you will write a basic "integrator" which solves for the evolution of a system of particles interacting under gravity. You won't be using the octree directly here. You will pull that back in to make a more advanced integrator in assignment #10. This basic integrator solves for the forces between every pair or particles
So let's discuss a bit how you write an N-body integrator for gravity. You will be using Newtonian gravity. So F=-G*m1*m2/(r^2) and of course, F=ma. You can combine these to get that a1=-G*m2/(r^2), m2 is the mass of the "other" body. To keep things simple, people generally scale the units of a system so that G=1. This saves a multiply and can give you nicer units as well. For example, with our solar system, if you make a unit of time be one year and a unit of length 1AU (the average distance of the Earth from the Sun), then make the unit of mass such that the mass of the Sun is 4*PI^2, then G=1. The mass factor is less than ideal, but dealing with things in AU and years is quite nice so lots of people do it.
Now in the actual code, you have a system that is particlle a bunch of particles, the particles are not just the points you had in assignment 8, but instead have a position, (x, y, z), a velocity, (vx, vy, vz), a mass, and a radius. The whole system will be a list of these particles. You advance the system by small steps where you calculate new velocities for each particle, then update the positions given the new velocities. This will be done in a process where you are given the original list of particles and you produce a new one where all the particles have been updated. Because you are doing this by components, the acceleration a particle feels from another mass is given by
ax=-x*m2/(r^3)
ay=-y*m2/(r^3)
az=-z*m2/(r^3)
assuming again that G=1. You don't really have to store these, because the velocity components are changed by (ax*dt, ay*dt, az*dt) for each intereaction, where dt is the timestep. The timestep needs to be on the order of 1/1000th of an orbital period and is part of the input file. The new position for a particle is given by (x+dt*vx, y+dt*vy, z+dt*vz). For each particle you will run through the list of all particles, and calculate the change in velocity each of the others induces. That gives you a new velocity, which you can use to generate a new position. If you ever find that two particles have collided (distance is less than sum of radii) then you should merge them together into a larger body with the common center of mass position and velocity and a new radius that keeps the density of the larger body.
The functions you need for this are fairly simple: read, write, writePlot, and advance. The read function reads an XML file that stores the initial positions, velocities, masses, and radii of the particles. It should return a tuple with a first element that is dt, and a second element that is a list of particles, which I refer to it as a "system" here. The write function takes a file name and a similar tuple and writes it out to file. The writePlot function takes a file name and a system and writes all the particle positions out in a simple text file where each line has an "x y z" format. This format is nice to read in for plotting the position of things in gnuplot. The advance function is the one that does the real work. It takes a system and a timestep (dt) and returns a new system that is the state after it has been advanced by the given timestep.
A sample XML file for a system similar to our solar system can be found here.
As a hint, do the check for collisions in one pass and then do the forcing in a second check.
Ray Tracing - In many ways, a ray tracer is very simple, that's part of why I have used it for assignments. The basic idea is that you throw out rays and see what they hit. Literally, that is the main function you use in a ray tracer. However, doing that requires a fair bit of vector math. For this assignment you will write the math libraries that your ray tracer needs.
Some of the functions that you will need are very basic, like dot product and cross product. These each take two vectors. The dot product returns a scalar and the cross product returns another vector. Another simple function I want you to write is normalize. This function takes a vector and returns a vector that points in the same direction, but has a length of one. You do this by calculating the length of the vector and dividing each component by that length.
You also need to write functions to see if a ray intersects with a triangle or a sphere. The math for these functions is described in this PDF file. The basic idea is that you describe the ray as a point moving from the beginning of the ray and going out. You can then solve for when this point crosses the bounds of the sphere or when it crosses through the plane defined by the sphere. I want you to create a geometry datatype that can be either a Sphere or a Triangle and write an intersect method that takes a geometry and a ray and returns the parameter value for when they intersect. You will also write a function, rayPoint, that takes a ray and a parameter and returns the point on the ray that corresponds to. Lastly, you should write a method getNormal, that takes a geometry and a point and returns the normal vector of the geometry at that point.
dotProduct vect1 vect2 - returns the scalar product (x1*x2+y1*y2+z1*z2)
crossProduct vect1 vect2 - returns the vector product (y1*z2-z1*y2,z1*x2-x1*z2,x1*y2-y1*x2)
normalize vect - returns a vector with the same direction, but of length 1.0
intersectValue ray geomObj - returns the parameter for when the ray intersects the object (might be a triangle or a sphere). If they don't intersect it should return a negative value.
rayPoint ray value - returns the position on the ray given by that value.
getNormal geomObj point - assumes the point is on the object and returns a proper unit length normal vector.
To get the spheres and triangles into your program you will read an XML file with the geometry. The root element of the file will have the name geometry. Inside of it will be elements of type triangle and sphere that have attributes specifying all the information on them. Here is a short sample XML file.
XPath Processor - This is the next option in the advanced XML. XPath is an XML based technology for specifying locations in XML files. It is used significantly for XSLT which is the last assignment.
The official recommendation for XPath can be found here. Since you will be integrating this into an XSLT processor you might want to read this page describing XSLT. It also mentions XPath some. If you are going to attempt this option you must read these or some other references on XPath and XSLT.
Your implementation of XPath should be fairly fully functional except where URLs are concerned. You only have to be able to pull things from local files. What I want from you two functions called resolve and resolveIn that goes into the XML structure. The resolve function takes an absolute path that might refer to a local file and returns the information it refers to. The resolveIn method takes a relative XPath string and a loaded document and returns the information it refers to.