Getting lost and found with the C# Maze Generator and Solver

Today's project harkens back to days when we used to love mazes... (Okay, I still do, but that's besides the point).

C# Maze Generator and Solver

Introduction

This demo creates and solves mazes using the Breadth-First and Depth-First searches. It can be very useful in demonstrating these algorithms.

Background

This article assumes you have a basic knowledge of VC#.NET. A little bit knowledge of pointers, recursion, and GDI+ graphics is appreciated, too.

We will frequently use the Stack and Queue data structures. As reminders, recall that the stack is First-In-Last-Out (FILO), while the queue is First-In-First-Out (FIFO).

The Maze Generation

Depth-First Search and Breadth-First Search are very useful approaches in many applications. One of them is creating/solving mazes. To generate a maze with DFS, we have this simple algorithm:

• Have all walls in your maze intact (not broken).
• Choose a random start point, push it into the stack. Call this initial square 'current square'.
• Repeat while the stack is not empty:
  • Get list of all neighboring squares to the current square where those neighbors have all their walls intact (unvisited).
  • If there are neighbors (i.e., List.Count > 0):
    • Choose one of the neighbors at random. Call it 'temp'.
    • Knock the wall between 'temp' and the current square.
    • Push the current square into the stack.
    • Make the current square equals 'temp'.
  • Else if there are no neighbors, pop a square from the stack. Make current square equal to it.

After executing this algorithm, you will have a 'prefect maze' which indicates that your maze doesn't have 'dead ends' (i.e., unreachable squares) and has a single solution.

BFS generation is the same except the stack that will be replaced with a queue.

If the generation is with DFS, the program will choose a random wall and knock it, then it moves to the new square. When it reaches an edge (or visited cell), it backs again to the nearest "UNVISITED" square.

When generation is with BFS, program will knock the wall in a way similar to DFS, but BFS uses queue, causing to finish near squares first before the far ones. In contrast, DFS uses stack, which causes it to finish far first then back to near.

The Maze Solving

Again, DFS and BFS have many helpful applications. We will now use them to solve the maze they created, as in the following backtracking algorithm:

Have an empty list for the found path. Call it 'foundPath'.

function DFS(Cell start) : Boolean
    if start is equal to the maze end
        Add start to 'foundPath' 
        Mark start as visited 
        Return true
    Else if start is visited already
        Return false
    Else:
        Mark start as visited 
        For each neighbor of start 
            If the wall between start and neighbor is knocked 
            Recursively call DFS function with the neighbor
            If the call returns true
            Add start to 'foundPath'
            Return true
        If you reached this point, return false

This algorithm finds path to the maze end. When it returns true, it adds the current location to 'foundPath', causing all other calls in the stack to return true and add their current locations, too. At finish, we will have a complete list of squares between begin and end.

However, we won't use those recursive versions, since they may cause a StackOverFlowException when the calls are too many for that stack. We will instead use the same algorithms but iteratively (i.e., with a loop). Instead of making every recursive call, add its 'start' to 'foundPath', and we will have a pointer to the previous one (as we will see later in the article).

The same is about BFS, but again, we will use a queue rather than a stack.

For generation, DFS searches at random. When it reaches an edge, it backs to the nearest (UNVISITED) square and repeats the process until it finds the end.

On the other hand, BFS searches the near squares first. When it reaches an intersection, it divides into two tracks and discovers the near squares. The process is repeated until the end is found.

We have a third method that traverses the maze, the right-hand rule. It considers "putting" your right hand on the wall, never leaving it. Even if the way will be longer, you'll absolutely reach the end, or back again to the beginning if there is no end. We are sure, however, that we have a path to the end, since we are using BFS/DFS that gives perfect mazes. In the right-hand rule, we will consider only traversing the maze without finding the path.

Let's take a peek at the project (which ran for me the first time with no problems).

The maze generation happens here;

private void backgroundWorker1_DoWork(object sender, DoWorkEventArgs e)
   {
       object[] args = e.Argument as object[];

       int value = (int)args[0];
       bool solving = (bool)args[1];
       if (!solving)
       {
           this.maze.Generate(this.pictureBoxDraw.Width / value,
               (this.pictureBoxDraw.Height - value) / value,
               (int)args[2]);
       }
       else
       {
           this.maze.Solve((int)args[2]);
           this.hasSolution = true;
       }
       this.pictureBoxDraw.Invalidate();
   }

public void Generate(int width, int height, int method)
{
    this.working = true;

    this.initailze(this.maze, width, height);

    this.mazePen.Dispose();
    this.mazePen = this.unitX < 5 ? new Pen(Brushes.WhiteSmoke, 1) : new Pen(Brushes.WhiteSmoke, 3);
    if (method == 0)
        this.depthFirstSearchMazeGeneration(this.maze, this.width, this.height);
    else
        this.breadthFirstSearchMazeGeneration(this.maze, this.width, this.height);
    this.working = false;
}

private void depthFirstSearchMazeGeneration(Cell[,] arr, int width, int height)
{
    Stack<Cell> stack = new Stack<Cell>();
    Random random = new Random();

    Cell location = arr[this.random.Next(height), this.random.Next(width)];
    stack.Push(location);
    
    while (stack.Count > 0)
    {
        List<Point> neighbours = this.getNeighbours(arr, location, width, height);
        if (neighbours.Count > 0)
        {
            Point temp = neighbours[random.Next(neighbours.Count)];

            this.currentGenerateLocation = temp;

            this.knockWall(arr, ref location, ref arr[temp.Y, temp.X]);

            stack.Push(location);
            location = arr[temp.Y, temp.X];
        }
        else
        {
            location = stack.Pop();
        }

        Thread.SpinWait(this.Sleep * sleepPeriod);
    }

    this.makeMazeBeginEnd(this.maze);
}

\

Once you have a maze, you can then have the program solve it too...

public unsafe void Solve(int method)
{
    this.solving = true;
    // initialize
    this.foundPath.Clear();
    this.unvisitAll(this.maze);
    
    // selecting the method
    if (method == 0)
    {
        if (this.height * this.width < 40 * 80)
            fixed (Cell* ptr = &this.begin)
                this.depthFirstSearchSolve(ptr, ref this.end);
        else
            this.iterativeDepthFirstSearchSolve(this.begin, this.end);
    }
    else if (method == 1)
        this.breadthFirstSearchSolve(this.begin, this.end);
    else if (method == 2)
        this.iterativeRightHandRuleSolve(this.begin, Directions.Right);

    this.solving = false;
}