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.

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.