Maze generations: Algorithms and Visualizations.

Hybesis - H.urna
Nov 18, 2019 · 15 min read

Introduction

We will first have an overview of the maze world, we will then explore 6 different strategies and algorithms to generate random mazes; we will learn their pros and cons and how to choose the right one.

For each of them, we can play with interactive visualizations online and download the source code used : H.urna

Note: the illustrated glossary is at the bottom of this story.

Objectives

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.

Why do we enjoy so much mazes?

“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 mazes on cereal boxes

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

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.

Let us build them !

1. Binary Tree

Binary Tree Maze Generator is one of the very rare algorithms with the ability to generate a perfect maze without keeping any state at all: it is an exact memory-less Maze generation algorithm with no limit to the size of Maze you can create. It can build the entire maze by looking at each cell independently. This is the most straightforward and fastest algorithm possible.

Mazes generated are real Binary Tree Data Structure (cf. following images) while having a very biased texture (cf. Texture section).

We turn it by 45 to help the visualization.

Decomposing it within a path tree makes it fully clear.

How To Build

As its name suggests, it merely requires you to choose between two possible options at each step: For each cell in the grid, toss a coin to decide whether to carve a passage north or west.

Steps

  • For each existing cell in the grid:
  • 1. Get if they exist, north or west neighbors.
  • 2. Toss a coin to connect with one of them.
  • It is already done!

Texture

Binary tree Mazes are different from standard perfect Mazes; since about half the cell types can never exist in them. For example, there will never be a crossroads, and all dead ends have passages pointing down or right, and never up or left.

The Maze tends to have a strong diagonal bias from upper left to lower right, where the Maze is much easier to navigate from the lower right to the upper left. You will always be able to travel up or left, but never both. Then, leading to the top left corner, you can always deterministic travel diagonally up and left without hitting any barriers to reach the root.

Last but not least, two of the four sides of the maze will be spanned by a single corridor due to its directional construction.

2. Depth First Search (DFS)

Depth First Search (DFS) Maze Generator is a randomized version of the depth-first search traversal algorithm. Implemented with a stack, this approach is one of the simplest ways to generate a maze.

How To Build

Let us first have a look at the DFS traversal algorithm: One starts at any cell and explores as far as possible along each branch before backtracking.

To generate a maze, we have to randomize the traversal: meaning we pick a random but unvisited neighbor to continue our traversal. When we hit a dead end (cell with no unvisited neighbors), we ‘backtrack’ to the most recent cell in the stack.

Steps

  • Choose a starting cell in the field and add it to the stack.
  • While there is a cell to be handled in the stack:
  • 1. Pop cell from the top of the stack.
  • 2. Connect and visit all available neighbors from the bottom, left, right, top and unvisited.
  • 3. Randomly select the one to be on the top and Push those neighbors on the stack.

Texture

Mazes generated have a low branching factor and contain many long corridors, because the algorithm explores as far as possible along each branch before ‘backtracking’ (using the previous cell on the stack).

The River characteristic means that when creating the Maze, the algorithm will look for and clear out nearby cells: It flows into the Maze like water. DFS Mazes tend to have a main River, resulting in a large amount of short dead ends.

All of this makes depth-first an excellent algorithm for generating mazes in video games.

In mazes generated by that algorithm, it will typically be relatively easy to find the way to the root since most paths lead to or from there, but it is hard to find the way out.

3. Kruskal’s

Kruskal’s Maze Generator is a randomized version of Kruskal’s algorithm: a method for producing a minimal spanning tree for a weighted graph.

Kruskal’s is interesting because it does not “grow” the Maze like a tree, but instead carves passage segments all over the Maze at random, making it very fun to watch. Still, it results in a perfect Maze in the end.

The counterpart is to require storage proportional to the size of the Maze, along with the ability to enumerate each edge between cells in random order (Using here a set of edges and taking them randomly).

How To Build

Once we have all of the edges into a big set and a unique subset id associated to each cell; all we need is to pick an edge at random, check if the adjacent cells belong to a different subset and unify them by setting the same id for all cells of both subsets.

Steps

The randomized algorithm changes the first loop step so that instead of pulling out the edge with the lowest weight, you remove an edge from the set at random.

Texture

Mazes generated tend to have a lot of very short dead-ends, giving the maze a kind of “spiky” look. This algorithm yields Mazes with a low “River” factor, but not as low as Prim’s algorithm.

4. Prim’s

Prim’s Maze Generator is a randomized version of Prim’s algorithm: a method for producing a minimal spanning tree from an undirected weighted graph.

