再来尝试一下迷宫文章。这次是认真的。
DLL 库代码和控制台代码，用于生成与图像匹配的迷宫
引言
CodeProject 有一篇关于导航迷宫的文章 Solve_Maze_Problem，其中展示了一张迷宫的图片。我当时想，酷，一个迷宫求解器。我想知道别人会怎么做？我开始阅读文章，但规则毫无意义。那是因为文章与迷宫的实际工作方式无关，而是遵循了作者自定义的迷宫定义。我将提供可以创建和解决任何真实迷宫（例如图片中的迷宫）的代码，以及一个用于解决原始图片迷宫的控制台应用程序。（修改后的图片如下，我修改了它以定位迷宫中的位置。）
背景
此代码使用了一些您可能会觉得有用的技术。它使用递归方法来查找并验证迷宫是否有解决方案。我写这段代码直接源于我读到的文章以及我对其中提供的迷宫代码版本感到多么失望。下载的内容包括代码、一个包含有关程序工作原理的更多信息的文档文件，以及有关代码内容的更多信息。（我很快写了这个应用程序，可能存在 bug，但应该很容易修复，测试不足。）
Using the Code
下载内容包含一个 DLL。这是库代码，如果您愿意，可以使用它来构建迷宫设计器应用程序。它包含一个 EXE。这是一个控制台应用程序，用于设计迷宫并创建 HTML 输出以图形化方式显示迷宫。其中有一个目录，里面有几个图像文件。需要按原样创建这些文件以生成 Web 输出。HTML 文件是 EXE 生成的输出的副本。请阅读文档文件！它告诉您代码的功能和局限性、方法、属性、意外情况等。
DLL 包含两个 public 类：MazeArray 和 MazeElement。您使用 MazeArray 来定义您设计的迷宫，而 MazeElement 则在两个 MazeElement 数组属性中提供。迷宫元素具有为其在数组中位置定义的元素属性，它还具有定义其在数组中位置的 x/y 属性。（因此您也可以独立于数组来处理它们）您可以通过两种方式实例化 MazeArray 。默认情况下，它将与 9X9 数组一起工作，第二种方式是提供两个字节（x 和 y）来获取“x”乘以“y”的数组。任何小于 2 的 x 或 y 值都将重置为 9。此时，还没有设置起点或终点，也没有定义任何路径。您需要使用 MazeElement 数组来获取起点和终点，以及检索元素时的元素属性。
您可访问的数组不会保留在 MazeArray 实例中。如果您想从设计器类检索重新设计的元素，则必须检索新数组。
MazeTest 控制台应用程序设计了原始迷宫，验证了路径是否存在，并且还启动了使用原始迷宫作为基础来设计一个新 16X16 迷宫的过程。以下是使用新迷宫设计开始时生成的图像。（EXE 代码也将其中的数字放入了它生成的 HTML 中。）
请注意，在 7,0 和 15,0 处，迷宫在外部边框上戳了洞。一旦创建了路径，就可以稍后使用“DropMaze...”函数将其删除，就像“SetMaze...”函数创建路径一样。水平方向，正数表示“右”，负数表示“左”。垂直方向，正数表示向下，负数表示向上。顶部的数字对应 x 值，左侧的数字对应 y 值。此图像由代码的这一部分生成，该部分启动了新设计的延续，如下所示。
maze.XSize = 16;//Tested, right exit turned into down exit.
maze.YSize = 16;//Tested, converts the end element into no outside access
Fin = maze.Maze;// need to redefine the array here so Fin[15, 8] exists.
maze.SetMazeStart(Fin[7, 0], true, false);//Saying I do want exterior access,
//but with horizontal exit that is overridden to vertical exterior access
maze.SetMazeEnd(Fin[15, 8], true, true);//Similar result here with vertical exit.
maze.SetMazeRow(Fin[8, 0], 9);
maze.SetMazeRow(Fin[8, 5], 2);
maze.SetMazeRow(Fin[10, 4], -1);
maze.SetMazeRow(Fin[9, 3], 1);
maze.SetMazeRow(Fin[9, 2], 1);
maze.SetMazeRow(Fin[9, 1], 2);
maze.SetMazeRow(Fin[8, 8], 1);
maze.DropMazeRow(Fin[13, 0], 1);
maze.SetMazeCol(Fin[9, 0], 2);
maze.SetMazeCol(Fin[9, 3], 1);
maze.SetMazeCol(Fin[9, 6], 2);
maze.SetMazeCol(Fin[10, 2], 1);
maze.SetMazeCol(Fin[9, 6], 2);
Fin = maze.Maze; // need to redefine the array here so the
//endpoints are known in Fin
// Val = maze.ShowValidPath; // No point in executing,
//should now have no valid path
Console.WriteLine("The following is a modified maze<br>");
Console.WriteLine("<table border=\"0\" cellpadding=\"0\" cellspacing=\"0\">");
Console.Write("<tr><td> <br></td>");
for (x = 0; x <= Fin.GetUpperBound(0); x++)
{Console.Write("<td>{0}</td>",x);}
Console.WriteLine("</tr>");
for (y = 0; y <= Fin.GetUpperBound(1); y++) //Do Y first to get rows together
Console.Write("<tr><td>{0} </td>", y);
for (x = 0; x <= Fin.GetUpperBound(0); x++)
byte sum = 0;// determine the png images to display across the x dimension.
if (Fin[x, y].UpPathExists) sum += 1;
if (Fin[x, y].DownPathExists) sum += 2;
if (Fin[x, y].LeftPathExists) sum += 4;
if (Fin[x, y].RightPathExists) sum += 8;
Console.WriteLine("<td><img src=\"MazeImages\\" + png[sum] + ".png\"></td>");
Console.WriteLine("</tr>");
Console.WriteLine("</table>");
此代码的一个特点是递归逻辑。这是编程中一个非常有用的、广泛使用但又被高度误解的特性。这是我的递归例程的一个子集（DLL 代码的一部分）
/// <summary>
/// Recursive routine to go through all the pathways from starting point
/// to ending point.
/// Finding all valid pathways and dead ends.
/// </summary>
/// <param name="stx">Current starting point for the maze in the x direction
/// </param>
/// <param name="sty">Current starting point for the maze in the y direction
/// </param>
/// <param name="enx">Target end point for the maze in the x direction</param>
/// <param name="eny">Target end point for the maze in the y direction</param>
private void FindPaths(byte stx, byte sty, byte enx, byte eny)
{
MazeElement1 m;
MazeElement1 n;
mze[stx, sty].ThisPathUsed = true;
m = this.mze[stx, sty];//Don't update this path until finished
if (stx == enx && sty == eny)
{
mze[stx, sty].IsValidPath = true;
mze[stx, sty].NumValidPaths++;
return;
}
byte cnt=0;
// if (mze[stx, sty].upExists && sty > 0){...}
// Similar but more verbose logic dropped in this sample code
if (mze[stx, sty].dpExists && sty < this.ysz - 1)//concise version of the logic
{
cnt++;
n = this.mze[stx, sty + 1];
if (n.ThisPathUsed) m.NumLoopBacks++;
else FindPaths(stx, (byte)(sty + 1), enx, eny);
n = this.mze[stx, sty + 1];
m.NumDeadEnds += n.NumDeadEnds;
m.NumValidPaths += n.NumValidPaths;
m.NumLoopBacks += n.NumLoopBacks;
mze[stx, sty].DownPathUsed = true;
}
// if (mze[stx, sty].lpExists && stx > 0)){...}
// Similar logic dropped
// if (mze[stx, sty].rpExists && stx < this.xsz - 1){...}
// Similar logic dropped
if (cnt <= 1) m.NumDeadEnds++;
m.NumLoopBacks--;//Remove the count of the traceback to the calling source
m.UpPathUsed = mze[stx, sty].UpPathUsed;
m.DownPathUsed = mze[stx, sty].DownPathUsed;
m.LeftPathUsed = mze[stx, sty].LeftPathUsed;
m.RightPathUsed = mze[stx, sty].RightPathUsed;
m.ThisPathUsed = false;//Turn off the used flag so traceback calls
//to deadends can later be used to find actually valid paths
mze[stx, sty] = m;
return;
}
为什么它是递归的？因为该例程被调用为 FindPaths，并且它又调用了一个名为 FindPaths 的例程。另一种递归方式（但在此情况下不是）是它调用一个例程，该例程（最终）调用 FindPaths。（在另一种类型的循环中反复调用的例程不属于递归。）
这是子集，因为使用相似逻辑的四个方向中的三个方向的逻辑已在此代码片段中注释掉了。（请使用下载内容获取真实代码。）
第一次调用它是在一个名为 CalculatePaths 的例程中。这是由 get 属性 ShowValidPath 调用的。它之所以调用，是因为迷宫已被修改，并且自上次修改以来该属性尚未执行。如果迷宫没有正确设置起点和终点，该属性将返回一个 1X1 的 MazeElement 数组。（我的 EXE 不正确地检查上边界是否等于 1 而不是小于 1。至少这个 bug 存在于测试 EXE 中。）
ShowValidPath 是一个属性，它返回一个包含一个 null MazeElement 的 1X1 数组，或者返回当前定义的迷宫，但有一个例外。属于从起点到终点的有效路径的每个元素都将是终点位置的元素，而不是该位置的有效元素。第一次调用可能来自 CalculatePaths，它将是最后调用的那个也调用了递归例程 FindPaths。
如果迷宫设置不正确，这应该始终返回一个包含 null 的 1X1 MazeElement 数组。（我没有充分测试以验证这一点总是会发生。）该例程的目的是遍历所有可能的路径以找到所有有效的路径。防止这种情况成为无限循环的关键是命令“mze[stx, sty].ThisPathUsed = true;”
其他 PathUsed bool 字段用于什么？噪音。我尚未修复的逻辑。抱歉，我想我之前提到过递归逻辑可能会让人头疼。我曾计划停止使用已检查过的路径，然后意识到循环路径需要重新检查。您走了一条路，它选择了一条通往调用例程的路。它已经被使用过了，所以将其“杀死”。现在选择另一条路，这条路找到了终点。太好了，找到了路，但“杀死”了那条路，所以之前的调用不会通过它，也不会发现有一条路。
请注意，255X255 的迷宫有超过 63K 个迷宫元素，可能会导致代码中止。（由于各种资源/计数问题。）我考虑了一种显示解决方案和无效路径的替代方法。下载内容中未提供代码，但它看起来会是这样
这是生成上述图像的代码
Console.WriteLine("<br><br>
The following shows the full maze, then the bad pathways,
finally only solution pathways<br><br>");
Console.WriteLine("<table border=\"1\"
cellpadding=\"5\" cellspacing=\"10\"><tr><td>");
Console.WriteLine("<table border=\"0\"
cellpadding=\"0\" cellspacing=\"0\">");
for (y = 0; y <= Val.GetUpperBound(1); y++)
{
Console.Write("<tr>");
for (x = 0; x <= Val.GetUpperBound(0); x++)
{
byte sum = 0;// determine the png images to display across the x dimension.
if (Fin[x, y].UpPathExists) sum += 1;
if (Fin[x, y].DownPathExists) sum += 2;
if (Fin[x, y].LeftPathExists) sum += 4;
if (Fin[x, y].RightPathExists) sum += 8;
Console.WriteLine("<td><img src=\"
MazeImages\\" + png[sum] + ".png\"></td>");
}
Console.WriteLine("</tr>");
}
Console.WriteLine("</table></td><td><
table border=\"0\" cellpadding=\"0\" cellspacing=\"0\">");
for (y = 0; y <= Val.GetUpperBound(1); y++)
{
Console.Write("<tr>");
for (x = 0; x <= Val.GetUpperBound(0); x++)
{
byte sum = 0;// determine the png images to display across the x dimension.
if (Val[x, y].XLocation == 8 && Val[x, y].YLocation == 8) sum = 0;
else
{
if (Fin[x, y].UpPathExists) sum += 1;
if (Fin[x, y].DownPathExists) sum += 2;
if (Fin[x, y].LeftPathExists) sum += 4;
if (Fin[x, y].RightPathExists) sum += 8;
}
Console.WriteLine("<td><img src=\"
MazeImages\\" + png[sum] + ".png\"></td>");
}
Console.WriteLine("</tr>");
}
Console.WriteLine("</table></td><td><
table border=\"0\" cellpadding=\"0\" cellspacing=\"0\">");
for (y = 0; y <= Val.GetUpperBound(1); y++)
{
Console.Write("<tr>");
for (x = 0; x <= Val.GetUpperBound(0); x++)
{
byte sum = 0;// determine the png images to display across the x dimension.
if (Val[x, y].XLocation == 8 && Val[x, y].YLocation == 8)
{
if (Fin[x, y].UpPathExists) sum += 1;
if (Fin[x, y].DownPathExists) sum += 2;
if (Fin[x, y].LeftPathExists) sum += 4;
if (Fin[x, y].RightPathExists) sum += 8;
}
Console.WriteLine("<td><img src=\"
MazeImages\\" + png[sum] + ".png\"></td>");
}
Console.WriteLine("</tr>");
}
Console.WriteLine("</table></td></tr></table>");
}
关注点
我忘了 struct 在我写这段代码时是一个值类型。它破坏了我的逻辑（递归=无限循环），后来却意外地成为了递归逻辑的一个好处（在准备好提供数组之前，可以进行中间更改）。
我曾有宏图伟志。递归逻辑可能会让人谦逊。其中一些计划仍然存在于 struct 中，可以删除，或者您可能更擅长？
我原本没有计划生成 HTML。生活中发生了一些事情。（我需要提高我的网页技能。）现在，我意外地有了真实的迷宫图像可以查看，或者您可以验证您新设计的迷宫是否可以。
历史
- 2011 年 8 月 31 日：发布初始版本
- 2011 年 9 月 1 日：在文章中添加了代码
- 2011 年 9 月 2 日：修改了代码，创建了新的下载内容，并在文章中添加了其他代码示例
- 2011 年 9 月 5 日：新的示例代码和迷宫/无效/有效路径的图像
- 2011 年 9 月 7 日：修复了指向原始文章的链接（发布时，更改了链接）