Last Modified 12/16/09
Navigating a 4-Dimensional Maze
Connor Simmons, Math 198
The goal of this project is to create a 4-dimensional maze that a user can attempt to
navigate. Additionally, the maze will be solved by a computer
algorithm which can optionally be viewed or hidden by the user. The ability to move through
the 4th dimension will be visualized by colored fog.
This project will be written in C++ using OpenGL and will be implemented for The Cube.
- Generate a 2-dimensional maze, draw it to the screen.
- Add solving algorthim and incorporate it into the 2-d maze display.
- Expand the generation/solving algorthim of the maze into the 3rd dimesion.
- Display 3-dimensional maze in OpenGL by drawing cubes.
- Add perspective and lighting to the 3D scene.
- Apply texture mapping to the walls and floor.
- Expand generation/solving algorithm to the 4th dimension.
- Draw scene using scene (similar to 3d) but including fog effects to visualize a path through 4th dimension.
Kruskal's Algorithm and Maze Generation
Kruskal's Algorithm is an algorithm that, in graph theory, finds a minimum spanning tree for a connected weighted graph. When we represent a maze as a graph, however, we do not give the edges any weight and the algorithm merely finds a spanning tree. This is useful in the creation of perfect mazes, because we can represent each "room" in a maze as a node on a graph.
Maze Being Generated. Click on picture for larger view.
We start with every edge in place, so every adjacent room is separated from its neighbors. We then remove one edge (randomly) at a time, as long as the following two conditions are met:
- The two rooms (nodes) separated by this edge are not already connected by a path.
- The edge does not fall on the outer wall of our maze (the border).
We remove a total of (#rooms-1) edges, because this will ensure that every room within our maze is connected to every other.
In this project the algorithm used to solve a perfect maze is loosely based off Dijkstra's Algorithm, which is used to find a single-source shortest path tree through a graph. In solving a perfect maze, however, we are not concerned with distances, so much of Dijkstra's Algorithm can be simplified.
Maze being solved. Click on picture for larger view.
The maze solution, for a 2-dimensional maze, runs as follows:
1. If we are at the end of the maze, CELEBRATE. Otherwise:
2. If we did not just move left, move to the right and go to step 1. If we cannot move right or a "breadcrumb" is there, go to step 3.
3. If we did not just move up, move down and go to step 1. If we cannot move down or a "breadcrumb" is there, go to step 4.
4. If we did not just move right, move to the left and go to step 1. If we cannot move left or a "breadcrumb" is there, go to step 5.
5. If we did not just move down, move up and go to step 1. If we cannot move up or a "breadcrumb" is there, go to step 6.
6. We were unable to move in any direction, so place a "breadcrumb" in our current location and move back one space.
This will successfully navigate a perfect maze (eg. a maze with no loops) in a worst case of O(n^2) time.