Solving Mazes Using Recursion

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. You can find a 9 page PDF in the download .zip or that and more PDF lessons at http://masteringcsharp.com/. I hope you enjoy my lesson!

Project Details

Project Goals:

• Goal 1: Create a maze creator using PictureBoxes. The PictureBoxes are referenced by a multi-dimensional array, mazeTiles[,] 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 the top right corner and the finish is 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 choosen a different name then it will have to be changed in code.

Name Space
//You must make sure you use your project name
namespace Your_Project_Name

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:

Solve Button - button1
Reset Button - button2
PictureBox White - pictureBox1
PictureBox Black - pictureBox2
Label Path - label1
Label Wall - label2



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 determinded by 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; // <- Add it here
        public Form1()
        {
            InitializeComponent();
        }
    }
}

Next make pixtureBox1 and pictureBox2 clickable by adding the following method to the form.cs. A quick way 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 PictureBoxes 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 (pixles)
private PictureBox[,] mazeTiles;

There needs to be a way to create the maze easily with one call from a method. The createNewMaze() method will create a gird of pictureBoxes. 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.Conrols.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 cordinate 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

8//make it clickable
EventHandler clickEvent = new EventHandler(PictureBox_Click);
mazeTiles[i, j].Click += clickEvent; // += 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 expermiment with the constants at the top of the code file to manipulate the tiles.

Constants:

private int XTILES = 25; //Number of X tiles
private int YTILES = 25; //Number of Y tiles
private int TILESIZE = 10; //Size of the tiles (pixles)
public partial class Form1 : Form



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
alreadySearched - 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
alreadySearched, Search the tile

Search: Marking in alreadySearched and Check right, down, left, up and return and if one returns the correct path return true.



Direction Precidence: 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 infinit loop. To prevent one we are adding an alreadySearched bool array and passing it as an argument though the solveMaze recursive method. The will prevent paths that are allready search 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".



Infinite Search

Adding the Solve Button Code

private void button1_Click(object sender, EventArgs e)
{
//Create a previously searched array
bool[,] alreadySearched = new bool[XTILES,YTILES];
//Starts the recursive solver at tile (0,0). If false maze can not be solved.
if(!solveMaze(0,0, alreadySearched))
MessageBox.Show("Maze can not 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;
     //should the computer check this tile
     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 precidence is direived 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.

Quick Tip: Create a maze with multiple solutions. Why does the program choice 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 [email protected]. The full source code is below.

Adding the Reset Button Code

private void button2_Click(object sender, EventArgs e)
{
    //Change all greay 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)

Complete Source Code

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 (pixles)
        private PictureBox[,] mazeTiles;

        public Form1()
        {
            InitializeComponent();
            createNewMaze();
        }

        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 cordinate 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 incase other events are used
                    }
 
                    //Add to controls to form (display picture box)
                    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];

            //Starts the recursive solver at tile (0,0). If false maze can not be solved.
            if(!solveMaze(0,0, alreadySearched))
                MessageBox.Show("Maze can not be solved.");
        }

        private void button2_Click(object sender, EventArgs e)
        {
            //Change all greay 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;
            //should the computer check this tile
            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;

        }

    }
}