2010 October 28 / |j|d|a|v|i|s|@|c|a|r|l|e|t|o|n|.|e|d|u

Assignment: Mazes

Carleton College CS 201, Prof. Joshua R. Davis

Introduction

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 and 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 an AI to find the shortest path through a maze. You must complete this assignment alone. Your work is due Monday at class time.

Acquaint Yourself with the Maze Format

A maze can be specified as a grid of characters, constructed programmatically or loaded from files. Here are some maze files for you to try out.

In the maze format we're using, 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 a single ending point represented by 'e'. We require that the maze be completely enclosed in walls. For example, the firstmaze.txt file contains

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
It describes the following 11 x 9 maze, with walls drawn in black and empty squares drawn in other colors. The start square is in green and the end square is in red. (You have to rotate your head 90 degrees in order to see the resemblance to the character grid above.) I have filled the shortest path from the start square to the end square in blue. The light blue squares indicate all of the other empty maze locations that I tried, before settling on the correct path.

Here's a randomly generated maze and its solution.

Write Your Maze Solver

Download maze.py to your computer. This is the program file that you'll be editing and handing in. It already contains a few features: a function to load maze files, a function to randomly generate mazes, and a main section that shows how to retrieve command-line arguments. I'd like your program to load maze files specified by the user on the command line. Try running the program in the Terminal using the command

python maze.py firstmaze.txt
The command-line arguments "maze.py" and "firstmaze.txt" are given to the program as a list sys.argv of strings. If your user gives you a maze file to solve, then you should load and solve that maze. If your user does not give you a maze file to solve, then you should randomly generate a decently large maze and solve that. Some mazes don't have any solution; you should handle these gracefully.

So the first step of your program is to obtain a maze array, either randomly or from a file indicated by the user.

The second step of your program is to solve the maze. You are required to find the shortest solution using some kind of breadth-first search. If you like, you can hand-code the search; as long as it uses a queue and produces the optimal solution, it's probably a breadth-first search and thus fine with me. On the other hand, you could simply create a Graph object from the maze array and use Graph's searchBreadthFirst method to solve the maze; that's what I did. It's up to you.

The third step of your program is to draw the maze and its solution using Bopagopa. I'm not psychic, but I foresee a great many rectangles in your future.

Submit Your Work

Submit your edited maze.py electronically as usual. It will be graded according to these criteria: