Click here to Skip to main content
15,867,771 members
Articles / Programming Languages / C#

A Simple C# Labyrinth/Maze Solving Application

Rate me:
Please Sign up or sign in to vote.
3.67/5 (5 votes)
30 Apr 2009CPOL2 min read 68.3K   538   25   3
An application to solve a custom/random labyrinth represented with a .NET GridView control
MazeApp_small.GIF

This is a simple application where by clicking you can create a maze using a GridView control. Cells have either true or false values. The ones with false ones represent the passable areas and the true-valued ones are so to say the walls. Most importantly, of course, the maze gets solved.

Background

I have accidentally landed once on an article regarding maze solving algorithms. I decided to try and find a solution myself.

Using the Code

As I have explained earlier in the introduction, the maze is represented via a GridView control, false-valued cells being the passable areas. You create your own paths and crossroads by clicking each individual cell. The movement is represented by changing the style of the current cell and changing the x, y coordinates according to the passable areas. The rules that the "algorithm" follow are:

  1. It stores all the visited coordinates (KeyValuePair of integers)
  2. It marks the crossroads (KeyValuePair of integers) it goes by and when a blockage is recognized, it goes back to the last crossroad and continues "moving" if possible.
  3. It has one main method which is being called recursively to perform the movement. We also have 4 supporting methods called: LookLeft(), LookRight(), LookUp(), LookDown() which return boolean and perform a move by changing x, y int variables corresponding to the coordinates of cell and row indices and depending on the result, call each other in this GoMove() main method.
  4. To recognize a blockage on the path taken, the program uses CanLookRight(), CanLookLeft(), etc. methods which also return boolean values. The only difference they have to the previously mentioned methods is that they don't change the x,y variables and perform no actual "movement" on the GridView.

This is the main GoMove method which uses the supporting LookLeft, etc. supporting methods and calls itself recursively to perform movement on the passable areas:

C#
// we run this method on a separate thread to avoid "hanging" in the form
void GoMove0()
{
    CheckForIllegalCrossThreadCalls = false;
    if (x == 0 && y == 0)
    {
        return;
    }

    if (hasPassed)
    {
        if (z < crossroads.Count)
        { 
#region [ checks if it has stucked up ]
            if (!CanLookUp()) // checks if it can go up
            {
                if (!CanLookRight()) // checks if it can go right
                {
                    if (!CanLookLeft()) // checks if it can go left
                    {
                        if (!LookDown()) 	// checks if it can go down;
					// if true goes all the way
                        {	// sets the current coordinates to those of the 
			// last visited crossroad and calls the method again.
                            y = crossroads[z].Key;
                            x = crossroads[z].Value;
                            z++;

                            GoMove0();
                        }
                    }
                }
            }
#endregion
#region [ checks if it has stucked down ]
            if (!CanLookDown())
            {
                if (!CanLookRight())
                {
                    if (!CanLookLeft())
                    {
                        if (!LookUp())
                        {
                            y = crossroads[z].Key;
                            x = crossroads[z].Value;
                            z++;

                            GoMove0();
                        }
                    }
                }
            }
#endregion
#region [ checks if it has stucked left ]
            if (!CanLookLeft())
            {
                if (!CanLookUp())
                {
                    if (!CanLookDown())
                    {
                        if (!LookRight())
                        {
                            y = crossroads[z].Key;
                            x = crossroads[z].Value;
                            z++;

                            GoMove0();
                        }
                    }
                }
            }
#endregion
#region [ checks if it has stucked right ]
            if (!CanLookRight())
            {
                if (!CanLookUp())
                {
                    if (!CanLookDown())
                    {
                        if (!LookLeft())
                        {
                            y = crossroads[z].Key;
                            x = crossroads[z].Value;
                            z++;

                            GoMove0();
                        }
                    }
                }
            }
#endregion
        }
    }
    hasPassed = true;
    if (LookUp()) // goes all the way up
    {
        if (!LookLeft()) 	// it went all the way up tries left, 
			// if not goes right if possible
        {
            LookRight();
        }

        GoMove0(); // recursive call to continue movement
        return;
    }
    if (LookDown())
    {
        if (!LookLeft())
        {
            LookRight();
        }
        GoMove0();
        return;
    }
    if (LookRight())
    {
        if (!LookDown())
        {
            LookUp();
        } 
        GoMove0();
        return;
    } 
    if (LookLeft())
    {
        if (!LookDown())
        {
            LookUp();
        } 
        GoMove0();
        return;
    } 
}

