CS4
Project: Lunar Lander


UPDATE: Download this new, improved version of SimplexSearch.java and use it to replace the version that came with the project.

Overview

Welcome to your final project. You and your partner have been hired to build a flight simulator for the next lunar landing. (Please make sure you have a partner; don't do the project alone.)

You have four weeks to complete a very large program that will simulate landing on the moon, but in the context of a computer game. The coin-op video game Lunar Lander was one of the hits of 1979. We have broken it up into four weekly checkoffs. It is crucial that you do not fall behind—please visit us if you need help. The project is worth 10% (40/400 points) of your final grade.

Calendar

Here is how the rest of the semester looks. There is a project-related due date every Thursday lab.

Monday Tuesday Wednesday Thursday
Week 11
2006-04-03 – 2006-04-07
Lecture & lab
Lecture
Final project is released.
Week 12
2006-04-10 – 2006-04-14
Lecture & lab
Lecture
Checkoff 1 due & verified in lab.
Week 13
2006-04-17 – 2004-04-21
Lecture & lab
Lecture
Checkoff 2 due & verified in lab.
Week 14
2006-04-24 – 2006-04-28
Lecture & lab
Lecture
Checkoff 3 due & verified in lab.
Week 15
2006-05-01 – 2006-05-05
Lecture & lab
Lecture
Lab
Week 16
2006-05-08 – 2006-05-12
Lecture & lab
FINAL PROJECT DUE

Checkoff 1: Put in the 1D physics

A rocket accelerates by expelling fuel at high velocities. By the law of conservation of momentum, the downward thrust of the fuel must be matched by an equal increase in the upward momentum of the rocket. However, because the rocket expels fuel, the lunar lander is always getting lighter, until the fuel runs out. You will encode the relevant equations of motion (including how forces, masses, positions, velocities and accelerations affect each other) so that the lander simulation behaves correctly.

However, to simplify the problem, for this checkoff (which you must demonstrate to the staff by Thursday, April 13) you will only need to solve a 1D problem. The lander is oriented directly above a landing pad. All you have to do is encode the 1D equations of up-and-down motion for gravity, thrust, etc. Once you've done this, you can play the game (the up and down arrows control the thrust) and try to get the best score by landing as softly as possible with as much leftover fuel as possible. Your score is based on a complicated formula involving both of these numbers; see the Scoring section below. If the lunar lander hits the ground with a velocity of greater than 4 m/s, it will crash.

Technical details

Download the Lunar Lander project file here and import it into Eclipse as usual. You will see several classes that contain over 3,000 lines of code (around 400 of these lines will be written by you).

For the simulation, all of your code will go into the LunarLander class which, as you've already guessed, represents a lunar lander. Open LunarLander.java and take a look at what's already been written. Because we are only working in 1D, we will only be concerned with the following instance variables.

    // Rate-of-change variables
    private Vect2D position;  // Position of the center of the lander
    private Vect2D momentum;  // Mass * velocity of lander
    private double totalMass; // Mass of lander and fuel

    // Other state variables
    private double throttle;  // Percent engine boost to use
    private int status;       // Lander's status (flying, crashed, etc.)

The position, momentum, and totalMass variables are our variables that you must calculate at each timestep by integrating the appropriate differential equations. Note that totalMass includes the weight of the lander itself (stored in the constant LANDER_MASS) and the weight of the remaining fuel. The initial amount of fuel the lander has is stored in the constant MAX_FUEL. You must update these variables every timestep.

The throttle is a number between 0.0 and 1.0 (a percentage), and it represents what percentage of the maximum fuel burn rate (stored in the constant FUEL_BURN_RATE) we are using. For example, if our engine can burn at most 100 kg of fuel per second and our throttle is set to .25, then the lunar lander is currently burning 25 kg of fuel per second.

The status variable tells us whether our lunar lander is flying, has crashed, or has landed. It always has one of the following values.

    // Status constants
    public static final int STATUS_FLYING = 0;  // Lander is currently flying
    public static final int STATUS_LANDED = 1;  // Lander has safely landed
    public static final int STATUS_CRASHED = 2; // Lander has crashed

Your job is to fill in the body of the step() method. This method takes in a single argument, the timestep dt, and updates all the rate-of-change variables, as well as the status of the lander (if the lander has crashed or landed safely). The momentum is affected both by gravity and by rocket burn. Make sure to look at the constants defined at the bottom of LunarLander.java, such as EXHAUST_VELOCITY; these will prove helpful.

You should also make sure that you have enough fuel to perform the rocket boost. If there's no fuel left, then the rocket can't thrust.

To complete the step() method, you will need to make use of two other classes. The LunarLanderGame class contains the main() method. You will run this class when you want to play the game. It also contains a static variable called moon (you access it as LunarLanderGame.moon), which contains the Moon object.

The Moon class represents the moon you are trying to land on. It contains information about the terrain and gravity of the moon. For this part of the project, you will need to know the constant acceleration due to gravity and whether the lander is above a landing pad. If you browse through the Moon class, you will find an indispensible method: getGravity(). This is how you know what the gravity is.

In the step method, you also need to check whether you've collided with the terrain yet. The LunarLander class has two convenient methods to help you—isTouchingGround and landedSafely. If your lunar lander landed safely, set its status to STATUS_LANDED. If it didn't land safely but is touching the ground, set its status to STATUS_CRASHED.

After you have finished writing the step() method, go ahead and run the game. Run the LunarLanderGame class with the following command-line arguments: -vx 0 -terrain flat -turbo 2. These arguments tell the game to start your lunar lander with 0 horizontal velocity (we're only working in 1D right now), to generate a completely flat landscape, and to run the simulation at 2x speed.

Checkoff 2 - Put in the 2D physics

The world isn't 1D, it's 2D! No, wait, it's 3D but we will pretend it's 2D for this entire project. That means you have to now handle rotation and horizontal velocity. Rotation can be thought of as an instantaneous single burst of fuel from a side booster, which generates a constant rotational velocity. You do this through the interface by pushing on the left and right arrow keys and holding them down. When you release them, the spaceship stops rotating by generating the same burst of fuel, but this time in the opposite side which stops your rotation. To simplify, we will assume that the amount of fuel used to rotate the craft is proportional to the angle you rotate the craft.

Note that now that you can rotate, you can move out of your confining 1D world! You simply rotate (arrow keys) and then thrust (up and down arrows), yielding an arbitrary 2D position and velocity. As before, your job is to land on any one of the landing pads the softest with the most fuel. However, now there are landing pads with different point multipliers (1x and 2x) which multiply your entire score. Also, you have to land with the legs directly below you and an angle of 0 (you must be straight up-and-down). You are allowed to have a horizontal "sliding" velocity of 2 m/s but as you see from the Scoring section below, that also affects your score.

Technical details

Modify the step() method to handle rotation. We will need to deal with two new instance variables of the LunarLander class:

    private double angle;        // Current angle
    private double desiredAngle; // Target angle

angle is the current angle of the lunar lander. An angle of 0 means the lunar lander is straight upright. A positive angle rotates the lander counter-clockwise (its booster would begin facing towards the right and its nose to the left). desiredAngle is the angle that the pilot wants the lander to rotate to. Because the lander can only rotate at a maximum angular velocity of TURN_RATE radians per second, the actual angle of the lunar lander may be different then the angle the pilot desires.

Rotating the craft burns up fuel. The amount of fuel burned per radian is stored in the constant ROTATIONAL_FUEL_BURN_RATE. Just like in the 1D problem, you need to make sure that you have enough fuel before rotating the craft. Since both the main booster and rotation uses up fuel, you should first use fuel for the main booster, and then use any remaining fuel to rotate the lander.

Another complication arises in 2D. The moon is spherical, so our world must wrap horizontally (that is, if your lander's x position is 0 and you move left, your lander's position should wrap around instead of being negative). You can access the "width" of the world by using the getWorldWidth() method in the Moon class. Make sure your step() method wraps your lunar lander's position correctly!

To keep everything simple and consistent, we also want to wrap our lunar lander's angle so that the angle and desiredAngle instance variables always lie in the range between -PI and PI. Make sure you step() method does this.

When you've finished adding rotation, run the LunarLanderGame class without any arguments (or use -turbo 3 to speed up the simulation if it is too slow). This time, a random terrain will be generated, and there will be multiple landing spots of different sizes. Test out your lander and see if you can land it safely!

Checkoff 3 - Create a 1D autopilot

Your job for this checkoff is to write an autopilot lander which will perform a 1D automated landing. This is engaged when you align your spaceship directly over a landing strip. Optimizations of this sort typically are computed offline, and it is unusual to compute an optimal landing during the middle of flight. You are to write the code that figures out how much thrust to apply (ie what throttle settings you should use) so that your lander lands safely. Assume that you are directly over a landing pad, and as soon as you engage the autopilot, the autopilot will set the throttle to some value, and keep it at that value until you land safely or crash violently.

Technical details

The first step to writing the 1D autopilot is to devise a mathematical function that takes one input (a throttle) value and returns a number. We want the function value to be small if the input (throttle) value causes the lander to land gently, and large if the throttle value causes the lander to hit the ground hard. After devising the function, we can use the SimplexSearch optimizer to find the minimum of the function. The input corresponding to that minimum must be a throttle value that causes the lunar lander to land gently. Given a throttle value, how can we determine how hard the lander hits the ground (ie how large is the vertical velocity when the lander hits the ground)? Hint: make a copy of the LunarLander, set its throttle, and run the simulation!

Write a class called VerticalAutopilotFunction which implements the OptFunction interface, just as you've done in lab. This class will be the function you optimize to determine what throttle setting is safe.

After writing the VerticalAutopilotFunction, fill in the skeleton for the VerticalAutopilot class. This class has an engageVerticalAutopilot() method, which gets called when the user presses the space bar. This method should engage the autopilot (ie run the optimizer to determine the throttle setting). The class also contains an updateLanderInputs() method. Once the autopilot is engaged, the game will call this updateLanderInputs() method every time step, and the method should then update the throttle of the lunar lander (in this case, however, we have a constant throttle).

Test out your 1D autopilot! You can first run the game with the -terrain flat option to test out your autopilot on a flat terrain. Later, try playing with a random terrain. Center your lander above a landing pad and hit spacebar to see your autopilot in action.

Project deadline: Create a 2D autopilot; write a final report

As you could guess now your job will be to drive a generalized 2D autopilot landing. Your lander will have an initial position, velocity and rotation, and your job is to "right" your craft, position it over a landing pad, and then perform a 1D vertical landing, thus reducing the problem to one previously solved! So here your job is simply to move your lander directly over a landing spot with no rotation or horizontal motion, and then call the optimizer you just wrote last week!

You have the option of adding a single interesting feature to the project. Feel free to use your creativity here -- this could be as simple as figuring out how to draw "CAL" on the side of the lander, to color-coding the landing "smoke dots" based on velocity, to animating an explosion and crater if the lander lands too hard. Improvements can be internal too, such as improving the autopilot to use less fuel. Again, this is an optional feature; don't feel as if you have to do this.

Technical details

This is perhaps the hardest part of the whole project, but we can break it into manageable pieces. The first step is to write an autopilot which will stop (bring the horizontal velocity to 0) the lander right above a landing site. We can assume that the lander starts with a sufficiently high horizontal velocity and that the lander is rotated so that it can fire it's main booster to slow down. Note that this is almost the exact same problem as the vertical autopilot problem! In the vertical optimization problem, we had a landing height and velocity we wanted to reach. In this horizontal optimization problem, we have an x-position and a horizontal velocity that we want to reach.

First, write a class called HorizontalAutopilotFunction which implements the OptFunction interface and is completely analogous to the VerticalAutopilotFunction, just in the horizontal direction! You will need to first find a suitable landing spot to land on. Look through the Moon class to see if any of the provided methods will help you do this.

Although the horizontal problem is very similar to the vertical problem, there are some subtle complications. To help you avoid these pitfalls, we will give you some guidance on how to construct your performance function. Your performance function should make a copy of the lunar lander and run the simulation using the throttle value given to your performance function. You should stop the simulation when either your horizontal velocity changes directions (this signifies that you slowed down, and then sped up in the opposite direction) or when the distance between your lander and target increases. You should measure the distance between lander and target as the distance the lander needs to travel to reach the target when heading in its current direction. So, since you are heading in the correction direction, the distance should be getting smaller and smaller. If the distance gets larger, this means that you overshot the landing pad. Finally, after stopping the simulation, your performance function should be calculated by adding the distance between your lander and the target landing pad, and the horizontal velocity. If your performance function obtains a value of 0, this means that you are 0 meters away from your target (ie right above it!) and you have 0 horizontal velocity. So, we can use the optimizer to find this minima.

After completing the HorizontalAutopilotFunction class, write the Autopilot class. This class is similar in structure to the VerticalAutopilot class you wrote during week 3. However, this class will act as a full 2D autopilot. That is, you can assume you have some horizontal velocity. Your autopilot should rotate the lander so that it can slow down, determine the throttle needed to hover above a landing pad (by optimizing your HorizontalAutopilotFunction class), set the throttle to bring the lander above the landing pad, rotate to straighten out the craft, and then engage the vertical autopilot you developed in week 3.

You can now test your autopilot by running the game with the -auto on option. If all goes well, your autopilot will successfully land your lunar lander.

Your autopilot will not need to work for all possible scenarios. For full credit, you may assume that it will always be possible to land on the nearest landing pad in the direction that you are traveling. You will get extra credit if your autopilot also works when it's not possible to land on that nearest landing pad. We list the scenarios that we will be testing your autopilot with below. To launch a scenario, simply include the noted command line arguments.

EASY:
-terrain t1.ter -vx 25  (easy to land on 1x to immediate right)
-terrain t2.ter -vx 25  (easy to land on 2x to immediate right)
-terrain t3.ter -vx 15  (easy to land on 2x to immediate right)
-terrain t4.ter -vx -25  (easy to land on 2x to immediate left)

MEDIUM:
-terrain t5.ter -vx 25  (easy to land on 2x to immediate right, but passes world's wrapping point)
-terrain t6.ter -vx -25  (same to immediate left, and passes world's wrapping point)

HARD (these count for extra credit):
-terrain t3.ter -vx 35  (too fast to land on 2x to immediate right)
-terrain t4.ter -vx -40  (too fast to land on 2x to immediate left)

Note that the -terrain command line argument allows you to load in a specific terrain file (instead of just a flat or randomly-generated one). Inside the parentheses, we recommend the landing pad that your autopilot will probably find easiest to land on. However, it's okay if your autopilot chooses a different pad, as long as it lands on one. You will get full credit for the autopilot section if it can land in the EASY and MEDIUM scenarios. If not, the easier ones weigh more points than the harder ones. Your autopilot doesn't have to work for the HARD scenarios, but you'll get extra credit if it does.

Tips:

FINAL REPORT: Your final report will rely on the data recorder component you write for your lunar lander. The final report will be a document that has plots of time versus x-position, y-position, x-velocity, y-velocity, throttle and angle for BOTH a successful manual landing AND a successful autopilot landing. That's 12 plots total (6 for manual, 6 for autopilot)! The plots, as in the lab, should be done in Matlab. You can just copy and paste the plots into a Word document. You should also describe any extra features you implemented for extra credit, what each feature does and how you implemented it. Email the final report to ryanc@cs.


Submitting Your Project

Export your project as a "Zip file"—not as a "Gild Archive"! The Gild Archive option does not export settings.txt or the terrain (.ter) files. Mail the file to ryanc@cs, and include both your partner's name and your name in the email.

Playing

To play the game, run the main() method in the LunarLanderGame. There are three buttons at the bottom of the screen: Start Over, Generate Random Terrain, and Save Flight Data. The 'Start Over' button restarts the game, but the terrain stays the same. The 'Generate Random Terrain' button generates a random lunar landscape and then restarts the game. The 'Save Flight Data' button is only available after a game ends. Press this button to save data such as positions, velocities, remaining fuel, etc. to a comma-separated file.

In the game, use the up and down arrows to increase and decrease the throttle of your engine. Use the left and right arrows to rotate the lander.

The goal of the game is to land your lunar lander onto a landing pad. The lunar lander must be upright and gently touch down onto the landing pad to successfully land.

You can run LunarLanderGame with several command-line arguments to change the behavior of the game. Run LunarLanderGame with the -h option to get a list of command-line options for the game.

Scoring

The equation for your score is determined by your landing velocity and the amount of fuel remaining. In addition, you score is double if you land on a narrow landing pad. The full equation is:

Score multiplier * 
    ([40000 * (Percentage of fuel remaining - 50%)] + 
     [30000 * (|Vertical velocity| / Maximum vertical velocity for a safe landing)^2] + 
     [30000 * (|horizontal velocity| / Maximum horizontal velocity for a safe landing)^2])

Terrain

You can imagine that we generated the terrain by orbiting the lunar surface a few times and doing high-resolution range scans. So from your point of view, assume that we know the surface of the moon completely. We encode the terrain as a list of terrain segment. Each segment is a line, so each segment is defined by two end points.