Maze Solver (shortest path finder)

• Download demo project in Visual C# (requires Visual Studio .Net 2003) - 17.1 Kb
• Download source of Maze Solver class - 24 Kb

Introduction

The article presents a simple technique to find the shortest path between two points in a 2D Maze. Similar applications use graphs in such situations but this article shows how this can be done without the headache of graphs. It uses a technique similar to breadth-first search. The MazeSolver class stores the Maze as a 2D integer array with value '0' for open (available) nodes and non-zero for closed nodes (walls). If a path is to be found, a new 2D integer array is created with the path traced by PathCharacter whose default value is '100'. The class can also trace diagonal paths if it is allowed to do so.

Throughout this article, we will use "node" to refer elements of the matrix (2D integer array representing a maze). I assume that reader is familiar with graphs and its terminologies (edges, nodes, etc).

Breadth-First Search Algorithm

The general idea behind a breadth-first search algorithm is that we examine a starting node, say A. Then we examine all the neighbors of A, then we examine all the neighbors of all the neighbors of A, and so on.., until we reach the desired ending node or until we have no nodes to examine (in this case no path will exist). Naturally, we need to keep a track of all the nodes to assure that no node is processed more than once. This is accomplished by linking a field "status" with all the nodes. The outline of the algorithm is as follows:

1. Initialize all nodes to the ready state (Status=Ready)
2. Put the starting node, say A, in Queue and change its status to the waiting state (Status=Waiting)
3. Repeat steps a and b until Queue is empty:
   1. Remove the front node, say N, of Queue. Process N and change the status of N to the processed state (Status=Processed)
   2. Add to the rear of Queue all the neighbors of N that are in the ready state (Status=Ready), and change their status to the waiting state (Status=Waiting)
4. Exit

Shortest Path using the above algorithm

A minimum path between two nodes can be found using breadth-first search if we keep track of the origin of each edge (i.e. how we reach a particular element in the maze) by using an array Origin together with the array Queue. This method is used in the class.

Without Graphs!

Yes, the class uses breadth-first search technique without actual implementation of graphs. i.e. there is no class/struct used for graphs, no adjacency lists, no weights assigned to edges, etc. The only thing is mathematics; the class uses certain mathematical formulae to access the adjacent nodes of an element (node) in the matrix (maze). Lets see how it is done.

Node numbers

First, we assign node numbers to every element of the array starting from 0 to 'RowsXCols-1' in the manner below.

Methods below can be used to transform between node number and indexes of a matrix

int GetNodeNo(int matrix, int ithIndex, int jthIndex)
{
    return ( ithIndex*matrix.GetLength(1)+ jthIndex );
}

void GetMatrixIndexes(int matrix, int iNodeNo, out ithIndex, out jthIndex)
{
    int iCols=matrix.GetLength(1);
    ithIndex=iNodeNo/iCols;
    jthIndex=iNodeNo-iNodeNo/iCols*iCols;
}

The class, however, doesn't use separate methods for these transformations, they are done directly.

To apply the above algorithm, the class uses two integer array; Queue and Origin. A dummy array (equivalent to that of maze) is used to hold the current status of the respective nodes in the maze. To examine a node's adjacent nodes, we have to examine its left, right, top, bottom and 4 diagonal nodes (if diagonals are also to be searched).

Accessing Adjacent Nodes of a Node

Lets concentrate on the above picture representing node numbers of array elements. We'll have the following observations

To access the left node of a current node, the node number decreases by 1. If the current node is referred by iCurrent, then its left node can be accessed as:

iLeft=iCurrent-1;		// get node no of the left node

But we have to make sure that this node no. is valid. For this, we have to check:

• whether this node no. is inside the array bounds
• whether this node (iLeft) is in the same row of the maze as current node (iCurrent)
• whether there is a path from current node to this node (to check whether this node is empty or represents a wall etc)

we can do the above by the following code fragment

if (iLeft>=0 && iLeft/iCols==iCurrent/iCols)
    if ( GetNodeContents(m_iMaze, iLeft)==empty )
    {
				    //if left node is not a wall
        // then do something
    }

Similarly, we can write codes for accessing the right node by adding 1 to the current node no.

