Personal Project
Maze Generation Visualizer
A C# and WPF application that reveals how ten maze-generation algorithms build their paths, one step at a time.
Challenge
Make the behavior of different maze-generation algorithms visible without tying the algorithms to the interface.
My contribution
I implemented ten generators, including my own hybrid algorithm that combines random paths with target-directed navigation.
Approach
Separate MazeLogic from the WPF presentation layer using a shared strategy interface, generation events, and MVVM.
Outcome
A step-by-step visualizer for comparing maze patterns, from classic algorithms to my custom hybrid.
Maze Generation Algorithms
The application implements 10 distinct maze generation algorithms, each producing unique maze characteristics and patterns:
Classic Algorithms
- Recursive Backtracking - Creates long, winding corridors using depth-first search
- Kruskal's Algorithm - Uses union-find to build minimum spanning trees
- Prim's Algorithm - Grows the maze from a random starting point
- Wilson's Algorithm - Generates unbiased mazes via loop-erased random walks
- Aldous-Broder - Random walk approach creating uniform spanning trees
Specialized Algorithms
- Hunt and Kill - Hybrid approach combining random walk with scanning
- Binary Tree - Extremely fast algorithm with diagonal bias
- Sidewinder - Row-by-row generation with horizontal corridors
- Eller's Algorithm - Memory-efficient row-based generation
- Custom Hybrid Algorithm - My original algorithm combining random paths with smart navigation
All algorithms implement the IMazeGenerator interface and use an event-driven architecture, raising OnCurrentCellChanged and OnWallRemoved events that allow the visualizer to display the generation process in real-time without tight coupling between algorithm and UI layers.
Algorithm Theory & Implementation
Custom Hybrid Algorithm (Original)
My Custom Algorithm is a unique hybrid approach that combines elements of random walks, path finding, and intelligent navigation. Unlike traditional algorithms, it selects random pairs of visited and unvisited cells, then creates connections by navigating toward the target cell while preferring unvisited paths.
How it works: The algorithm maintains visited and unvisited cell sets. It randomly selects a start cell from the visited set and a target from the unvisited set, then navigates toward the target using Manhattan distance-based direction (preferring horizontal or vertical movement). When it encounters an unvisited cell, it carves a path. If it hits already-visited territory after carving has started, it connects to the existing maze structure. This creates mazes with interesting characteristics - longer corridors than Prim's algorithm but more branching than pure Recursive Backtracking.
Custom Algorithm Implementation
public class CustomMazeAlgorithm : IMazeGenerator
{
public void Generate(Maze maze)
{
List<Cell> visited = [];
List<Cell> unvisited = [];
HashSet<Cell> visitedSet = [];
for (int x = 0; x < maze.Width; x++)
for (int y = 0; y < maze.Height; y++)
unvisited.Add(maze.GetCell(x, y));
Cell startCell = maze.GetCell(rng.Next(maze.Width), rng.Next(maze.Height));
visited.Add(startCell);
visitedSet.Add(startCell);
unvisited.Remove(startCell);
while (unvisited.Count > 0)
{
Cell start = visited[rng.Next(visited.Count)];
Cell target = unvisited[rng.Next(unvisited.Count)];
IntVector2 direction = new(
target.X > start.X ? 1 : (target.X < start.X ? -1 : 0),
target.Y > start.Y ? 1 : (target.Y < start.Y ? -1 : 0)
);
int currentX = start.X, currentY = start.Y;
bool carvingStarted = false;
while (currentX != target.X || currentY != target.Y)
{
List<IntVector2> possibleMoves = [];
if (direction.X != 0) possibleMoves.Add(new(direction.X, 0));
if (direction.Y != 0) possibleMoves.Add(new(0, direction.Y));
IntVector2 move = possibleMoves[rng.Next(possibleMoves.Count)];
Cell current = maze.GetCell(currentX, currentY);
Cell next = maze.GetCell(currentX + move.X, currentY + move.Y);
if (!visitedSet.Contains(next))
{
maze.RemoveWallBetween(current, next);
visited.Add(next);
visitedSet.Add(next);
unvisited.Remove(next);
carvingStarted = true;
currentX += move.X;
currentY += move.Y;
}
else if (carvingStarted)
{
maze.RemoveWallBetween(current, next);
break;
}
else
{
currentX += move.X;
currentY += move.Y;
}
}
}
}
}This algorithm demonstrates creative problem-solving by blending concepts from multiple classic algorithms into a novel approach with unique maze generation characteristics.
Recursive Backtracking
Recursive Backtracking: This algorithm uses a depth-first search approach with a stack. It starts at a random cell, randomly chooses an unvisited neighbor, removes the wall between them, and repeats. When it reaches a dead end (no unvisited neighbors), it backtracks to the previous cell. This creates mazes with long, winding corridors and relatively few dead ends.
Pseudocode
RecursiveBacktracking:
stack.push(startCell)
while (stack is not empty) {
current = stack.peek()
unvisitedNeighbors = getUnvisitedNeighbors(current)
if (unvisitedNeighbors.length > 0) {
neighbor = random(unvisitedNeighbors)
removeWall(current, neighbor)
stack.push(neighbor)
} else {
stack.pop()
}
}Kruskal's Algorithm
Kruskal's Algorithm: A minimum spanning tree algorithm that treats the maze as a graph. It creates a list of all possible walls, shuffles them, and processes them randomly. For each wall, if removing it would connect two separate regions (using a union-find data structure), the wall is removed. This creates mazes with many short dead ends and a more uniform distribution of passages.
Pseudocode
Kruskal:
walls = getAllWalls()
shuffle(walls)
for each wall in walls {
cellA = wall.cellA
cellB = wall.cellB
if (find(cellA) != find(cellB)) {
removeWall(wall)
union(cellA, cellB)
}
}Wilson's Algorithm
Wilson's Algorithm: Uses loop-erased random walks to generate uniform spanning trees. It starts with one cell in the maze, then performs random walks from unvisited cells until they hit the existing maze. Any loops formed during the walk are erased. This creates unbiased mazes where every possible maze has an equal probability of being generated.
Pseudocode
Wilson:
addRandomCellToMaze()
while (unvisitedCells exist) {
current = randomUnvisitedCell()
path = [current]
while (current not in maze) {
neighbor = randomNeighbor(current)
if (neighbor in path) {
index = path.indexOf(neighbor)
path = path.slice(0, index + 1)
} else {
path.add(neighbor)
}
current = neighbor
}
for (i = 0; i < path.length - 1; i++) {
removeWall(path[i], path[i+1])
addToMaze(path[i])
}
}Architecture and Design Patterns
This project demonstrates professional software engineering principles with a focus on clean code, maintainability, and extensibility. Multiple design patterns work together to create a robust architecture.
Strategy Pattern
All maze generation algorithms implement the IMazeGenerator interface, allowing them to be used interchangeably. This enables runtime selection of algorithms without coupling the client code to specific implementations.
Strategy interface (C#)
public interface IMazeGenerator
{
event EventHandler<CellEventArgs>? OnCurrentCellChanged;
event EventHandler<WallEventArgs>? OnWallRemoved;
void Generate(Maze maze);
}Observer Pattern
Each algorithm publishes events (OnCurrentCellChanged, OnWallRemoved) that observers (the UI) can subscribe to. This decouples the algorithm logic from the visualization layer, enabling real-time updates without tight coupling.
Generation events (C#)
OnCurrentCellChanged?.Invoke(
this, new CellEventArgs(x, y));
OnWallRemoved?.Invoke(
this, new WallEventArgs(x1, y1, x2, y2));Code Examples
Explore key components of the codebase that demonstrate clean coding practices and design patterns.
IMazeGenerator Interface (Strategy Pattern)
using MazeLogic.Events;
using MazeLogic.Models;
namespace MazeLogic.Interfaces;
public interface IMazeGenerator
{
event EventHandler<CellEventArgs>? OnCurrentCellChanged;
event EventHandler<WallEventArgs>? OnWallRemoved;
void Generate(Maze maze);
}Maze Model (Core Domain Logic)
namespace MazeLogic.Models;
public class Maze
{
public int Width { get; }
public int Height { get; }
public Cell[,] Grid { get; }
public Maze(int width, int height)
{
Width = width;
Height = height;
Grid = new Cell[height, width];
for (int y = 0; y < height; y++)
{
for (int x = 0; x < width; x++)
{
Grid[y, x] = new Cell(x, y);
}
}
}
public Cell GetCell(int x, int y) => Grid[y, x];
public List<Cell> GetNeighboringCells(int x, int y)
{
var neighbors = new List<Cell>();
if (x > 0) neighbors.Add(GetCell(x - 1, y));
if (x < Width - 1) neighbors.Add(GetCell(x + 1, y));
if (y > 0) neighbors.Add(GetCell(x, y - 1));
if (y < Height - 1) neighbors.Add(GetCell(x, y + 1));
return neighbors;
}
public void RemoveWallBetween(Cell a, Cell b)
{
if (a.X == b.X)
{
if (a.Y == b.Y + 1)
{
a.TopWall = false;
b.BottomWall = false;
}
else if (a.Y == b.Y - 1)
{
a.BottomWall = false;
b.TopWall = false;
}
}
else if (a.Y == b.Y)
{
if (a.X == b.X + 1)
{
a.LeftWall = false;
b.RightWall = false;
}
else if (a.X == b.X - 1)
{
a.RightWall = false;
b.LeftWall = false;
}
}
}
}Recursive Backtracking Implementation
using MazeLogic.Events;
using MazeLogic.Interfaces;
using MazeLogic.Models;
using System.Numerics;
namespace MazeLogic.GenerationAlgorithms;
public class RecursiveBacktracking : IMazeGenerator
{
public event EventHandler<CellEventArgs>? OnCurrentCellChanged;
public event EventHandler<WallEventArgs>? OnWallRemoved;
public void Generate(Maze maze)
{
int startX = Random.Shared.Next(0, maze.Width);
int startY = Random.Shared.Next(0, maze.Height);
GenerateWithStack(maze, startX, startY);
}
private void GenerateWithStack(Maze maze, int startX, int startY)
{
var stack = new Stack<Vector2>();
stack.Push(new Vector2(startX, startY));
while (stack.Count > 0)
{
Vector2 currentPosition = stack.Peek();
int x = (int)currentPosition.X;
int y = (int)currentPosition.Y;
OnCurrentCellChanged?.Invoke(this, new CellEventArgs(x, y));
Cell currentCell = maze.GetCell(x, y);
if (!currentCell.IsVisited)
currentCell.IsVisited = true;
var unvisitedNeighbors = maze.GetNeighboringCells(x, y)
.Where(c => !c.IsVisited)
.ToList();
if (unvisitedNeighbors.Count > 0)
{
Cell randomNeighbor = unvisitedNeighbors[Random.Shared.Next(unvisitedNeighbors.Count)];
maze.RemoveWallBetween(currentCell, randomNeighbor);
OnWallRemoved?.Invoke(this, new WallEventArgs(x, y, randomNeighbor.X, randomNeighbor.Y));
stack.Push(new Vector2(randomNeighbor.X, randomNeighbor.Y));
}
else
{
stack.Pop();
}
}
}
}Kruskal's Algorithm with Union-Find
using MazeLogic.Events;
using MazeLogic.Interfaces;
using MazeLogic.Models;
namespace MazeLogic.GenerationAlgorithms;
public class Kruskal : IMazeGenerator
{
public event EventHandler<CellEventArgs>? OnCurrentCellChanged;
public event EventHandler<WallEventArgs>? OnWallRemoved;
private readonly Dictionary<Cell, Cell> parent = [];
public void Generate(Maze maze)
{
Random rng = new();
var walls = new List<Wall>();
for (int y = 0; y < maze.Height; y++)
{
for (int x = 0; x < maze.Width; x++)
{
var cell = maze.GetCell(x, y);
parent[cell] = cell;
}
}
for (int y = 0; y < maze.Height; y++)
{
for (int x = 0; x < maze.Width; x++)
{
var cell = maze.GetCell(x, y);
if (x < maze.Width - 1)
{
var rightNeighbor = maze.GetCell(x + 1, y);
walls.Add(new Wall(cell, rightNeighbor, rng.NextDouble()));
}
if (y < maze.Height - 1)
{
var bottomNeighbor = maze.GetCell(x, y + 1);
walls.Add(new Wall(cell, bottomNeighbor, rng.NextDouble()));
}
}
}
walls = walls.OrderBy(w => w.Weight).ToList();
foreach (var wall in walls)
{
var root1 = Find(wall.Cell1);
var root2 = Find(wall.Cell2);
if (root1 != root2)
{
Union(root1, root2);
maze.RemoveWallBetween(wall.Cell1, wall.Cell2);
OnCurrentCellChanged?.Invoke(this, new CellEventArgs(wall.Cell1.X, wall.Cell1.Y));
OnWallRemoved?.Invoke(this, new WallEventArgs(
wall.Cell1.X, wall.Cell1.Y, wall.Cell2.X, wall.Cell2.Y));
}
}
}
private Cell Find(Cell cell)
{
if (parent[cell] != cell)
parent[cell] = Find(parent[cell]);
return parent[cell];
}
private void Union(Cell root1, Cell root2) => parent[root2] = root1;
}Event Args (Observer Pattern)
namespace MazeLogic.Events;
public class CellEventArgs : EventArgs
{
public int X { get; init; }
public int Y { get; init; }
public CellEventArgs(int x, int y)
{
X = x;
Y = y;
}
}
public class WallEventArgs : EventArgs
{
public int X1 { get; init; }
public int Y1 { get; init; }
public int X2 { get; init; }
public int Y2 { get; init; }
public WallEventArgs(int x1, int y1, int x2, int y2)
{
X1 = x1;
Y1 = y1;
X2 = x2;
Y2 = y2;
}
}