12,996,388 members (71,654 online)
alternative version

#### Stats

195.2K views
90 bookmarked
Posted 12 Dec 2004

# Maze Solver (shortest path finder)

, 1 Mar 2005
 Rate this:
An article on finding shortest path in a 2D maze.

## 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).

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:

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)
{
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)```

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.

## Share

 Software Developer Pakistan

Syed Mehroz Alam, living in Karachi, Pakistan, is a developer focusing Microsoft technologies. He has completed his bachelors as a Computer Systems Engineer in 2006 and is currently pursuing a Masters degree in Computer Science. He loves to learn, discover and master all aspects of .NET and SQL Server. Mehroz has developed rich internet enterprise applications using Silverlight in addition to the traditional ASP.NET and Windows Forms applications. He has worked with all three components of SQL Business Intelligence Studio: SSIS, SSRS and SSAS for developing BI Solutions and Data warehouse. He loves to write complex TSQL queries and evaluate his skills by participating in various TSQL Challenges. His blog can be viewed at http://smehrozalam.wordpress.com.

## You may also be interested in...

 First Prev Next
 My vote of 5 vspin6-Jul-12 17:00 vspin 6-Jul-12 17:00
 modified version - with advanced path analysis abutun1-Jul-10 8:40 abutun 1-Jul-10 8:40
 hi here is my modified SHORTEST PATH FINDER, http://u2m.nu/aK[^] this one can find all possible solutions and cost analysis of the founded paths. thanks Ahmet BÜTÜN Ahmet BÜTÜN http://www.ahmetbutun.net
 How to add path weight jrcutbu17-Feb-10 13:07 jrcutbu 17-Feb-10 13:07
 Re: How to add path weight Syed Mehroz Alam18-Feb-10 1:01 Syed Mehroz Alam 18-Feb-10 1:01
 A small correction i think Kamran Vighio1-May-09 10:50 Kamran Vighio 1-May-09 10:50
 check this out abutun16-Nov-07 12:37 abutun 16-Nov-07 12:37
 Shortest path finder component dark_sidus2-Sep-07 22:07 dark_sidus 2-Sep-07 22:07
 all paths finder osazuwa2-Jun-06 8:11 osazuwa 2-Jun-06 8:11
 Needs more to read Will Gray21-Feb-05 5:05 Will Gray 21-Feb-05 5:05
 Re: Needs more to read Syed Mehroz Alam1-Mar-05 19:57 Syed Mehroz Alam 1-Mar-05 19:57
 Making your code somewhat more efficient Martin Friedrich16-Feb-05 11:50 Martin Friedrich 16-Feb-05 11:50
 Re: Making your code somewhat more efficient Martin Friedrich16-Feb-05 11:57 Martin Friedrich 16-Feb-05 11:57
 Re: Making your code somewhat more efficient Bert Buiskool25-Feb-05 1:41 Bert Buiskool 25-Feb-05 1:41
 Re: Making your code somewhat more efficient David Gallagher1-Mar-05 3:18 David Gallagher 1-Mar-05 3:18
 Re: Making your code somewhat more efficient Syed Mehroz Alam1-Mar-05 20:05 Syed Mehroz Alam 1-Mar-05 20:05
 Re: Making your code somewhat more efficient Syed Mehroz Alam3-Mar-05 15:21 Syed Mehroz Alam 3-Mar-05 15:21
 Re: Making your code somewhat more efficient BigBertB8-Mar-05 2:24 BigBertB 8-Mar-05 2:24
 Re: Making your code somewhat more efficient Syed Mehroz Alam1-Mar-05 20:02 Syed Mehroz Alam 1-Mar-05 20:02
 maths surgeproof16-Feb-05 0:28 surgeproof 16-Feb-05 0:28
 Re: maths Syed Mehroz Alam17-Feb-05 16:00 Syed Mehroz Alam 17-Feb-05 16:00
 Last Visit: 31-Dec-99 18:00     Last Update: 22-Jun-17 2:25 Refresh 1