Introduction 

The program described here uses OpenGL to render a three-dimensional maze, through which the user must maneuver (walk or run) using the mouse and/or arrow keys. A first-person perspective is used, with collision detection implemented at the maze walls. Each maze is randomized, and moreover each maze has only a single best (i.e., detour-free) solution path. The size and difficulty of the maze are controlled by compile-time constants. A relatively easy maze is provided by default, but very large and circuitous mazes have been simulated during testing, with good results.

The demonstration code is less than 650 lines long, even with liberal use of comments. The code provided is therefore architecturally minimalist in nature; like much of OpenGL itself, the demo is largely an unadorned C program. This makes for a clear presentation, which is still adaptable to more involved designs.

The simulation developed here is somewhat similar in appearance to Wolfenstein 3D, one of the earliest widely used 3D simulations. However, the use of OpenGL enables some effects not seen in Wolfenstein 3D.

At the start of each game session, for example, the user drops into the game world from slightly above, as if by parachute, near the entrance to the maze. This affords the user the opportunity to view the maze solution briefly before play, and adds another skill dimension to the game. An example of this airborne-style view is shown below:



Background

To put together such a simulation requires a complex, multidisciplinary development process. Questions of design, physics, etc., must be addressed, along with the computer science issues inherent to 3D programming, and to a randomized maze game. So, much of the design work evident here, and much of the code provided here, is discussed in a previous article by the same author. Readers who are particularly interested in certain aspects of the implementation may derive greater benefit from one of these predecessor articles.

The article titled Fast Generation of Single-Solution Mazes gives an algorithm for the generation of abstract square-based mazes of arbitrary size, and having just one solution. A runtime image from that article is shown below. Note that the maze is an abstract construct intended for expansion into a full simulation; there is no gameplay per se in this earlier article, only a well-documented generator of mazes that could ultimately be rectangular, cubic, or even prismatic in some non-cubic way, in a full application.

























This implementation, and the next, are both basically MS-DOS (more recently "Command Prompt") applications. However, a very different 3D implementation of the algorithm used here is evident in the next picture. As in this OpenGL implementation, one dimension of the abstract maze is mapped to the "Z" dimension of the 3D system, and the "Y" dimension of the 3D system is used to add vertical depth to the maze. The code for this second, 3D MS-DOS implementation is not currently available on The Code Project, but is available from the author upon request.

















In both of the maze programs shown above, note that the maze is composed of regular rectangular units, and that the randomization algorithm operates in terms of these discrete units. Logically, the maze definitions used are thus built around two-dimensional arrays. This technique is carried forward into the OpenGL implementation described here, where (as in the MS-DOS 3D implementation) array elements represent whole cubes.

The article at hand thus focuses on the additions necessary to build this prior work up into a three-dimensional first-person maze game. Collision detection and collision handling (e.g., with the maze walls) are new topics which are discussed in depth in the text below. Another key topic is the mapping of the abstract mazes described in Fast Generation of Single-Solution Mazes  into a three-dimensional OpenGL coordinate space. Finally, real game-style user input is a topic that is new in this third article, and this issue is dealt with in some depth in the text below.

Using the Demo

The demo archive provided at the top of this article contains a single folder in Zip format. This Zip should be extracted to a single Windows folder, and the single ".exe" file contained therein should be executed, in order to run the demo application. The demo application will query the screen resolution, and then size itself to use about 90% of the display.

During the user's parachute-style descent, no input of any sort is processed. After that, either the mouse or the arrow keys, or even both of these input devices in tandem, can be used to play the game.

The user is allowed to move throughout an open-ended game world in a fashion which, it is hoped, will prove to be intuitive. In keyboard mode, the left and right arrow keys rotate the user about the "Y" (or "yaw") axis, i.e. about the player character's own height. This is done without actually changing position. The up arrow key moves forward in the current direction and the down arrow key moves backward, at a slower rate. It should be noted that running into one of the gray brick maze walls will cause the user to be bounced backward slightly.

