Solving Mazes Using Recursion

Kevin OFlaherty
1y
60.7k
0
1

Article

Introduction

In this lesson, we will be creating a C# form that creates and solves a maze using a recursive technique. It will cover the creation of the maze creator using PictureBoxes and solving the maze.

Project Goals

Goal 1: Create a maze creator using PictureBoxes. The PictureBoxes are referenced by a multi-dimensional array, maze tiles, for easy access and manipulation.
Goal 2: Solve the maze using a recursive technique marking the correct path with the color gray. If the maze cannot be solved, then show a dialogue box.
Goal 3: Make a reset button that will remove the gray coloring and remark the start and finish in light blue. The start is in the top right corner, and the finish is in the bottom left.

Create a New Project

I'm using Visual C# 2010 for this lesson. Create a new Windows Form Application. I have named mine as MCS_Week_003, and if you've chosen a different name, then it will have to be changed in code.

namespace YourActualProjectName
{
    // Your classes, methods, and other code go here
}

Creating the Interface

Once you have created your project, a new form will be available. Add the following controls using the toolbox in the form designer. Note the squares are picture boxes with thier background color changed. This, in code, is BackColor. Name them as the following.

using System;
using System.Drawing;
using System.Windows.Forms;
namespace Your_Project_Name
{
    public partial class Form1 : Form
    {
        private Color currentColor = Color.White;
        private int XTILES = 25; // Number of X tiles
        private int YTILES = 25; // Number of Y tiles
        private int TILESIZE = 10; // Size of the tiles (pixels)
        private PictureBox[,] mazeTiles;
        public Form1()
        {
            InitializeComponent();
            createNewMaze();
        }
        private void createNewMaze()
        {
            mazeTiles = new PictureBox[XTILES, YTILES];

            // Loop for creating all tiles
            for (int i = 0; i < XTILES; i++)
            {
                for (int j = 0; j < YTILES; j++)
                {
                    // Initialize a new PictureBox at coordinate (i, j)
                    mazeTiles[i, j] = new PictureBox();

                    // Calculate size and location
                    int xPosition = (i * TILESIZE) + 13; // 13 is padding from the left
                    int yPosition = (j * TILESIZE) + 45; // 45 is padding from the top
                    mazeTiles[i, j].SetBounds(xPosition, yPosition, TILESIZE, TILESIZE);

                    // Make top-left and bottom-right corners light blue (used for start and finish)
                    if ((i == 0 && j == 0) || (i == XTILES - 1 && j == YTILES - 1))
                    {
                        mazeTiles[i, j].BackColor = Color.LightBlue;
                    }
                    else
                    {
                        // Make all other tiles white
                        mazeTiles[i, j].BackColor = Color.White;

                        // Make it clickable
                        mazeTiles[i, j].Click += PictureBox_Click;
                    }

                    // Add PictureBox to the form's controls
                    this.Controls.Add(mazeTiles[i, j]);
                }
            }
        }
        private void pictureBox1_Click(object sender, EventArgs e)
        {
            currentColor = Color.White;
        }
        private void pictureBox2_Click(object sender, EventArgs e)
        {
            currentColor = Color.Black;
        }
        private void PictureBox_Click(object sender, EventArgs e)
        {
            ((PictureBox)sender).BackColor = currentColor;
        }
        private void button1_Click(object sender, EventArgs e)
        {
            // Create a previously searched array
            bool[,] alreadySearched = new bool[XTILES, YTILES];

            // Start the recursive solver at tile (0, 0). If false, maze cannot be solved.
            if (!solveMaze(0, 0, alreadySearched))
            {
                MessageBox.Show("Maze cannot be solved.");
            }
        }
        private void button2_Click(object sender, EventArgs e)
        {
            // Change all gray tiles to white
            for (int i = 0; i < XTILES; i++)
            {
                for (int j = 0; j < YTILES; j++)
                {
                    if (mazeTiles[i, j].BackColor == Color.Gray)
                    {
                        mazeTiles[i, j].BackColor = Color.White;
                    }
                }
            }
            // Reset start and finish to light blue
            mazeTiles[0, 0].BackColor = Color.LightBlue;
            mazeTiles[XTILES - 1, YTILES - 1].BackColor = Color.LightBlue;
        }
        private bool solveMaze(int xPos, int yPos, bool[,] alreadySearched)
        {
            bool correctPath = false;
            bool shouldCheck = true;

            // Check for out-of-boundaries
            if (xPos >= XTILES || xPos < 0 || yPos >= YTILES || yPos < 0)
            {
                shouldCheck = false;
            }
            else
            {
                // Check if at the finish, not (0, 0 and colored light blue)
                if (mazeTiles[xPos, yPos].BackColor == Color.LightBlue && (xPos != 0 || yPos != 0))
                {
                    correctPath = true;
                    shouldCheck = false;
                }
                // Check for a wall
                if (mazeTiles[xPos, yPos].BackColor == Color.Black)
                {
                    shouldCheck = false;
                }
                // Check if previously searched
                if (alreadySearched[xPos, yPos])
                {
                    shouldCheck = false;
                }
            }
            // Search the tile
            if (shouldCheck)
            {
                // Mark tile as searched
                alreadySearched[xPos, yPos] = true;
                // Check the right tile
                correctPath = correctPath || solveMaze(xPos + 1, yPos, alreadySearched);
                // Check the down tile
                correctPath = correctPath || solveMaze(xPos, yPos + 1, alreadySearched);
                // Check the left tile
                correctPath = correctPath || solveMaze(xPos - 1, yPos, alreadySearched);
                // Check the up tile
                correctPath = correctPath || solveMaze(xPos, yPos - 1, alreadySearched);
            }
            // Make the correct path gray
            if (correctPath)
            {
                mazeTiles[xPos, yPos].BackColor = Color.Gray;
            }
            return correctPath;
        }
    }
}

