Lab 2: Dungeon Crawling

Overview: For Overview: For this lab you will be implementing a Rat agent class that will explore an unknown virtual space (dungeon). The learning outcomes are

Programming with classes in Python
Implementing depth-first search (DFS)

This lab is based on Zork, a text-based game in which you use natural language (English) commands to move about a dungeon with rooms. You can play the full game at textadventures.co.uk. Here is getting into the dungeon, where the user’s text is shown with > marks, directing the character to go south, east, etc.:

    Welcome to ZORK.
    West of House
    This is an open field west of a white house, with a boarded front door.
    There is a small mailbox here.
    A rubber mat saying 'Welcome to Zork!' lies by the door.

    >go south
    South of House
    You are facing the south side of a white house.  There is no door here, and all the windows are barred.

    >go east
    Behind House
    You are behind the white house.  In one corner of the house there is a small window which is slightly ajar.

    >open window
    With great effort, you open the window far enough to allow entry.

    >go west
    Kitchen
    You are in the kitchen of the white house.  A table seems to have been used recently for the preparation of food.  A passage leads to the west and a dark staircase can be seen leading upward.  To the east is a small window which is open.
    On the table is an elongated brown sack, smelling of hot peppers.
    A bottle is sitting on the table.
    The glass bottle contains:
     A quantity of water

    >

For the next several labs, you will build a tool that will be used by a rat agent to forage programmatic dungeons for food. We are not implementing this full game due to the sheer complexity. Along the way, the rat agent may do things like avoid trolls, traps, and poisonous food. In this first lab, you will write code to enable a rat to navigate in and interact with the dungeon. In later labs you will use other algorithms to search this dungeon more effectively.

A dungeon is a collection of rooms represented as instances of classes. Each dungeon has at least one entry room and one exit room. Rooms are connected to each other using Cardinal coordinates. Specifically, each room has

A (unique) name
A level number
An optional trap
An optional monster
A set of connected rooms and their Cardinal direction from the current room

The code for the rooms and dungeon is being given to you as dungeon.py. Elements to note:

You should not modify dungeon.py.
Directions are captured as an enumeration.
Class Room captures a single room with exits. Exits are stored in the list _neighbors (in a particular order) so there is a consistent order to them. Having a consistent ordering simplifies keeping track of which rooms have been visited.
Class Dungeon captures the collection of rooms that make up the dungeon.
The file contains auxiliary functions that help set up dungeon and provide a way to read and write dungeons as JSON text. This feature may be used in later labs but is not used in this lab.

You will complete rat.py. This file contains stubbed-out methods with documentation; see that documentation to determine the methods to write. The method path_to is to use depth-first search to find a route from the rat’s location to the destination. The state space this is searching is the possible location of the rat; what room the rat would be in after making appropriate moves.

An algorithm for depth-first search is in Figure 3.4 in the textbook; see section 3.4. To implement depth-first search, note that the Frontier (in the algorithm) is stored as a simple stack, so you always select the topmost element from the stack. There is no Stack class in Python, but you can implement it using Python arrays: given “stack” stk, add a new element x on “top” of stk by stk.append(x) and remove the topmost element by stk.pop(). The textbook algorithm shows the sequence of nodes on each path between angle brackets; you would also implement that using Python arrays. It can be a good idea to introduce your own Stack and Path classes to ensure you do not mix the two arrays.

The algorithm captures finding the neighbors of nodes (in our case, the neighboring rooms!) as finding elements of A, the set of arcs in the graph. For this lab, you will visit the rooms in the order they are returned by Room.neighbors(). Ensuring you visit the rooms in the correct order is important to get results that are consistent with ours (that is, matching the expected output). Note you will want to push these on to the frontier stack in reverse order.

The option Rat.set_echo_rooms_searched() is used by esubmit to ensure you visit rooms in the correct order. When this is set, print

        Visiting: xyz

when visiting a room with the name xyz. Do this before checking if the room is a goal and adding its neighbors if it is not. However, there is an additional consideration. There are multiple ways to reach rooms, so if you are not careful your rat will search the same room multiple times. Use a Python set - see section 5.4 in the Python 3 datastructures documentation - to track which rooms have been visited. Every time you take a room from the frontier stack, you will ignore it (without printing any messages) if it has already been visited. It is fine to use a hash table instead of a set to track this, but the data structure should have approximately constant-time addition and lookup operations.

Additional Notes

path_to returns an empty array list, [] if there is no path. This corresponds to where the textbook returns the “bottom” symbol, ⊥.
Note the the method directions_to can be implemented by calling path_to and returning just the names of the rooms.
If it makes more sense to you, you can write a protected method _search which implements the depth-first-search algorithm and call that from path_to. path_to has been named to simplify calling the method from external clients, but some find it easier to think in terms of a search method that is called by path_to.
You can add additional protected or private methods and attributes.
Room names are unique, so you can store the room names in the set used to track which rooms have been visited.
test_dungeons.py contains test code used by esubmit to ensure your solution works. You will likely find it handy to
lab2_main.py is the file you must submit as main for lab 2. This code will execute the main in test_dungeons.py; see below for additional details.
Keep an eye on type errors as flagged by PyCharm/mypy - these will be very helpful in catching mistakes in your code.

Submission

Submit your solution using esubmit. You will submit two files, your version of rat.py and the unchanged version of lab2_main.py. The other two files, dungeon.py and test_dungeons.py, are already provided by esubmit.

Remember that you can submit as many times as you like; only the last submission will be graded. Be sure to follow the coding standard provided by your instructor.

Hints

This section does not add any new requirements, but does give you hints that might help in getting started and once you start debugging your code.

Getting started

A great starting point is to hand-execute the algorithm in the textbook. Create a simple tree with (say) four layers where some nodes have two children and some have three. Label them with letters, and hand-execute the code assuming there is a solution in the bottom right part of the tree. This assignment is about translating this algorithm into Python, which is fairly straightforward since Python has a number of useful tools. The textbook shows paths being stored as tuplies (between < and >), but you might find it more convenient to implement that using Python arrays.

Note there are recursive algorithms for depth-first search online. Recursion is a great tool and can certainly help in many cases, but there are some tricky elements when applying it to this problem. Most students find the non-recursive algorithm (in the textbook) easier to implement.

Take a look at test_dungeons.py. It has functions that create dungeons in various configurations, and the comments generally describe those dungeons. The comment in rat_in_dungeon_x illustrates a particularly interesting dungeon.