C# Maze Generator and Solver

• Download source code - 106 KB

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 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, the 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 the 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 this 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.

The Pointers

If you have a C\C++ background, then you already know how to use pointers. However, C# also can use pointers with some restrictions. We will use pointers to find the path between the start point and the end point. I'll assume you know what pointers are. If you don't, you should make a search and learn them.

Using the Code

The Cell Struct

As we have seen in the Background section, we need to have walls in order to generate and solve a maze. So let's have a struct called Cell that encapsulates four boolean variables: RightWall, LeftWall, UpWall, and DownWall. At first, all the walls should be intact, so we initialize them to true. When we knock a wall, we will simply set its boolean variable to false. Cell should have a Visited boolean too, which indicates whether this cell has been visited already. Every cell should draw itself, so every cell has a Draw() method.

If we want to generate a maze of 40 by 40 squares, for example, we will need a container for them. Let's have a two-dimensional array that carries all the cell instances, call it 'maze'. For any cell, we have two locations: one that represents its location for the graphics, and another that represents its location in the two-dimensional array. In the previous section, we demonstrated the recursive version of the DFS solution. We stated that we won't use the recursion. Instead of having every recursive call add its 'start' to foundPath, we will have a pointer in every cell to its 'previous' cell. A chain of these 'previous' pointers will form the complete path. So before we push the 'temp' (which indicates the next neighbor of 'start' to be visited) to the stack, we set its 'previous' pointer to 'start'.

The Maze Class

We have a class Maze that encapsulates the 2D array maze (of Cell instances). For the array, we represent it as Height x Width, not the reverse. So when we have a position Point of x and y coordinates, we access the array as maze[position.Y, position.X]. We take its maximum width and height in the constructor and reverse the array. Yet we can use any smaller width and height the user selects. This makes more sense because the repeated reserve\release operations are bad in terms of performance. Maze has a method Draw which draws every cell (in the bounds the user selects).

In the methods iterativeDepthFirstSearchSolve and breadthFirstSearchSolve, we use pointers to refer to the previous cell in the foundPath. To enable pointers usage, those methods must be marked as "unsafe". The .NET Common Language Runtime usually moves objects from one place to another while the program runs. However, if we want to refer to an object with a pointer, that object must be "fixed" in its place so the pointer can always point to it correctly. Therefore we use the syntax:

fixed(Cell* cell = &start)
next.Previous = cell;

to set the previous pointer of "next" to point to "start".

To use pointers, we must tell the compiler about it. By going to the Properties window in Visual Studio (form Solution Explorer) > Build we can set the option "Allow unsafe code" to enable using pointers.

The Form Class

In the form, we have a picture box which we draw on. Recall that picture boxes are appreciated for graphics, because they are double-buffered which prevents flickering. The user can select the difficulty level of the maze. The more difficult the maze, the larger. The user can select between 1 and 100 difficulties. Let's call the value the user selects 'value'. We then calculate the maze width as:

width = pictureBoxDraw.Width / value;

where pictureBoxDraw is the picture we draw on. Similarly, we define the height as:

height = (pictureBoxDraw.Height – value) / value;

We then pass them to Maze.Generate which initializes this specific size (resets all cells in the specific bounds). Width is the number of cells per row, and Height is the number of cells per column. The width\height should be bigger when 'value' is bigger, so before calculation, we set the value to:

value = 100 – value;

We use a BackgroundWorker to do the work on another thread, so the GUI doesn't hang when the maze is being generated and solved. We use a timer to frequently call Maze.Draw while the maze is working.

The user can select the speed of working. The larger the value, the faster the work. We use Thread.SpinWait to slow the operation according to the specific speed.