CSE 326 Project 2, Autumn 2000

DUE OCTOBER 23, 2000 at 2:30PM

In this project, you will explore graphs through the context of a text-based virtual world, similar to old Infocom games (Zork) or MUDS. You will implement a path-finding algorithm called Breadth First Search and some items from a list of options.

Background

Once logged in to a unix machine, do the following sequence of commands at the % prompt:

  1. "cd 326" - The cd command changes the current directory to your cse326 directory.
  2. "mkdir project2"
  3. "cd project2"
  4. "cp /cse/courses/cse326/00au/project2/* ."
  5. "make"
That should copy all of the starting source files into your directory to modify.

The Simulator

The simulator consists of a set of rooms, exits between the rooms, an overall world, and an avatar.

Rooms: A room represents an abstract area. A room could be an actual room, like a living room or a lab in Sieg. It could be a generic area, like Drumheller Fountain or Red Square. It could also be part of an area, like the eastern part of the ring around the Fountain, the southern part of the ring, the western, and so on. Each room has a name, a description, and is identified by a unique number (the "room number").

Exits: Each room has a list of exits to other rooms. Each of those exits has the room number of the destination and the command necessary to move there.

World: The rooms are stored in a large vector in the World class with their index in that array equal to their room numbers. There is an accessor for that array called room(). If room A has room number 5, then world->room(5) is that room. If room B is room number 619, then world->room(619) is that room. The World class also keeps track of the highest room number in use. You'll find that useful to know when you want to keep track of which rooms your search algorithm has visited. Finally, the World class also handles parsing of commands and calling the appropriate command functions.

Avatar: Your position in the world is represented by an avatar. An avatar represents your person in the virtual world. The current version of avatars are extremely simple: they only keep track of their location in the world (via a pointer to a Room). In a real virtual world, they might have size, weight, names, pictures, and so on.

Mechanics

This project may be done individually or in a team of two students. Sorry, no teams of three or more. If you choose to work individually, you must implement the BFS algorithm and 2 "points" of bells and whistles. If you choose to work in a two-person team, you must implement the BFS algorithm and 5 "points" of bells and whistles. The point values are in parenthesis in the title of each feature below.

Breadth First Search (required)

You must implement a new command called "wayfind." The wayfind command takes a room number as an argument. It should tell the user which exit from the current room he should take to move towards the destination. The exit must be on the shortest path. The command must also display the distance to the destination (the current room is distance 0). If there is no path to the destination, the command reports that fact. You must use a breadth-first-search algorithm. Record keeping functions (like marking) and the memory required to enabled them should be handled within your wayfind or BFS code. Temporary memory is probably easiest, but you can use dynamic (new/delete) if you wish. If you want to write your own queue routines, that's fine. Otherwise, a queue implementation from Weiss is given in QueueAr.h/cpp.

Iterative Deepening Search (3 points)

One drawback to BFS is that the queue can use a large amount of memory if the tree/graph has a large fan-out (lots of children or outgoing edges at each node). Another algorithm used sometimes in AI, Iterative Deepening Search, can eliminate that memory requirement at a cost of slightly increased computation time. Iterative Deepening Search works by calling a bounded depth first search algorithm repeatedly, increasing the maximum depth each time (thus "iterative deepening"). Implement this algorithm (as "step"), again reporting an exit on one of the shortest paths to the destination. Indicate the distance to the destination. [When do you stop deepening and declare your destination unreachable? When the number of marked nodes is the same for depth k and depth k+1. In your README, explain why this criteria works.] For more information, see http://tina.lancs.ac.uk/computing/research/aai-aied/people/paulb/old243prolog/subsection3_6_4.html or send me email.

Save world (2 points)

Write a command ("save") that takes a string as an argument and saves the current state of the world (the rooms and their exits) to a file with the same name as the argument. The file you produce must be valid as input to the simulator. See the comments in World.cpp for file format details. Also examine small.world to see an example.

Add exit (1 point)

Implement "add_exit ." You should allocate the memory needed for a new exit, set the fields correctly, and add it to the Avatar's current room. I suggest the "oneword" method of strings as a way of further splitting the argument to addexit into the room number and command string, but you can also implement it as "add_exit" and prompt the user for each of the options separately. Look at how exits are added in add_room (World.cpp) for some ideas.

Delete exit (1 point)

Implement "delete_exit ." This command deletes the exit with that command from the current room. You should free memory that is appropriate to free.

Exit order (1 point)

In add_room (World.cpp), exits are prepended to the beginning of the list of exits. That causes the order in which exits are displayed in the simulator to be the reverse of the order in which they're input in the world file. Make the order in the simulator be the same order as the world file.

Room configurability (1 point)

Add two commands, one of which is "roomname " that sets the room name to the specified string. The other is "description" which then prompts the user to enter a series of lines that comprise the description. The user stops entering description lines by putting a tilde (~) on a blank line. Note that descriptions should have newlines (endl or \n) inside them if multiple lines are entered, and must have a trailing newline as the last character.

Room Addition (1 point)

If you choose this option, you must choose "Room configurability." Create a command that adds a new room to the World. It should take the room number for the new room as an argument and fail if that number is invalid or a room with that number already exists. The command should then query the user for a name. After a name is entered, it should force the user to call the Room configurability command. The new room should have no exits.

Room Deletion (2 point)

Implement "delete_room ." You need to remove the room from the rooms array in the World class, remove all exits from the room, remove all exits that have this room as their destination, all while freeing memory that should be freed. (This one has a lot of details that can be hard to get just right.)

Others (X points)

If you have some really cool idea for your own feature to add, send me email and we can work out a point value. Please don't make changes the simulator structure not on this list without asking me first, even if you're not going to claim point value for them.

Turnin Items

You must use the turnin program to turn in your entire project2 directory. Here's the list of things you need to turn in:
  1. All of the code and support files required to compile it.
  2. The README file (answer the questions in it).
That's it! If you have any questions, either email me (amohr@cs) or send mail to the class mailing list (cse326@cs).