CS W1007 Introduction to Computer Science

Homework #5 (11 points)

Kill the Wumpus, Kill the Wumpus,...

Due Date

Section 2: Wednesday, April 15. Section 1: Thursday, April 16.

Hardcopy submission, which must be identical to electronic submission, may only be handed in at class on the due date, or directly to your TA. Do not place in folder, except between 3:00 and 5:00 on the due date. Please be careful not to let other people see your solution.

Reading: Chapters 8, 10, and 11, and sections 16.1 through 16.3.

Your Mission: Create a program that lets the user play the game Wumpus. This time, there is but ONE program for you to write. Please start thinking about the program early; just because there is only one program does not mean that this assignment will be easy. Please use submit to hand in your homework. Also, hand in a printout of your program to your TA. This way, your TA can try your code and also has a copy to write comments on.

Goal: The main goal for this assignment is for you to work on decomposition. A secondary goal is for you to use structs and to get some experience in implementing a graph.

You are in a dark cave.  Three tunnels provide exits to other caves.  You
have a magic arrow.  You smell a wumpus!  What do you want to do?
Instructions: In Wumpus, the object is to hunt the wumpus in a completely dark cave system. Each cave is connected to 3 others by tunnels. Part of the fun of playing the game is figuring out how the caves are connected. In each cave you will be told whether or not you hear bats, feel a draft, or smell the wumpus. If you feel a draft, you are next to a cavern with a pit. If you go there, you will fall in the pit and die. The wumpus has suckers on its feet which prevents it from falling into a pit. If you hear bats you are next to a cavern that contains a really large nasty bat. If you go into that cave, you get picked up and carried by the bat to another randomly chosen cave, and it is too dark to see which cave you get dropped off in. The wumpus is very heavy which prevents the bats from grabbing it. If you smell a wumpus, you are next to a cavern that holds the wumpus. If you enter a cavern that holds the wumpus, it will either get scared and exit through one of the tunnels or eat you (50-50 chance).

Each turn you can choose to move or fire a magic arrow into an adjacent cavern. If an arrow enters a cavern that holds a wumpus it gets hit and dies or you miss, and it gets scared and moves to a randomly selected adjacent cave other than the one you are in (50-50 chance). Wumpi are lazy, and do not move unless scared.

The trick is that you only have one magic arrow. Once you have fired the arrow, it's too dark to find it again. However, the arrow is magic: if it is fired into a room with the wumpus but the wumpus escapes, the arrow magically returns to you. (That is, if you fire the arrow into a room without the wumpus, you have lost the arrow.) Thus, if you lose the arrow, you might as well quit the game since you cannot win now. The object is to kill the wumpus without getting killed first.

The Maze of Caverns: There are 20 rooms (but you should set your program up so that we can change the number of rooms by just resetting a constant). Passages between rooms are symmetric: if you can get from room x to room y, then you can also go from room y to room x.

Rooms are connected in the following way: there is a path through the rooms that goes through each room exactly once ending up in the place where you started from. This path is determined randomly at the start of the game.

Next, Rooms are then paired up and the third door in each room is assigned according to this pairing. The pairing assigns room n to the room (n+10)%20 (10 rooms down the list). For example, if there are six rooms, we can generate the following random path: 5, 2, 0, 1, 4, 3, and back to 5 giving us doors between rooms 5 and 2, 2 and 0, 0 and 1, 1 and 4, 4 and 3, 3 and 5. The final three doors would be between the pairs 0 and 3, 1 and 4, 2 and 5. This describes pairings of rooms to be connected in addition to the connections created by the "path". Note that the same two rooms can be paired up twice -- once in the path, and once in the pairings.

The function(s) that initialize the topology of the rooms should be designed so that if we decide to have a different topology for the rooms, then all you would have to do is change the program in as few places as possible. Hint: make it a global array (see page 355).

All the information about rooms should be kept in an array of structs. Exactly how you implement this array and how you define the structs is up to you.

The player and wumpus's initial locations, and which rooms have bats and pits, should be initialized randomly before the game begins.

Output: Each time the player enters a room, you should tell the player whether you smell the wumpus, whether you hear the bats, and whether you feel a breeze. The user should also be told which tunnel number they just walked out of, i.e., which tunnel goes back to the room they just came from. You should of course inform the player of the rules at the beginning of the game, whether the player won at the end of the game, if the wumpus had the player for dinner, if the player was transported by a bat, if the player fell in a pit, if the wumpus moved from one room to another, and so on.

Input: For each move in the game, the player can either type in Move n or Fire n where n is one of the tunnels leading to an adjacent rooms (1, 2 or 3). The player can also type quit to exit the game. (Hint: is there some other assignment where you could borrow a couple of functions for use in this one?)

Player's problem:The player of your game will not know the number of the cave she is in. Rather, she will need to deduce the topology. For example, if she enters a cave and smells a wumpus, she better backtrack, since either of the other two exits may lead to dead. Eventually, by a process of elimination, she will be able to deduce which cave has the wumpus, and then use her arrow wisely.

Extra Credit: Extra credit is available for cool added features or a graphical interface. Examples of added features could include additional gadgets, added room features, or additional denizens populating the maze.

Grading: The program in this assignment is worth 11 points.

email: evs at cs dot columbia dot edu