A Simple C# Labyrinth/Maze Solving Application
An application to solve a custom/random labyrinth represented with a .NET GridView control
- 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:
- It stores all the visited coordinates (
KeyValuePairof integers) - It marks the crossroads (
KeyValuePairof integers) it goes by and when a blockage is recognized, it goes back to the last crossroad and continues "moving" if possible. - It has one
mainmethod 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, yintvariables corresponding to the coordinates of cell and row indices and depending on the result, call each other in thisGoMove() mainmethod. - 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 theGridView.
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
- 30th April, 2009: Initial post