I recently finished my first (ever) graphics project. It was conducted in Unity 5, were I leveraged my math and programming skills to procedurally generate navigable 3D mazes. To learn about Unity, I tried several online tutorials and videos, but some were found more useful than others. I would like to especially point out the tutorials by Jasper Flick, which were very helpful and have inspired the project and the code.1

When choosing to work with maze generation, I was inspired by Adam Savage’s Overlook Hotel maze model, which is a detailed replica of the hedge maze architectural model from Stanley Kubrick’s film The Shining. I was intrigued by the effort that he had put into the project and wondered how hard it would be to create a similar maze digitally, using 3D graphics.

Graph theory

The mazes were generated using graph theory, and two different algoritms were applied. First, a recursive backtracker, with a randomized depth-first search algorithm, was implemented to generate a perfect maze. Thus, the maze had only one path from any point in the maze to any other point in the maze (it contained no circular paths).2

2D maze generated with randomized depth-first search. 2D maze generated with randomized depth-first search.

Second, a randomized version of Prim’s algorithm was implemented to compare the results. Similar for both approaches (algorithms) is the notion of keeping track of cells or sides, respectively, until all have been visited and fully initialized. Also, both algorithms result in openings when encountering unvisited cells, while visited cells are walled off.

2D maze generated with randomized Prim’s algorithm. 2D maze generated with randomized Prim’s algorithm.

The two algorithms gave mazes with different appearances and user experiences. The randomized depth-first search algorithm generated long corridors with low branching. Also, a solution path passes through relatively many cells with this algorithm compared to other maze generation algorithms.3 On the other hand, randomized Prim’s algorithm had a quite a lot of branching and short dead ends. Also, it spreads from the starting cell in a way that makes it easy to get from anywhere to the starting cell, but hard to get anywhere else.4

Prim's algorithm: The maze grows at the frontier. Prim’s algorithm: The maze grows at the frontier.

Decorations

After generating the 2D representations of the mazes, these were be turned into 3D. Decorations and camera movement were added to make the mazes more interesting from a user perspective. The result looked something like this:

3D hedge maze with minimap and decorations. 3D hedge maze with minimap and decorations.

3D hedge maze after moving the camera upwards. 3D hedge maze after moving the camera upwards.

For those who would like to see more of the results and generation process, here are the videos showing maze generation, navigation and decorations:

The project is documented in detail in my Maze Generation blog.

  1. Especially the Maze tutorial

  2. L. Wan, X. Liu, T.-T. Wong, and C.-S. Leung. Evolving mazes from images. IEEE Transactions on Visualization and Computer Graphics, 16:2, pp. 287–297, March 2010. 

  3. W. D. Pullen. Think labyrinth - perfect maze creation algorithms, 2015. 

  4. Wikipedia. Maze generation algorithm, 2015.