Prim’s algorithm creates a tree by getting the adjacent cells and finding the best one to travel to next. To Generate mazes using Prim’s, we will instead take a random cell to travel to the next one.

Although the classical Prim’s algorithm keeps a list of edges, here is studied the modified version for our maze generation by maintaining a list of adjacent cells. Running faster, it still requires storage proportional to the size of the Maze.

How To Build

Prim’s approach starts from any cell and grows outward from that cell. The algorithm keeps a set of the possible cells the maze could be extended to. At each step, the maze is extended in a random direction, as long as doing so does not reconnect with another part of the maze.

Steps

The randomized algorithm changes the cell connection, so that instead of pulling out the cell with the lowest weight, you connect a cell at random.

Texture

Mazes generated by Prim’s algorithm share many of the characteristics of those created via Kruskal’s algorithm, such as having an abundance of very short dead-ends, giving the maze a kind of “spiky” look. The algorithm also yields mazes with a very low “River” factor and a rather direct solution.

It will usually be relatively easy to find the way to the starting cell, but hard to find the way anywhere else.

5. Recursive Division

Recursive Division Maze Generator is the fastest algorithm without directional biases. While recursive division stands out concerning parallelism, this algorithm is particularly fascinating because of its fractal nature: you could theoretically continue the process indefinitely at finer and finer levels of detail (smaller and smaller scales).

This algorithm is somewhat similar to recursive backtracking, since they are both stack based, except this focuses on walls instead of passages. As a Wall Builders generator, the process begins with ample space (all cells are connected) and adds walls (disconnect cells) until the maze results.

How To Build

The general idea of a recursive division is very straightforward: We start with an empty “room”, split it in two part with a wall, make a hole in the wall and repeat this on the two newly created rooms.

Steps

  • Begins with ample space (all cells are connected).
  • 1. Randomly build a wall within this space.
  • 2. Randomly build a path within this wall.
  • 3. Recurse on both sides of the wall.

At every step, you still have a valid maze. Each repetition of the algorithm increases the level of detail. This could lead to an infinite maze level diving animation.

Texture

Mazes generated by Recursive Division algorithm are in the form of the rectangular nested fractal. The method results in mazes with long straight walls crossing their space, making it easier to see which areas to avoid. It also tends to have a lot of short dead-ends.

6. Sidewinder

Sidewinder Maze Generator is very similar to the Binary Tree algorithm, and only slightly more complicated. Furthermore, the Sidewinder algorithm only needs to consider the current row, and therefore can be used to generate infinitely large mazes (like the Binary Tree).

While binary tree mazes have two of its four sides being one long passage, a Sidewinder mazes have just one long passage.

How To Build

while it is related to the Binary Tree algorithm, it is a bit more complicated. However, words do not do it justice; it is a lot more straightforward than it sounds.

Steps

  • For each row in the grid:
  • 1. For each cell randomly decide whether to carve a passage leading East
  • a. If the passage is carved add the cell to the current run set
  • b. If the passage is not carved, randomly pick one cell from the route set, carve a passage leading North and empty the current run set

Texture

Any maze generated by the Sidewinder algorithm will never have any North-facing dead-ends, which means you can never get stuck when moving from South to North. This is similar to the Binary Tree algorithm, which will never have any dead-ends in the direction of its bias.

A sidewinder Maze tends to have an elitist solution, where the East path is straightforward, but many long false paths are leading down from North path next to it.

The solution is deterministic without error from bottom to top: it will never double back on itself or visit a row more than once, although it will wind (or wave) from side to side.

H.urna Explorer

We may play with those generation algorithms freely on H.urna Explorer.

Glossary

The dimension class is basically how many dimensions in space the maze covers. Types are:

2D: Most mazes are this dimension, it’s always possible to display them on a paper sheet and navigate it without overlapping any passages.

H.urna Blocks — Globo in mazes (Level 10)

3D: maze with multiple levels, where passages may go up and down in addition to the 2D directions. A 3D maze may be seen as 2D mazes stack on each other.

Maze game toys that can be found in some shops

Higher dimensions: It’s possible to have 4D and higher dimension mazes. These are sometimes rendered as 3D mazes, with special “portals” to travel through the 4th dimension (e.g. “past” and “future” portals).

Here is a 4D maze game, just think it as a 3D maze that can be modified while playing (e.g. over time, you will have a time controller additionally to the 3D moves).

Weave (2.5D): A weave maze is basically a 2D (or more accurately a 2.5D) maze, but where passages can overlap each other. For instance real life size mazes that have bridges passing above other passages.

A real life maze with bridges. This is the Longleat Hedge Maze build in 1975 in England.

