CAVE Maze

by Juliet Bishop

CS490 Project
Project Advisor: Bruce Land

Introduction

This program was written in C under X Windows on the SGI Indigo 2 Extreme platform, using OpenGL. It was made to work in the CAVE* environment.
The user begins in the starting position and must find his way to the exit at one of the outside walls. The user can move by holding down wand button 1 and pointing the wand in the direction he wants to go. While not holding down the wand button, the user can turn his head to look around without moving in the maze.

Structure of a CAVE Program

The CAVE is an application created by EVL which has many predefined functions and constants. The CAVE begins operation with calls to CAVEConfigure and CAVEInit. Then, CAVEInitApplication is called which calls my function, Make_Maze, once before the looping processes begin. The display loop is started with a call to CAVEDisplay, which continuously calls my function, Display_Maze. The CAVE's event loop is started after this. The event loop continues until the Escape key is pressed, which closes the application. A call to CAVEExit exits the CAVE. For a detailed description of the CAVE, see the CAVE User's Guide.

Maze Construction Method

The program begins by prompting the user whether he wants the ceiling displayed or not. If the ceiling is not displayed, it is possible for the user to get a top view of the maze in simulator mode. A percolation cluster is used to build the grid for the maze in the function Calculate_Maze_Array. The user is prompted to enter a number from 0 to 1000. The number entered becomes the seed for the random number generator. A different maze is generated for each number entered. Entering the same number on another run will generate the same maze again. An N by N array to represent squares in a grid is constructed and initialized to zero. Each member of the array is conisdered a cell. A parallel array to keep track of which cells have been visited is also initialized. Four cells in the center of the array are initialized to 1 to form the seed for the percolation cluster. A loop goes through all the members of the array, checking to see how many of each cell's perpendicular neighbors are set to 1. If this sum is 1 or 2, then a random number is generated and if the number is less than the cutoff value, the cell is set to 1. Otherwise, the cell is left as 0. The cutoff value for the random number was very important. If it was too low the maze would not grow out to the outside walls and if it was too high, the maze would have no walls. The cutoff value is 21830. In either case, the visited flag for that cell is set to 1. Cells which have 3 or 4 neighbors that are 1 are left as 0 with the visited flag set to 1. In this way, the cells that are set to 1 move out from the initial seed cells, until the entire array has been visited.

After the array is initialized, calls are made to configure and initialize the CAVE. The function Make_Maze is then called. It goes through the array and determines where the 0's are. Then it determines if the cells perpendicularly adjacent to the cell are 1's or 0's. A polygon is added to the display list for the maze at every position corresponding to a 1 adjacent to a 0. Polygons for the floor, the ceiling, the starting position, and the outside walls (leaving a space for the exit) are also added to the display list. The ceiling polygon is only drawn if the user types "y" or "Y" at the prompt at the start of the program. Texture maps are applied to all surfaces and a normal vector is assigned to each polygon. The floor of the starting area has a different texture than the rest of the floor.

The display loop of the CAVE calls Display_Maze, which clears the buffers and calls the display list. The display loop is continuously looping and drawing the polygons for the maze relative to where the user is located.

Maze Navigation

In addition to the display loop, the CAVE has an event loop running that can take input from the user. When the user presses wand button 1, he will move through the maze in the direction the wand is pointed. The user cannot move up towards the ceiling or down towards the floor though. When the user turns his head, the wand follows. While navigating through the maze the user is prevented from passing through the walls. This is accomplished by checking the original array of 1's and 0's. If the user is about to pass from a 1 cell to a 0 cell, his movement is halted in the direction of the wall. The user can press "k" to move faster and "j" to move slower. There are limits set for how fast or slow the user can move.

The Files

My Makefile compiles my main program, maze.c with image.c and generates the executable JulietMaze. Here is the code for my program, maze.c, image.c, Makefile.

Further Work

My program allows the user to navigate through the maze and it's pretty cool, but there are some problems.

The most important problem is that the maze will only work in simulator mode on Slash (an SGI Indigo2 Extreme). The program does not work on any of the other SGIs (Hack, Howe, Crystal). For this reason, I have never tested it in the actual CAVE, only in simulator mode.
While the user usually does not pass through walls, there are times when it happens. The collision-detection code needs to be tweaked to allow it to be 100 percent successful.
When the user physically moves in the CAVE, he can pass through walls. I am only controlling the navigation of the CAVE (and the user with it) through the maze, I have no control over whether the user moves within the CAVE itself to pass through walls.
I am not sure that every seed for the random number generator will generate a maze with an exit. I have made a test for this, so the user has a chance to pick another random number if the first one doesn't work out.
The maze is so big that part of it is clipped by the far clipping plane. The variable CAVEFar controls the far clipping plane distance in the CAVE, but I wasn't able to change it successfully.
Shading needs to be implemented to allow better depth perception.
The perspective should be changed to correct the fisheye effect.

Acknowledgements

Thanks to Bruce Land, Justin McCune, Alex Benton, Frank Wood, Pat Nichols, Dan Brown, and Mike Arcuri.

* The CAVE is an application created by the Electronic Visualization Laboratory, University of Illinois at Chicago.

Juliet Bishop, jbishop@tc.cornell.edu