visualizing mazes

by thomas graham, 3155640

  1. introduction
  2. the binary tree algorithm
  3. eller's algorithm
  4. the recursive tree algorithm
  5. the growing tree algorithm
  6. about this project

maze-building is a simple problem with a world of solutions

Building a maze: how hard could it be? Take a start, find an exit, and throw a bunch of twists in between.

Try getting an algorithm to do that. To automate any solution, we have to reason in very explicit terms. We have to tell the algorithm what a maze is, what a twist is.

This explorable will show how simple tasks have many approaches. Maze building is a world of solutions finding their way around a single problem.

some approaches are dead simple

The binary tree algorithm, while unintuitive and inefficient, follows a very basic set of rules.

the binary tree algorithm

In a two-dimensional grid:

  1. Start at top-left corner.
  2. Connect the current cell to its northerly or easterly neighbour.
  3. Move one cell east. If the current cell has no easterly neighbour, start the next row.
  4. Repeat steps 2 and 3.
slower

faster

algorithms leave fingerprints on their results

The binary tree algorithm has two notable characteristics:

  • Since connections follow two possibilities, mazes have a strong diagonal tendency.
  • Since the top row can only connect east, it always forms a straight line.

different algorithms have different priorities

Eller's algorithm prioritizes speed. By handling rows as units, it readily keeps pace with grids of any size.

Although Eller's algorithm is fast, it is much harder to implement than a binary tree algorithm.

eller's algorithm

In a two-dimensional grid:

  1. Randomly assign a group to each cell in the top row.
  2. Randomly connect neighbouring cells of different groups, merging their groups as you go.
  3. For each group, create at least one vertical connection to the next row. Add the newly connected cell to the group.
  4. In the next row, give each unvisited cell its own set.
  5. Repeat steps 2-4 until the last row.
slower

faster

eller's algorithm outperforms the binary tree

Play through this example a few times.

Time after time, Eller's algorithm runs ahead of the binary tree algorithm. Partially handling the next row in advance gives it an edge.

Blue: Eller's algorithm

Red: Binary tree algorithm

algorithms that wander

The recursive backtracker algorithm takes a different approach than the methods shown so far.

Instead of proceeding in a linear fashion, it snakes around the grid, building the maze from a central point.

the recursive backtracker algorithm

In a two-dimensional grid:

  1. Pick any cell.
  2. Connect with any unvisited neighbour and set that neighbour as the current cell.
  3. If all neighbours have been visited, move back to the last cell with unvisited neighbours.
  4. Repeat steps 2-3 until the algorithm moves back at the starting point.

Blue cells had unvisited neighbours when last passed over.

slower

faster

the recursive backtracker is dead slow

Although it's pretty to watch, the recursive backtracker is an absolute turtle.

Play through this example a few times.

Between Eller's algorithm and the binary tree, the recursive backtracker is consistently slower.

The blue line represents the recursive backtracker.

The red line is for Eller's algorithm.

Green indicates the binary tree.

algorithms that grow

The growing tree algorithm has idiosyncracies of its own.

Starting from any given point, it blooms outward to fill the grid.

about this project

concept

This data visualization re-interprets the maze-building section of Mike Bostock's Visualizing Algorithms. The intention is to tell a story: that one can program many solutions to a given problem, none objectively 'better' than the other.

This project was conceived with an eye for implementing ideas presented in two articles: Mike Bostock's How to Scroll, and Bret Victor's Up and Down the Ladder of Abstraction. The former article delineates a set of best practices for 'scrollytelling'—a web-specific means of presenting information that reveals content through scrolling. The latter article serves as a high-level guidebook for presenting information in explorable explanations.

process work

This assignment was approached with an eye for building an explorable. In the process of drawing up a concept, several ideas caught my eye:

design exploration

Mike Bostock's Visualizing Algorithms splits key information between prose and diagrams. I found this disjointing and wanted to improve on it. To do so, I enlisted some ideas put forward in Bret Victor's Explorable Explanations—in particular, using images and text as redundant, as opposed to interdependent channels. I also employed some best practices detailed in Bostock's How to Scroll; a style guide for effective 'scrollytelling.'

I was interested in some of Bret Victor's ideas in Up and Down the Ladder of Abstraction, an article extending from his work in explorables. I found the idea of representing high-level and concrete phenomena in parallel worth experimenting with.

development

Having landed on maze generation, I found several helpful resources. The one that gave the most mileage was Jamis Buck's blog series on maze generation algorithms.

I experimented with each algorithm specified, building a minimum viable product to get a feel for how they work. The first execution went in a bad direction, both visually and technically, but it set the foundations for work to follow. After rebuilding it, I selected the four most interesting algorithms to present in the final work.

Following Visualizing Algorithms, I made each maze generator a time-lapse. Building on the Ladder of Abstraction, I added basic features to stop, slow, and reset each maze. I also added a graph measuring the speed of three algorithms, which I then superimposed over their live performance.