University of Wisconsin Computer Sciences Header Map (repeated with 
textual links if page includes departmental footer) Useful Resources Research at UW-Madison CS Dept UW-Madison CS Undergraduate Program UW-Madison CS Graduate Program UW-Madison CS People Useful Information Current Seminars in the CS Department Search Our Site UW-Madison CS Computer Systems Laboratory UW-Madison Computer Sciences Department Home Page UW-Madison Home Page

CS559 Spring 2002: Project 2

Maze Visibility and Rendering

Due Date: 5pm Monday April 22

Your task in this project is to implement a maze rendering program, not too far removed from those used in computer games of the first-person shooter variety. Read this entire document carefully before beginning, as it provides details of the required implementation and various tips.


A maze consists of rectangular cells separated by edges. The edges may be either transparent or opaque. The viewer is supposed to see through transparent edges into the neighboring cells, and they should not see through opaque edges. Each edge is assigned a color (which is meaningless for transparent edges).

The maze is described as a 2D structure assumed to lie in the XY plane. To make it 3D, each edge is extruded vertically from the floor to the ceiling. The floor is at z=-1 and the ceiling is at z=1. Each wall should be drawn with its assigned color.

Associated with the maze is a viewer. The viewer has an (x,y,z) location, a viewing direction, and a horizontal field of view. The view direction is measured in degrees of rotation counter-clockwise about the positive z axis. The horizontal field of view is also measured in degrees.

The maze file format consists of the following information (also look at one of the example mazes):

Software Provided

Source code can be found in the src directory.

Several classes have been provided. Together they build to two programs. The first program creates mazes in a certain format. The second is a skeleton maze renderer. The code is reasonably well documented, but part of the project is figuring out how the given code works and how to integrate your code into it. The programs are described below. To build them, set the appropriate active configuration in Visual C++ and build.


The BuildMaze program provides a simple user interface for building mazes. The user specifies the following parameters:

Cells in X: The number of cells in the x direction.
Cells in Y: The number of cells in the y direction.
Cell X Size: The size of the cells in the x direction.
Cell Y Size: The size of the cells in the y direction.
Viewer X: The initial x location of the viewer.
Viewer Y: The initial y location of the viewer.
Viewer Z: The initial z location of the viewer.
Viewer Dir: The initial viewing direction, given in degrees of rotation about the positive z axis (the standard way of specifying a rotation in the plane).
Viewer FOV: The horizontal field of view of the viewer.

The Build Maze button builds a maze with the given parameters and displays it. The Save Maze button requests a file name then saves the maze to that file. The Load Maze button requests a maze file to load and display. Quit should be obvious.


The RunMaze program provides a skeleton for the maze walkthrough that you will implement. As provided, it displays both a map of the maze and an OpenGL window in which to render the maze from the viewer's point of view. On the map is a red frustum indicating the current viewer location, viewing direction and field of view. The map is intended to help you debug your program by indicating what the viewer should be able to see.

To move the viewer, hold down a mouse button and drag in the OpenGL window. Mouse motion up or down is translated as forward or reverse motion of the viewer. Left and right mouse motion changes the direction of view. As the skeleton exists now, the viewer will move in the map window to reflect the mouse motion.

The system performs collision detection between the wall and the viewer to prevent the viewer from passing through opaque walls. You should examine the code that does that to see an implementation of clipping that clips a line segment to an edge using an approach similar to Liang-Barsky clipping. The RunMaze program also keeps track of which cell the viewer is currently in, which is essential information for the cell-portal visibility algorithm you must implement.

You should pay particular attention to the function draw in MazeWindow.cpp that sets up the OpenGL context for the window. As you will read later, all of the drawing you do in this project must be in 2D, so the window is set up as an orthogonal projection using the special OpenGL utility function gluOrtho2D. That function also draws the projection of the ceiling and the floor of the maze. You should be able to reason as to why is it safe to treat the floor and ceiling as infinite planes (hint: the maze is closed), and why those planes project to two rectangles covering the bottom and top half of the window. You do not need to change this function.

C++ Classes

This document will not go into details of the C++ classes provided. You should spend a considerable amount of time perusing them to figure out how everything works, and too look for little functions that will be useful in your implementation, such as functions to convert degrees to radians and back again (recall that all the C++ trigonometry functions take radians).

Your Task

Produce the viewer's view of the maze. You must extend the function Maze::Draw_View to draw what the viewer would see given the maze and the current viewing parameters. Note that the function is passed the focal distance, and you also have access to the horizontal field of view. Your implementation must have the following properties.

Helpful Tips

It cannot be stressed enough: This project can be completed in somewhere between one hundred and five hundred lines of code. Spend a lot of time thinking about what you are trying to do with each piece of code. And spend a lot of time looking at the code you are given.

Grading and Submission

The project will be graded out of 50. You get:

Submission will work similar to project 1. Grading of this project will be by demo in a series of face-to-face grading sessions.

If you wish to work in pairs, you may do so. Pairs will have to implement general 3D maze visibility, which is not as hard as it sounds. Talk to Prof Chenney or a TA if you plan to work in a pair.

Back to CS559 Home Page