| CMSC 106 | Project #3 | Spring 2002 |
In this project you will write a program using loops and nested loops. Although as a matter of style and clarity it is usually extremely important to determine the most appropriate type of loop for each iterative task in a program, in order to get practice with all of C's loop statements it is suggested that you intentionally use several different types in your project.
You are developing a program to allow a user to play the game of Sokoban. Sokoban, a video game invented by Thinking Rabbit, Inc. in Japan, is played on a 2-dimensional board. The game board is surrounded by walls, and there may be other walls inside the game board. There are one or more boxes which must be pushed to their proper locations in the warehouse. The warehouse keeper may push a box one square at a time: to the left, right, up, or down. Of course, a box may not be pushed through a wall, and only one box may be pushed at a time. To gain some experience with the game, you decide to develop a version using several simplified geometric patterns and only one box. After reading the starting locations of the warehouse keeper, the box, and the goal (target location), the program will read in a list of moves and determine the results, printing out the final configuration of the game board.
As you read this section, you may also want to refer to the ``Sample output'' section below.
The input to your program is to consist of a sequence of lines redirected from an ASCII text file using UNIX standard input redirection.
The first line of input will consist of three integers:
The second line will contain two integers, the row and column which represent the starting position of the player (warehouse keeper). The rows are numbered starting with 1 at the top of the game board, and the columns are numbered starting with 1 at the left of the game board.
The third line will contain two integers which are the starting row and column for the box.
The fourth line will contain two integers which are the row and column of the goal.
Following the starting configuration data for the game board, the program will read a series of moves for the player. Each move is repesented by an integer which corresponds to an arrow key on the numeric pad of the keyboard:
Valid board patterns, their descriptions, and examples are listed below. Walls are indicated by an upper-case "W", and open squares are indicated by a dash ("-").
Game board pattern 1 is a rectangle with a wall at the middle column. There is is single "doorway" in the wall at the center of the rectangle. In order to be symmetric, pattern 1 must have an odd number of rows and columns.
WWWWWWWWW W---W---W W---W---W W---W---W W---W---W W-------W W---W---W W---W---W W---W---W W---W---W WWWWWWWWW
Pattern 2 is a rectangle with 4 "pillars" arranged in a square around the center, as shown in the example below. Each pillar is a single square, and each is located 1 row and 1 column away from the center square. In order to be symmetric, pattern 2 must have an odd number of rows and columns.
WWWWWWWWW W-------W W-------W W--W-W--W W-------W W--W-W--W W-------W W-------W WWWWWWWWW
Pattern 3 has an open area shaped like an upper-case "H". Walls occupy the middle third of the columns, with a "corridor" of open squares along the middle row. In order to be symmetric, pattern 3 must have an odd number of rows, and the number of columns must be a multiple of 3.
WWWWWWWWWWWW W---WWWW---W W---WWWW---W W---WWWW---W W---WWWW---W W----------W W---WWWW---W W---WWWW---W W---WWWW---W W---WWWW---W WWWWWWWWWWWW
There is no specific maximum number of rows or columns. Note that there must be a minimum number of rows and columns in order to be able to draw a particular board pattern. The program may assume that the number of rows and columns each satisifes the minimum necessary for the given pattern.
The program will first read the game board configuration information as described above. If the input contains an incorrect board pattern your program must print an explanatory error message without doing any further processing. This explanatory error message must be printed all on one line and contain the exact word ``ERROR'' followed by the two words ``Board Pattern'' followed by the invalid input value.
If the board pattern type is valid, but the input line contains an invalid number of rows or columns, your program must print an explanatory error message without processing any other data values. This error message must be printed all on one line and contain the exact word ``ERROR'', followed by a description of the error and the pattern type. If the number of rows is incorrect, the message must be of the form:
ERROR: Number of rows must be odd for type t.
where t is the board pattern type.
If the number of columns is incorrect for types 1 or 2, the word "rows" must be replaced with "columns"above. If the number of columns is incorrect for type 3, the message must be:
ERROR: Number of columns must be multiple of 3 for type 3.
If both the number of rows and the number of columns is incorrect, then only the message for the number of rows should be printed.
After the program has verified that the board pattern and dimensions are correct, it must read the positions for the player, box, and goal. (The program may assume that the positions are valid.) Then it must read the move values until it reads a move value of -1. As it reads each move value, the program will attempt to move the player, and if possible, the box. If the player is unable to move in the given direction because there is a wall at that location, the program must print a message of the form:
Wall moving M at r c!
where M is L for left, R for right, U for up, or D for down,r is the row and c is the column for the player's current position.
If the player is unable to move in the given direction because there is a wall blocking the box from moving in that direction, the program must print a message of the form:
Box blocked moving M at r c!
where M is L for left, R for right, U for up, or D for down,r is the row and c is the column for the player's current position.
After all the moves have been processed (the value of -1 has been read),
the program must print out the final configuration of the game board,
using "W" to show a wall,
"-" to show an open square,
"O" to show the location of the player,
"B" to show the location of the box,
and "X" to show the location of the goal.
If the box is located at the goal, the location must be shown as "*",
and the game board must be followed by a blank line and the message:
Congratulations, you have solved level n!
(If the player is located at the goal, the location must simply be shown as "O".)
where n is the game board pattern type.
cc -std1 -trapuv on the OIT
UNIX Class Cluster. You will lose credit if your program generates any
warning messages when it is compiled. Even if you already know what they
are, you may not use any C language features other than those introduced
in Chapters 1 through 6 of your textbook, plus those presented in lecture
while these chapters were covered. Note that as a result arrays and
user-defined functions may not be used. In addition, neither the
goto nor the continue statement may be used, and the
break statement may not be used in any loop. Lastly, your program
must contain only one single return statement at its end, and may not
use the exit() function at all. Using C features not in these
chapters, or using the goto statement, multiple
returns, or break or continue in loops will
result in losing credit.
Your program must have a comment near the top which contains your name, login ID, student ID, your section number, your TA's name, and an original description of the action and operation of the program. Do not put your alias in this comment! Your program should be written using good programming style and formatting, as discussed in class and throughout your textbook. For this project, style is considered to consist of:
Your project must be electronically submitted by the deadline stated above to avoid losing credit per 24 hours as indicated on the syllabus. No project more than 48 hours late will be accepted without prior permission or a valid medical excuse, as described on your syllabus. Lost passwords or other system problems do not constitute valid justifications for late projects. You should start working on your project now!
You may want to skip this section at first, read the rest of the project, and come back to study it carefully when you are about to begin writing your program.
One of the important skills which must be learned in this course is how to track down the causes of and fix both syntax and semantic errors in your code. As your program will inevitably have many errors while you are developing it, you will need to follow procedures such as those described below before coming to office hours for assistance. Should you still not be able to solve the problem and have to come to office hours, you will be required to clearly describe your error and what you have already done to try and find it, and bring current printouts of your source code, and any compiler errors or execution results.
As mentioned in the earlier project assignments it is extremely important to type in only a part of your program at a time and compile and test it to verify that it is correct before going on. Different choices can be made in selecting which parts of a program to implement first; the following is just one possibility. It's fine if you prefer to follow different steps, but whichever order you choose to develop your program it is essential to enter small parts at a time and test each one before going on!
Be sure to compile and thoroughly test the code implementing this step (in fact, you could implement this step itself in several substeps, testing each as you go). These substeps could include assuming the user will only ask for the first type of board pattern. Take each step allowing more flexibility in the input - make sure you have the correct values in your input file for whichever level you are assuming at that time.
A useful strategy to use for narrowing down the cause of such
types of errors is to comment out one section of the program at a
time and recompile it after each part is commented out, until the
syntax error goes away. At that point, the cause of the error
must be in the most recently commented-out code. If you comment
out parts of your code your program certainly won't work
correctly, but this technique is just to help you quickly find the
syntax error, and once you correct it you can just remove the
/* and */ symbols which you added to comment out
your code.
A few things to keep in mind about this technique are as follows.
You can't comment out only a part of a larger statement, for
instance, you can't comment out the first half of an if
statement but leave the else part- you would have to
comment out the whole if/else. You can't comment
out half of a compound statement such as the opening brace
({) and some of the statements inside but leaving the
closing brace (}) uncommented as part of the code- you
would have to comment out the whole compound statement. You also
can't comment out code containing comments- you would have to
copy your program to a different file, delete the comments, and
then use this strategy. Once you find the syntax error in this
temporary copy of your program you can correct it in your real
version.
A file used for UNIX input redirection (using the < symbol after
the name of a program being run) is just a text file which you can create
with any UNIX text editor (e.g., emacs). You type the exact lines to be
used for the program's input the same way you would have typed them from the
keyboard while the program was running if you were not using input
redirection. To run the program with different input you can modify the
file or create a new one with different contents.
The newline character will not be visible at the end of each line of the input file you create. It is necessary that there be a newline character at the end of the last input line, so be sure you press the return (or enter) key at the end of the last line of any file you create containing input values you are going to test your program with. Otherwise your program may not work properly in some circumstances.
printf
statements. Since you are writing a program to draw something,
the debug printf output will prevent your game board from being
displayed correctly, but it can help you figure out why your
program is wrong and the debug printfs can be easily
removed after that.
printf
statement inside the body of each loop and run your program again,
the printf which gets repeated identifies which loop is the
infinite one. If no line gets repeated, the infinite loop was
either missed when you added the debug printfs or this loop
does not have a body. An extra (unwanted) semicolon in the wrong
place can cause the loop to have a null (empty) statement for its
body.
printf statements and you didn't see their results
printed, so the problem would seem to be above that point in the
program. However, it could be that those statements were
executed, but their results were just not displayed on the screen
because the infinite loop or fatal error occurred soon afterwards
in the program.
It may sound like it's a difficult debugging problem to even
figure out where in your program an error occurs, if printf
results may or may not appear on the screen, but there is an easy
way to see all of a program's output at any time. If a newline
character (\n) is printed, then any pending output which
has not actually been displayed yet will be immediately printed.
So if your program seems to have an infinite loop (or a fatal
error), either simply print some newlines, or even better, as
mentioned above, add debug printf statements to every loop
to see which one has the problem- but make sure each such debug
printf ends in a newline character! Extra newlines or
debug printf results will probably cause your output to
appear incorrect, but at least they will help you figure out where
your program's error is, and the extra print statements can be
easily removed later.
If there is any chance you may ever have to come to office hours, you should make your code readable from the very beginning. You should be able to easily understand it, and so should your instructor or a teaching assistant in office hours. If your code is a mess, the teaching assistants will direct you to first clean it up before returning so they can understand it and be able to help you. Naturally you want your code to be clear and easily readable by the graders after you have submitted it as well.
Any evidence of unauthorized use of computer accounts or cooperation on projects will be submitted to the Student Honor Council, which could result in an XF for the course, suspension, or expulsion from the University. Projects are to be written INDIVIDUALLY. For academic honesty purposes, projects are to be considered comparable to a take-home exam. Any cooperation or exchange of ideas which would be prohibited on an exam is also prohibited on a project assignment, and WILL BE REPORTED to the Honor Council.
VIOLATIONS OF ACADEMIC HONESTY INCLUDE:
|
IT IS THE RESPONSIBILITY, UNDER THE UNIVERSITY HONOR POLICY, OF ANY STUDENT WHO LEARNS OF AN INCIDENT OF ACADEMIC DISHONESTY TO REPORT IT TO THEIR INSTRUCTOR.
Turn in your program using the ``submit'' program as before, except using ``3'' for the project number. You are to submit only the .c file containing your source code, not the executable version of your program! If your program is in a file named boxman.c, submit would be run as shown. Don't forget to read the class announcements in your instructor's account every time you log in.
% submit 3 boxman.c
Before you submit your project, you must exactly follow the specific submission checklist in the ``Testing projects before submitting'' handout separately posted by your instructor!
If the name of the executable version of your program is boxman.x, here is a sample execution for the input data shown. Each of the three sample sessions show the input file and then what the program does when run with that input file. The first column is what we will be grading as the primary input - the other two are just to show other output for more advanced features of your program.
Be sure to test your program against a variety of data, so you are sure it works in all circumstances!
|
|