Maze Visualization

Overview

If you ever want to write a new and improved version of Quake, you will need to be able to perform a 3-D walk-through of a maze. That's what you will be doing in this assignment.

Assignment

For this assignment you will write a program that takes as input a file describing a maze, and graphically displays the maze in three dimensions. Your program should allow the user to manually walk through the maze, and of course quit if they get sick of it.

The main data structure you will be using is a BSP-tree (Binary Space Partition tree). See http://reality.sgi.com/bspfaq/ for a detailed description of how BSP-trees work.

You only need to create the BSP-tree once, when you start up the visualization, and then you can use it to perform the "painter's algorithm" (see the above web site) to correctly display the maze as the user walks through.

WARNING: the most challenging part of this assignment will most likely be doing the graphical calculations! There is a LOT of vector analysis required to determine what direction the user is looking from, and so forth. We will not explicitly tell you how you should do this, but we (and probably any of your friends who have taken the graphics course) will help you through any difficulties you encounter.

As for the walk-through, you have two options on how to do the display. In both of these options, the user should start in the center of the start node, facing a direction of your choice.

The first option is just to have a discrete number of points the user may view from. Whenever a user enters a room, they will automatically be placed at the center of the room, facing the center one of the walls (or openings). There should be some control that allows the user to turn left or right to face the center of one of the adjacent walls. When the user moves through an opening, they should by default face the wall most directly in front of them (otherwise it would be very confusing to keep track of your orientation).

The second option is to allow smooth control of moving. Allow the user to move forward (and back, if you'd like) within a room as well as between rooms. Instead of always facing the center of a wall, the user may rotate to face any arbitrary direction. If you choose this option, be very careful not to let the user get too close to a wall (or walk through it) as this can cause overflows and other nasty things in your display algorithm.

And of course you can implement some combination of these if you wish, such as allowing free rotation but forcing the user to stand in the middle of a room.

File Format:

Because we will uses mazes of this format in our tests, it is VITALLY IMPORTANT that the input to your visualizer conform to the format described below. You are responsible for ensuring that your program behaves properly on legal input. Everything between (but not including) BEGIN and END is a description of the file format. Brackets ('<' and '>') are used to designate descriptions of the file text, rather than the text itself. Anything after a # is a comment; you do not have to implement comments in your visualizer's parser!

BEGIN <width> <height> <number of points> #including the vertices of the bounding rectangle <number of lines> #lines with points in the middle should be divided # into the shortest possible line-segments such that each # line is described by two points in the set <number of rooms> <x0> <y0> #the first point <x1> <y1> #the second point #and so forth... <x_NumPoints-1> <y_NumPoints-1> #there should be "number of points" #points <p0> <q0> <t0> #p0 and q0 are the indices of the points defining #this edge; t0 has four possible values: #0=open, 1=wall, 2=half-wall, 3=wildcard #(see below for a description of what this means) #Example: "3 0 1" describes the line connecting points #(x3,y3) and (x0,y0), and the 1 tells us that there is a wall <p_NumLines-1> <q_NumLines-1> <t_NumLines-1> #again, there should be #"number of lines" lines <deg0> <l0_0> <...> <l0_deg0-1> #deg0 is the number of edges this #borders; l0_0 is the index of the first of these edges, and #so forth up to l0_deg0-1 <deg_NumRooms> <l_NumRooms_0> <...> <l_NumRooms_deg_NumRooms-1> #and of course there are "number of rooms" rooms! <index of start room> <index of exit room> END A couple notes on the edge classification scheme: 0 means don't draw the wall; 1 means draw a solid wall; 2 means draw a half-wall (draw the bottom half so that the user can see that there is an obstacle there but they can also see past it into the next room); and if there's a 3 then you can do whatever you want. You could just treat every 3 as a solid wall, or a wall with a funny picture, or whatever you like. Keep in mind that the maze generators are not required to produce any mazes with edge codes other than 0 or 1, but you should write your visualizer to be able to handle 2s and 3s as well.

If you need further clarification on the maze file format, please read this email.

Extensions:

There are several extensions you can add. One thing purposely left out of the above description is what happens when the user finds the exit. This is up to you. Also, if you wish to color the exit differently, or add texture mapping to the walls, or any other visual candy that is perfectly fine. Two other possible extensions are to allow an overhead 2-D view as well, and to allow the user to choose to run the maze automatically using one of the maze runners from previous projects.