七彩迷宫实验报告

PAGE 本科学生设计性实验报告数据结构课程设计项目组长学号专业软件工程班级软件125班成员实验项目名称七彩迷宫指导教师涂保东开课学期2013至2014学年第二学期实验设计方案实验名称：七彩迷宫实验时间：3月24号至4月14号实验场地：W202软件环境：Java实验任务与目的（简单介绍实验内容，说明实验任务和目的）1.1性能需求随着社会经济和人们物质生活的不断提高，人们对精神生活的需求也越来越高，在现今社会里，人们对诸如智商、情商等的重视无疑反映了对精神生活的态度。当然具体到我们每个人来说，想必大多数人小时候都曾玩过魔方、迷宫吧。作为这种智力游戏，人们是百玩不厌的。正是鉴于这种需求，本设计应用计算机语言及其算法，将人的意志赋予机器实现，使人们不必再陷于枯燥的重复劳动，从而将更多的精力投入到对未知领域的探索上。1.2功能需求本设计的关键在于将人的想法自能化，由所编软件自动的搜索可行路径。因此，软件必须拥有自动搜索并记录可行路径的功能，除此之外，软件需要有自动生成迷宫的功能；当然对于迷宫问题还有很多要考虑的地方，比如由用户自己来探索可行路径，但由于本设计侧重于迷宫求解的算法设计，并非以游戏的形式为初衷，定有不全之处。1.3实验内容随机生成一个可以出去的迷宫，老鼠的入口在左上顶点，出口在右下顶点。老鼠走迷宫的过程可以模拟为一个搜索的过程：每到一处，总让它按东、北、南、西的方向顺序试探下一个位置；如果某方向可以通过，则前进一步，在新的位置上继续进行搜索，直到走出迷宫。1.4实验任务自动生成一个n*n的二维数组，作为迷宫，并显示生成迷宫耗时；保证迷宫是否存在一条从入口到出口的通路（用深度优先搜索方法实现）。如果通路不存在，就重新生成一个迷宫，直到通路存在为止；在迷宫内部的每一格都有四个方向可以走。如果某格的三个方向都走不通，则返回上一格（回溯），选取另一个能走通的方向进行移动；显示老鼠走出迷宫所用时间。1.5实验目的熟练掌握随机生成的方法。熟练掌握Java面向对象程序设计的方法，以及类模板的应用。用深度优先搜索算法生成一个有通路的迷宫。1算法背景1：深度优先搜索算法：是搜索算法的一种，是沿着树的深度遍历的节点，尽可能深的搜索树的分支，当节点V的所有边都已经被探寻过，搜索讲回溯到发现节点v的那条边的起始节点，这一过程一直进行到已发现从源节点可到达的所有节点为止，如果还存在为发现的节点，则选择其他一个作为源节点并重复以上过程，整个过程反复进行止到所有节点都被访问为止。2：回溯法生成迷宫算法：1.以一个M*N的长方形表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通过的结论2.根据二位数组，输出迷宫的图形。3.探索迷宫的四个方向：RIGHT为向右，DOWN为向下，LEFT向左，UP为上，输出从入口到出口的行走路径。3：调用java中的time类：直接调用time()函数，计算实现通路的时间。4：栈：栈是一种可以实现“先进后出”的存储结构。是一种特殊的线性表，而其特殊性在于限定插入和删除数据元素只能在线性表的一端进行。用回溯方法解决问题的一般步骤：1针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。2确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间。3以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。问题的解空间通常是在搜索问题解的过程中动态产生的，这是回溯算法的一个重要特性。确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。实验思路（详细描述解决问题的整体思路、涉及的算法思想及数据结构等）首先随机生成迷宫，设计好模板。进入迷宫，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路返回，换一个方向再继续探索，直到所有肯呢过的通路都探索到为止。采用的是回溯算法找到出口因为没有实现吃豆子的功能，我们的实验结果没有七彩豆子，能力有限，还请见谅。二、实验结果与分析1、程序结构（程序结构图，主要函数的功能描述，算法实现的细节等）1．程序流程图：2：程序主要代码：privateJPanelpanel;privateJPanelsouthPanel;privateJPanelcenterPanel;privateMazeGridgrid[][];privateJButtonrestart;privateJButtondostart;privateintrows;//rows和cols目前暂定只能是奇数privateintcols;privateList<String>willVisit;privateList<String>visited;privateLinkedList<String>comed;privatelongstartTime;privatelongendTime;//生成迷宫publicMazeGrid[][]createMap(MazeGridmazeGrid[][],intx,inty){intvisitX=0;intvisitY=0;if(x-2>=0){if(!mazeGrid[x-2][y].isVisited()){willVisit.add((x-2)+"#"+y);}}if(x+2<cols){if(!mazeGrid[x+2][y].isVisited()){willVisit.add((x+2)+"#"+y);}}if(y-2>=0){if(!mazeGrid[x][y-2].isVisited()){willVisit.add(x+"#"+(y-2));}}if(y+2<rows){if(!mazeGrid[x][y+2].isVisited()){willVisit.add(x+"#"+(y+2));}}if(!willVisit.isEmpty()){intvisit=(int)(Math.random()*willVisit.size());Stringid=willVisit.get(visit);visitX=Integer.parseInt(id.split("#")[0]);visitY=Integer.parseInt(id.split("#")[1]);mazeGrid[(visitX+x)/2][(visitY+y)/2].setMark(true);mazeGrid[visitX][visitY].setVisited(true);if(!visited.contains(id)){//将这个点加到已访问中去visited.add(id);}willVisit.clear();createMap(mazeGrid,visitX,visitY);}else{if(!visited.isEmpty()){Stringid=visited.remove(visited.size()-1);//取出最后一个元素visitX=Integer.parseInt(id.split("#")[0]);visitY=Integer.parseInt(id.split("#")[1]);mazeGrid[visitX][visitY].setVisited(true);createMap(mazeGrid,visitX,visitY);}}returnmazeGrid;}//走迷宫publicStringgoMaze(MazeGridmazeGrid[][],intx,inty){intcomeX=0;intcomeY=0;//leftif(x-1>=0){if(mazeGrid[x-1][y].isMark()){if(!comed.contains((x-1)+"#"+y))willVisit.add((x-1)+"#"+y);}}//rightif(x+1<cols){if(mazeGrid[x+1][y].isMark()){if(!comed.contains((x+1)+"#"+y))willVisit.add((x+1)+"#"+y);}}//upif(y-1>=0){if(mazeGrid[x][y-1].isMark()){if(!comed.contains(x+"#"+(y-1)))willVisit.add(x+"#"+(y-1));}}//downif(y+1<rows){if(mazeGrid[x][y+1].isMark()){if(!comed.contains(x+"#"+(y+1)))willVisit.add(x+"#"+(y+1));}}if(!willVisit.isEmpty()){intvisit=(int)(Math.random()*willVisit.size());Stringid=willVisit.get(visit);comeX=Integer.parseInt(id.split("#")[0]);comeY=Integer.parseInt(id.split("#")[1]);mazeGrid[x][y].setPersonCome(false);mazeGrid[comeX][comeY].setPersonCome(true);mazeGrid[x][y].repaint();mazeGrid[comeX][comeY].repaint();willVisit.clear();comed.add(x+"#"+y);}else{if(!comed.isEmpty()){Stringid=comed.removeLast();comeX=Integer.parseInt(id.split("#")[0]);comeY=Integer.parseInt(id.split("#")[1]);mazeGrid[x][y].setPersonCome(false);mazeGrid[comeX][comeY].setPersonCome(true);mazeGrid[x][y].repaint();mazeGrid[comeX][comeY].repaint();comed.addFirst(x+"#"+y);}}returncomeX+"#"+comeY;}——————————————————————————————————————测试设计与数据（设计充足合理的测试用例，说明测试策略）1.迷宫的初始状态：迷宫你尚未添加任何东西。2.在迷宫的墙还没随机生成时的状态：这时的迷宫已经基本有了一个雏形，接下来就是随机的将墙删去，改为路。迷宫生成的最后状态。在迷宫的生成中需要满足每一行至少有一个通路，每一列中也要有一个通路。——————————————————————————————————————实验现象及结果（应用文字和程序运行的截图说明测试现象，并解释结果）点击生成迷宫可以随机生成一个新迷宫。点击开始，老鼠开始走迷宫。在走完迷宫后会提示所花费的时间。——————————————————————————————————————实验分析与探讨（对测试现象和观察结果进行分析，探讨算法，提出见解）对于老鼠走迷宫来看，走迷宫的方法很笨，即使在终点前有一个叉路口，有时它也不会走向终点，所以本方法不是最有方法，对于最短的路径不会有判断。这也就是本次使用的算法的不足的地方，回溯法无法最好的找出最短路径。——————————————————————————————————————实验结论（算法设计是否得到实现，测试结果表明程序是否成功解决问题等）在老鼠走迷宫程序中，迷宫的生成使用的是回溯法，走迷宫也使用的回溯法，程序可以运行，但是程序中没有魔法豆，无法实现穿墙。——————————————————————————————————————6、实验总结（成败得失，实验关键，算法改进，程序改善，自我评价）在这次实验中，我们还有没有完善的地方，有些要求还没有达到，但是也做的还不错。只差一个吃魔法豆穿墙的要求没有达到。本次实验指导老师评语：小组成员共同努力，完成了大部分实验的要求，锻炼了实际操作的能力，有了一定的进步。验报告格式正确，文档规范，描述清楚，风格统一。通过试验巩固了所学的知识，能够将一些算法灵活运用，有一定的进步。但程序还是略有不足，希望能好好改进。争取达到实验的所有要求，并加以拓展。得分：签名：年月日importjava.awt.Canvas;importjava.awt.Color;importjava.awt.Graphics;publicclassMazeGridextendsCanvas{privatebooleanmark;//标记是否是通路，TRUE为通路，FALSE为不通privatebooleanisVisited;//标记是否是访问过的,这是在生成迷宫的时候判断的。privatebooleanisPersonCome;//标记是否已经走过privatebooleanisStart;//判断是否为入口privatebooleanisEnd;//判断是否为出口publicMazeGrid(){this.setBackground(newColor(112,128,144));this.setSize(25,25);}publicMazeGrid(booleanmark,intwidth,intheight){ this.mark=mark;this.setSize(width,height);if(mark==true){this.setBackground(newColor(255,255,255));}else{this.setBackground(newColor(112,128,144));}}publicbooleanisMark(){returnmark;}publicvoidsetMark(booleanmark){this.mark=mark;}publicvoidpaint(Graphicsg){ Colorc[]={Color.RED,Color.blue,Color.GRAY};if(this.mark){if(this.isStart||this.isEnd){this.setBackground(newColor(218,112,214));//入口出口颜色}elsethis.setBackground(newColor(255,255,255));//路的颜色}else{this.setBackground(c[(int)(Math.random()*3)]);//墙的颜色}if(this.isPersonCome){g.setColor(Color.ORANGE);//老鼠颜色g.fillOval(2,2,40,40);//位置大小}}publicbooleanisVisited(){returnisVisited;}publicvoidsetVisited(booleanisVisited){this.isVisited=isVisited;}publicbooleanisPersonCome(){returnisPersonCome;}publicvoidsetPersonCome(booleanisPersonCome){this.isPersonCome=isPersonCome;}publicbooleanisStart(){returnisStart;}publicvoidsetStart(booleanisStart){this.isStart=isStart;}publicbooleanisEnd(){returnisEnd;}publicvoidsetEnd(booleanisEnd){this.isEnd=isEnd;}}importjava.awt.BorderLayout;importjava.awt.Color;importjava.awt.GridLayout;importjava.awt.event.ActionEvent;importjava.awt.event.ActionListener;importjava.util.ArrayList;importjava.util.LinkedList;importjava.util.List;importjava.util.TimerTask;importjavax.swing.JButton;importjavax.swing.JFrame;importjavax.swing.JOptionPane;importjavax.swing.JPanel;//迷宫publicclassMazeextendsJFrameimplementsActionListener{privateJPanelpanel;privateJPanelsouthPanel;privateJPanelcenterPanel;privateMazeGridgrid[][];privateJButtonrestart;privateJButtondostart;privateintrows;//rows和cols目前暂定只能是奇数privateintcols;privateList<String>willVisit;privateList<String>visited;privateLinkedList<String>comed;privatelongstartTime;privatelongendTime;publicMaze(){ rows=15;cols=15;willVisit=newArrayList<String>();visited=newArrayList<String>();comed=newLinkedList<String>();init();this.setTitle("老鼠走迷宫");this.add(panel);this.pack();this.setVisible(true);this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);}publicvoidinit(){panel=newJPanel();southPanel=newJPanel();centerPanel=newJPanel();panel.setLayout(newBorderLayout());grid=newMazeGrid[rows][cols];restart=newJButton("生成迷宫");dostart=newJButton("开始");centerPanel.setLayout(newGridLayout(rows,cols,1,1));//边框粗细centerPanel.setBackground(newColor(0,0,0));//边框颜色southPanel.add(restart);southPanel.add(dostart);dostart.addActionListener(this);restart.addActionListener(this);for(inti=0;i<grid.length;i++)for(intj=0;j<grid[i].length;j++){if(j%2==0&&i%2==0)grid[i][j]=newMazeGrid(true,40,40);//true为路elsegrid[i][j]=newMazeGrid(false,40,40);//false为墙}grid[0][0].setVisited(true);grid[0][0].setPersonCome(true);grid[0][0].setStart(true);visited.add("0#0");grid[rows-1][cols-1].setEnd(true);//出口grid=createMap(grid,0,0);for(inti=0;i<grid.length;i++)for(intj=0;j<grid[i].length;j++){grid[i][j].repaint();//重绘centerPanel.add(grid[i][j]);}panel.add(southPanel,BorderLayout.SOUTH);panel.add(centerPanel,BorderLayout.CENTER);}//生成迷宫publicMazeGrid[][]createMap(MazeGridmazeGrid[][],intx,inty){intvisitX=0;intvisitY=0;if(x-2>=0){if(!mazeGrid[x-2][y].isVisited()){willVisit.add((x-2)+"#"+y);}}if(x+2<cols){if(!mazeGrid[x+2][y].isVisited()){willVisit.add((x+2)+"#"+y);}}if(y-2>=0){if(!mazeGrid[x][y-2].isVisited()){willVisit.add(x+"#"+(y-2));}}if(y+2<rows){if(!mazeGrid[x][y+2].isVisited()){willVisit.add(x+"#"+(y+2));}}if(!willVisit.isEmpty()){intvisit=(int)(Math.random()*willVisit.size());Stringid=willVisit.get(visit);visitX=Integer.parseInt(id.split("#")[0]);visitY=Integer.parseInt(id.split("#")[1]);mazeGrid[(visitX+x)/2][(visitY+y)/2].setMark(true);mazeGrid[visitX][visitY].setVisited(true);if(!visited.contains(id)){//将这个点加到已访问中去visited.add(id);}willVisit.clear();createMap(mazeGrid,visitX,visitY);}else{if(!visited.isEmpty()){Stringid=visited.remove(visited.size()-1);//取出最后一个元素visitX=Integer.parseInt(id.split("#")[0]);visitY=Integer.parseInt(id.split("#")[1]);mazeGrid[visitX][visitY].setVisited(true);createMap(mazeGrid,visitX,visitY);}}returnmazeGrid;}//走迷宫publicStringgoMaze(MazeGridmazeGrid[][],intx,inty){intcomeX=0;intcomeY=0;//rightif(x+1<cols){if(mazeGrid[x+1][y].isMark()){if(!comed.contains((x+1)+"#"+y))willVisit.add((x+1)+"#"+y);}}//downif(y+1<rows){if(mazeGrid[x][y+1].isMark()){if(!comed.contains(x+"#"+(y+1)))willVisit.add(x+"#"+(y+1));}}//leftif(x-1>=0){if(mazeGrid[x-1][y].isMark()){if(!comed.contains((x-1)+"#"+y))willVisit.add((x-1)+"#"+y);}}//upif(y-1>=0){if(mazeGrid[x][y-1].isMark()){if(!comed.contains(x+"#"+(y-1)))willVisit.add(x+"#"+(y-1));}}if(!willVisit.isEmpty()){intvisit=(int)(Math.random()*willVisit.size());Stringid=willVisit.get(visit);comeX=Integer.parseInt(id.split("#")[0]);comeY=Integer.parseInt(id.split("#")[1]);mazeGrid[x][y].setPersonCome(false);mazeGrid[comeX][comeY].setPersonCome(true);mazeGrid[x][y].repaint();mazeGrid[comeX][comeY].repaint();willVisit.clear();comed.add(x+"#"+y);}else{if(!comed.isEmpty()){Stringid=comed.removeLast();comeX=Integer.parseInt(id.split("#")[0]);comeY=Integer.parseInt(id.split("#")[1]);mazeGrid[x][y].setPersonCome(false);mazeGrid[comeX][comeY].setPersonCome(true);mazeGrid[x][y].repaint();mazeGrid[comeX][comeY].repaint();comed.addFirst(x+"#"+y);}}returncomeX+"#"+comeY;}intcomeX=0;intcomeY=0;publicvoidactionPerformed(ActionEvente){if(e