using System;
namespace Mehroz
{
///
/// Summary description for MazeSolver.
/// Class name: MazeSolver
/// Developed by: Syed Mehroz Alam
/// Email: smehrozalam@yahoo.com
/// URL: Programming Home "http://www.geocities.com/smehrozalam/"
///
/// Constructors:
/// ( int[,] ): takes 2D integer array
/// ( int Rows, int Cols ) initializes the dimensions, indexers may be used
/// to set individual elements' values
///
/// Properties:
/// Rows: returns the no. of rows in the current maze
/// Cols: returns the no. of columns in the current maze
/// Maze: returns the current maze as a 2D array
/// PathCharacter: to get/set the value of path tracing character
///
/// Indexers:
/// [i,j] = used to set/get elements of maze
///
/// Public Methods (Description is given with respective methods' definitions)
/// int[,] FindPath(int iFromY, int iFromX, int iToY, int iToX)
///
/// Private Methods
/// void GetNodeContents(int[,] iMaze, int iNodeNo)
/// void ChangeNodeContents(int[,] iMaze, int iNodeNo, int iNewValue)
/// int[,] Search(int iBeginningNode, int iEndingNode)
///
///
delegate void MazeChangedHandler(int iChanged, int jChanged);
class MazeSolver
{
///
/// Class attributes/members
///
int[,] m_iMaze;
int m_iRows;
int m_iCols;
int iPath=100;
public event MazeChangedHandler OnMazeChangedEvent;
///
/// Constructor 1: takes a 2D integer array
///
public MazeSolver(int[,] iMaze)
{
m_iMaze=iMaze;
m_iRows=iMaze.GetLength(0);
m_iCols=iMaze.GetLength(1);
}
///
/// Constructor 2: initializes the dimensions of maze,
/// later, indexers may be used to set individual elements' values
///
public MazeSolver(int iRows, int iCols)
{
m_iMaze=new int[iRows, iCols];
m_iRows=iRows;
m_iCols=iCols;
}
///
/// Properites:
///
public int Rows
{
get { return m_iRows; }
}
public int Cols
{
get { return m_iRows; }
}
public int[,] GetMaze
{
get { return m_iMaze; }
}
public int PathCharacter
{
get { return iPath; }
set
{
if (value==0)
throw new Exception("Invalid path character specified");
else
iPath=value;
}
}
///
/// Indexer
///
public int this[int iRow, int iCol]
{
get { return m_iMaze[iRow,iCol]; }
set
{
m_iMaze[iRow,iCol]=value;
if (this.OnMazeChangedEvent!=null)
this.OnMazeChangedEvent(iRow, iCol);
}
}
///
/// The function is used to get the contents of a given node in a given maze,
/// specified by its node no.
///
private int GetNodeContents(int[,] iMaze, int iNodeNo)
{
int iCols=iMaze.GetLength(1);
return iMaze[iNodeNo/iCols,iNodeNo-iNodeNo/iCols*iCols];
}
///
/// The function is used to change the contents of a given node in a given maze,
/// specified by its node no.
///
private void ChangeNodeContents(int[,] iMaze, int iNodeNo, int iNewValue)
{
int iCols=iMaze.GetLength(1);
iMaze[iNodeNo/iCols,iNodeNo-iNodeNo/iCols*iCols]=iNewValue;
}
///
/// This public function finds the shortest path between two points
/// in the maze and return the solution as an array with the path traced
/// by "iPath" (can be changed using property "PathCharacter")
/// if no path exists, the function returns null
///
public int[,] FindPath(int iFromY, int iFromX, int iToY, int iToX)
{
int iBeginningNode = iFromY*this.Cols + iFromX;
int iEndingNode = iToY*this.Cols + iToX;
return ( Search(iBeginningNode, iEndingNode) ) ;
}
///
/// Internal function for that finds the shortest path using a technique
/// similar to breadth-first search.
/// It assigns a node no. to each node(2D array element) and applies the algorithm
///
private enum Status
{ Ready, Waiting, Processed }
private int[,] Search(int iBeginningNode, int iEndingNode)
{
int iStart=iEndingNode, iStop=iBeginningNode; // the function displays the reverse path
const int empty=0;
int iRows=m_iRows;
int iCols=m_iCols;
int iMax=iRows*iCols;
int[] Queue=new int[iMax];
int[] Origin=new int[iMax];
int iFront=0, iRear=0;
//check if starting and ending points are valid (open)
if ( GetNodeContents(m_iMaze, iStart)!=empty || GetNodeContents(m_iMaze, iStop)!=empty )
{
return null;
}
//create dummy array for storing status
int[,] iMazeStatus=new int[iRows,iCols];
//initially all nodes are ready
for(int i=0;i=0 && iLeft/iCols==iCurrent/iCols) //if left node exists
if ( GetNodeContents(m_iMaze, iLeft)==empty ) //if left node is open(a path exists)
if (GetNodeContents(iMazeStatus, iLeft) == (int)Status.Ready) //if left node is ready
{
Queue[iRear]=iLeft; //add to Q
Origin[iRear]=iCurrent;
ChangeNodeContents(iMazeStatus, iLeft, (int)Status.Waiting); //change status to waiting
iRear++;
}
iRight=iCurrent+1;
if (iRight=0 ) //if top node exists
if ( GetNodeContents(m_iMaze, iTop)==empty ) //if top node is open(a path exists)
if (GetNodeContents(iMazeStatus, iTop) == (int)Status.Ready) //if top node is ready
{
Queue[iRear]=iTop; //add to Q
Origin[iRear]=iCurrent;
ChangeNodeContents(iMazeStatus, iTop, (int)Status.Waiting ); //change status to waiting
iRear++;
}
iDown=iCurrent+iCols;
if (iDown=0; i--)
{
if (Queue[i]==iCurrent)
{
iCurrent=Origin[i];
if (iCurrent==-1) // maze is solved
return ( iMazeSolved );
ChangeNodeContents(iMazeSolved, iCurrent, iPath);
}
}
//no path exists
return null;
}
}
}
(
geocities.com/smehrozalam)