Task 1: Moving through Simple Mazes

The first task deals with the simplest type of mazes. These mazes have no obstacles, so you won't need to worry about gullies, mud, or dogs! They also are guaranteed to have only a single path from the start to finish with no branches or dead ends. When you run your program, make sure that the "Task 1" button is selected so that your program will generate only these simple mazes.

You control Puss's actions by the code you write in the body of the step method of the CondMazeLab class in the file CondMazeLab.java. This method initially looks like:

        
	public void step()
	{
		// ADD YOUR CODE HERE
                // to make PussInBoots take a SINGLE STEP.
                //
                // Note: NO LOOPING STATEMENTS ARE NEEDED!
                //
                // The code we've provided repeatedly calls
                // this method to make PussInBoots take multiple
                // steps through the maze.
	}

When finished, this step method contains the conditional statements to make Puss take a SINGLE step, that is, to move him safely to the next square. You do not need to run the step method over and over again; we do that for you using a loop hidden in our code. Use the slider to slow down the speed Puss steps through the maze. It's found in the lower-left corner of the window. Move the slider right to slow him down and then back to the left to return his speed to normal.

Your task is to figure out how to move Puss one step forward in general, not just for the current maze. How? You'll need to give Puss the smarts to decide what to do depending on his current circumstances. How do you know his current circumstances? We've given Puss several boolean methods that you can use to ask (true/false) questions about the square Puss is facing (i.e., what's directly in front of him). One is for seeing walls:

• isFacingWall() - Returns true if Puss is facing a wall and false otherwise.

Use if statements to determine what action to do. For example, you could add the following code to the step method:

		if (puss.isFacingWall()) {
			puss.right();
		}

The code above would give Puss the smarts to turn to the right if he is facing a wall.

		if (!puss.isFacingWall()) {
			puss.forward();
		}

This would give Puss the smarts to move forward to the empty adjacent square if he is not facing a wall. Be careful though. If your code causes Puss step into a wall, then he'll be sent back to the start and an error message will appear in Eclipse's console window! We've coded our program to check when problems like this occur. Remember, our program runs your step method over and over again until Puss either reaches the end of the maze or has a problem causing him to be sent back to start.

What things can Puss do? We've given Puss methods to do several basic movements as described below:

• forward() - This method moves Puss forward one step.
• right() - Turns Puss to the right.
• left() - Turns Puss to the left.

All of these methods are in the PussInBoots class, which contains our code specifying how the software object, puss, works. Our program has already created puss too. You simply need to tell it what to do by making method calls as shown above.

Use Eclipse to run your code to see what it causes Puss to do. Run the CondMazeLab.java program by right clicking on the file and choosing "Run As" and then "Java Application". When the program is running our screen with the maze and additional controls is displayed. On our screen select the "Task 1" button and then click the "Run" button at the bottom of the screen. Puss will now do what you programmed him to do.

The challenge for this task is to determine how to make Puss find an empty adjacent square without him backtracking along in the maze. When you believe you have a working solution, Puss should move through the maze and a message should be printed when he reaches the finish square. If Puss does something wrong a message is displayed on Eclipse's console saying what's wrong. You'll probably want to use the slider to slow Puss down before you click "Run" again. This should help you figure out what situation caused the problem. If the run button nolonger runs the program but just resets the maze, then you'll need to press "Quit" in the bottom-right of the maze window and then rerun your program in Eclipse.

TIP: If the indenting of your code is getting messy, highlight that messy code and hit ctrl-i and Eclipse will clean up your indenting for you! You can also select Source → Format to fix indenting. Note this is a very handy feature to use before you submit your programming assignments.

When you have a working solution show your Lab TA.

Task 2: Gully Jumping

Now that you've programmed Puss to navigate simple mazes, let's add an obstacle - gullies! Remember to select the "Task 2" button to get mazes with only gullies! If Puss encounters a gully, he'll need to jump over it. Add an if statement to check for gullies using the following boolean (i.e., true/false) method of the PussInBoots class:

• isFacingGully() - Returns true if Puss is facing a gully and false otherwise (Warning: if true, moving Puss forward will cause him to fall into the gully and results an error message and Puss being returned to the start).

When you encounter a gully, you'll want to jump over it (you may assume there is a safe square to land over on the other side). Use Puss's jump method:

• jump() - Jumps Puss over one square.

Having a problem with your program? Make sure to check the console window in Eclipse to see if an error message was displayed.

When you are finished with this task, show your lab TA your work.

Task 3: Mud and Sleeping Dogs

Let's add the other two obstacles - mud and sleeping dogs. To pass through mud, we recommend Puss put his boots on and not be tiptoeing. To pass the dog, he should tiptoe with boots off. Also note now, if Puss is going to jump a gully, he should consider taking off his boots and not be tiptoeing! Remember to select the "Task 3" button to get mazes with all obstacles. As with previous tasks, you may assume the maze will have one path that Puss can safely navigate. Specifically, there won't be a situation where a dog and mud are right next to each other since that would be impassable. Now you'll need to add statements to check for these additional obstacles using the following boolean methods:

• isFacingMud() - Returns true if Puss is facing a square with mud and false otherwise.
• isFacingDog() - Returns true if Puss is facing a square with a sleeping dog and false otherwise.

To tackle these obstacles, we've given Puss more methods:

• startTipToe() - Puss starts to tiptoe as he moves.
• stopTipToe() - Puss stops tiptoeing.
• putOnBoots() - Puss puts on his boots.
• takeOffBoots() - Puss takes off his boots.

There are also boolean methods to determine if puss is currently wearing boots or tiptoeing:

• isTipToeing() - Returns true if puss is tip toeing and false otherwise.
• isInBoots() - Returns true if puss is wearing his boots and false otherwise.

Having a problem with your program? Make sure to check the console window in Eclipse to see if an error message was displayed.

When you have a working solution show your Lab TA what you've done.

Task 4: Branching Paths

The code that you've written so far is a general solution for mazes containing obstacles but having just one path. The next step is to introduce branches in the maze. These branches might lead to the finish or might be dead-ends. You can make the same assumptions as in the prior tasks, that is, there will be at least one path that Puss can safely navigate to the finish. Remember to select the "Task 4" button to get these branching mazes.

Think about how you might solve a maze with just the information that Puss has, that is, just a view of the adjacent squares but no view of the entire maze. How would you solve such a maze? Randomly walk in a direction? Or is there some guideline you can use to determine your choice whenever the maze branches? Have you heard of the "left-hand" (or "right-hand") rule? The left-hand rule is an algorithm guarantees to solve certain types of mazes. The rule is quite simple, always keep your left hand "on the wall" and never take it off while you are walking. Eventually this will get you to the end of the maze.

You'll reuse some of your code for solving the previous 3 tasks, and write new code to have Puss follow the left-hand rule to solve branching mazes that also have all three types of obstacles. Note that your solution to Task 4 should also be able to solve all of the mazes from the previous tasks.

Be sure to show your Lab TA your final solution.

Challenge Tasks

If your are reading this, then you've successfully completed the tasks above and have shown your Lab TA your work. If there is time remaining in the lab, use it to try these challenge tasks. If you are able to complete either challenge below, show your Lab TA your solution.

Challenge 1

Implement the right-hand rule, that is where you keep your right hand on the wall instead of your left hand.

Challenge 2

In Task 4 it says that the left-hand rule is guaranteed to solve certain types of mazes. Can you think of a maze (without obstacles, the obstacles are not what will make certain mazes unsolvable but the structure of the maze itself) that the left-hand rule will not solve? Think about what the left-hand rule does and what will happen if you didn't stop at the finish and just continued following the left-hand rule until you got back to the beginning.