iRight=iCurrent+1;    // get node no of the right node
if (iRight<iMax && iRight/iCols==iCurrent/iCols)
    if ( GetNodeContents(m_iMaze, iRight)==empty )
    {
        // then do something
    }

for Top and Bottom nodes, we have to add the "no. of columns of the array" to the current node. Also in this case, we only have to check whether the new node no. is inside the bounds of array or not.

iTop=iCurrent-iCols;   // get node no of the top node
if (iTop>=0 )
    if ( GetNodeContents(m_iMaze, iTop)==empty )
    {
				    //if this node is not a wall
        // then do something
    }
    
iDown=iCurrent+iCols;    // get node no of the bottom node
if (iDown<iMax )
    if ( GetNodeContents(m_iMaze, iDown)==empty )
    {
				    //if this node is not a wall
        // then do something
    }

We can also access 4 diagonals nodes using similar approach. For simplicity of the article, lets only see how our upper-left diagonal is accessed:

iLeftUp=iCurrent-iCols-1;
if (iLeftUp>=0 && iLeftUp<iMax 
 && iLeftUp/iCols==iCurrent/iCols-1)
    //if upper-left node exists
    if ( GetNodeContents(m_iMaze, iLeftUp)==empty )
    {
				    //if this node is open(a path exists)
        // then do something
    }

Now lets see what is this "do something" in the above code fragments. Once we get the nodes adjacent to the current node, we have to add them to "Queue" if their status is Ready and change their status to Waiting. Lets see how to do this with our left node

iLeft=iCurrent-1;		// get node no of the left node
if (iLeft>=0 && iLeft/iCols==iCurrent/iCols)    
    //if this node exists
    if ( GetNodeContents(m_iMaze, iLeft)==empty )
        //if this node is open(a path exists)
        if (GetNodeContents(iMazeStatus, iLeft) 
         == (int)Status.Ready)
        //if this node is ready
        {
            Queue[iRear]=iLeft; //add to Q
            Origin[iRear]=iCurrent;
            //change status to waiting
            ChangeNodeContents(iMazeStatus, iLeft, 
             (int)Status.Waiting);
            iRear++;
        }

Once we have processed all the nodes in this way, we have to do "back-tracking" from our end-point to start-point. The array Queue contains node numbers of all the nodes in the maze which can be reached by node number stored in Origin array at corresponding index. i.e. the array Origin contains node numbers of all such nodes which are used as a path for the corresponding node no. in Queue. For example, lets assume that array contents of Queue and Origin as as under.

How can we find a path from node no. 1 to 8 :

• Start with the ending node 8 and see how is it reached. 8 is at 5th index in Queue while the corresponding 5th index in Origin is 9 which implies that 8 can be reached via node 9.
• Search for value 9 in the Queue. Its at 2nd index while the corresponding element at 2nd index in Origin is 1. This implies that node 9 can be reached via node 1.
• Search for value 1 in the Queue. Its at the 0th index with corresponding node no. -1 in Origin. This implies that node 1 was our initial point.
• Hence final path from 1 to 8 is: 1->9->8

Using the class

The class has two constructors, one that takes an integer array directly and the other that takes only dimensions. Indexers can be used to modify the contents of each node (i.e., to build/remove walls/obstacles in the maze).

MazeSolver maze=new MazeSolver(10,12)
maze[2,3]=1    // create wall at postion [2,3]
maze[3,3]=1    // create wall at postion [3,3]
maze[2,3]=0    // remove wall at postion [2,3]

To find a shortest path between, say [1,2] and [6,9], the user should call the method FindPath() which returns a solved maze (of course a 2D integer array) with the path traced by value 100 (this can be changed using the property PathCharacter). If no path exists, the function returns null.

// gets shortest path traced by '100' from [1,2] to [6,9]
int[,] iSolvedMaze=maze.FindPath(1,2,6,9)

About the Demo Project

The application presents a simple way to use the class. It consists of a 16x20 grid where walls can be created or removed. The ball rolls to every new position when the user clicks on a new location accessible from the original location.

History

Version 1.0

• Initial version

Version 1.1

• Extended the demo program so that it can handle rectangular (non-square) mazes also
• Fixed some small bugs

Version 1.2

• The class now allows diagonal paths as well.