MazeCreator

Generates mazes using various algorithms.

Special Thanks

Special thanks to Jamis Buck for writing the blog posts I used to learn these algorithms. Jamis Buck's blog.

Features

Algorithms

The currently supported algorithms are:

1. Kruskal
2. Prim
3. Recursive Backtracker
4. Aldous-Broder
5. Growing Tree
   1. Add oldest cell
   2. Add newest cell
   3. Add middle cell
   4. Add random cell
   5. Allow mixing of methods
6. Hunt-and-Kill
7. Wilson
8. Eller
9. Recursive Division
10. Sidewinder
11. Binary Tree
    1. North-West
    2. North-East
    3. South-West
    4. South-East

Step generation

Each step of generating a maze can be written to a file using the -v flag.

Example

Running MazeCreator -v demo.steps 2 2 may produce the maze:

#####
#  X#
### #
#S  #
#####

and a file names demo.steps that contains:

#####
# # #
#####
# # #
#####

#####
# # #
### #
# # #
#####

#####
#   #
### #
# # #
#####

#####
#   #
### #
#   #
#####

#####
#   #
### #
#S  #
#####

#####
#  X#
### #
#S  #
#####

Build

CMAKE

To build, simply run:

mkdir build
mkdir lib
mkdir bin
cmake -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build

The compiled program will be found in bin.

Generate a maze

Simply running MazeCreator will generate a 10x10 maze.

Running MazeCreator <W> <H> will generate a maze of size WxH.

Generating example

This is an example of a generated maze:

#####################
#        X  # #   # #
### ##### # # # ### #
# # #     #       # #
# # ### # ### ##### #
# # # # # #     # # #
# ### # ##### # # # #
#     #   # # # #   #
# ### # # # # # # # #
# #   # # #   #   # #
# # # # # ######### #
# # #   #     #     #
# ##### ### ### #####
# # # # # # #       #
### # ### ### ### ###
#   #           # # #
# ######### # ### # #
#       # # # #     #
# ### # # ### ##### #
# #   #       #    S#
#####################

Symbol Definition

The following symbols are defined for a maze:

• # - Wall
• space - Path
• S - Starting location
• X - Destination
• : - Observing
• Q - Queued

Format

A valid maze will have:

1. A border of walls.
2. A start labeled S.
3. An end labeled X.

The maze consist of cells. Each cell is defined as a 9x9 grid of text.

This is an example of a cell:

###
# #
###

Only the 4 cardinal directions (up, down, left, right) are considered for walls. The corners are included mainly for alignment and ascetics.

This is an example of a cell with no walls:

# #
   
# #

Two neighboring cells will share the same wall.

This is an example of two neighboring cells (1 and 2):

#####
#1 2#
#####

This is an example of four cells in a 2x2 formation:

#####
#1 2#
### #
#3 4#
#####

Notice that for a maze of size MxN, it takes $(2M+1)\times(2N+1)$ characters to store the maze.

Notes:

Observing cells (:) only come into play for verbose step generation. The observing cell allows the user to see which cells the algorithm is currently considering for processing.

Queued cells (Q) cells only come into play for verbose step generation. The queued cells are cells that the algorithm is remembering, but not actively observing.

TODO

• Maze Viewer (text based)
• Maze Generator
• • Kruskal
• • Prim
• • Recursive Backtracker
• • Aldous-Broder
• • Growing Tree
• • • Add oldest cell
• • • Add newest cell
• • • Add middle cell
• • • Add random cell
• • • Allow mixing of methods
• • Hunt-and-Kill
• • Wilson
• • Eller
• • Recursive Division
• • Sidewinder
• • Binary Tree
• Verbose Steps
• Write Help