Development

Building Mazex: Maze Generation with Elixir

November 25, 2024
9 min read

Mazex is an Elixir-based tool for maze generation implementing seven different algorithms. Each algorithm produces unique visual patterns and performance characteristics, making it suitable for games, education, and art.

Why Different Algorithms Matter

Different maze algorithms produce wildly different results. Some create long corridors, others produce dense passages. Some are fast but biased, others are slow but perfectly uniform. Elixir's pattern matching and immutable data structures make implementing these algorithms elegant and efficient.

The Seven Algorithms

All maze algorithms create a spanning tree of a grid without loops. Here's what Mazex implements:

  • Binary Tree: Fastest (~5ms for 100x100). Carves passages north/south or east/west. Creates visible diagonal bias.
  • Sidewinder: Very fast (~10ms). Groups cells horizontally before carving south. Less bias than Binary Tree.
  • Aldous-Broder: Slow (~250ms) random walk. Perfectly uniform, no visible patterns.
  • Wilson's Algorithm: Slower (~200ms) but more efficient than Aldous-Broder. Perfectly uniform distribution.
  • Recursive Backtracker: Popular for games (~40ms). Depth-first search creates long corridors and organic feel.
  • Kruskal's: Good performance (~25ms). Uses randomized edge selection with distinctive visual patterns.
  • Prim's: Solid performance (~30ms). Weighted spanning tree approach with different visual patterns.

Usage

Generate mazes with simple commands. For real-time applications, use Binary Tree or Sidewinder. For visual quality, choose Wilson's or Aldous-Broder. For games, Recursive Backtracker creates explorable layouts.

Basic command: 

mix mazex --rows=10 --columns=15 --algorithm=binary_tree

Available options: --rows, --columns, --algorithm (binary_tree, sidewinder, aldous_broder, wilsons, recursive_backtracker, kruskals, prims), --output, --filename

Technical Implementation

The core uses a map of cell coordinates with immutable transformations. Key optimizations: tail recursion for depth-first algorithms, sets instead of lists for O(log n) lookups, and pattern matching for clean boundary handling. PNG generation uses Elixir ports to interface with native image processing.

Applications

Mazex works for game dungeons, educational tools for graph theory, visual art, and procedural generation. MIT licensed and fast enough for runtime generation without lag.

Conclusion

Mazex demonstrates how Elixir's pattern matching and immutability make algorithm implementation elegant. Check it out on GitHub to explore different maze generation approaches.