2009 April 17 / |j|d|a|v|i|s|@|c|a|r|l|e|t|o|n|.|e|d|u
Carleton College CS 201, Prof. Joshua R. Davis
Many computer/video games have a "vs. computer" mode in which a human player plays against the computer. Such a game must be programmed with a sense of strategy; it must exhibit some degree of complex, high-level "thinking", which computer scientists call artificial intelligence (AI). In fact, AI is not just for computer games (or science fiction films); AI techniques are used in a wide variety of applications, from web search to robotics to electronic surveillance.
One of the fundamental AI problems is path-finding: Given a "space" of some sort (a grid of squares or hexagons, a network of roads, etc.) and two points in that space, can you find a path through the space from one point to the other? In fact some games, such as Six Degrees of Kevin Bacon, are entirely about path-finding.
In this assignment you'll write a recursive solution to the problem of finding a path through a maze laid out on a grid. Although this may seem to be a rather simple or special kind of problem, its methods of solution are typical of path-finding algorithms in general.
You may work on this assignment with a partner, if you like. It is due electronically by class time (1:10 PM) Friday April 24.
Download the following files to a single folder on your computer.
maze.py is the maze-solving program that you'll be editing.
bopa.py is our usual Bopa graphics library. You don't have to write any graphics code on this assignment; I supply the code to draw the maze for you.
firstmaze.txt, cyclicmaze.txt, impossiblemaze.txt, bigmaze.txt, hugemaze.txt are text files that describe mazes. You'll test your program on them and on mazes of your own creation.
A maze file is a plain text file containing a rectangular grid of characters. An 'X' represents a wall and a space represents an empty square that you can pass through. Also, there is a single starting point represented by 's' and one or more ending points represented by 'e'. We require that the maze be completely enclosed in walls. For example, the firstmaze.txt file contains
It describes the following 9 x 11 maze, with empty squares drawn in white, the start square drawn in green, and end squares drawn in red.XXXXXXXXXXX XsX X X X X X XXX X XXX X X X XXX X XXX XeXXXXX X X X X X X X X XXXXXXXXXXX
Because they are plain text, the maze files are easy to edit. You are encouraged to design your own mazes. If you come up with an especially interesting maze, please e-mail it to me and I'll distribute it among the class.
maze.py
In maze.py the arrayFromFile() function loads a maze from a file into a two-dimensional array of characters. You pass this two-dimensional array to the Maze constructor, along with a size parameter to indicate how big of a picture you want. Once you have a Maze object, you can access its entries using getSquare() and setSquare(). For example, after we load firstmaze.txt a call to maze.getSquare(7, 1) returns 's', because that is the start square. The squares are counted from the lower left of the maze, and as always we count from 0.
There is also a randomArray() function that you can use to randomly generate a maze. The results are not great, but they're good enough to test your program.
If you run the program as it stands, it will show you the maze. Your job in this assignment is to solve the maze before showing it to the user.
In maze.py write a function solveMaze() that takes in a Maze object and an i and a j, tries to solve the maze starting from location (i, j), and returns True or False indicating whether it succeeded or not. I have several additional requirements, as follow.
Your solveMaze() must accomplish its work through recursion. Here's the basic idea. If you are at a given location, then you can move north, south, east, or west. (Diagonal moves are not permitted.) So move one square north and try to solve the maze (recursively) from there. If you succeed, then that's great; otherwise, try moving in another direction and solving the maze from there. If all four directions lead to failure, then there must not be a solution.
Once you have solved (or failed to solve) the maze, the entries of the Maze object should be updated to show your solution. The solution steps should be marked with the 'o' character; they will be drawn in blue. Squares that were tried, but that didn't make it into the solution, should be marked with the '.' character; they will be drawn in light blue. Squares that were never tried should be left marked with a space. Here is the solution produced by my program.
These 'o' and '.' markings are not just for showing the solution to the user; they are useful during the solution-finding process itself. For example, you obviously should not try to move into an 'X' square, because that is a wall. But I argue that you should not try to move into an 'o' square, either. Why?
Recursion is so powerful that you can end up with a surprisingly short and simple maze-solving function that works on all mazes. On the other hand, this algorithm does not necessarily produce the shortest path from the starting point to the ending point, as you can see in the following example. Later in the term we will study more sophisticated path-finding algorithms, that do find short paths.
You already know that you should comment your code, so that anyone reading it (including you, three months from now) can understand how it works. In this section we describe two additional practices that will make your programs better. You are expected to adopt these practices on all assignments henceforth.
First, Python has a built-in documentation system that goes beyond mere comments to actually providing user help at run time. For an example, enter this class into Python.
class Employee:
"""Employee encapsulates information common to all employees. Right now it's just an ID number."""
def __init__(self, id):
"""Initializes the employee with the given ID number (an integer). Returns nothing."""
self.id = id
def getID(self):
"""Returns the ID number (an integer)."""
return self.id
Then enter help(Employee) and help(Employee.getID). You see that Python's help system recognizes the strings as documentation and displays them to the user in a helpful manner. From now on, every class, method, and function in your programs should have such a documentation string. The string should describe what the class/method/function does. In the case of a method/function, it should also describe the types of the inputs and output.
Second, the sequence of top-level commands that your program executes should be contained in a function main(), and main() should be called if and only if the user did not import the file. For example, the program
import math
class Employee:
"""Employee encapsulates information common to all employees. Right now it's just an ID number."""
def __init__(self, id):
"""Initializes the employee with the given ID number (an integer). Returns nothing."""
self.id = id
def getID(self):
"""Returns the ID number (an integer)."""
return self.id
jim = Employee(29473273)
temp = math.sqrt(jim.getID())
print str(temp) + str(temp)
should be rewritten as
import math
class Employee:
"""Employee encapsulates information common to all employees. Right now it's just an ID number."""
def __init__(self, id):
"""Initializes the employee with the given ID number (an integer). Returns nothing."""
self.id = id
def getID(self):
"""Returns the ID number (an integer)."""
return self.id
def main():
"""Prints some garbage."""
jim = Employee(29473273)
temp = math.sqrt(jim.getID())
print str(temp) + str(temp)
if __name__ == "__main__":
main()
The three commands that constitute the main body of the program are put into main(). Importation statements, class definitions, and function definitions do not go into main(). The little bit at the end calls main() if the user ran this file directly rather than importing it.
Why do this? In many of our assignments we implement an ADT that can be used by other programs (such as the grader's grading program). Whoever writes that program should be able to import your ADT implementation file without actually executing whatever test code you have in that file. In this example, a user who imports the file gets access to Employee without printing out the test garbage.
In this assignment, parts of the file maze.py are in good Python style and other parts are not. Edit the entire file, including the parts that you didn't write, so that the entire file is good Python.
Submit your maze.py file electronically (either using hsp or by putting it on COURSES manually). It will be graded based on these criteria: