Maze Generation Project

Project Overview

A comprehensive maze generation and visualization application built with C# .NET 8 and WPF, featuring 10 distinct algorithms including a custom hybrid algorithm. The application provides real-time, step-by-step visualization of how each algorithm constructs mazes, making algorithmic behavior transparent and educational.

This project demonstrates professional software engineering practices including clean architecture, design patterns (Strategy, Observer, MVVM), and event-driven programming. The separation between MazeLogic (core algorithms) and MazeVisualiser (presentation layer) ensures modularity, testability, and maintainability - making it an excellent showcase of software craftsmanship.

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 = [];
        
        // Initialize all cells as unvisited
        for (int x = 0; x < maze.Width; x++)
            for (int y = 0; y < maze.Height; y++)
                unvisited.Add(maze.GetCell(x, y));
        
        // Pick random starting cell
        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)
        {
            // Select random visited cell and random unvisited target
            Cell start = visited[rng.Next(visited.Count)];
            Cell target = unvisited[rng.Next(unvisited.Count)];
            
            // Calculate direction toward target
            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;
            
            // Navigate toward target
            while (currentX != target.X || currentY != target.Y)
            {
                // Build possible moves based on direction
                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))
                {
                    // Carve through unvisited cell
                    maze.RemoveWallBetween(current, next);
                    visited.Add(next);
                    visitedSet.Add(next);
                    unvisited.Remove(next);
                    carvingStarted = true;
                    currentX += move.X;
                    currentY += move.Y;
                }
                else if (carvingStarted)
                {
                    // Connect to existing maze and stop
                    maze.RemoveWallBetween(current, next);
                    break;
                }
                else
                {
                    // Navigate through visited cells
                    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) {
      // Erase loop: remove path from neighbor to end
      index = path.indexOf(neighbor)
      path = path.slice(0, index + 1)
    } else {
      path.add(neighbor)
    }
    
    current = neighbor
  }
  
  // Add entire loop-erased path to maze
  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.

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.

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;

/// <summary>
/// Defines the contract for maze generation algorithms.
/// Implements Strategy Pattern for interchangeable algorithms.
/// </summary>
public interface IMazeGenerator
{
    /// <summary>
    /// Raised when the algorithm moves to a new cell during generation.
    /// </summary>
    event EventHandler<CellEventArgs>? OnCurrentCellChanged;
    
    /// <summary>
    /// Raised when a wall is removed between two cells.
    /// </summary>
    event EventHandler<WallEventArgs>? OnWallRemoved;
    
    /// <summary>
    /// Generates a maze using the specific algorithm implementation.
    /// </summary>
    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) // Vertical neighbors
        {
            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) // Horizontal neighbors
        {
            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;
            
            // Notify observers of current cell
            OnCurrentCellChanged?.Invoke(this, new CellEventArgs(x, y));

            Cell currentCell = maze.GetCell(x, y);
            if (!currentCell.IsVisited)
                currentCell.IsVisited = true;

            // Find unvisited neighbors
            var unvisitedNeighbors = maze.GetNeighboringCells(x, y)
                .Where(c => !c.IsVisited)
                .ToList();

            if (unvisitedNeighbors.Count > 0)
            {
                // Choose random neighbor and carve path
                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
            {
                // Backtrack
                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>();

        // Initialize union-find structure
        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;
            }
        }

        // Create list of all possible walls with random weights
        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()));
                }
            }
        }

        // Sort walls by weight (randomized)
        walls = walls.OrderBy(w => w.Weight).ToList();

        // Process walls in random order
        foreach (var wall in walls)
        {
            var root1 = Find(wall.Cell1);
            var root2 = Find(wall.Cell2);

            // If cells are in different sets, join them
            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));
            }
        }
    }

    // Union-Find with path compression
    private Cell Find(Cell cell)
    {
        if (parent[cell] != cell)
            parent[cell] = Find(parent[cell]); // Path compression
        
        return parent[cell];
    }

    private void Union(Cell root1, Cell root2) => parent[root2] = root1;
}

Event Args (Observer Pattern) ▸


namespace MazeLogic.Events;

/// <summary>
/// Event data for cell-related events during maze generation.
/// Uses init-only properties for immutability.
/// </summary>
public class CellEventArgs : EventArgs
{
    public int X { get; init; }
    public int Y { get; init; }

    public CellEventArgs(int x, int y)
    {
        X = x;
        Y = y;
    }
}

/// <summary>
/// Event data for wall removal events during maze generation.
/// </summary>
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;
    }
}

Maze Generation Visualizer

Project Overview

Maze Generation Algorithms

Classic Algorithms

Specialized Algorithms

Algorithm Theory & Implementation

Custom Hybrid Algorithm (Original)

Recursive Backtracking

Kruskal's Algorithm

Wilson's Algorithm

Architecture and Design Patterns

Strategy Pattern

Observer Pattern

Code Examples