Solving a Maze Without Recursion In C#

Some mazes have a very large number of solutions. In this case, we may encounter some problems of memory capacity. We will consider mazes whose number of solutions remain reasonable. Furthermore, we will avoid the solutions that pass repeatedly through the same cell in order not to have an infinite number of solutions.

Representation of mazes

We can represent a maze by a two-dimensional array of the integers with the following conventions,

• 1 = Wall
• 0 = Path

We set the table size to 10x10 in the source code, but this size can be changed or even become variable. The cells are located by their coordinates in a Windows coordinate system; i.e,. by pairs of the form column/line.



Algorithm

We will build the paths, starting from the entry point of the Maze and going in all the possible directions.

Actually a path extending from one point to another will be represented by a list of X-axis values and a list of Y-axis values of the points that make up the path.

The idea is to replace a path by all the paths obtained from it, by adding an unoccupied box not already visited at the end.

It initializes a list with a path containing a single point of departure.

It traverses the list of paths and for each path,

• If its last cell coincides with the point of arrival of the Maze, it moves the path to the list of the solutions.
• Down the path, it finds the free cells in one of the three directions, it creates new paths by cloning this path and adding a free cell at the end. We add all the new paths at the end of the list of the path and it removes the old ones from the list.
• If at the end of the path there is no free cell, it removes the path from the list.

The program

bool alreadyVisited(List < int > pX, List < int > pY, int x, int y)
{
    bool notVisited = true;
    int n = pX.Count - 1;
    while (n >= 0 && notVisited)
    {
        if (pX[n] == x)
            if (pY[n] == y)
            {
                notVisited = false;
            }
        n--;
    }
    return !notVisited;
}

public void SolveMaze()
{
    List < List < int >> pathXList = new List < List < int >> ();
    List < List < int >> pathYList = new List < List < int >> ();
    List < int > pathX = new List < int >
    {
        startX
    };
    List < int > pathY = new List < int >
    {
        startY
    };
    pathXList.Add(pathX);
    pathYList.Add(pathY);

    while (pathXList.Count > 0)
    {
        int pathNumber = pathXList.Count;
        while (pathNumber > 0)
        {
            pathX = pathXList[0];
            pathY = pathYList[0];
            int n = pathX.Count - 1;
            int x = pathX[n];
            int y = pathY[n];
            if (x == endX && y == endY)
            {
                completePathX.Add(pathX);
                completePathY.Add(pathY);
                pathXList.RemoveAt(0);
                pathYList.RemoveAt(0);
            } else
            {
                if (x < width - 1) // Checks if not on right edge
                    if (maze[x + 1, y] != 1)
                    if (!alreadyVisited(pathX, pathY, x + 1, y))
                    {
                        List < int > pX = new List < int > (pathX);
                        List < int > pY = new List < int > (pathY);
                        pX.Add(x + 1);
                        pY.Add(y);
                        pathXList.Add(pX);
                        pathYList.Add(pY);
                    }
                if (x > 0) // Checks if not on left edge
                    if (maze[x - 1, y] != 1)
                    if (!alreadyVisited(pathX, pathY, x - 1, y))
                    {
                        List < int > pX = new List < int > (pathX);
                        List < int > pY = new List < int > (pathY);
                        pX.Add(x - 1);
                        pY.Add(y);
                        pathXList.Add(pX);
                        pathYList.Add(pY);
                    }
                if (y > 0) // Checks if not on top edge
                    if (maze[x, y - 1] != 1)
                    if (!alreadyVisited(pathX, pathY, x, y - 1))
                    {
                        List < int > pX = new List < int > (pathX);
                        List < int > pY = new List < int > (pathY);
                        pX.Add(x);
                        pY.Add(y - 1);
                        pathXList.Add(pX);
                        pathYList.Add(pY);
                    }
                if (y < height - 1) // Checks if not on bottom edge
                    if (maze[x, y + 1] != 1)
                    if (!alreadyVisited(pathX, pathY, x, y + 1))
                    {
                        List < int > pX = new List < int > (pathX);
                        List < int > pY = new List < int > (pathY);
                        pX.Add(x);
                        pY.Add(y + 1);
                        pathXList.Add(pX);
                        pathYList.Add(pY);
                    }
                pathXList.RemoveAt(0);
                pathYList.RemoveAt(0);
            }
            pathNumber--;
        }
    }
}

 
The program can be improved by adding a method of automatically generating mazes. There is already an article in C# Corner about it.