Maze.cs

Maze.cs
using System;
using System.Collections;
using System.Drawing;
using System.Threading;

/*
 * create a CellStack (LIFO) to hold a list of cell locations
set TotalCells = number of cells in grid
choose a cell at random and call it CurrentCell
set VisitedCells = 1

while VisitedCells < TotalCells
find all neighbors of CurrentCell with all walls intact
if one or more found
choose one at random
knock down the wall between it and CurrentCell
push CurrentCell location on the CellStack
make the new cell CurrentCell
add 1 to VisitedCells
else
pop the most recent cell entry off the CellStack
make it CurrentCell
endIf
endWhile
*/

namespace MazeSolution
{
	/// <summary>
	/// Summary description for Maze.
	/// </summary>
	public class Maze
	{
		public static int kDimension = 20;
		Cell[][] Cells = null;
		Stack CellStack = new Stack();
		int VisitedCells = 1;
		int TotalCells = kDimension * kDimension;
		Cell CurrentCell = null;

		// A delegate type for hooking up completion notifications.
		public delegate void MazeEventHandler(object sender, EventArgs e);

		public event MazeEventHandler MazeSolutionComplete;

		public Maze()
		{
			Initialize();
		}

		private ArrayList GetNeighborsWithWalls(Cell aCell)
		{
			ArrayList Neighbors = new ArrayList();
			//int count = 0;
			for (int countRow = -1; countRow <= 1; countRow++)
				for (int countCol = -1; countCol <= 1; countCol++)
				{
					if ( (aCell.Row + countRow < kDimension) &&
						 (aCell.Column+countCol < kDimension) &&
						 (aCell.Row+countRow >= 0) &&
						 (aCell.Column+countCol >= 0) &&
						 ((countCol == 0) || (countRow == 0)) &&
						 (countRow != countCol)
						)
					{
						if (Cells[aCell.Row+countRow][aCell.Column+countCol].HasAllWalls())
						{
							Neighbors.Add( Cells[aCell.Row+countRow][aCell.Column+countCol]);
						}
					}
				}

			return Neighbors;
		}

		public void Initialize()
		{
			Cells = new Cell[kDimension][];
			TotalCells = kDimension * kDimension;
			for (int i = 0; i < kDimension; i++)
			{
				Cells[i] = new Cell[kDimension];
				for (int j = 0; j < kDimension; j++)
				{
					Cells[i][j] =  new Cell();
					Cells[i][j].Row = i;
					Cells[i][j].Column = j;
				}
			}

			CurrentCell = Cells[0][0];
			VisitedCells = 1;
			CellStack.Clear();

		}

		public void  Generate()
		{
			while (VisitedCells < TotalCells)
			{
				// get a list of the neighboring cells with all walls intact
				ArrayList AdjacentCells = GetNeighborsWithWalls(CurrentCell);
				// test if a cell like this exists
				if (AdjacentCells.Count > 0)
				{
					// yes, choose one of them, and knock down the wall between it and the current cell
					int randomCell = Cell.TheRandom.Next(0, AdjacentCells.Count);
					Cell theCell = ((Cell)AdjacentCells[randomCell]);
					CurrentCell.KnockDownWall(theCell);
					CellStack.Push(CurrentCell); // push the current cell onto the stack
					CurrentCell = theCell; // make the random neighbor the new current cell
					VisitedCells++;
				}
				else
				{
					// No cells with walls intact, pop current cell from stack
					CurrentCell = (Cell)CellStack.Pop();
				}

			}

			// Show the entry and exit
			Cells[0][0].Walls[0] = 0;
			Cells[kDimension-1][kDimension-1].Walls[3] = 0;

		}

		public void SolveIt( Cell.CellState cellState )
		{
			bool steadyState = true;

			// Loop through the maze, with each pass blocking off more and more
			// dead ends until steadyState = true.
			do
			{
				steadyState = true;

				for( int i=0; i<kDimension; i++ )
				{
					for( int j=0; j<kDimension; j++ )
					{
						if( Cells[i][j].cellState == Cell.CellState.FREE )
						{
							if ( !IsFree(i,j) )
							{
								Cells[i][j].cellState = cellState;
								steadyState = false;
							}
						}
					}
					Thread.Sleep(0);
				}
			} while( !steadyState );
		}

		public void SolveItBackward( Cell.CellState cellState )
		{
			bool steadyState = true;

			// Loop backward through the maze, with each pass blocking off more and more
			// dead ends until steadyState = true.
			do
			{
				steadyState = true;

				for( int i=kDimension-1; i>=0; i-- )
				{
					for( int j=kDimension-1; j>=0; j-- )
					{
						if( Cells[i][j].cellState == Cell.CellState.FREE )
						{
							if ( !IsFree(i,j) )
							{
								Cells[i][j].cellState = cellState;
								steadyState = false;
							}
						}
					}
					Thread.Sleep(0);
				}
			} while( !steadyState );
		}

