Voronoi diagram maze

I created a Javascript demo of a maze generator based on a Voronoi diagram.

Voronoi maze demo

A maze is fundamentally a tree. Given any connected graph, a maze generation algorithm finds a random spanning tree for that graph. Each node in the graph is a maze cell and the edges represent walls. Here, the maze is generated using a randomized depth-first search:

History := new stack.
Current := random cell.
Do:
    History.push(Current).
    Current := random neighbour.
    Destroy wall between Current and History.
    While Current has no neighbours and History is not empty:
        Current := History.pop().
While History is not empty.

Being able to run on any kind of graph, the maze generation algorithm is very general and works for higher dimensions as well. The choice of what kind of graph to start with, however, has traditionally been an unimaginative one. People almost always chose the classical rectangular lattice, i.e. the square grid, where each cell has four neighbours. Possibly the second most common lattice is the hexagonal lattice, where each cell has six neighbours.

In this blog post I present a demo for a maze generated from a Voronoi diagram. A Voronoi diagram is a way of dividing a space into convex polygons based on a set of points. When used for generating mazes, each maze cell is a Voronoi cell, and corresponds to a node on the graph. The maze generation algorithm randomly but judiciously destroys walls between Voronoi cells until every Voronoi cell is walkable and the walkable area is simply connected. The advantage of using a Voronoi diagram approach is that, depending on how the original set of points were chosen, any kind of maze can be generated. This includes all the regular lattices such as the square lattice and the hexagonal lattice. As such the Voronoi approach to maze generation is more general.

My Javascript demo uses Raymond Hill’s excellent Javascript library for Voronoi diagrams. For fun, I’ve also included the use of Visibility Polygon (see previous blog post).

The demo works with random points, square lattice, and hexagonal lattice.