Adding a Color Selector

The maze builder will allow the user to create walls and paths by clicking on the maze tiles. The color will be determined by the last PictureBox selected and will be white by default. Create a global variable of the Color class naming it currentColor. The addition is below.

Adding the Variable currentColor

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
namespace MCS_Week_003
{
    public partial class Form1 : Form
    {
        Color currentColor = Color.White; // This line declares a Color variable and initializes it with the color White
        public Form1()
        {
            InitializeComponent();
        }
    }
}

Next, make pixtureBox1 and pictureBox2 clickable by adding the following method to the form. cs. A quick way to do this is to double-click the object in the designer.

Making the White Picture Box Clickable

private void pictureBox1_Click(object sender, EventArgs e)
{
    currentColor = Color.White;
}

Making the Black Picture Box Clickable

private void pictureBox2_Click(object sender, EventArgs e)
{
    currentColor = Color.Black;
}

Creating the Maze Tiles

The maze contains a grid of picture boxes that will be used to store the walls, path, start, and finish depending on their color. We will make the maze expandable using XTILES and YTILES to determine the number of tiles in the maze. The size of each tile will be determind by TILESIZE. Feel free to change these values to any non-negative and zero number. The PictureBoxes will be stored in the mazeTiles array. Add the following variables to your Form1.cs

Adding more Variables

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
namespace MCS_Week_003_final
{
    public partial class Form1 : Form
    {
        Color currentColor = Color.White;
        private int XTILES = 25;    // Number of X tiles
        private int YTILES = 25;    // Number of Y tiles
        private int TILESIZE = 10;  // Size of the tiles (pixels)
        private PictureBox[,] mazeTiles;
        public Form1()
        {
            InitializeComponent();
        }
        // Other methods and event handlers can be added here
    }
}

There needs to be a way to create the maze easily with one call from a method. The createNewMaze() method will create a grid of picture boxes. It makes the top left and bottom right light blue and all other tiles white and clickable, calling the method PictureBox_Click(). The last line, this.Controls.Add(mazeTile[i,j]); adds the PictureBox controls to the form allowing them to be displayed. Add the following code to your form. cs.

