Tip

Scroll to the bottom for GIFS

aMazeGen

A perfect maze generator with the purpose of illustrating a few of the algorithms for both generating and solving them

The definition of a perfect maze is one in which all cells are reachable and any two cells will have only one path between them

The primary goal of this project was to learn Python. Mazes have always fascinated me so to accomplish this task I decided to create this project

Features

Execution

Note

See release notes for details

There are a few methods of running this program

User can

• Run an executable file to open the guided text-based interface
• Run the program from a terminal with arguments to bypass the interface (mistakes will print the expected usage)
• Compile for non-windows platforms from source with PyInstaller

Interface

Once the user has entered the correct parameters, they are greeted with the TKinter GUI where they can select an animation timestep and click the button to begin

The order of events are as follows

• Maze is generated at the timestep specified with colored animations
• User can change timestep or pause during generation
• Wait for user input to begin solution
• User can change timestep or pause during solution
• User can restart the solution or close the program

Generation Algorithms

I chose these based on what I thought looked the most interesting to watch in action and the fact that they all generate "perfect" mazes

Wilson's

This algorithm can be incredibly slow especially on larger mazes for the first few iterations, but it is my personal favorite of the methods. It is also one of the few algorithms capable of generating completely unbiased maze.

Steps

1. Start with a random cell
   • Add cell to maze (WHITE)
2. Choose another random unvisited cell A
3. Traverse "walk" the maze from cell A until a cell that is part of the maze is reached (RED)
   • If at any point this path encounters itself (loop), backtrack to this collision cell
4. Add "walk" path cells to the maze (WHITE) and remove walls between cells
5. Repeat from step 2. until all cells are visited

Prim's

The following algorithm is a little more efficient than the last. However it results in mazes with many short paths due to its generation technique. It is fun to watch, as it looks like a slow growing explosion from the starting point.

Steps

1. Start with a random cell A
   • Add cell to maze (WHITE)
2. Add cells neighboring A to "frontier" (RED)
3. Choose a random frontier cell B
   • Add frontier cell to maze (WHITE)
   • Carve path back to random cell that is part of the maze
4. Expand frontier from cell B (RED)
5. Rpeat from step 3. until all cells are visited

Eller's

This is the most complex of the generation methods, but in its complexity are some benefits. This is the only algorithm that can generate endless mazes in linear time and even maintain its minimal memory requirements by only needing to keep track of the sets for the current and previous row.

Steps

1. Add each cell in the first row to its own set (RED)
2. Moving from left to right
   • Randomly remove vertical (right) walls of cells not a part of the same set
   • If a wall was removed, join the sets of cells on the left and right (WHITE)
3. Moving from left to right
   • Randomly remove horizontal (bottom) walls
   • If a cell is the only member of its set, remove the bottom wall
   • If a cell is the only member of its set with a bottom wall, remove this wall
   • If a wall was removed, join the cell below to the set above (PINK)
4. Move to the next row and add each cell not a part of an existing set to its own new set
5. Repeat from step 2 until the last row
6. Moving from left to right
   • Remove vertical (right) walls separating cells of different sets
   • If a wall was removed, join the sets of cells on the left and right (WHITE)
   • All cells in the bottom row should be a part of the same set

Solution Algorithms

I selected these particular solutions because the third algorithm is a nice combination of the first two with the addition of a heuristic

Depth First Search

This algorithm is totally random and as such can end up exploring most of the maze before finding the exit or get lucky and go straight to the end. As such, each run on the same maze will result differently.

Steps

1. Visit a random unvisited neighbor (RED)
2. If all neighbors are visited, backtrack until one is unvisited (PINK)
3. Repeat from step 1 until exit is reached

Breadth First Search

BFS operates much like Prim's, but for solving the maze instead. This algorithm expands in every direction, with each iteration one step further from the start. Each run of this method on the same maze will be identical.

Steps

1. Visit each unvisited neighbor (RED)
2. From each now visisted neighbor (PINK) repeat step 1
3. Continue until exit is reached

Best First Search

The final solution algorithm operates a little like both of the previous methods. It has a singular travel path like DFS, but can branch off in another direction like BFS. The determination of where it branches off is a heuristic based on cell distance from the exit.

Steps

1. Measure the distance from each neighboring cell in path to the exit
   • Measured cells were checked, but not visited are YELLOW
2. Visit the closest (to exit) unvisited neighbor (RED)
   • Previously visited path cells are PINK
3. Repeat from step 1 until exit is reached

Scale

This program can handle mazes of many sizes if the processing power is available, I decided to cap the width/height at a maximum of 500 with a minimum of 3. The program will lag a bit during startup at higher bounds due to the increased initialization that has to occur.

I also setup the GUI so that it will scale the UI + cells to fit in a window that is 70% of the screen size its running on.

Asymmetric Dimensions

The app will also handle asymmetric sizes and take into account the aspect of the dimensions provided to size the UI and cells accordingly

Review

Working with Python was a pleasant experience. I appreciated the simplicity of the syntax and the speed at which I could go from writing code to running my program. There was not a lot of setup involved. Packaging the app was also very streamlined and took next to no input from myself with PyInstaller. There seems to be limitless numbers of libraries and extensions available as well. You can choose which constructs if any you want to include from more robust languages like abstract classes or enums.

I started out planning to use MatPlotLib for the GUI and animation and got so far as to be running the animations with it. However it turned out to be much too slow due to how MPL manages its drawn plots and has to update every drawn object on every frame. It would get exponentially slower above a grid size of 15x15. I tried many methods to get around it or speed MPL up to no avail. I ended up scrapping that code and rewriting the GUI with TKinter, which in hindsight was much more appropriate for this task. Now I can get up to a grid size of 500x500 with little to no slowdown in animation at least.

The algorithms were all fun to implement and see executed in real time. Eller's was easily the most challenging. There is not a lot of documentation anywhere regarding how the algorithm works and its a difficult method to wrap your head around in general. This was part of the reason I chose it, but it did take some effort to get through.