Mouse control operates in a fashion very similar to keyboard control, but with the introduction of variable speed based on control position. Pressing the mouse sufficiently forward will effect forward motion just like the motion effected by the up arrow. Left and right mouse movements are used to rotate the player's view, just like the left and right arrow keys. Backward mouse movements (i.e., movements of the mouse back towards the user) are analogous to down-arrow key presses, that is, such movements result in backward movement in the direction currently being faced by the player.

Keyboard and mouse control can be used alternately in the same game session, or even used at the same time. Pressing the up arrow and moving forward simultaneously, for example, offers a sort of "run" feature, in which forward movement faster than what is attainable using either input device alone can be achieved.

It is possible to wander off into the wasteland around the maze, and to continue indefinitely. No change in display will happen while travelling in the wasteland; a generic horizon display will be seen during this time. If the user wanders too far in such a direction, the maze may seem to be lost. If this happens the user should press ESC to exit the simulation, and then restart it.

By default, the maze will be 8 cubes by 8 cubes in size, not including the two solid walls on the sides without an entrance or exit. There is no specific indication when the maze is solved; however the program does reliably enforce the solidity of the walls.

Using the Demo

As downloaded, the archive linked to at the top of this post contains everything necessary to run the demo. Simply execute program "openmaze.exe". The remainder of this section is dedicated to building this executable using the MinGW compiler, which is a port of the GCC compiler to the Windows environment.