Creating The Maze PictureBoxes

private void createNewMaze()
{
    mazeTiles = new PictureBox[XTILES, YTILES];
    // Loop for getting all tiles
    for (int i = 0; i < XTILES; i++)
    {
        for (int j = 0; j < YTILES; j++)
        {
            // Initialize a new PictureBox array at coordinate XTILES, YTILES
            mazeTiles[i, j] = new PictureBox();
            // Calculate size and location
            int xPosition = (i * TILESIZE) + 13; // 13 is padding from left
            int yPosition = (j * TILESIZE) + 45; // 45 is padding from top
            mazeTiles[i, j].SetBounds(xPosition, yPosition, TILESIZE, TILESIZE);
            // Make top left and right bottom corner light blue. Used for start and finish
            if ((i == 0 && j == 0) || (i == XTILES - 1 && j == YTILES - 1))
            {
                mazeTiles[i, j].BackColor = Color.LightBlue;
            }
            else
            {
                // Make all other tiles white
                mazeTiles[i, j].BackColor = Color.White;

                // Make it clickable
                EventHandler clickEvent = new EventHandler(PictureBox_Click);
                mazeTiles[i, j].Click += clickEvent; // += used in case other events are used
            }
            // Add to controls to form (display picture box)
            this.Controls.Add(mazeTiles[i, j]);
        }
    }
}

Making the PictureBoxes Clickable

The following code in the last code block made the PictureBoxes clickable calling the method PictureBox_Click(). The += is used add the event plus any click events that may have been already added.

Making the White Picture Box Clickable

// Make it clickable
EventHandler clickEvent = new EventHandler(PictureBox_Click);
mazeTiles[i, j].Click += clickEvent; // += is used in case other events are used

Next, make the PictureBox_Click method by adding the following method to your Form1.cs. This code will set the PictureBox's BackColor property to currentColor.

Adding the PictureBox_Click Method

private void PictureBox_Click(object sender, EventArgs e)
{
    ((PictureBox)sender).BackColor = currentColor;
}

Run your project, and you should be able to change the color of the PictureBoxes. You can experiment with the constants at the top of the code file to manipulate the tiles.

Constants

public partial class Form1 : Form
{
    private int XTILES = 25;      // Number of X tiles
    private int YTILES = 25;      // Number of Y tiles
    private int TILESIZE = 10;    // Size of the tiles (pixels)
    // Rest of your Form1 class code
}

The Recursive Algorithm

Recursion is the act of a method calling itself and is the key to solving the maze.

Arguments

xPos - the x coordinate to search
yPos - the y coordinate to search
already searched - bool array of searched elements

Return

Bool - is it the right path?

Algorithm

If out of boundary, return false
If at a wall, return false
If at finish return true
If not returned and not

Already searched; search the tile

Search

Marking in already searched and Check right, down, left, up and return and if one returns the correct path return true.

Direction Precedence

Checks right, down, up, then up. Will not be the shortest path.

Making the Solve Button Clickable

Before calling the solveMaze recursive method, there needs to be a way to prevent an infinite loop. To prevent one, we are adding an alreadySearched bool array and passing it as an argument through the solveMaze recursive method. This will prevent paths that are alreadysearched from being searched again.

The solveMaze() recursive method is then called starting at tile 0,0 and if it returns false a message box will be shown displaying "Maze can not be solved".

Adding the Solve Button Code

private void button1_Click(object sender, EventArgs e)
{
    // Create a previously searched array
    bool[,] alreadySearched = new bool[XTILES, YTILES];
    // Start the recursive solver at tile (0, 0). If false, maze cannot be solved.
    if (!solveMaze(0, 0, alreadySearched))
    {
        MessageBox.Show("Maze cannot be solved.");
    }
}

Solving the Maze

