一个简单的 C# 迷宫/迷宫求解应用程序

• 下载完整源代码 - 35.72 KB
• 下载 Visual Studio 2008 解决方案 - 62.54 KB
• 下载终极迷宫 2 - 575 B

这是一个简单的应用程序，您可以通过单击来使用 GridView 控件创建迷宫。单元格具有 true 或 false 值。 值为 false 的单元格表示可通过的区域，而值为 true 的单元格可以认为是墙壁。 当然，最重要的是，迷宫会被解决。

背景

我不小心看到了一篇关于迷宫求解算法的文章。 我决定自己尝试寻找解决方案。

Using the Code

如我之前在介绍中所解释的那样，迷宫通过 GridView 控件表示，值为 false 的单元格是可通过的区域。 您可以通过单击每个单元格来创建自己的路径和十字路口。 移动是通过更改当前单元格的样式以及根据可通过的区域更改 x, y 坐标来表示的。 该“算法”遵循的规则是

1. 它存储所有访问过的坐标（整数的 KeyValuePair ）
2. 它标记它经过的十字路口（整数的 KeyValuePair ），并且当识别到阻塞时，它会返回到最后一个十字路口并继续“移动”，如果可能的话。
3. 它有一个 main 方法，该方法被递归调用以执行移动。 我们还有 4 个支持方法，称为：LookLeft()、LookRight()、LookUp()、LookDown()，它们返回布尔值并执行移动，通过更改对应于单元格和行索引的坐标的 x, y int 变量，并根据结果，在 GoMove() main 方法中相互调用。
4. 为了识别路径上的阻塞，程序使用 CanLookRight()、CanLookLeft() 等方法，这些方法也返回布尔值。 它们与前面提到的方法唯一的区别在于，它们不更改 x,y 变量，并且在 GridView 上不执行实际的“移动”。

这是主要的 GoMove 方法，它使用支持的 LookLeft 等支持方法并递归调用自身以在可通过的区域上执行移动

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

关注点

您还可以将创建的迷宫保存为 *.txt 文件，然后将其加载到应用程序中。 这是我创建的 2 个示例迷宫，您可以在下载 VS 2008 解决方案后立即加载和测试。 您还可以调整迷宫求解的速度（每毫秒一个单元格）。

历史

• 2009 年 4 月 30 日：初始发布