We will explore different strategies and algorithms to generate random mazes; we will learn their pros and cons and how to choose the right one for the job.

For each of them, we can play with interactive visualizations online, consult copiously illustrated descriptions and download the source code used.

To get fun.
To enjoy animations of our maze constructions.
To explore.

What else?

We will learn how to code and generate mazes step-by-step. We will also practice algorithmic thinking and programming concepts such as adjacency lists, memory efficiency, recursion, spanning tree, speed efficiency.

What is next?

Now that we handle maze creation, we may try to find the way out with pathfinding algorithms.

The first thing to do when studying an algorithm is to understand the data.
What is the input? What is the output?
Here is the kind of board we will generate here.

How is the data structured?
Here is a labyrinth with a few more details.

In this grid, each box represents a node. A connection between two nodes is represented by a path between two boxes. This information is also displayed textually (top left tooltip in the image). Here, our mouse is on the first node (x:0, y:0) and displays connections with the nodes (x:0, y:1) and (x:1, y:0).

We choose to describe our grid (or graph) using an adjacency lists data structure. The idea is pretty simple : an array of nodes with node storing the list of their neighbors. Easy to create, easy to manipulate, here is how the data could be represented in JSON :

[
  {
    "x":0, "y":0,
    "neighbors":[1,5]
  }, {
    "x":0, "y":1,
    "neighbors":[0,2]
  }, {
    "x":0, "y":2,
    "neighbors":[1,3,7]
  }
  ...
] 

The node id is given by its array index, this id is used to refer to the neighbors.
Yes, it’s that simple! It includes all the information we need to go through and to visualize the maze.

Perfect, we know everything to build our mazes!

Note: A grid can use a non-grid maze generator. Here, grids are used for explanations as it is easier to understand, work and visualize.

“Your mind is a walled garden. Even death cannot touch the flowers blooming there.”
(Ford - Westworld)

For thousands of years, humans have been fascinated by mazes and labyrinths : they built them, told stories about them, created games and puzzles around them, and even studied animal comportment within them.

Please note that maze and labyrinth do not have the same meaning. Compared to mazes there are no tricks or dead ends on labyrinths : they have a single circuitous path instead (they are unicursal) and are most often used for relaxation, meditation or spirituality.

Itoi Labyrinth - Man in the maze (described within the spiritual section below)

Labyrinth board game

The classical mazes on cereal boxes

Giant Ice Maze as the largest (2006) in the resort town of Zakopane, Poland

You may find tons of movies about mazes.

Maze of Life and the Prevailing Uncertainty

According to ancient Greek legend, the original maze was built by the architect Daedalus and his son Icarusto to house the Minotaur: a creature with the body of a man and the head of a bull. The legend further tells that Daedalus had so cunningly made the maze, he could barely escape it after the construction.

From the mythological mazes of Ancient Greece to the massive vegetation/ice/stage/corn mazes of the 21st century, here are 3 of the main reasons why we think mazes are so attracting.

Entertaining

Mazes are confusing and comforting at the same time: we are lost, but heading toward an existing exit. It makes it very entertaining and addictive.

Since the 16th century, mazes were meant to entertain, as well as to provide private, out-of-the-way places for secret meetings. Nowadays, they are in all forms and you may find them everywhere : on almost all of the cereal boxes, at amusement parks (e.g. Alice in Wonderland, Mirror labyrinth at the fair), in board games (e.g. the game that's literally named "Labyrinth"), in video games (almost in all of them), in movies (e.g. the film that's literally named "Labyrinth") etc.

Educative

Children seem to have an almost immediate and deep natural connection with mazes. They will take on the challenge of almost any maze. Maze provides the experience of problem solving while kiddos see it as a game. Instead of hurt feelings or embarrassment a classical problem may have, mazes assist anyone to calm down, make transitions, and focus.

Mazes particularly help children to develop skills such as:
- Planning and brainstorming various strategies.
- Getting spatial representation and developing orientation.
- Scanning complex environment and memorizing paths.
- Relaxing.

Spiritual

There is love in the labyrinth
There is darkness in the labyrinth
The exit may not be where you think it is

We all are on a path. The labyrinth is a metaphor for life's journey; a symbol that creates a sacred space and place that takes us out of our ego to that which is within. Ancient labyrinths were designed to be serene and introspective. In some lands, young men would walk through a labyrinth as part of their initiation into adulthood.

Unicursal labyrinth patterns like the “Itoi” (“Man in the Maze”) above may represent life's cycles, constant motion, and the choices we are confronted with. The right choices lead us to the point of harmony with all things, no matter how hard or long the road is taken. At the center of the maze is a circle, which stands for death. Death is not the exit, but the beginning of a new journey and, thus, to a new cycle.

• Astrolog by Walter D. Pullen
• Deadalus: The world’s most sophisticated Maze program by Walter D. Pullen
• The maze book for programmers by Jamis Buck
• Wikipedia