Hyperdimension — Hypermaze

The hyperdimension class refers to the dimension of the object you move through the maze, as opposed to the dimension of the maze environment itself (hypermaze can only exist in a 3D or higher dimension environment). A hypermaze increases the dimension of the solving object and the passages themselves.
In a normal Maze you move a point through it, and the path behind you forms a line.
In a hypermaze you move a line through it, and your path forms a surface!

Hypermaze:
Orthographic rendering of a perfect, and very complex, hypermaze (73x73x73 cubes). Note there’s literally billions of ways of arranging the string across and moving it into one of the hypermaze’s faces and because this is a “perfect” hypermaze, only one solution and hence initial starting configuration actually works!
Source: Walter D. Pullen using Daedalus Software

Routing

Routing refers to the types of passages geometry resulting from the maze generation strategy.

Braid — Partial Braid: A “Braid” Maze means one without any dead ends. Such a Maze uses passages that coil around and run back into each other (hence the term “braid”) and cause you to spend time going in circles instead of bumping into dead ends. A well-designed braid Maze can be much harder than a perfect Maze of the same size.
Note that the adjective “Braid” can be used quantitatively. A “heavily braid Maze” will includes many loops or detached walls.

You won’t get stuck in any cul-de-sac.
Source: Wikipedia

Perfect — Simply-Connected: All the maze generation proposed at H.urna have a perfect routing. A “perfect” maze means being without any loops, closed circuits and inaccessible areas. From each point, there is exactly one path to any other point : the maze has exactly one solution. In Computer Science terms, such a maze can be described as a spanning tree.

Maze tree generation and flooding showing structure and duality between the maze and its spanning tree representation.
Source: Michael Jeulin-L using H.urna Explorer

Sparseness: A sparse Maze is one that doesn’t carve passages through every cell, meaning some are left uncreated. This amounts to having inaccessible locations, making this somewhat the reverse of a braid maze. A similar concept can be applied on wall adders algorithms (e.g. the Recusive Division), resulting in an irregular maze with wide passages and rooms.

Sparse maze with big rooms from a Recursive Division generation algorithm.
Source: Michael Jeulin-L using H.urna Explorer

Unicursal: A unicursal Maze means one without any junctions. Such mazes are also called labyrinth, there are no tricks or dead ends : they have a single circuitous path instead and are most often used for relaxation, meditation or spirituality.

The mysterious Christ in the Labyrinth of Alatri showing unicursal pattern.

Tessellation

The tessellation class is the geometry of the individual cells that compose the maze. You may imagine any geometry you want; here is a small list of the common ones : Orthogonal (Rectangle cells), Crack (Amorphous), Delta (Triangle cells), Fractal (Recursive), Omega (Non-orthogonal), Sigma (Hexagon cells), Theta (Concentric Circles of passages), Upsilon (Octagons and Squares cells), Zeta (Orthogonal with diagonal passages allowed)…
Images talk more than words, see below some of those ‘common’ types:

Orthogonal: Also named Gamma, its a standard rectangular grid where cells have passages intersecting at right angles.
Source: Michael Jeulin-L using H.urna Explorer

Sigma: A Sigma maze is composed of interlocking octagons.
Source: Dr. Mc Children’s Book

Theta: A Theta maze is composed of concentric circles of passages.

Fractal: A fractal maze is composed of smaller mazes. An infinite recursive fractal maze is a true fractal and is in effect an infinitely large mazes.

Source: Curvature Of The Mind

Texture

The texture class is subtle and describes the style of the passages in whatever routing, whatever geometry. This property is more qualitative than quantitative one.

River: texture flowing like rivers. Here a river maze from our Depth First Search (DFS) generator.
Source: Michael Jeulin-L using H.urna Explorer

Topology

The topology class describes the geometry of the space the maze as a whole exists in:
Normal: standard maze in Euclidean space.
Planar: any maze with an abnormal topology. Examples are mazes on the surface of a cube, tore, sphere etc.

We hope you had fun with this dive into mazes.

Analytics Vidhya

Analytics Vidhya is a community of Analytics and Data…

Hybesis - H.urna

Written by

Learn sciences with your senses

Analytics Vidhya

Analytics Vidhya is a community of Analytics and Data Science professionals. We are building the next-gen data science ecosystem https://www.analyticsvidhya.com

More From Medium

More from Analytics Vidhya

More from Analytics Vidhya

More from Analytics Vidhya

The Illustrated Word2vec

More from Analytics Vidhya

More from Analytics Vidhya

Financial Transaction Fraud Detection

219

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade