让我们再次尝试迷宫文章.这次,这是真实的.（译文）

原文地址：https://www.codeproject.com/Articles/248134/Lets-try-the-Maze-article-again-This-time-its-for

原文作者：KP Lee

译文由本站 robot-v1.0 翻译

前言

DLL library code and Console code to produce a Maze that matches the image

DLL库代码和控制台代码以生成与映像匹配的迷宫

• 下载源154.21 KB(Download source - 154.21 KB)

介绍(Introduction)

CodeProject上有一篇关于迷宫导航的文章(CodeProject had an article for navigating a maze) 解决迷宫问题(Solve_Maze_Problem) 并显示出迷宫的图像.我想,很酷,一个迷宫求解器.我不知道别人会怎么做？我开始阅读这篇文章,但规则没有任何意义.那是因为本文与迷宫的真正工作方式无关,并遵循了作者对迷宫的自定义定义.我将提供代码来创建和解决任何真实的迷宫,例如图像中的迷宫,以及提供一个控制台应用程序的代码,该应用程序仅对原始的迷宫一样. (下面的修改图像,我对其进行了修改以定位迷宫中的位置.)(and showed an image of a maze. I thought, cool, a maze solver. I wonder how someone else would do it? I started to read the article and the rules didn’t make any sense. That was because the article had nothing to do with how Mazes really work and followed the author’s custom definition of a Maze. I am going to provide code that can create and solve any real maze like the one in the image and a Console app that does just that for the original pictured maze. (Modified image below, I modified it to locate positions in the maze.))

背景(Background)

该代码使用了几种您可能会发现有用的技术.它使用递归方法来查找并验证迷宫是否具有解决方案.我写代码是阅读文章的直接结果,并且对所展示的迷宫代码版本感到失望.下载内容包括代码,一个doc文件,其中包含有关程序运行方式的更多信息以及有关代码内容的更多信息. (我快速编写了该应用程序,可能存在错误,但应该易于修复,测试不足.)(This code uses several techniques you may find useful. It uses recursive methods to find and verify that the maze has a solution. I wrote the code as a direct result of the article I read and how disappointed I was in the version of maze code presented. The download includes code, a doc file with more information about how the program will work and more information about the contents of the code. (I wrote the app quickly, bugs may exist, but should be easy to fix, inadequate testing was done.))

使用代码(Using the Code)