To set up the development environment described in this article, it is first necessary to install MinGW (go to the MinGW Sourceforge site or the main MinGW web page). The rest of the article will be easier to follow if the default installation paths (e.g. "C:\MinGW\") are used during MinGW installation; and in general, accepting the defaults during the installation process will result in a development setup suitable for OpenGL. 

 The latest versions of the MinGW installer use a GUI that is somewhat complicated-looking. The procedure necessary to actually get MinGW installed is not particularly complicated, though. Once it has finished loading, the MinGW installer will present the user with the dialog seen below:



















Simply press "Continue" at this point. Next, the installer will show the dialog pictured below:



















Here, wait for the progress indicator to reach 100%, then press "Continue". Finally, the installation process concludes by opening the dialog seen in the picture below:




























This dialog (which is used to manage MinGW packages) can simply be closed. After installation, Windows may ask whether installation completed successfully, and it is advisable to answer "yes."

OpenGL is a somewhat decentralized development project. As a result the development setup described here must rely on a conglomeration of several auxiliary tools. The OpenGL Utility Toolkit (GLUT) provides the ability to create and manage a viewing window. The OpenGL Extension Wrangler (GLEW) library manages extensions to OpenGL, which exist to provide abstract support for the wide variety of 3D devices (and host platforms) available. (The necessary components of these two libraries are included with the supplied code.) Finally, the work presented here depends on The OpenGL Utility Library (GLU), although this most basic level of abstraction has become part of many default GCC installations, MinGW included. The other dependencies mentioned above are, as appropriate, linked or compiled into the object executable created by following the build procedure described below.

As installed, MinGW already contains a basic OpenGL development kit, as exposed by the -lopengl command line parameter. Beyond this, though, it is still necessary to install GLEW and GLUT. In the example at hand, GLEW is compiled into the target executable from a ".c" file. GLEW is thus statically linked into the target executable, and in general the author prefers this approach for its predictability. GLUT, though, is linked dynamically in classic Windows fashion: a stub ".lib" file is referenced during compilation, and this makes calls into a ".dll" file which must be present alongside the demo executable at runtime. (Technically there are other places it can be stored, e.g., under "c:\Windows\System32"). This linking strategy proved expedient because of the large number of source code files provided for GLUT. Unlike GLEW, building GLUT into a project is not necessarily a matter of compiling just one (or even just a few) ".cpp" files.

The file "glew.c" is provided with the source code for this article, since it is essentially a part of the source. In addition to "glew.c", a header ("glew.h") is required to use GLEW. This header should be obtained and placed in the MinGW #include path, e.g., in the "c:\MinGW\include\GL\" folder. The exact versions of this header, and all the headers the author had to add to the "c:\MinGW\include\GL\" folder, are present in a subfolder named "GL" in the source code archive folder provided. These files are available in many other places on the Internet, and most versions of these files should work with the techniques described in this article.

GLUT relies on some headers in "GL" as well, and it also requires a ".dll" (at runtime) and a ".lib" file (to build). So, the necessary ".dll" is provided in the demo (executable) download accompanying this article, and the ".lib" is present in the corresponding source code archive. 

An example build command (e.g., for execution in the Windows "Command Prompt") is shown below. In this example, the folder "c:\test\" is assumed to contain the source code. This is a MinGW build command, but the code provided can be built using a wide variety of compilers. MinGW is a version of GCC, for example, so building under GNU/Linux should be very similar.

The demonstration executable is built from the Windows "Command Prompt" with the working folder set to the folder containing the provided source code. Prior to using MinGW from the Command Prompt, it is necessary to include the MinGW "bin" folder (e.g. "c:\mingw\bin") in the OS default search path. This can be done using a "cd" command:

set path=c:\mingw\bin;%PATH%

Above, note that, as suggested, MinGW has been allowed to install itself into the default folder it prefers. In general, MinGW seems to work better if this folder structure is used (versus using the more elaborate folder names typical of pure Windows applications (such as "C:\Program Files (x86)\"). If it is absolutely necessary to use a more traditional Windows folder structure, it is recommended that you use an 8.3 alias for any parts of the command that use the "long file names" feature, substituting "C:\PROGRA~2\" (or similar) for "C:\Program Files (x86)\".

In the build command, the GLEW source file name ("glew.c") is passed to the compiler (which is named "c++.exe"), just like the source file name for the demo itself ("mingl.cpp"). The -lopengl and -lglu32 options are used to statically link OpenGL and GLU, respectively, and the -o option is used to name the output file.  Library "glut32.lib" is build directly into the target .EXE, and its filename is therefore included alongside the requisite C and C++ source code files. Finally, the -static-libstdc++ and -static-libgcc options are used to link the standard C and C++ libraries directly into the target .EXE file, removing any need to include their .DLLs alongside the .EXE at runtime.

An example of the full command line is shown below.  In this example command, it is assumed that the source archive has been decompressed to folder  "c:\users\beau\documents\openmaze".  This folder name is evident in several places in the command above. In each case, you will need to adjust your own build command to contain the correct folder in your own environment.

c:\mingw\bin\c++.exe c:\users\beau\documents\openmaze\openmaze.cpp c:\users\beau\documents\openmaze\glew.c c:\users\beau\documents\openmaze\glut32.lib -lglu32 -lopengl32 -static-libstdc++ -static-libgcc  -oc:\users\beau\documents\openmaze\openmaze.exe

Coordinate System

The development of a coordinate system is the main step necessary to make the conceptual maze described in Fast Generation of Single-Solution Mazes into a useful on-screen representation. The simple array-based representation generated in the first of these two articles must be translated into a three-dimensional representation suitable for OpenGL.

Four constants in particular play a key role in this mapping:  MAZE_EXTREME_LEFT,  MAZE_EXTREME_TOP,  HALF_CUBE, and FULL_CUBE. Similarly, a pointer returned by the function maze_innards() plays a key role in this coordinate mapping; specifically, it points to an array holding the definition of the variable portion of the maze, i.e., the maze other than the two solid walls in which there is no entrance or exit. \

Finally, the constants XSIZE andYSIZE often enter into coordinate calculations. These define the size of the abstract maze in its X and Y dimensions, e.g., 8 by 8 in the default build configuration. The role played by each of these values is shown in the diagram shown below:




























In this diagram, first note that the squares shown above actually translate to cubes in the program display. The OpenGL "Y" dimension, which is the vertical dimension in the simulation, is omitted from the diagram. (The "Y" dimension of the abstract maze translates to the "Z" dimension of the OpenGL rendering, as indicated in the diagram shown above.)

All the shaded squares in the diagram above (both light and dark gray) are solid cubes in the OpenGL rendering, textured to represent wall segments. The use of cubes in this way introduces some extra faces to the maze as supplied to the OpenGL rendering pipeline, in the form of invisible, internal cube boundaries. This has not proven to be an issue in actual practice.

As shown,  MAZE_EXTREME_LEFT  and MAZE_EXTREME_TOP define a starting corner for the maze, and all the coordinate calculations in the code (e.g., for collision detection) use these constants in conjunction with size constants  HALF_CUBE and FULL_CUBE. These constants all have type GLfloat, and together they describe the nominal values used in the OpenGL coordinate system, as well as how each abstract square from Fast Generation of Single-Solution Mazes is located in 3D space.

Furthermore, in this last diagram shown, note that the darker squares represent the contents of the array pointed to by maze_innards(). As shown, this pointer is indexed from maze_innards()[0][0] to maze_innards()[XSIZE-1][YSIZE-1] (the 7,7 shown above). Again, the solid walls are not counted. As in Fast Generation of Single-Solution Mazes, constants are defined such that each element can either be 0 (closed, i.e., a cube or wall), 1 (a false path), or 2 (on the optimal solution path).

New Abstractions

The program described in Fast Generation of Single-Solution Mazes generated an abstract maze, in the form of an in-memory data structure. Then, a graphical representation of the maze was shown, in which rectangular areas of the maze where a barrier to movement had been determined by the algorithm to exist were represented by a colored-in rectangular area on the display. Other areas of the maze resulted in basically no display, i.e. the simple black background was shown.

 The program described here is more sophisticated in its output, and more interactive, but the same fundamental translation between abstract, in-memory maze definition and on-screen rendering must occur. In this latest program, though, the filled-in areas take the form of textured cubes. 

The beginning of the cube() function, which draws a cube of the designated size centered around coordinate(x,y,z), is shown below:
void cube(GLfloat x, GLfloat y, GLfloat z) //Draws a cube centered at (x,y,z)
{
 // Top of cube
 glTexCoord2d(1.0,1.0);
 glVertex3f(x+HALF_CUBE, HALF_CUBE,z-HALF_CUBE); // Top Right Of The Quad (Top)
 glTexCoord2d(0.0,1.0);
 glVertex3f(x-HALF_CUBE, HALF_CUBE,z-HALF_CUBE); // Top Left Of The Quad (Top)
 glTexCoord2d(0.0,0.0);
 glVertex3f(x-HALF_CUBE, HALF_CUBE, z+HALF_CUBE); // Bottom Left Of The Quad (Top)
 glTexCoord2d(1.0,0.0);
 glVertex3f(x+HALF_CUBE, HALF_CUBE, z+HALF_CUBE); // Bottom Right Of The Quad (Top)
 //...

In considering the entirety of this function, consider that OpenGL works in terms of triangular facets, two of which are required to each face of the rendered cube. These triangular facets must be passed to OpenGL in counter-clockwise order, to allow OpenGL to optimally determine which facets are facing the camera (and must therefore be rendered) in a given frame. Translation factors x, y, and z are respected, by simply adding them into each vertex's natural coordinate if it were rendered about the origin. These natural coordinates are built using constant HALF_CUBE, which is used to size all cubes at the whole-program level.

A few other, similar abstractions are created in this latest program. For example, a general texture load function is employed. The program adds a static background image, which is a rectangle having its own texture distinct from the maze, so this function proved necessary. Its prototype is shown below:

GLuint maketex(const char* tfile,GLint xSize,GLint ySize);

The value returned by this function is a number assigned to the texture by OpenGL. This acts as a runtime handle for the texture resource.

Maze Rendering

The rendering of the maze display is handled by print_maze(). This function, shown below, is entirely based around calls to cube(). It begins by drawing the solid walls, whose centers are located at Y=MAZE_EXTREME_TOP+HALF_CUBE and Y=MAZE_EXTREME_TOP+HALF_CUBE+FULL_CUBE+(YSIZE*(FULL_CUBE))). (The first FULL_CUBE term in this last expression accounts for the top solid wall, which is not included in YSIZE). For both walls, the drawing extends across the full breadth of the maze, i.e., from the center of the leftmost column of cubes at MAZE_EXTREME_LEFT+HALF_CUBE to the center of the rightmost column atMAZE_EXTREME_LEFT+HALF_CUBE+((GLfloat)(XSIZE-1)*FULL_CUBE). After these walls are drawn, a nested loop is used to draw a cube for each element of maze_innards() having the value NO_PATH. Finally, note that each cube in both of these sections is centered around 0.0 in the "Y" dimension, which is also where the camera is located (after landing).
void print_maze() //Renders the necessary OpenGL cubes
{
 int x,y; 
 for(x=0; x<XSIZE ; ++x ) //Print a border
 {
  cube(MAZE_EXTREME_LEFT+HALF_CUBE+((GLfloat)x*FULL_CUBE),
  0.0,
  MAZE_EXTREME_TOP+HALF_CUBE);

  cube(MAZE_EXTREME_LEFT+HALF_CUBE+((GLfloat)x*FULL_CUBE),
  0.0,
  MAZE_EXTREME_TOP+HALF_CUBE+FULL_CUBE+(YSIZE*(FULL_CUBE)) );
 } 
 for(y=0; y<YSIZE ; ++y ) //Maze proper
 {
  for(x=0; x<XSIZE ; ++x )
  {
   if((maze_innards())[x][y]==NO_PATH)
   {
    cube(LEFTMOST_CUBE_CENTER+((GLfloat)x*FULL_CUBE),
    0.0,
    MAZE_EXTREME_TOP+HALF_CUBE+FULL_CUBE+((GLfloat)y*FULL_CUBE)); 
   }
  }
 }
}

Fast Sky / Ground

The sky and ground are handled using a common, flat display. This is just a background image (defined by "sky.bmp"), with a horizon drawn at its approximate midpoint. This image is drawn into 3D space using texturing and glVertex3f(), just like a cube face. (In fact, it is based on the cube's front.) The function sky() takes care of the necessary drawing:
void sky(GLuint haze)
{
 //Modeled after cube front
 glBindTexture(GL_TEXTURE_2D,haze); //Texture "haze" holds the sky image
 glBegin(GL_QUADS); 
 glTexCoord2d(1.0,1.0);
 glVertex3f( (windowwidth()/SKY_SCALE), (windowheight()/SKY_SCALE),-SKY_DISTANCE); 
 glTexCoord2d(0.0,1.0);
 glVertex3f( -(windowwidth()/SKY_SCALE), (windowheight()/SKY_SCALE),-SKY_DISTANCE); 
 glTexCoord2d(0.0,0.0);
 glVertex3f( -(windowwidth()/SKY_SCALE), -(windowheight()/SKY_SCALE),-SKY_DISTANCE); 
 glTexCoord2d(1.0,0.0);
 glVertex3f( (windowwidth()/SKY_SCALE), -(windowheight()/SKY_SCALE),-SKY_DISTANCE); 
 glEnd();
}

This function is called near the beginning of each frame, before gluLookAt() is used to position the camera. This means that the sky quadrangle is always placed directly in front of the camera; it is simply drawn in the back of the scene, off in the distance (specifically in the plane defined by Z=-SKY_DISTANCE), regardless of camera position. The gradients used in the texture give a cheap illusion of lighting (or, at least, add interest to the scene).

Finally, in the code above, note that windowwidth() and windowheight() allow the program to obtain the screen dimensions, and SKY_SCALE is used to reduce the sky surface down to dimensions that are not needlessly large. This constant was set to 6.0f based on ad hoc tuning during testing.

Surface Culling

"Culling" is a process by which many hidden OpenGL surfaces can be excluded from the rendering process early in its evolution, resulting in a performance boost. It relies on a property of point orderings (such as surface definitions) as they are rotated in 3D space. Consider what happens when a polygon face is drawn, for example, using four successive points that happen to be in clockwise order when the face is at the front of the solid. If rotated to the back of the solid, without altering camera position/orientation, these same points will be in counter-clockwise order. OpenGL can use this property to determine which surfaces of a solid are facing the viewer, and render these faces only.

In the surface-drawing code given above, comments around each call to glVertex3f() detail how each face of the cube (as well as the single face of the sky/ground object) is rendered in counter-clockwise order when seen with the surface rotated to face the viewer (top right, top left, bottom left, and finally bottom right). This is because the OpenGL culling mode selected, GL_CCW, expects this. The code used to set up surface culling is located in the function initgl(), and is shown below:

glEnable(GL_CULL_FACE);
glFrontFace(GL_CCW);
glShadeModel(GL_SMOOTH);

User Input

Under GLUT, it is very typical for application code to pass handler function pointers into event-specific GLUT library functions at startup. Then, GLUT calls into the functions whose addresses were passed as it becomes necessary during the simulation process. This is a form of inversion of control which is very typical of APIs, especially those declared primarily in C or assembly language.

In the demonstration program provided here, this function wire-up is handled by the code shown below:
glutSpecialFunc(&arrows);      //"Special" key presses
glutKeyboardFunc(&keypress);   //Regular key presses
glutPassiveMotionFunc(&mouse); //Mouse move
The first statement wires up event handler arrows(), for arrow key presses. (The arrow keys are "special" keys in OpenGL's nomenclature.) Then, a handler is established for other key presses (keypress()). Finally, a handler is set up for the mouse motion event.

The OpenGL signatures for these functions are very intuitive. This allowed the author to focus on the algorithms used to simulate the physics of the random maze world. The function arrows() demonstrates how many of the issues associated with control and motion are addressed in the simulation code:
void arrows(GLint key, GLint x, GLint y) 
{
 if(key == GLUT_KEY_UP) 
  move(WALK_KEY_SENSE);
 if(key == GLUT_KEY_DOWN) 
  move(-WALK_KEY_REVERSE_SENSE);  
 if(key == GLUT_KEY_RIGHT)
  rot+=ROTATE_KEY_SENSE;
 if(key == GLUT_KEY_LEFT)
  rot-=ROTATE_KEY_SENSE;
}

This function accepts as its parameters a key code, followed by two parameters that convey the position of the mouse. These two parameters are not used here, since there is no special interaction between keyboard and mouse. Each of the four arrow keys is checked for. If the left or right arrow is pressed, the variable rot, which holds the viewer's angular position about his/her own "Y" axis, is adjusted using a compile-time sensitivity constant (ROTATE_KEY_SENSE).

If the up arrow (forward) or the down arrow (back) is pressed, a bit more work must be done. In these cases, the viewer is actually changing position, not just orientation. Collision detection thus comes into play (as abstracted over by the move() function), and this is discussed in the next section.

Mouse-based motion is somewhat more complex than keyboard-based motion. One reason for this is the fact that movement performed using the mouse is proportional to the mouse position; this is fundamentally more complex than the system of keyboard control shown above, which is based on movements of fixed size. Ultimately, though, supporting such proportional control is a simple matter of performing an additional subtraction, involving control position and the midpoint of the control's range (which is windowwidth()/2.0f or windowheight()/2.0f here). This subtraction establishes the magnitude of the user's command, and is multiplied by the appropriate sensitivity constant. These tasks are performed by the statements shown below:
if(yin<CONTROLLER_PLAY) 
   move((yin-windowheight()/2.0f)*-WALK_MOUSE_SENSE);
   
if(yin>(windowheight()-CONTROLLER_PLAY))
   move(((windowheight()/2.0f)-yin)*WALK_MOUSE_REVERSE_SENSE);
   
if(xin<CONTROLLER_PLAY || xin>(windowwidth()-CONTROLLER_PLAY))
   rot+=(xin-(windowwidth()/2.0f))*ROTATE_MOUSE_SENSE;

In the code shown above, the constant CONTROLLER_PLAY is used to establish a "dead spot" around the center of the mouse's range, which is necessary for stability. As in arrows(), user mouse actions ultimately lead to either a call to move() or an adjustment to rot. The variables xin and yin, which are discussed in detail below, hold the current mouse position.

Another complexity associated with mouse control is the fact that motion is not necessarily a result of an OpenGL event. For example, if the user pushes the mouse forward, an event is generated. But if the user leaves the mouse in this position, no further events are generated, and yet the user interface description given above for this simulation specifies that movement does continue to occur.

To support this mode of operation, the code provided here keeps track of the current mouse position in file-level variables xin and yin. These are edited by the handler mouse(); but it is drawscene(), which is called on a recurring basis, that actually inspects these position variables. Also, a static flag variable is used within mouse()to ignore the first mouse move event; this is triggered automatically at startup by OpenGL, and it should not be interpreted as a user action.

Collision Detection

The detection of player impact with a maze wall is made easier by the use of right angles in constructing the maze. The "Coordinate System" section above already gives the basic information necessary to determine which entry inmaze_innards() corresponds to the user's current position in the maze. If this array element contains NO_PATH, then it has been collided with.

After any move, such calculations are used in the code developed here to determine whether the user has impacted a wall. A slight threshold value is included into these calculations, which results in collisions happening somewhat before they would otherwise. This keeps the viewer from getting too close to the wall surface, which helps eliminate aliasing and glitches. The value of COLLIDE_MARGIN was set empirically during testing; however, the value selected does seem to translate well to disparate hardware.

The function collide() takes care of performing these calculations and determining if a collision has occurred, in which case it returns true. It begins as shown below:
bool collide() //Is player in a state of collision?
{
 int x,y;

 //Walls...
 if(x_at>=MAZE_EXTREME_LEFT-COLLIDE_MARGIN && 
   x_at<=MAZE_EXTREME_LEFT+XSIZE*FULL_CUBE+COLLIDE_MARGIN)
 {
  if( y_at<=(MAZE_EXTREME_TOP+FULL_CUBE)+COLLIDE_MARGIN && 
    y_at>=MAZE_EXTREME_TOP-COLLIDE_MARGIN)
  {
   return 1; 
  }

  if(y_at<=(MAZE_EXTREME_TOP+FULL_CUBE)+FULL_CUBE+
      (YSIZE*FULL_CUBE)+COLLIDE_MARGIN && y_at>= MAZE_EXTREME_TOP+
      FULL_CUBE+(YSIZE*FULL_CUBE)-COLLIDE_MARGIN)
  {
   return 1;
  }
}

This first section checks for collisions between the viewer and either of the two solid walls that surround maze_innards(). The first if determines whether x_at, the current position of the viewer in the OpenGL "X" dimension, is within the horizontal expanse of these walls. These walls both span the whole width of the maze, from MAZE_EXTREME_LEFT to MAZE_EXTREME_LEFT+XSIZE*FULL_CUBE. Note that COLLIDE_MARGIN is incorporated into each comparison, with the sign necessary to make the comparison more likely to return true.

The next if after that checks for intersection in the OpenGL "Z" dimension between the viewer and the upper of these two solid walls. Here, the variable y_at is inspected. Despite its name, this variable does indeed describe the position of the viewer in the OpenGL "Z" dimension; the "y" in the variable's name refers to the original "Y" dimension in the abstract, two-dimensional maze that underlies the simulation. The upper wall extends from MAZE_EXTREME_TOP to MAZE_EXTREME_TOP+FULL_CUBE, and these terms are present in the comparisons.

Finally, the third if shown above performs a similar check for intersection with the lower of the two solid walls. In this case, the comparison terms for the boundary both include an additional YSIZE * FULL_CUBE + FULL_CUBE in compared to the analogous terms in the top wall's if. This accounts for the vertical expanse of the maze proper, i.e. of the array pointed to by maze_innards(), along with the top solid wall.

The remainder of collide checks for the intersection between the viewer and those parts of the maze proper where walls have been placed. At a high level, this code operates by checking each element of the abstract maze (i.e.,maze_innards()) for a wall, using nested loops. 

For each wall found, the code checks to see if the viewer position is within the boundaries of the wall cube. The necessary comparisons are similar to the last comparison shown, except that instead of adding YSIZE * FULL_CUBE to MAZE_EXTREME_TOP to get the vertical collision zone, we must add  FULL_CUBE  multiplied by the wall's loop index to MAZE_EXTREME_TOP. A similar calculation must be made to verify the collision in the "X" dimension:

//Maze proper
for(y=0; y<YSIZE ; ++y )
{
  for(x=0; x<XSIZE ; ++x )
  {
   if((maze_innards())[x][y]==NO_PATH)
   {
    if( x_at>=MAZE_EXTREME_LEFT+x*FULL_CUBE-COLLIDE_MARGIN && 
      x_at<=MAZE_EXTREME_LEFT+FULL_CUBE+x*FULL_CUBE+COLLIDE_MARGIN && 
      y_at>=MAZE_EXTREME_TOP+(y+1)*FULL_CUBE-COLLIDE_MARGIN && 
      y_at<=MAZE_EXTREME_TOP+(y+2)*FULL_CUBE+COLLIDE_MARGIN )
    {
     return 1;
    }
   }
  }
}
If the code reaches this point and has not returned true, then no collision has occurred, and 0 is returned to the called:
    return 0;
}

Collision Handling

The detection of collisions is actually more straightforward, in many ways, than the handling of collisions. In the code described here, collision handling comes into play during a call to move(). That function calls collide() to check for a forward or reverse move resulting in a collision, and must take action of some sort whenever true is returned.

Simply reversing the move that led to the collision will result in a simulation where the camera freezes when it hits the wall. Rotation can still occur when this happens, since rotation does not involve a call to move(). This is how the user can escape the collision.

A more exciting and playable design has the viewer bounce backward (i.e., in the opposite direction from the move) by some amount greater than the move itself. The problem with this technique is that it can result in a second collision, or in fact in any number of cascading collisions. The algorithm ultimately decided upon here allows for some constant-driven bounce-back to occur, but also for this effect to be cancelled in cases where it leads to a subsequent collision. This cancellation is observed infrequently, but its existence prevents a host of infrequent-but-unacceptable issues involving collision detection, e.g., situations where the user can pass through walls.

The move() function, which is built around the algorithm just described, is shown below:
void move(GLfloat amt) //Move, incorporating collision and bounceback
{
  x_at+=cos(rot)*amt;
  y_at+=sin(rot)*amt; 
  if(collide()) //Don't let player walk through walls
  {
   x_at-=BOUNCEBACK*cos(rot)*amt;
   y_at-=BOUNCEBACK*sin(rot)*amt;
  } 
  if(collide()) //Bounced into another wall... just reverse original move
  {
   x_at+=BOUNCEBACK*cos(rot)*amt;
   y_at+=BOUNCEBACK*sin(rot)*amt;
   x_at-=cos(rot)*amt;
   y_at-=sin(rot)*amt; 
  } 
}
In the function shown above, the movement is first executed. The sine and cosine functions are used to effect motion in the direction indicated by rot. (The role played by these functions is similar to their role in constructing the Unit Circle). Then, if a collision occurs, bounce-back is applied. Finally, if this leads to yet another collision, the bounce-back movement is cancelled, and then the original move itself is cancelled as well. This results in the viewer's position simply freezing at the wall, as in a simplistic implementation.

Future Expansion

The supplied code handles the basics of first-person perspective simulation in OpenGL. One obvious direction for further work is the addition of more competition into the program, e.g., formal timing or score-keeping. The addition of some sort of enemy or non-player character into the simulation would also add interest.

The development of various levels, with different textures, is another potential avenue for expansion. In fact, much greater use of OpenGL features like lighting is possible.

Finally, it would not be that difficult to add more vertical motion to the game, e.g., some sort of jumping feature. Whether this is a cosmetic gimmick, a really useful maze-viewing feature, or even a system that allows the user to actually walk on and over the maze walls depends on the complexity of the implementation; but all of these variations are envisioned by the work presented here, which aims to be a fast, stable basis for many such applications.

License