3D mazes with Javascript, WebGL and Three.js

Mazes from OFF files


Given a surface, defined as collection of cells divided by walls, we can generated a simple maze by finding a spanning tree of the graph whose nodes are the cells and whose edges are the walls. Here we use Kruskal's algorithm to build up the spanning tree: pick walls randomly to include or exclude from the tree; include if the cells on either side are already connected, otherwise exclude (so as to connect the cells on either side in the resulting tree). Repeat until all walls have been considered.

We can describe a 3-dimensional surface by a set of points and a set of faces, with each face having a list of points as its boundary. A wall is then just a pair of points that are adjacent in one or two cell boundaries and we can then apply our maze generating algorithm as above.

Having determined the set of walls in the maze, we can then use the coordinates of the points to construct a 3-dimensional model. All we need is a base model to start with, and this is conveniently given by an OFF file as generated by a tool such as Antiprism, used here to generate models for a (dual) geodesic sphere, a torus and a Möbius strip.

Click on a pane for an expanded, more interactive view. Controls for the expanded view are:

  • Mouse drag: Orbit controls
  • Up/down: move forward/back
  • r: rotation on/off
  • f: step through color styles
  • ?: info display on/off

A real 3D maze


Alternatively, we can construct a true 3d maze. Here we generate the underlying geometry directly with some Javascript:

This is all using a framework I've been experimenting with, based on Three.js, for drawing polyhedra and other geometric objects: