Maze

Rust code for generating large, perfect, uniform mazes efficiently.

This project started after watching this YouTube video about generating massive mazes. The backtracking approach shown there is simple and fast, but biased. The goal here is different: generate a perfect, uniform maze while still scaling to large sizes.

Standard approaches such as Origin-Shift and Wilson's Algorithm run into problems at scale: they are expensive, mostly sequential, and memory-hungry. This project addresses those limits with a block-based algorithm.

Each maze cell stores a single direction (N/E/S/W), so the maze needs just 2 bits per cell. That is twice as compact as the bitmap-style representation from the video. As little bonus, the optimal path between any two points is trivial to extract.

1. Compute block transition probabilities. Each interior block has size $B \times B$. Instead of simulating random walks cell by cell, the code computes a probability matrix describing how a walk entering the block exits through its boundary.

2. Run origin-shift on block boundaries. The global process only tracks transitions along block edges.

3. Fill block interiors independently. Once the block-level structure is fixed, each block interior is filled with Wilson's algorithm using the teleport map constraints. These fills can run independently and in parallel.

What it stores: During the macroscopic phase, the global walk steps into blocks and samples exits using transition probabilities. For each boundary cell we record only the most recent entry/exit event. Earlier events don't matter: origin-shift erases loops, so only the final traversal of each boundary cell affects the result.

Example — crossing paths:

  +-----------------+
  |                 |
A |..             ..| D
  |  '...........'  | 
  |       _X_       |
B |......'   '......| C
  |                 |
  +-----------------+

Suppose the macroscopic walk records A $\to$ C, then later B $\to$ D. These paths topologically cross on a planar grid, so any interior realization must intersect at some point _X_.

Because paths in the spanning tree are directed (toward the root), a walk from A that hits the already-established B $\to$ D path at _X_ must follow it onward to D. So A's path exits at D, not C. Entry cells (B) cannot be followed backwards, and the exit C may never be reached internally — it becomes a stub connected later.

How the fill resolves this: The fill algorithm (wilson_fill) processes teleport map entries in reverse chronological order, handling the exit before the entry within each pair:

1. Exit (e.g. D): point the adjacent interior cell outward and mark it visited — this seeds the tree.
2. Entry (e.g. B): run a loop-erased random walk from the adjacent interior cell until it hits a visited cell, then trace back and mark the path visited.

With B $\to$ D processed first, its interior path becomes part of the visited tree. When A $\to$ C is processed next, C's neighbor is seeded, but the random walk from A's neighbor cannot reach C without crossing the existing B $\to$ D path. It gets absorbed there and exits at D — exactly matching the planarity constraint. The C stub and any remaining unvisited cells are connected in a final pass.

For an interior block of side length $B$, the $4B$ boundary cells are indexed clockwise:

         0    1   ...  B-1
      +-------------------+
 4B-1 |                   | B
      |                   |
  ... |  Interior Block   | ...
      |     (B x B)       |
   3B |                   | 2B-1
      +-------------------+
       3B-1  ...  2B+1  2B

By D4 symmetry, only one side needs to be stored explicitly. Paths entering from the other three sides are recovered by rotating the indices, reducing storage by a factor of 4.

Sampling does not scan an entire probability row at runtime. Instead, each stored entry row is preprocessed into a Walker alias table over its nonzero exit probabilities.

At runtime the sampler:

1. maps the entry index to its canonical side,
2. samples an exit from the alias table in $O(1)$ time,
3. looks up the corresponding boundary index, and
4. rotates that exit index back to the original side.

This keeps sampling cheap even when a block has many possible exits, and it matches the compressed D4-symmetric storage used for the probability matrix.

To build the probability matrix for a $2B \times 2B$ block, the algorithm combines four $B \times B$ blocks:

               North Boundary (2B)
          0 ... B-1  B ... 2B-1
        +----------+----------+
        |          |          |
        | Block 0  | Block 1  |
        |  (BxB)   |  (BxB)   |
West    |          |          |  East
(2B)    +----------+----------+  (2B)
        |          |          |
        | Block 3  | Block 2  |
        |  (BxB)   |  (BxB)   |
        |          |          |
        +----------+----------+
               South Boundary (2B)

The internal cross contains the transitions between sub-blocks. After rotating the four sub-blocks into a common orientation, the assembled system becomes block-circulant, which can be exploited during the solve. The code then eliminates the internal cross with an $O(B^3)$ LU-based solve and produces exact transition probabilities for the outer $8B$-cell perimeter.

Let $N$ be the maze side length, so the maze has $N^2$ cells, and let $P$ be the number of threads.

• Probability matrices: A block has boundary size $4B$, so the matrix has size $(4B) \times (4B)$. Using one entry side reduces storage by 4x. The doubling solve runs in $O(B^3 / P)$. A naive approach without doubling would require solving a $B^2 \times B^2$ system, which is $O(B^6)$.
• Origin-shift on block edges: The active state drops from all $N^2$ cells to about $O(N^2 / B)$ edge transitions. Time and teleport-map memory are both $O(N^2 / B)$.
• Wilson fill: Running Wilson independently inside each block gives total work about $O(N^2 \log B / P)$, with $O(B^2)$ working memory per thread.

Balancing teleport-map memory $O(N^2 / B)$ against probability-matrix memory $O(B^2)$ gives the natural choice $B \approx N^{2/3}$. With that choice, peak memory is $O(N^{4/3})$, and total runtime is dominated by Wilson's fill at about $O(N^2 \log N / P)$.

cargo run --release --bin blockmaze -- 1026 100 tiny.bin

cargo run --release --bin navigate tiny.bin

The navigate binary will fail on very large mazes because it needs to load the full maze into memory.

cargo run --release --bin doubling_test -- 4098

cargo build --release