University of California, Berkeley
EECS Department - Computer Science Division

CS4 - Introduction to Computing for Engineers
Final Project : "Lunar Lander"


Project Announcements

Overview

Welcome to your final project. You and your partner have been hired to build a flight simulator the next lunar landing. How exciting!

You will have four weeks to complete a very large program that will simulate landing on the moon, but in the context of a computer game. After all, 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 critical that you do not fall behind – please visit us in office hours 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 will look for you. We've highlighted any due date related to the final project.

Monday Tuesday Wednesday Thursday
Week 10
2004-11-01 – 2004-11-05
Lecture 10a
Lab 10a
Lecture 10b
Lab 10b
Final project is released.
Week 11
2004-11-08 – 2004-11-12
Lecture 11a
Lab 11a
Lecture 11b
Checkoff 1 due (email code to TAs). Veteran's Day Holiday.
(you may be asked to demonstrate it next week)
Week 12
2004-11-15 – 2004-11-19
Lecture 12a
Lab 12a
Checkoff 1 verified in lab
Lecture 12b
Checkoff 2 due & verified in lab.
Work on project in lab.
Week 13
2004-11-22 – 2004-11-26
Lecture 13a
Lab 13a
Lecture 13b
Checkoff 3 due (email code to TAs). Thanksgiving Holiday.
(you may be asked to demonstrate it next week)
Week 14
2004-11-29 – 2004-12-03
Lecture 14a
Lab 14a
Checkoff 3 verified in lab
Lecture 14b
FINAL PROJECT DUE
Week 15
2004-12-06 – 2004-12-10
Lecture 15a
Lab 15a
Lecture 15b
Farewell lecture
FINAL EXAM
2pm-5pm in 380 Soda

Checkoff 1 - Put in the 1D physics

As you recall from lecture, a rocket (including lunar landers) don't obey the simplified force equation F=ma. This is because the mass is changing over time as the lander generates its thrust by expelling fuel at high velocities in the other direction. You will encode the relevant equations of motion (including how forces, positions, velocities and accelerations affect each other) so that the lander simulation behaves correctly. You may wish to review the physics lecture slides.

However, to simplify the problem, for this checkoff (which has to be mailed to your TAs by the following Thursday) you will only need to solve this as a 1D problem, as the lander is oriented correctly straight 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 then play the game (up and down arrows control the thrust) and try to get the best score by landing the softest with the most fuel (your score is based on a complicated formula involving both of these numbers, see the Scoring section below). Landing with more than a velocity of 4 m/s will result in a 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 3000 lines of code (around 400 of these lines will be written by you). This is a big project! However, thanks to abstraction, we don't need to understand most of these classes.

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

    // ROC 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 rate-of-change variables. 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). We will need to 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 uses the following constants:

    // 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). Make sure to look at the constants defined at the bottom of the LunarLander.java file, for example EXHAUST_VELOCITY, which may prove helpful!

You should also make sure that you have enough fuel to perform the rocket boost (if not, don't). Note that momentum is affected both by gravity and by rocket burn.

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 see that it contains a convenient methods: 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, you can 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.

Final Project deadline - Create a 2D autopilot (and add a feature to the simulation for extra credit)

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 credits!)
-terrain t3.ter -vx 25 (too fast to land on 2x to immediate right)
-terrain t4.ter -vx -30 (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 probably should land on. Note that it DOES NOT HAVE TO DO THAT! We don't care which landing pad it lands on, 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. We may change these scenarios around if some of them are found to be unreasonable (so tell us if you think any of them is!) Note that your autopilot doesn't have to work for the HARD scenarios, but you'll get extra credit if you do!


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.


CS4 (Last Updated: 2004-12-01 @ 18:39:59)