A Simple C# Labyrinth/Maze Solving Application

• Download complete source - 35.72 KB
• Download Visual Studio 2008 solution - 62.54 KB
• Download the ultimate maze 2 - 575 B

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:

// 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

• 30^th April, 2009: Initial post