		// Each solution method just uses a different wall type
		// which is drawn in a different color so that we can
		// see each threads progress.  When complete, the event
		// MazeSolutionComplete is raised.
		public void SolveA()
		{
			SolveIt( Cell.CellState.WALLA );
			MazeSolutionComplete( this, EventArgs.Empty );
		}

		public void SolveB()
		{
			SolveItBackward( Cell.CellState.WALLB );
			MazeSolutionComplete( this, EventArgs.Empty );
		}

		public void SolveC()
		{
			SolveIt( Cell.CellState.WALLC );
			MazeSolutionComplete( this, EventArgs.Empty );
		}

		public void SolveD()
		{
			SolveItBackward( Cell.CellState.WALLD );
			MazeSolutionComplete( this, EventArgs.Empty );
		}

		public void SolveE()
		{
			SolveIt( Cell.CellState.WALLE );
			MazeSolutionComplete( this, EventArgs.Empty );
		}

		public void SolveF()
		{
			SolveItBackward( Cell.CellState.WALLF );
			MazeSolutionComplete( this, EventArgs.Empty );
		}

		public void SolveG()
		{
			SolveIt( Cell.CellState.WALLG );
			MazeSolutionComplete( this, EventArgs.Empty );
		}

		public void SolveH()
		{
			SolveItBackward( Cell.CellState.WALLH );
			MazeSolutionComplete( this, EventArgs.Empty );
		}

		public void SolveI()
		{
			SolveIt( Cell.CellState.WALLI );
			MazeSolutionComplete( this, EventArgs.Empty );
		}

		public void SolveJ()
		{
			SolveItBackward( Cell.CellState.WALLJ );
			MazeSolutionComplete( this, EventArgs.Empty );
		}

		public void SolveK()
		{
			SolveIt( Cell.CellState.WALLK );
			MazeSolutionComplete( this, EventArgs.Empty );
		}

		public void SolveL()
		{
			SolveItBackward( Cell.CellState.WALLL );
			MazeSolutionComplete( this, EventArgs.Empty );
		}

		public void SolveM()
		{
			SolveIt( Cell.CellState.WALLM );
			MazeSolutionComplete( this, EventArgs.Empty );
		}

		public void SolveN()
		{
			SolveItBackward( Cell.CellState.WALLN );
			MazeSolutionComplete( this, EventArgs.Empty );
		}

		public void SolveO()
		{
			SolveIt( Cell.CellState.WALLO );
			MazeSolutionComplete( this, EventArgs.Empty );
		}

		public void SolveP()
		{
			SolveItBackward( Cell.CellState.WALLP );
			MazeSolutionComplete( this, EventArgs.Empty );
		}

		/// <summary>
		/// This is the key to solving the maze.  If a cell isn't free, block it off.
		/// We determine whether it is free by examining its walls and the free state
		/// of all neighboring cells.
		/// </summary>
		/// <param name="x"></param>
		/// <param name="y"></param>
		/// <returns></returns>
		private bool IsFree( int x, int y )
		{
			int walls = 0;

			if( Cells[x][y].Walls[0] == 1 )
				walls ++;
			else if( y > 0 && ((int)Cells[x][y-1].cellState > (int)Cell.CellState.FREE ))
				walls++;

			if( Cells[x][y].Walls[1] == 1 )
				walls ++;
			else if( x > 0 && ((int)Cells[x-1][y].cellState > (int)Cell.CellState.FREE ))
				walls++;

			if( Cells[x][y].Walls[2] == 1 )
				walls ++;
			else if( y < kDimension-1 && ((int)Cells[x][y+1].cellState  > (int)Cell.CellState.FREE ))
				walls++;

			if( Cells[x][y].Walls[3] == 1 )
				walls ++;
			else if( x < kDimension-1 && ((int)Cells[x+1][y].cellState  > (int)Cell.CellState.FREE ))
				walls++;

			return (walls < 3);
		}

		public void Draw(Graphics g)
		{
			for (int i = 0; i < kDimension; i++)
				for (int j = 0; j < kDimension; j++)
				{
					Cells[i][j].Draw(g);
				}
		}

		public void Reset()
		{
			for (int i = 0; i < kDimension; i++)
				for (int j = 0; j < kDimension; j++)
				{
					Cells[i][j].cellState = Cell.CellState.FREE;
				}
		}



	}
}