# Astar Algrithom maze **Repository Path**: edocevol/Astar-Algrithom-maze ## Basic Information - **Project Name**: Astar Algrithom maze - **Description**: 人工智能的作业，使用C#实现的A* 算法的demo，是迷宫寻径，使用了深度搜索和广度搜索作为对比，文档齐全。 - **Primary Language**: C# - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 5 - **Forks**: 0 - **Created**: 2015-12-27 - **Last Updated**: 2020-12-19 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README #Astar Algrithom maze 一、 程序目的 2 二、 程序开发及运行环境 2 （一） 程序开发环境 2 （二） 程序运行环境 3 三、 程序功能设计 3 （一） 生成标准迷宫 3 （二） 生成随机迷宫 3 （三） 设置迷宫规模、 3 （四） 设置演示延时 3 （五） 手动寻找寻径 3 （六） A*算法搜索路径 3 四、 程序实现流程 3 （一） 现实中的我们 3 （二） 考虑现实的产生原因 4 （三） 利用A*算法快速寻径 4 （四） 如何实现之迷宫布局初始化 4 （五） 如何实现之迷宫生成 5 （六） 如何实现之路径寻找 6 （七） 如何实现之迷宫生成示例 6 五、 关键代码 6 （一） 获取一个迷宫单元格的所有没有被遍历过的邻居单元格 6 （二） 迷宫生成初始化的代码 7 （三） 迷宫初始化后的构造的程序代码 8 （四） A*搜索的实现代码 8 （五） 计算某个节点到终点的距离 10 （六） 按照距离的远近进行排序 10 （七） 判断两个节点节点之间是否存在通路 10 （八） 手动寻径主控程序 11 （九） 路径选择动画演示 13 六、 程序运行示例图 14 七、 程序实现参考书 14 八、 致谢 14 一、程序目的 利用人工智能的知识，解决实际的问题。人工智能领域有很多著名的、高效的算法，其中启发式算法在实际应用中，不仅算法易懂，而且对解决实际问题具有很好的效果。本程序是基于武汉大学研究生高级人工智能课程中所学的A*启发式算法，试图通过启发式的算法，快速的找到迷宫的出口，通过动画的演示，可以清楚地展示A*算法的工作流程，同时也提供了手动寻找路径的功能，让读者可以自己动手体验一下身处在迷宫之中的人如何能够抉择下一步的操作。 二、程序开发及运行环境 （一）程序开发环境 本程序采用C#语言进行开发，基于.NET Framework 3.0框架，利用微软的Visual Studio 2010 集成开发环境进行开发。由于作者对C#语言比较熟悉，而且C#语言目前是微软主推的桌面程序开发语言，配合.NET运行时框架能够充分利用C#提供的桌面组件进行快速开发。 （二）程序运行环境 本程序依赖于.NET 运行时环境，程序为了适应不同的Windows操作系统，已经将运行时环境调至最低，目前程序运行所需用的环境是.NET Framework3.0，几乎支持所有的Windows操作系统。几乎在作用的Windows操作系统上不需要安装额外的系统组件来运行本程序。 三、程序功能设计 （一）生成标准迷宫 此功能是根据深度搜索，生成一副有出路的完美迷宫，涉及迷宫初始化，带有出路的迷宫的选择。 （二）生成随机迷宫 此功能是根据用户实时的输入作为迷宫的规模，并对生成的标准迷宫进行优化，增加随机性。 （三）设置迷宫规模、 为了能够满足不同的迷宫规模的需求，将程序的迷宫的规模设为全局私有变量，允许用户在需要时进行自定义迷宫规模，从而更好地体验A*算法的准确性与高效的适应性。 （四）设置演示延时 为了能够满足不同的演示时间的需求，将程序的演示时间设为全局私有变量，允许用户在需要时进行自定义时间。 （五）手动寻找寻径 手动寻找路径是为程序使用者提供自己动手寻找迷宫路径的功能，用户通过键盘的W、A、S、D分别在迷宫中的向上、左、下、右进行移动，并对用户的移动进行边界判断，只有存在通路时，才允许用户进行移动，否则不响应用户的操作，通过四种不同的颜色来标记用户的移动方向的不同，来标记用户的移动顺序。 （六）A*算法搜索路径 此功能是A*算法针对迷宫寻径问题的实现，利用 （其中 代表起始点到当前点的代价， 代表的是当前节点到结束节点的代价），因为针对当前节点选择直接后继节点，所有直接后继节点的 是相同的，因此，在选择后继节点是只需要选择最小的 就能够选择最好的直接后继节点。因为 代表的是代价，因此本程序中，直接令 ，即 对应当前节点的所有的可选择的直接后继节点到终点的距离作为代价。 四、程序实现流程 （一）现实中的我们 如下图，当我们面对电脑中的迷宫图，我们可以很快速地从迷宫的开始节点找到一条通往迷宫终止界面的路径。 （二）考虑现实的产生原因 为什么我们可以快速找到上面迷宫的有效出口路径的呢？原因可以大致划归一下四个方面。 1. 迷宫规模小 2. 我们可以直接看到迷宫的整体布局 3. 有了整体布局，我们可以择优选择 4. 迷宫简单 作为计算机却对以上四点没有什么好感，因为这些信息对它来说，没有任何意义，那么从计算机的角度，该怎么样才能实现人类的步骤呢？ （三）利用A*算法快速寻径 A*算法是启发式的一种，在路径选择中有着广泛的应用。A*算法根据 ，能够快速地选择好的路径进行拓展。 （四）如何实现之迷宫布局初始化 迷宫生成之前的初始化的算法框图如下 （五）如何实现之迷宫生成 迷宫初始化之后，生成一副具有有效逃生路径的迷宫图的算法流程如下。 （六）如何实现之路径寻找 A*算法寻找路径的算法流程如下 （七）如何实现之迷宫生成示例 五、关键代码 （一）获取一个迷宫单元格的所有没有被遍历过的邻居单元格 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(); } } } （四）A*搜索的实现代码 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); } } } //TODO 添加显示open表和close表 } return false; } （五）计算某个节点到终点的距离 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; } （六）按照距离的远近进行排序 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; } } } } （七）判断两个节点节点之间是否存在通路 public static bool OpenWay(Cell c1, Cell c2) { bool tag = false; if ((Math.Abs(c1.Row - c2.Row) == 0) || (Math.Abs(c1.Column - c2.Column) == 0)) { if (c1.Row == c2.Row + 1 && c1.Column == c2.Column) { if (c1.Walls[1] != 1 && c2.Walls[3] != 1) { return true; } } else if (c1.Row == c2.Row - 1 && c1.Column == c2.Column) { if (c1.Walls[3] != 1 && c2.Walls[1] != 1) { return true; } } else if (c1.Row == c2.Row && c1.Column == c2.Column + 1) { if (c1.Walls[0] != 1 && c2.Walls[2] != 1) { return true; } } else if (c1.Row == c2.Row && c1.Column == c2.Column - 1) { if (c1.Walls[2] != 1 && c2.Walls[0] != 1) { return true; } } } return tag; } （八）手动寻径主控程序 private void richTextBox1_TextChanged(object sender, EventArgs e) { if (ended) { MessageBox.Show("您成功地寻找到出口了"); } string txt = richTextBox1.Text.Trim(); if (txt.Equals("W")) { if (y != 0) { if (Cell.OpenWay(TheMaze.getCells()[x, y], TheMaze.getCells()[x, y-1])) { y--; Graphics g = pictureBox1.CreateGraphics(); TheMaze.getCells()[x, y].DrawFill(g,Color.Green); } } } else if (txt.Equals("A")) { if (x != 0) { if (Cell.OpenWay(TheMaze.getCells()[x, y], TheMaze.getCells()[x-1, y])) { x--; Graphics g = pictureBox1.CreateGraphics(); TheMaze.getCells()[x, y].DrawFill(g,Color.Pink); } } } else if (txt.Equals("S")) { if (y 0 ? Color.Green : Color.Salmon; System.Threading.Thread.Sleep(delayTime);//画搜索格子，每格都会延时delayS //player1.Dispose(); } } int index = 0; richTextBox2.ForeColor = Color.Red; richTextBox2.AppendText("有效逃生路径为:\r\n"); // richTextBox1.ForeColor = Color.Green; while (TheMaze.PathStack.Count != 0) { index++; Cell PathCell = (Cell)TheMaze.PathStack.Pop(); Graphics g = pictureBox1.CreateGraphics(); PathCell.DrawFill2(g, index); int olength = richTextBox2.Text.Length; String newline = "第" + index + "节点为:(" + PathCell.Row + "," + PathCell.Column + ").父节点为:(" + (index == 0 ? 0 : PathCell.parent.Row) + "," + (index == 0 ? 0 : PathCell.parent.Column) + ")" + "\r\n"; richTextBox2.AppendText(newline); richTextBox2.Select(olength, newline.Length); richTextBox2.SelectionColor = index % 2 > 0 ? Color.Salmon : Color.DarkGreen; System.Threading.Thread.Sleep(delayTime);//画路径格子，每格都会延时delayP } MessageBox.Show("yeah，找出出口！！！", "TIPS"); } 六、程序运行示例图 七、致谢 感谢朱老师的谆谆教诲，让我接触人工智能的世界，学会用科学的方法解决问题。