Maze Generation Project

Project Overview

A comprehensive maze generation and visualization application built with C# .NET 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 = [];
        
        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.

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;

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;
    }
}

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