The following code will search the maze one tile at a time, and if a correct path is found, the path will be marked in gray. To understand the code run through it tile by tile. You may want to shrink the amount of tiles with XTILES and YTILES. Add the following method to your Form1.cs.

Creating the solveMaze() Method

private bool solveMaze(int xPos, int yPos, bool[,] alreadySearched)
{
    bool correctPath = false;
    bool shouldCheck = true;
    // Check for out of boundaries
    if (xPos >= XTILES || xPos < 0 || yPos >= YTILES || yPos < 0)
    {
        shouldCheck = false;
    }
    else
    {
        // Check if at finish, not (0,0 and colored light blue)
        if (mazeTiles[xPos, yPos].BackColor == Color.LightBlue && (xPos != 0 && yPos != 0))
        {
            correctPath = true;
            shouldCheck = false;
        }
        // Check for a wall
        if (mazeTiles[xPos, yPos].BackColor == Color.Black)
        {
            shouldCheck = false;
        }
        // Check if previously searched
        if (alreadySearched[xPos, yPos])
        {
            shouldCheck = false;
        }
    }
    // Search the Tile
    if (shouldCheck)
    {
        // Mark tile as searched
        alreadySearched[xPos, yPos] = true;

        // Check right tile
        correctPath = correctPath || solveMaze(xPos + 1, yPos, alreadySearched);
        // Check down tile
        correctPath = correctPath || solveMaze(xPos, yPos + 1, alreadySearched);
        // Check left tile
        correctPath = correctPath || solveMaze(xPos - 1, yPos, alreadySearched);
        // Check up tile
        correctPath = correctPath || solveMaze(xPos, yPos - 1, alreadySearched);
    }
    // Make correct path gray
    if (correctPath)
    {
        mazeTiles[xPos, yPos].BackColor = Color.Gray;
    }
    return correctPath;
}

The order of precedence is derived from the order of the searchMaze() calls. You can experiment by changing the order, for example making the algorithm move down before traveling right. You can also try to modify this algorithm into highlighting all correct paths.

Using the Maze Program

The maze solver is now complete, and you can start creating mazes for the computer to solve.

Create a maze with multiple solutions. Why does the program choose one path over another? Why doesn't it highlight both paths? Once you understand the answers to these questions, you will have a better understanding of this algorithm and recursion.

Resetting the Maze

The last thing needed is a reset button that changes the grey tiles to white and the start and finish back to light blue. Add the following code to your Form1.cs, and you are finished. I hope you have enjoyed this resource. If you have any questions or comments, feel free to email me at koflaherty@masteringcsharp.com. The full source code is below.

Adding the Reset Button Code

private void button2_Click(object sender, EventArgs e)
{
    // Change all gray tiles to white
    for (int i = 0; i < XTILES; i++)
    {
        for (int j = 0; j < YTILES; j++)
        {
            if (mazeTiles[i, j].BackColor == Color.Gray)
            {
                mazeTiles[i, j].BackColor = Color.White;
            }
        }
    }
    // Reset start and finish to light blue
    mazeTiles[0, 0].BackColor = Color.LightBlue;
    mazeTiles[XTILES - 1, YTILES - 1].BackColor = Color.LightBlue;
}

Complete Source Code (Form1.cs)

