This project generates a random maze which you can traverse. For those not feeling up to the challenege there is a cheat mode which will lead you straight to the exit.
Details
Building The Maze
The maze is stored in a variably sized 2D character array, where X's represent walls and spaces represent hallways. To start I fill the whole array with X's, and then randomly pick a spawn locaion and an exit. The only requirement for these being that the player will always spawn next to the outside wall, and the exit is guaranteed to be on a different wall than the player spawn.
Next I create paths of random size and direction starting at both the spawn location and the exit. Then a few more paths starting from random locations in the maze. Next I add a bunch of paths (specifically: (maze_width + maze_height) * 2) into the maze starting only from locations which are already on one of the previous paths. This allows the maze to become nicely connected.
With a maze built I now have to ensure that it is solvable. This is done through a basic graph depth first search starting at the spawn and stopping if the exit is reached. Assuming that the maze is solvable I check the length of the shortest path to ensure that it is at least maze_width moves long (This is further discussed in the Cheating section). If both of these cases are true then the maze is written out to a file. If one of these conditions is not true then the maze we currently have is scrapped and the builder starts again from the top.
The ascii file representing a maze layout
Displaying the Maze
All the graphics for this project are done using OpenGL, and all shapes are simple geometric primatives which have been texture mapped to look more realistic. The ground is tiled in 1x1 squares so that the maze could be of arbitrary size without stretching the texture. The maze itself is represented by an array of 3D vectors containing the wall positions in the world. The bottom left hand corner of the maze sits at (0,0) and the maze builds up and out from there. Since each walls base is of size 1x1, the wall's position in the world is simply its index in the 2D maze array!
An arial view of the same maze
Navigating the Maze
You are able to move throughout the maze using the wasd keys and look around using your mouse. This movement is accomplished using a pitch and yaw camera. In addition I have implemented collision detection on the walls by using simple interval testing to insure you don't cross the border of any wall.
The first person view while navigating the maze
Cheating
The maze may feel impossible to solve, but fear not! There is a handy built-in cheat function that will guide you to the exit when you press 'h'. This displays the shortest possible path from your position to the exit. This is done using the A* Graph Search Algorithm, which is a modified version of Dijstra's algorithm. This path is then sent back to be drawn in the same way as the walls of the maze. One additional wrinkle in the cheat path comes from giving them a bouncing animation, this required store the data as a 4D vector, instead of the standard 3D, where the 4th dimension holds a flag to say if the diamond was rising or falling.
The path leading to the exit is marked by green diamonds
References
A* Algorithm Implementation in c++
A* Algorithm Description
Previous Similar Student Project
Hope You Enjoyed!
Taylor Woods