Last edited April 09, 2008 by Sam Sun
Find this document at http://cheer.math.edu/reulab/web/qsun2

illiMaze: Daedalus Redrawn

By Qiancheng Sun

Abstract

My project will be a maze generator and maze solver. It will be capable of generating perfect mazes, or those with no loops and no dead ends. Mazes with this specification are both difficult for humans to quickly solve and simple for computers to solve recursively. After constructing a maze composed of 90 degree turns and walls, it will find the shortest path from beginning to end, where the beginning and end are user-defined. The program will utilize C++ and OpenGL.

History

Maze construction is a usual task in a typical computer programming/graphics class because it's useful in demonstrating recursion and is a visually pleasing puzzle. Further, mazes occur surprisingly often in classical and popular culture. Mythological examples embedded into literature include the Labyrinth of Crete, meant to hold the illegitimate son of King Minos. From such strange beginnings, it has evolved to appear in such formats as the newspaper "extra" sections next to Sudoku. From a serious though allegoical standpoint, mazes represent the twisting, winding, and unpredictable "journeys" that people go through, whether they be spiritual, educational, or personal in nature.

Feel free to look at House of Leaves, an experimental novel that I was vaguely reminded of during this project.

I chose this project for these reasons, but more importantly, building a maze allowed a great deal of flexibility. I wasn't sure what I could do in a Math198 project. Therefore, I was thinking that it wouldn't be too difficult to build a 2-D maze with the walls extruded vertically into the third dimension. The user/computer could still only move in a 2-D plane though. If this was straightforward, I might be able to add things such as texture maps to the maze walls. Or, I could build mazes with non-orthogonal paths or mazes in higher dimensions.

Progress Report

April 20th: I started coding the maze, first by looking up various maze generation algorithms with Google. I looked at a very thorough listing of maze types and maze algorithms at this site. I decided to use a method of building AND solving a maze with Depth-First Search. It seems like this method applies to a generalized tree-structure, which I only have a vague intuition of right now. I guess I could give a mathematics presentation on this, among other things.

April 25th: As I should've done in the beginning, I'm now using the basic graphical interface construct from the skeleton program. I may also use snippets of useful code from Aszgard if I can get it to compile on my laptop.

Fun Stuff

Various Maze Pictures

illiMaze Pictures

illiMaze Source Code

Sources Consulted

http://www.w3schools.com/HTML/html_links.asp

http://www.astrolog.org/labyrnth.htm

http://www.mazeworks.com/mazegen/mazetut/index.htm