using System;
using System.Drawing;
using System.Windows.Forms;
namespace Your_Project_Name
{
    public partial class Form1 : Form
    {
        private Color currentColor = Color.White;
        private int XTILES = 25; // Number of X tiles
        private int YTILES = 25; // Number of Y tiles
        private int TILESIZE = 10; // Size of the tiles (pixels)
        private PictureBox[,] mazeTiles;
        public Form1()
        {
            InitializeComponent();
            createNewMaze();
        }
        private void createNewMaze()
        {
            mazeTiles = new PictureBox[XTILES, YTILES];

            // Loop for creating all tiles
            for (int i = 0; i < XTILES; i++)
            {
                for (int j = 0; j < YTILES; j++)
                {
                    // Initialize a new PictureBox at coordinate (i, j)
                    mazeTiles[i, j] = new PictureBox();

                    // Calculate size and location
                    int xPosition = (i * TILESIZE) + 13; // 13 is padding from the left
                    int yPosition = (j * TILESIZE) + 45; // 45 is padding from the top
                    mazeTiles[i, j].SetBounds(xPosition, yPosition, TILESIZE, TILESIZE);
                    // Make top-left and bottom-right corners light blue (used for start and finish)
                    if ((i == 0 && j == 0) || (i == XTILES - 1 && j == YTILES - 1))
                    {
                        mazeTiles[i, j].BackColor = Color.LightBlue;
                    }
                    else
                    {
                        // Make all other tiles white
                        mazeTiles[i, j].BackColor = Color.White;

                        // Make it clickable
                        mazeTiles[i, j].Click += PictureBox_Click;
                    }

                    // Add PictureBox to the form's controls
                    this.Controls.Add(mazeTiles[i, j]);
                }
            }
        }
        private void pictureBox1_Click(object sender, EventArgs e)
        {
            currentColor = Color.White;
        }
        private void pictureBox2_Click(object sender, EventArgs e)
        {
            currentColor = Color.Black;
        }
        private void PictureBox_Click(object sender, EventArgs e)
        {
            ((PictureBox)sender).BackColor = currentColor;
        }
        private void button1_Click(object sender, EventArgs e)
        {
            // Create a previously searched array
            bool[,] alreadySearched = new bool[XTILES, YTILES];

            // Start the recursive solver at tile (0, 0). If false, maze cannot be solved.
            if (!solveMaze(0, 0, alreadySearched))
            {
                MessageBox.Show("Maze cannot be solved.");
            }
        }
        private void button2_Click(object sender, EventArgs e)
        {
            // Change all gray tiles to white
            for (int i = 0; i < XTILES; i++)
            {
                for (int j = 0; j < YTILES; j++)
                {
                    if (mazeTiles[i, j].BackColor == Color.Gray)
                    {
                        mazeTiles[i, j].BackColor = Color.White;
                    }
                }
            }
            // Reset start and finish to light blue
            mazeTiles[0, 0].BackColor = Color.LightBlue;
            mazeTiles[XTILES - 1, YTILES - 1].BackColor = Color.LightBlue;
        }
        private bool solveMaze(int xPos, int yPos, bool[,] alreadySearched)
        {
            bool correctPath = false;
            bool shouldCheck = true;
            // Check for out-of-boundaries
            if (xPos >= XTILES || xPos < 0 || yPos >= YTILES || yPos < 0)
            {
                shouldCheck = false;
            }
            else
            {
                // Check if at the finish, not (0, 0 and colored light blue)
                if (mazeTiles[xPos, yPos].BackColor == Color.LightBlue && (xPos != 0 || yPos != 0))
                {
                    correctPath = true;
                    shouldCheck = false;
                }
                // Check for a wall
                if (mazeTiles[xPos, yPos].BackColor == Color.Black)
                {
                    shouldCheck = false;
                }
                // Check if previously searched
                if (alreadySearched[xPos, yPos])
                {
                    shouldCheck = false;
                }
            }
            // Search the tile
            if (shouldCheck)
            {
                // Mark tile as searched
                alreadySearched[xPos, yPos] = true;
                // Check the right tile
                correctPath = correctPath || solveMaze(xPos + 1, yPos, alreadySearched);
                // Check the down tile
                correctPath = correctPath || solveMaze(xPos, yPos + 1, alreadySearched);
                // Check the left tile
                correctPath = correctPath || solveMaze(xPos - 1, yPos, alreadySearched);
                // Check the up tile
                correctPath = correctPath || solveMaze(xPos, yPos - 1, alreadySearched);
            }
            // Make the correct path gray
            if (correctPath)
            {
                mazeTiles[xPos, yPos].BackColor = Color.Gray;
            }
            return correctPath;
        }
    }
}