Due midnight the evening of 9/14

Learning Objectives
Familiarity with complete robot tasks Familiarity with creating new subclasses Familiarity with writing test cases Familiarity with if statements Familiarity with simple recursion Familiarity with the Web-CAT Grader

In your first programming assignment, you will be writing a simple robot subclass for solving mazes, together with a maze-solving task that uses your robot. Your robot will start off in a world containing a 12x12 maze generated at random. Your robot should always start in the "home" position, at the intersection of 1st Street and 1st Avenue, facing North, and holding no beepers.

The entrance to the maze will always be immediately North of 1st Street at 3rd Avenue. The exit will always be at the intersection 14th Street and 13th Avenue. There is a beeper at the exit. Upon completing the maze, your robot should pick up the beeper, face North, and turn off.

Note that you must use SolveMaze as the name for your robot task class--the class that contains your task() method. Also, don't change the name of the task() method or you will get compilation errors--everything that implements RobotTask must use the method name task().

The cs1705 package contains a maze generator for use in this program assignment. The maze generator produces a description of the desired world situation, and this description can then be used as the starting point for your robot task. You can use the maze generator this way:

    World.startFromString( MazeGenerator.generateMaze() );

In this statement, you are asking the World class to start from an initial situation described by a string of text. This method requires that you provide a world description within the parentheses immediately following the startFromString method call. To get the initial world description needed by startFromString, this statement asks the MazeGenerator to generate a maze description, which is produced in the form of a string of text. The maze generator produces a new random maze each time, similar to the example shown below:

Click picture for a larger view

Solving the Maze

One technique that is helpful in solving a problems (whether they are programming problems or otherwise) is breaking the problem into smaller pieces. With a program like this, you need a place to collect solutions to those pieces. A natural strategy in object-oriented programming is to create a new class (or more, if needed), and frame each building block of the solution as a new method.

To this end, first devise a strategy for getting through the maze, bearing in mind the limited abilities robots have at sensing their environment. The basic predicates that a robot can use to examine the world around it are listed in KJR, Section 5.2. Break your strategy into pieces by asking yourself: "what capabilities must my robot have in order to carry out this strategy?"

Then, as indicated in the introduction to this assignment, you will most likely want to create a new kind of robot for solving mazes. You should create a new class to represent your new kind of robot--a class separate from your robot task. You can name your robot class anything you like.

Look at your strategy and your list of desired robot "capabilities." Add them one at a time to your new robot class. Also, be sure to test each method as it is created. By testing each method you add just after it is written, you can confirm that what you have done so far works the way you intended. If you wait until your whole robot is complete and then test it on a full maze, some problem will almost certainly arise. At that point, though, many students have difficulty figuring out where to start in finding and fixing the problem.

Note that you must also provide the following method in yout robot task class (where <karel> is the name you have used for your robot inside the robot task):

    public VPIRobot robot()
    {
        return <karel>;
    }

Note that you are not expected to find the shortest path through the maze. However, your solution must terminate. The grader applies a time limit to your program to detect "runaway" submissions that never end. For this assignment, the time limit is approximately one minute (with the robot running as fast as possible).

Program submissions work just like lab submissions. On BlueJ's main menu, click Tools->Submit.... Click on "Browse...", double-click to open the "CS 1705 Programs" folder, and select Program 1. Click "OK". Click "Submit". Click on the link provided in the submission response in order to view the results of the automated phase of program grading.

If any errors are indicated, you can fix them and resubmit. You may resubmit as many times as you like, up until the deadline. Be careful as the due time approaches--if you submit just over the deadline, a late penalty will be assessed.

Home  |   Notes  |   Homework  |   Labs  |   Programs