下载包含一个DLL.这是库代码,您可以根据需要构建迷宫设计器应用程序.它包含一个EXE.这是一个控制台应用程序,用于设计迷宫并创建HTML输出以图形方式显示迷宫.有一个目录,其中包含多个图像文件.需要按原样创建以产生Web输出. HTML文件是EXE生成的输出的副本.阅读文档文件!告诉您代码做什么和不做什么,方法,属性,惊喜等.(The download contains a DLL. This is the library code that will let you build a maze designer app if you wish. It contains an EXE. This is a Console app to design the maze and create HTML output to graphically show the maze. There is a directory with several image files in it. That needs to be created as-is to produce the web output. The HTML file is a copy of the output generated by the EXE. READ the doc file! Tells you what the code does and doesn’t do, methods, properties, surprises, etc.) DLL有两个(The DLL has two) public 类,(classes,) MazeArray 和(, and) MazeElement .你用(. You use) MazeArray 定义您设计的迷宫(to define the maze you design and) MazeElement 提供两个(is provided in two) MazeElement 数组属性.迷宫元素具有在其设计的数组中的位置处为该元素定义的属性,还具有x/y属性,用于定义其在数组中的位置. (因此,您也可以独立于数组对待它们)可以实例化(array properties. The maze element has properties defined for the element at the location in the array it is designed, it also has x/y properties that define where it is in the array. (So you can also treat them independently from the array) You can instantiate) MazeArray 两种方式.默认值适用于9X9数组,第二种方式,您提供了两个字节((two ways. The default will work with a 9X9 array, the second way, you provide two bytes () x 和(and) y )获得"() to get a “) x “由”(” by “) y “数组.小于(” array. Anything less than) 2 对于(for) x 要么(or) y 将重置为(will reset to) 9 .在这一点上,还没有开始或结束或定义任何途径.您需要与(. At this point, there isn’t a start or an end or any pathways defined. You need to work with the) MazeElement 数组以获取起点和终点,以及在检索元素时的元素属性.(array to get the start and end points and also the properties of the elements at the time they are retrieved.) 您有权访问的数组不会保留在(The arrays you have access to aren’t retained in the) MazeArray 实例.如果要从设计器类中检索重新设计的元素,则必须检索一个新数组.(instance. You have to retrieve a new array if you want to retrieve redesigned elements from the designer class.) 的(The) MazeTest 控制台应用程序设计原始迷宫,验证路径是否存在,并开始以原始迷宫为起点设计新的16X16迷宫的过程.以下是新迷宫设计开始时生成的图像. (EXE代码也将其生成的HTML中的数字放入其中.)(console app designs the original maze, verifies a path exists, and also STARTS the process of designing a new 16X16 maze using the original maze as a starting basis. The following is the image generated with the start of a new maze design. (The EXE code put in the numbers in the HTML it generates as well.))

不吃(Note at) 7,0 和(and) 15,0 迷宫在外面的边界上戳破了孔.创建路径后,以后可以使用”(the maze pokes holes in the outside borders. Once a path is created, it can then be removed later with “) DropMaze... “功能就像(” functions just like the “) SetMaze... 会创建路径.水平方向上,正数为"右”,负数为左.垂直方向,正数向下,负数向上.(” ones create paths. Horizontally, positive is “right” and negative is left. Vertically, positive is down, negative is up. Numbers on top match) x 左侧匹配的值和数字(values and numbers on the left match) y .该图像是由代码部分生成的,该代码部分开始进行中的新设计的继续,如下所示:(. This image is generated by the section of code that starts the continuation of the new design in progress is shown below:)

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代码的一部分):(One of the features of this code is recursive logic. This is a very useful, highly used, highly misunderstood feature of coding. Here is a subset of my recursive routine (part of DLL code):)

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

