A Maze Generator

Mission Statement

A collection of maze generation algorithms, interesting visualisations, and a web interface UI. The algorithms and visualisations are written in Rust and compiled to WebAssembly so they can be used in a browser. Here’s an example:

Status

The project is currently an MVP. It is hosted at https://aleks.bg/maze where you can tweak maze generation parameters. The web page provides a unique link to every generated maze[fn:1]. You can populate a PDF file with an arbitrary amount of mazes (one per page) and print them. The printed mazes have QR code backlinks to the site so you can check for a solution later.

There’s a command line application that similarly accepts the maze’s parameters and random seed and outputs an SVG file with the maze’s parameters as its name.

You can use one of two algorithms to create the mazes:

• “Growing Tree” (based on Jarník’s, aka Prim’s spanning tree algorithm) with a hard coded selection criterion that means the algorithm degenerates to a randomised depth-first search. Creates few, long, meandering passages
• “Kruskal’s Algorithm” (based on Kruskal’s spanning tree algorithm). Creates mazes with lots of intersections and many short passages

[fn:1] Note that the backlinks are not stable yet, and the maze you see when you follow a link may not be the one you printed as internals may change at any time.

You can also choose between different shapes of the overall maze: a square or a circle are available. The latter is also known as a θ-maze.

Circular mazes have an interesting property: their cell count grows: $2^log_2(n)$ where $n$ is the amount of rings. Compare square mazes that grow at $n^2$. In practice, the number of cells in a given θ-maze is

$$1 + ∑i=1i <n c2⌊\log_2(i)⌋$$

Where $c$ is the column factor, i.e. the number of cells in ring 1. (It is currently hard-coded to 8.) This means that a maze of size 10 maze has 297 cells, one of size 20 1193. When switching between square and circle mazes in the UI, we therefore halve the number of cells. This makes intuitive sense, as each ring is like one line of cells in a square maze, but the rings count twice. So a comparable circle maze will always have half the “size”. This means that it will have fewer cells, as the above function grows more slowly than $n^2$.

Building

The Rust project can be built using

cargo build --release

(You will need cargo and a Rust compiler.) To create the web page, you’ll also need node, bun~[fn:2], and ~wasm-bindgen.

cd web/frontend
wasm-pack build --target bundler --release && bun run build

To build it for a certain subdirectory of a page, use e.g. --base=/maze on the bun run build command.

[fn:2] npm or comparable programs should work fine, too.

Desiderata

A nicer UI

The current UI is bare-bones.

An adjustable selection criterion for GrowingTree

GrowingTree currently selects its next cell exclusively from the top of the stack. Were it to follow a certain random distribution, that could be made adjustable, which would allow for different maze topologies (choosing from further back will create more passages, intersections and dead ends).

Offer different maze topologies

Braid mazes as well as quasi-3D mazes with “bridges” and “tunnels”.

Offer different maze geometries

Circular, elliptic, triangular and hexagonal mazes look neat and might be fun to implement. Mazes could probably be drawn along Penrose tilings and similar irregular tilings.

Bugs

• [X] The last segment of the solution path of theta mazes (the extra one tacked on to the end so the path doesn’t end in the middle of the cell) is an elliptical arc segment, but should be a line. It’s a bit squiggly, visually.
• [X] Sigma mazes are stained from the exit, instead of from the entrance, like all other mazes (so the exit is yellow, and the entrance can be in a medium peachy segment)
• [X] Rectilinear mazes seem to just be stained from the origin. Why? Sample: #R24|GrowingTree|4078526631170035261
• [ ] Sigma mazes are printed with a narrower width than other mazes. My guess is they’re too tall to fit in the box, since sigma mazes are taller than they are wide.

License

This project is licensed under the GPLv3. Find more information here.