Download source - 154.21 KB

Introduction

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

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

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.

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

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. 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 array. (My EXE improperly checks if the upper boundary equals 1 instead of less than 1. At least that bug is in the test EXE.)

ShowValidPath 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.

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.

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:

ThreeImages.jpg - Click to enlarge image

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?

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

8/31/11: Original version published
9/1/11: Added code in article
9/2/11: Modified code, created new download, additional code samples in article
9/5/11: New sample code and images of maze/bad/good paths
9/7/11: Fixed link to point to original article (publishing, changed the link)

Let's Try the Maze Article Again. This Time, It's for Real.