bool LookLeft()
{
	bool hasMoved = false; 

	try
	{ 
	// checks if the following cell is a passable area 
	//(if the cell is false-valued) 
	while (!checkIfVisited(x-1,y) && 
	    Convert.ToBoolean(dataGridView1.Rows[y].Cells[x - 1].Value) == false)
	{ 
	// if it hasn't visited the current coordinates, performs a 'move'
	// and then sets the hasMoved flag to true;
	hasMoved = true;

	visitedCoordinates.Add(new KeyValuePair<int, int>(x, y));
	// performs a 'move'
	x = x - 1;
	listBox1.Items.Add("x = " + x.ToString() + "\t\ty = " + y.ToString());

	// sets a distinguished style for the visited cell
	dataGridView1.Rows[y].Cells[x].Style = style2;
	// set it's value to true
	dataGridView1.Rows[y].Cells[x].Value = true;
	// puts the thread to sleep to get that sleek move feel
	System.Threading.Thread.Sleep(Convert.ToInt16(textBoxSpeed.Text)); 

	#endregion 
	// checks for crosssroads on the way
	if ((bool)dataGridView1.Rows[y].Cells[x - 1].Value == false)
	{
		// if a passing on the upper side cell has false value we then have 
		// a 'T' shaped crossroad and add its coordinates to the list
		if ((bool)dataGridView1.Rows[y + 1].Cells[x].Value == false)
		{
			dataGridView1.Rows[y + 1].Cells[x].Style = style3;
			crossroads.Add(new KeyValuePair<int, int>(y + 1, x));
			listBox2.Items.Add("x = " + x.ToString() + " y = " + 
							(y + 1).ToString());
		}
		// if an underlying cell has false value we then have 
		// a 'T' shaped crossroad and add its coordinates to the list
		if ((bool)dataGridView1.Rows[y - 1].Cells[x].Value == false)
		{
			dataGridView1.Rows[y - 1].Cells[x].Style = style3;
			crossroads.Add(new KeyValuePair<int, int>(y - 1, x));
			listBox2.Items.Add("x = " + x.ToString() + " y = " + 
							(y - 1).ToString());
		}
	}
} 
if (hasMoved)
{
	return true;
}
else
	return false; 
}
catch
{
	if (hasMoved)
{
return true;
}
else
	return false;
	}
}

Points of Interest

You can also save the mazes you create as *.txt files and then load them into the application. Here are 2 sample mazes I have created which you can load and test right away after downloading the VS 2008 solution. You can also adjust the speed (cell per millisecond) the maze is being solved.

History

  • 30th April, 2009: Initial post

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer (Junior)
Bulgaria Bulgaria
I am a 26 year old programmer with 5 years of experience in .NET programming. I am interested in developing ASP.NET AJAX enabled applications utilizing SSRS, MSSQL Server etc.

Comments and Discussions

 
GeneralMy vote of 3 Pin
noreply-thephoenixprod14-Jul-11 0:35
noreply-thephoenixprod14-Jul-11 0:35 
Not bad.
JokeInfo Pin
Plamen Kovandjiev12-May-09 8:50
professionalPlamen Kovandjiev12-May-09 8:50 
GeneralRe: Info Pin
rusevd12-May-09 20:18
rusevd12-May-09 20:18 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.