Due Wednesday September 19, 5:00 pm

The task for this project is to write a simulator program for a robot designed to move packages around in a warehouse environment.

The input to your program (from standard input) will contain a map of the environment in its original state, together with a sequence of instructions to be performed by the robot.

The map specifies the size, shape and initial positions of all the packages in the environment, as well as the positions of the walls, and the initial position and orientation of the robot. The walls will be represented by the "star" character *. The robot will be represented by the characters ^,v,> or < depending on whether it is facing up, down, left or right. There will be at most 26 "packages" in the environment, labeled with the letters A,B, etc. (note that packages may vary in size and shape). For example, the map given below represents an environment with two packages, labeled A and B (the sequence of letters underneath are explained below).

           **************
  **********             *
 *            *  BB       *
*           A             *
*  ***      AA    *       *
*         ^  A    *      *
 ************************

(FFFFFRFFFLFRFFFFRFFPLFFFRFRFFFFFFFFFFFFFP)

Robot control commands

The robot is capable of four basic operations, as follows:

L turn left
R turn right
F (try to) move forward
P print the state of the environment

The instructions for the robot will consist of an ordered sequence of these four basic instructions L,R,F,P, enclosed in parentheses. When it executes an L or R instruction, the robot remains in the same location and only its orientation changes. When it executes the F instruction, the robot attempts to move a single step in whichever direction it is pointing.

If there is a package immediately in front of the robot when it tries to move forward, the package will move with the robot (in the same direction). If there are one or more packages immediately in front of that package, they will also move, as well the packages immediately in front of them, etc. We assume the robot is strong enough to push any number of packages in front of it. Since the walls are immovable, however, there will be some situations where the robot tries to move forward but fails. This will happen if there is a wall immediately in front of the robot, or if there is a wall immediately in front of a package being pushed by the robot (either directly or indirectly). In these cases, the F instruction has no effect on the environment, and the robot continues to the next instruction. (Part of the challenge of the project is to determine which packages are being pushed, and whether or not a wall is being pushed.)

The robot leaves a trail behind it wherever it goes. So, when the environment is printed, places where there is no package or wall should be indicated by a dot '.' if the robot has been there at some time during its path, and a blank space ' ' otherwise.

Example

For example, given the 9-line input above, your program should produce the following 16-line output:

           **************
  ********** .....       *
 *        ....*  v        *
*         . A    BB       *
*  ***    . AA    *       *
*         .  A    *      *
 ************************

           **************
  ********** .....       *
 *        ....*  ....     *
*     ABB<...........     *
*  ***AA  .       *       *
*      A  .       *      *
 ************************

Notes

The environment might not be rectangular, but you may assume that it is no larger than 40 by 80 (including walls) and that it is entirely surrounded by walls, so there is no danger of the robot falling off the edge of the environment.

Packages may have any shape, but each package will occupy no more than 100 characters. You can assume that each package is represented by a different letter from all the other packages, and that each package is "contiguous" (i.e. not a union of disconnected pieces).

Stages

It is recommended (but not required) that you implement the project in the following stages, with each stage designed to handle additional complexity in the environment:

Stage 1 (up to 6 marks) environments with no packages
Stage 2 (up to 9 marks) environments with one package, of minimal size (one character)
Stage 3 (up to 12 marks) environments with one package, of any shape
Stage 4 (up to 15 marks) environments with multiple packages, of any shape

Examples of input and output files for each of these stages may be provided in the student data area as the project progresses. Note that each stage extends the functionality of the previous stages. You do not need to submit each stage separately, but only the final program, implementing whatever stage you have reached at the time of submission. The number of the stage you have implemented should appear in the header documentation of your program.

Submission

You must submit one ANSI C source file which must be named projb.c (regardless of which stage has been implemented). Once submissions are open, you should submit by typing

submit 142 B projb.c

You can check that your submission has been received and has compiled by typing

verify 142 B | less

You can submit as many times as you like - later submissions will overwrite earlier ones.

Submissions after the deadline can be made by typing

submit 142 B.late projb.c

and then verified by typing

verify 142 B.late | less

Substantial marks will be deducted for late submission.

Note: additional information may be found in the QandA file in /common/cs/142 and will be considered as part of the specification for the project.

Assessment

Your program will be assessed for correctness of behaviour and quality of coding and documentation. Programs that generate compilation errors will receive a very low mark, no matter what other virtues they may have. In general, a program that attempts a substantial part of the job but does that part correctly will receive more marks than one that attempts to do the entire job with many errors.

The assessment will count 15% towards your final grade, so it is very important that you submit this project. Group submissions will not be allowed. Your program should be entirely your own work. If your program is suspiciously similar to someone else's, you may be subject to investigation and, if necessary, punitive action. Please refer to the section on Principles of Responsible Student Behaviour in Student Manual A if you require clarification on this matter.