Maze Builder

This program is designed to allow you to build (reasonably) memory and time efficient mazes. It is a CLI tool that can produce pngs of mazes with arbitrary greyscale foreground and background colors. The cli is built in python but uses a maze package written in C++, for efficiency. There are two algorithms, Wilson's Algorithm and the Hunt and Kill algorithm; the former tends to make mazes with shorter corridors and more turns where the latter tends to favor longer straight segments.

My publication outlining project intent

Note that a lot of the details in this publication are no longer accurate. A follow-up paper will be submitted to PACISE 2025 with updated details. Almost all discussion about memory is now irrelevant, as it has all been optimized.

Setup

All setup instructions will be provided assuming a Linux environment. If you are on Mac or Windows, it should be easy enough to translate them.

This project requires Python 3.11 or higher and CMake 3.29.2 or higher to run

1. Clone the repo
2. Navigate to the top level directory (should be ./MazeBuilder)
3. If you aren't already in a virtual environment, create one and enter it.
4. Type "pip install -e ." and wait until it says "maze ... successfully installed"
5. Type "python mazebuilder.py" to generate a maze using the default configuration

Usage

This section will be split into two sections: basic usage and profiling. This is because a number of the flags available only really matter if you want to profile this program or your CPU.

The default configuration generates a 50 x 50 maze with Wilsons algorithm serially and outputs it as a black maze with a transparent background to a file named with the date and time of generation to MazeBuilder/output.

Basic Usage Commands

-h, --help - displays a help menu that lists all of this information
-a, --algo [wilsons, hk] - allows manual selection of the algorithm used for maze generation (default is wilsons)
-s, --seed N - allows seeding the random number generator. The same seed will guarantee the same maze on successive invocations given that the algorithm used is the same as well.\ (default is a random signed 4 byte int generated with urandom)
-w, --width N - allows definition of the width of the generated maze (default 50)
-l, --length N - allows definition of the length of the generated maze (default 50)
-o, --output - allows renaming of the output pdf (default is the date and time of generation)
-n, --nopng - skips png generation (default false)
-fg, --foreground - allows definition of the color of the maze walls. Some helpful starting values: black = 0, dark grey = 65, light grey = 135, white = 255 (default 0)
-bg, --background - allows definition of the color of the background of the image. Some helpful starting values: 0 = transparent, 65 = light grey, 135 = dark grey, 255 = black (default 0)
-e, --edgewidth - defines the number of pixels on each edge of each cell in the maze. This means that the generated png will be width * edgewidth x length * edgewidth. BE CAREFUL CHANGING THIS - values too small will result in a solid image and values too large will make the walls hard to see, as they do not grow in thickness proportionally to the edge width (default 12)

Profiling Commands

-r, --repeat N - generate a maze N times (default 1)
-ls, --lenstep N - amount to increase the length of the maze by between repetitions (default 0)
-ws, --widstep N - amount to increase the width of the maze by between repetitions (default 0)
-rn, --repeatnum N - number of mazes to generate before stepping up length and width (default 1)
-c, --csv filename - export maze data (seed, size, time, valid generation) to csv file filename. This option automatically disables png generation (default filename is algorithm-time.csv)
-p, --parallel - parallelize maze generation (default false)
-nc, --num-cores N - override to select the number of cores used for parallelization (default is the result of multiprocessing::cpu_count())
-t, --test - test each maze after generation to insure it can be solved. This flag is automatically enabled if a csv is being generated. This flag prints every error found with a given maze to stdout (default false)

Learn about the algorithms

Original Wilsons Paper
Jamis Buck's blog post about Wilsons
Jamis Buck's blog post about Hunt and Kill

Acknowledgements

Thank you to Dr. Zoppetti, my advisor, for all his help (and occasionally telling me to get it together). His encouragement made the worst hills on this journey easier to climb.

Thank you to Jamis Buck. He has no clue who I am, but his website has very well decomposed explanations of how different maze generation algorithms work. His explanations of these are more clear than mine could be, so his links are above.

Thank you to Will Killian. He has sat in on a number of my Thesis progress meetings and always had incredibly helpful and insightful additions. His contributions pushed me down paths I wouldn't have walked otherwise, and I learned a lot in the process of implementing those suggestions.