maze.cs

福州大学人工智能课程02级的实验项目：实现深度、广度、A*算法的迷宫搜索以及演示程序

using System;
using System.Collections;
using System.Drawing;

/*
 * 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 DFSAlgorithmMaze
{
	/// <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;
		ArrayList OPEN = new ArrayList();//OPEN 表
		public ArrayList CLOSED = new ArrayList();//CLOSED 表
		ArrayList  NextCells = new ArrayList();//可扩展格 表
		public Stack PathStack = new Stack();
		public static int wallsrate = 30;//静态变量

		public Maze()
		{
			//
			// TODO: Add constructor logic here
			//
			Initialize();
			//Cells[0,0].Walls[0]=0;
			//		Cells[kDimension-1,kDimension-1].Walls[3]=0;
		}

		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)//去除（＋0，＋0）（即本身）的可能
						)
					{
						if (Cells[aCell.Row+countRow, aCell.Column+countCol].HasAllWalls())//邻居cell全墙
						{
							Neighbors.Add( Cells[aCell.Row+countRow, aCell.Column+countCol]);
						}
					}
				}

			return Neighbors;
		}

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

					Cells[i,j].Visited = 0;//搜索标记
					Cells[i,j].Pathmark = 0;//路径标记
					Cells[i,j].parent = null;//路径“指针”
				}

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

		//生成完美迷宫
		public void  Generate()
		{
			while (VisitedCells < TotalCells)
			{
				//深度优先搜索＋the random neighbor 构成 "perfect迷宫"生成算法
				// 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();
				}

			}
		}


		//生成随机迷宫
		public void GenerateRandom()
		{
            Generate();
			while (MazeWallsRate() > wallsrate)//....还有很大问题，随机数取值不均匀，很难有通路；因此先调用了Generate();
			{
				
				ArrayList AdjacentCells = GetNeighborsWithWalls(CurrentCell);
				if(AdjacentCells.Count > 0)
				{
					int randomCell = Cell.TheRandom.Next(0, AdjacentCells.Count);
					Cell theCell = ((Cell)AdjacentCells[randomCell]);
					CurrentCell.KnockDownWall(theCell);//随机在四面敲墙
				}
				
				int randomRow = Cell.TheRandom.Next(0,kDimension-1);
				int randomColumn = Cell.TheRandom.Next(0,kDimension-1);
				CurrentCell = Cells[randomRow,randomColumn];//随机取宫格
			}
		}

		//计算墙的比例
		private int MazeWallsRate()
		{
			int cellwalls = 0;
			int mazewalls = 0;
			int allwalls = 0;
			for (int i = 0; i < kDimension; i++)
				for (int j = 0; j < kDimension; j++)
				{
					cellwalls = Cells[i,j].Walls[2] + Cells[i,j].Walls[3];
					mazewalls += cellwalls;
				}			
			mazewalls -= 2*kDimension;
			/*墙总数的计算方法：
			 * 
			 * _|_|_|_|_|_|_|_|
			 * _|_|_|_|_|_|_|_|
			 * _|_|_|_|_|_|_|_|
			 * _|_|_|_|_|_|_|_|
			 * _|_|_|_|_|_|_|_|
			 * _|_|_|_|_|_|_|_|
			 * _|_|_|_|_|_|_|_|
			 * 
			 * 	每个宫格只要考虑右边和下边的 2 堵墙，总共有 kDimension*kDimension 个宫格
			 * 然后要去掉右边和下边的两个迷宫边界 ： 2*kDimension
			 */
			allwalls = 2*kDimension*kDimension - 2*kDimension;
			return (mazewalls*100)/allwalls - 30;
		}
			  


		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  reDraw(Graphics g)
		{
			for (int i = 0; i < kDimension; i++)
				for (int j = 0; j < kDimension; j++)
				{
					if(Cells[i,j].Pathmark == 1)
						Cells[i,j].DrawFillSearch(g);//CLOSED表重绘，灰色
					if(Cells[i,j].Pathmark == 5)
						Cells[i,j].DrawFill(g);//路径重绘，番茄色					
				}

		}

		//搜索切换清空
		public void clearSearch(Graphics g)
		{
			for (int i = 0; i < kDimension; i++)
				for (int j = 0; j < kDimension; j++)
				{					
					Cells[i,j].Visited = 0;//搜索标记
                    Cells[i,j].Pathmark = 0;//路径标记
                    Cells[i,j].parent = null;//路径“指针”

					Cells[i,j].DrawFillNull(g);//空白重绘，白色
				}
			
		}



		/// <summary>
		/// 搜索算法
		/// </summary>
		/// <param name="g"></param>


		//深度搜索
		/*
		 * 1. OPEN = (s), CLOSED = ();
		 * 2. LOOP if OPEN =() then EXIT(fail);
		 * 3. n = FIRST(OPEN);
		 * 4. if GOAL(n) then EXIT(success);
		 * 5. REMOVE(n, OPEN) , ADD(n, CLOSED)
		 * 6. EXPAND(n) --> {m1,m2……}		其中(mi NOT_IN CLOSED||OPEN)
		 * 7. ADD(mi, OPEN) , Parent(mi) = n
		 * 8. GO LOOP
		 * 
		 */
		public bool DFSearch()
		{			
			OPEN.Clear();
			CLOSED.Clear();//清空，必须清空
			CurrentCell = Cells[0,0];//“指针”？？引用！！
			OPEN.Add(CurrentCell);
			while(OPEN.Count != 0)
			{
				CurrentCell = (Cell)OPEN[0];
				if( CurrentCell == Cells[kDimension-1,kDimension-1])
				{
					do
					{
						PathStack.Push(CurrentCell);//搜索到的路径进栈
						CurrentCell = CurrentCell.parent;
					}while(CurrentCell != Cells[0,0]);
					PathStack.Push(CurrentCell);//入口格进栈

					return true;
				}
				OPEN.RemoveAt(0);
				CLOSED.Add(CurrentCell);
				
				NextCells = GetNextCells(CurrentCell);
				if(NextCells.Count>0)
				{
					for(int i=0;i< NextCells.Count;i++)//若用i < ( NextCells.Count-1)，死循环？！
					{
						Cell celltemp = (Cell)NextCells[i];
						Cell thecell = Cells[celltemp.Row,celltemp.Column];
						if(thecell.Visited == 0)
						{							
							thecell.parent = CurrentCell;//指针？？引用！！
							thecell.Visited = 1;//这东西忘了，晕！！死循环
							OPEN.Insert(0,thecell);
						}
					}
				}
			}			
			return false;
		}


		//广度搜索
		/*
		 * 1. OPEN = (s), CLOSED = ();
		 * 2. LOOP if OPEN =() then EXIT(fail);
		 * 3. n = FIRST(OPEN);
		 * 4. if GOAL(n) then EXIT(success);
		 * 5. REMOVE(n, OPEN) , ADD(n, CLOSED)
		 * 6. EXPAND(n) --> {m1,m2……}		其中(mi NOT_IN CLOSED||OPEN)
		 * 7. ADD(OPEN, mi) , Parent(mi) = n
		 * 8. GO LOOP
		 * 
		 */
		public bool BFSearch()
		{
			OPEN.Clear();
			CLOSED.Clear();
			CurrentCell = Cells[0,0];
			OPEN.Add(CurrentCell);
			while(OPEN.Count != 0)
			{
				CurrentCell = (Cell)OPEN[0];
				if( CurrentCell == Cells[kDimension-1,kDimension-1])
				{
					do
					{
						PathStack.Push(CurrentCell);
						CurrentCell = CurrentCell.parent;
					}while(CurrentCell != Cells[0,0]);
					PathStack.Push(CurrentCell);

					return true;
				}
				OPEN.RemoveAt(0);
				CLOSED.Add(CurrentCell);
				
				NextCells = GetNextCells(CurrentCell);		
				if(NextCells.Count>0)
				{
					for(int i=0;i< NextCells.Count;i++)
					{
						Cell celltemp = (Cell)NextCells[i];
						Cell thecell = Cells[celltemp.Row,celltemp.Column];
						if(thecell.Visited == 0)
						{							
							thecell.parent = CurrentCell;
							thecell.Visited = 1;
							//深度搜索OPEN.Insert(0,thecell);
							//广度搜索OPEN.Add(thecell);
							OPEN.Add(thecell);
						}
					}
				}
			}
			return false;
		}


		//启发搜索	
		/*
		 * 1. OPEN = (s), CLOSED = ();
		 * 2. LOOP if OPEN =() then EXIT(fail);
		 * 3. n = FIRST(OPEN);
		 * 4. if GOAL(n) then EXIT(success);
		 * 5. REMOVE(n, OPEN) , ADD(n, CLOSED)
		 * 6. EXPAND(n) --> {m1,m2……}		其中(mi NOT_IN CLOSED||OPEN)
		 * 7. ADD(mi, OPEN) , Parent(mi) = n
		 * 8  Sort(OPEN,Weight)		其中Weight = h(N) = |G.x - N.x| + |G.y - N.y|.
		 * 9. GO LOOP
		 * 
		 */
		public  bool AISearch()
		{
			OPEN.Clear();
			CLOSED.Clear();//清空OPEN、CLOSED表
			CurrentCell = Cells[0,0];//起点设为当前结点
			OPEN.Add(CurrentCell);//并加入OPEN表
			while(OPEN.Count != 0)
			{
				CurrentCell = (Cell)OPEN[0];
				if( CurrentCell == Cells[kDimension-1,kDimension-1])
				{//如果搜索成功的话，搜索到的路径进栈
					//从终点Cells[kDimension-1,kDimension-1]开始
					do
					{
						PathStack.Push(CurrentCell);
						CurrentCell = CurrentCell.parent;
					}while(CurrentCell != Cells[0,0]);
					PathStack.Push(CurrentCell);
					//到起点Cells[0,0]结束

					return true;
				}
				OPEN.RemoveAt(0);
				CLOSED.Add(CurrentCell);
				

				NextCells = GetNextCells(CurrentCell);//取得相通的邻居
				if(NextCells.Count>0)
				{
					for(int i=0;i< NextCells.Count;i++)
					{
						Cell celltemp = (Cell)NextCells[i];
						Cell thecell = Cells[celltemp.Row,celltemp.Column];
						if(thecell.Visited == 0)//相通的邻居还没被访问Visited == 0
						{
							thecell.parent = CurrentCell;//把当前结点设为他的父结点
							thecell.Visited = 1;//标识他被访问过

							//深度搜索OPEN.Insert(0,thecell);
							//广度搜索OPEN.Add(thecell);
							//A*搜索同深度搜索OPEN.Insert(0,thecell),然后PriorityUp(OPEN)根据启发函数排序                                     
							OPEN.Insert(0,thecell);
							PriorityUp(OPEN);
						}
					}
				}
			}
			return false;
		}


		//相通的邻居，下一步的路径可能
		private ArrayList GetNextCells(Cell bCell)
		{
			/* walls[]方向：
			 *        1
			 *         
			 *        ↑
			 * 
			 * 0  ← cell →  2
			 *  
			 *        ↓
			 * 
			 *        3 
			 */
			ArrayList nextcells = new ArrayList();
			if(bCell.Walls[3] == 0)
				nextcells.Add(Cells[bCell.Row+1,bCell.Column]);
			if(bCell.Walls[2] == 0)
				nextcells.Add(Cells[bCell.Row,bCell.Column+1]);
			if(bCell.Walls[1] == 0)
				nextcells.Add(Cells[bCell.Row-1,bCell.Column]);
			if(bCell.Walls[0] == 0)
				nextcells.Add(Cells[bCell.Row,bCell.Column-1]);
			return nextcells;
		}


		//让权最轻的Cell浮到表的顶端
		private void PriorityUp(ArrayList aArr)
		{
			if(aArr.Count > 0)
			{
				Cell firstCell = (Cell)aArr[0];
				object temp = new object();
				for(int i=0;i< aArr.Count;i++)
				{					
					Cell theCell = (Cell)aArr[i];
					if(CellWeight(theCell) < CellWeight(firstCell))
					{
						temp = aArr[0];
						aArr[0] = aArr[i];
						aArr[i] = temp;
					}                        					
				}				
			}
		}

		
		//以离终点远近为权重，h(N) = |G.x - N.x| + |G.y - N.y|
		private int CellWeight(Cell cCel)
		{
			Cell gCel = Cells[kDimension - 1,kDimension - 1];
			int rowW = Math.Abs(gCel.Row - cCel.Row);
			int colW = Math.Abs(gCel.Column - cCel.Column);
			int weight = rowW + colW;
			return weight;
		}
	}
}