为什么要递归？因为例程被调用(Why is it recursive? Because the routine is called) FindPaths 它调用了一个名为(and it calls a routine called) FindPaths .可以递归的另一种方式(但不是这种情况)是,如果它调用了(最终)调用的例程(. Another way it could be recursive (but isn’t in this case) is if it calls a routine that (eventually) calls) FindPaths . (在另一种类型的循环中反复调用的例程不是递归的.)(. (A routine called over and over in another type of loop is NOT recursive.)) 这是一个子集,因为在此代码段中注释了使用相似逻辑的四个方向中的三个方向的逻辑. (请使用下载获取真实代码.)(It’s a subset, because the logic for three of the four directions that use similar logic are commented out of this code snippet. (Do use the download to get the real code.)) 第一次从例程调用(The very first time it is called from a routine called) CalculatePaths .那叫(. That is called by the) get 属性(property) ShowValidPath .之所以这样称呼它,是因为迷宫已被修改,并且此属性从此以后就没有执行过.如果迷宫没有正确设置好迷宫中的起点和终点,则属性将返回1X1(. It calls it because the maze has been modified and the property hasn’t been executed since. If the maze isn’t properly set up with starting and ending points set in the maze, the property will return a 1X1) MazeElement 数组. (我的EXE错误地检查了上限是否等于(array. (My EXE improperly checks if the upper boundary equals) 1 而不是少于(instead of less than) 1 .至少该错误在测试EXE中.)(. At least that bug is in the test EXE.)) ShowValidPath 是一个属性,返回带一个1X1数组(is a property the returns either a 1X1 array with one) null MazeElement 或当前定义的迷宫,只有一个例外.从头到尾都是有效路径一部分的每个元素都将具有结束位置的元素(or the currently defined maze with one exception. Every element that is part of a valid pathway from start to finish will have the end position’s element) INSTEAD 该位置的有效元素的值.它可能执行的第一个调用来自(of the valid element for that location. The first call it may execute comes from) CalculatePaths ,这将是最后执行的调用,也称为递归例程(, it will be the very last call executed that also called the recursive routine) FindPaths .(.) 如果您没有正确设置迷宫,则应始终返回1X1(If you haven’t set up the maze properly, this should always return a 1X1) MazeElement 与数组(array with) null 在里面. (我没有经过适当的测试来验证是否总是这样.)例程的重点是遍历所有可能的路径以找到所有有效的路径.防止此循环成为无限循环的关键是命令"(in it. (I haven’t properly tested to verify this always happens.) The point of the routine is to go through all the possible paths to find all the valid paths. The key to keep this from being an infinite loop is the command “) mze[stx, sty].ThisPathUsed = true; “(") 还有什么(What are the other) PathUsed bool 字段用于？噪声.我还没有解决的逻辑.抱歉,我想我之前提到过递归逻辑会使您头痛.我计划停止使用已经检查过的路径,然后意识到需要重新检查循环路径.您沿着一条路径走,它选择了一条返回到调用例程的路径.它已经被使用过,所以杀死它.现在选择另一条找到终点的路径.太好了,找到了路径但杀死了该路径,因此较早的呼叫不会通过该路径,也不会发现存在路径.(fields used for? Noise. Logic that I haven’t fixed. Sorry, I think I mentioned before that recursive logic can give you headaches. I had plans to stop using pathways that were already checked and then realized that circular paths NEED to be rechecked. You go down one path, it picks a path that leads back to the calling routine. It’s been used so kill it. Now pick another path that finds the end point. Great, found the path but killed the path so the earlier call doesn’t go through it and doesn’t find out there is an path.) 请注意,255X255迷宫具有超过63K的迷宫元素,并可能导致代码中止. (针对各种资源/计数问题.)我想到了一种显示解决方案和错误路径的替代方法.该代码未在下载中提供,但看起来像这样:(Note that a 255X255 maze has over 63K maze elements and could cause the code to abort. (For various resource/counting problems.) I thought of an alternate way of showing solutions and bad paths. The code isn’t supplied in the downloads, but it would look like this:) 这是生成以上图像的代码:(Here is the code that generated the above images:)

    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>");
}

兴趣点(Points of Interest)

我忘了(I forgot that) struct 当我写这篇文章时是一个值类型.杀死了我的逻辑(递归=无限循环),然后证明了递归逻辑的意外好处(进行了一些中间更改,这些更改在准备好提供之前在数组中不可用).(is a value type when I wrote this. Killed my logic (recursive=infinite loop) and then turned out to be an unexpected benefit in the recursive logic (make intermediate changes that aren’t available in the array until ready to be supplied).) 我有很大的计划.递归逻辑可能有点令人毛骨悚然.其中一些计划仍在(I had big plans. Recursive logic can be kind of humbling. Some of those plans are still in the) struct 可以删除,或者您比较擅长？(and could be removed or maybe you are better at it?) 我没有计划生成HTML.生活中出现了一些事情. (提高我的网络技能.)现在,我意外地看到了迷宫的真实图像,或者让您验证您的新迷宫设计是否可以.(I had no plans to generate HTML. Something came up in life. (Brush up on my web skills.) Now I have unexpectedly real images of the maze to look at or for you to verify your new maze design is OK.)

历史(History)

• 11年8月31日:发布了原始版本(8/31/11: Original version published)
• 9/1/11:文章中添​​加了代码(9/1/11: Added code in article)
• 2011年9月2日:修改的代码,创建了新的下载文件,本文中的其他代码示例(9/2/11: Modified code, created new download, additional code samples in article)
• 9/5/11:新的示例代码和迷宫/不良/良好路径的图像(9/5/11: New sample code and images of maze/bad/good paths)
• 9/7/11:修复了指向原始文章的链接(发布,更改了链接)(9/7/11: Fixed link to point to original article (publishing, changed the link))

许可

本文以及所有相关的源代码和文件均已获得The Code Project Open License (CPOL)的许可。