数据结构课程设计java求解迷宫-回溯法-A算法

算法与数据结构课程设计课题：求解迷宫通路的图形界面演示程序作者：吴昊QQ：328035823目录1.题目及需求分析········································42.概要设计··············································43.详细设计·············································104.调试分析·············································395.课程设计总结·········································421．题目及需求分析1.1题目编制一个求解迷宫通路的图形界面演示程序。1.2需求分析输入一个任意大小的迷宫，任设起点、终点、障碍，用栈求出一条走出迷宫的路径，并显示在屏幕上；根据用户界面提示，用键盘输入，Home键设置迷宫起点，End键设终点，上下左右箭头键移动，Enter键添加墙，Del键删除墙，完成后按F9键演示，演示完毕后可F5刷新题图，重新对地图的起点、终点、障碍进行设置，Esc键退出；本程序要求至少得出一条成功的通路，也可求得全部路径。此外，也可尝试保存或载入测试文件（此功能不做强行要求）。当未输入起点时，消息显示“Error：YoumustsettheSTART.”；未输入终点时，显示“Error：YoumustsettheEND.”；找到路径时，屏幕显示足迹，并在消息框出现Pathfound，否则消去足迹，显示Pathnotfound。用户可以通过界面上提供的菜单选项，选择“帮助”查看操作说明。（算法选优）用户可以通过界面上提供的菜单选项，选择“A*算法求最短路径”演示求解迷宫最短路径。2.概要设计根据需求分析的用户界面的设计要求，考虑到我们在Java课程中学习过GUI设计，对Java的GUI的比较熟悉，所以我们用Java语言来开发本项目。在设计求解迷宫的程序时，要求编写8个Java源文件：Dialog.java、Maze.java、MazeGUI.java、Position.java、Rollback.java、stack.java、Astar.java和Aposition.java。该程序除了上述6个Java源文件所给出的类以外，还需呀Java系统提供的一些重要的类，如java.awt包中的容器类、画图类、事件类及监听器接口、javax.swing包中的各种轻量组件类和java.lang包中线程类等。2.1UML类图程序的所用到的一些重要的类以及之间的关联关系如图2-1所示。图2-1UML类图2.2Dialog.java(主类)Dialog.java(主类)是JDialog类的一个子类。该类负责创建提示用户输入迷宫大小的对话框，通过用户输入的参数来确定所要创建的迷宫图形界面的窗口的大小。该类含有main方法，程序从该类开始执行。Begin类的成员变量有JTextField、JButton、JFrame。Begin类的主要成员和成员方法的作用将在后面的详细设计中阐述。2.3Maze.javaMaze类创建的对象是MazeGUI类和Rollback类最重要的成员之一，代表迷宫。该类负责接收在迷宫窗口所设置起点、终点、障碍的位置参数来绘制迷宫图像并存储迷宫结构的信息。该类的主要成员变量有3种类型的对象：Position、Image以及存放整型数的二维数组。Maze类的主要成员和成员方法的作用将在后面的详细设计中阐述。2.4MazeGUI.javaMazeGUI类是Frame类的一个子类，创建的对象是Rollback类最重要的成员之一。该类负责创建迷宫图形窗口界面，方便用户在界面上设置起点、终点、障碍等并展现求解迷宫的过程。该类的主要成员变量有4种类型的对象：Maze、Rollback、Position和Thread。该类还包含一个内部类SolveThread，该内部类实现了runnable接口。MazeGUI类的主要成员和成员方法的作用将在后面的详细设计中阐述。2.5Position.java（图形界面坐标的存储结构） Position类创建的对象是Maze类、MazeGUI类和Rollback类最重要的成员之一。该类负责在Maze类、MazeGUI类和Rollback类之间传递消息，其对象存有当前位置的坐标信息。该类包含两个整型的成员变量x和y，记录当前位置在迷宫图形界面的横、纵坐标。Position类的主要成员和成员方法的作用将在后面的详细设计中阐述。2.6Stack.java（数据类型结构）为了体现算法与数据结构的课程特点，我们并没有用Java系统类库中java.Util.Stack类，而是编写了一个通用的Stack存储结构。Stack类创建的对象是Rollback类的最重要的成员之一。该类负责保存在求解迷宫过程中所走过的路径信息。该类包含一个内部类Node，定义了栈中存储的节点元素的类型。另外还含有一个整型成员变量n和一个Node类型的成员变量top，分别记录栈中元素的个数以及栈顶元素的信息。而Node类定义的是栈中节点的类型，包含当前节点的信息info（Object类型）和以及栈中下一个元素的引用next（相当在C语言中的指针）。Stack类的主要成员和成员方法的作用将在后面的详细设计中阐述。2.7Rollback.java（核心算法—回溯算法）Rollback类创建的对象是是MazeGUI类最重要的成员之一。该类负责根据Maze类中的迷宫数组的信息采用回溯算法，控制并绘制人物在迷宫图形界面窗口中的位置。该类的主要成员变量有4种类型的对象：Maze、MazeGUI、Position和Stack。Rollback类的主要成员和成员方法的作用将在后面的详细设计中阐述。2.8Astar.java（核心算法—A*算法）Astar类创建的对象是是MazeGUI类最重要的成员之一。该类负责根据Maze类中的迷宫数组的信息采用A*算法，找到起点到终点的最短路径并打印出来。该类的主要成员变量有4种类型的对象：Maze、APosition、Stack和LinkedList。Astar类的主要成员和成员方法的作用将在后面的详细设计中阐述。2.9Aposition（A*算法的存储结构）Aposition类是Position类的派生类，APosition类创建的对象是Astar类、MazeGUI类和Rollback类最重要的成员之一。该类负责在Astar类、MazeGUI类和Rollback类之间传递消息，其对象存有当前位置的坐标信息、A*算法的评估函数值、开关标记和父节点等。APosition类的主要成员和成员方法的作用将在后面的详细设计中阐述。2.9事件跟踪图2.9.1用户启动迷宫图形界面图2-2用户启动迷宫图形界面2.9.2用户设置迷宫参数图2-3用户设置迷宫参数2.9.3回溯法求解迷宫图2-4回溯法求解迷宫3.详细设计3.1工程文件视图3.2Dialog.java(主类)3.2.1效果图Dialog创建的对话框效果如图1所示。图1Dialog创建的对话框对象3.2.2UML图Dialog类是javax.swing包中JDialog的一个子类，标明该类的主要成员变量和方法的UML图如图2所示。图2Dialog类的UMl图以下是UML图中有关数据和方法的详细说明。成员变量tf1、tf2是JTextField类创建的文本框。用来接收用户输入的设置迷宫的大小参数，即行和列的数目。当用户没有输入时，tf1、tf2的默认文本内容为10。b是JButton类创建的按钮，名字为“生成迷宫”。b被放置在对话框的右下角。b还为自己注册了ActionEvent的事件监听器。当点击按钮时，根据tf1、tf2的文本内容创建一个MazeGUI的对象，生成迷宫图形界面窗口。2）成员方法Dialog()是构造方法，负责完成对话框的初始化操作。初始化操作包括：将内容为"列数："的JLabel对象、内容为"列数："的JLabel对象、tf1、tf2、b添加到对话框中，并设置对话框的布局，设置背景颜色，设置对话框的标题为“课程设计--求解迷宫”。另外还为对话框注册了WindowEvent的事件监听器。main(Stringsrgd[])方法是程序运行的入口方法。3.2.3代码（Dialog.java）packagemaze;importjava.awt.*;importjava.awt.event.*;importjavax.swing.*;/***启动窗口**/@SuppressWarnings("serial")publicclassDialogextendsJDialog{ privateJTextFieldtf1=newJTextField("10",10); privateJTextFieldtf2=newJTextField("10",10); privateJButtonb=newJButton("生成迷宫"); publicstaticvoidmain(Stringsrgd[]){ try{ Thread.sleep(300); }catch(Exceptione){ e.printStackTrace(); } newDialog(); } publicDialog(){ setTitle("课程设计--求解迷宫"); setLayout(newBorderLayout()); JPanelp=newJPanel(newGridLayout(4,1)); FlowLayoutflowLayout=newFlowLayout(); flowLayout.setAlignment(FlowLayout.LEFT); flowLayout.setHgap(10); FlowLayoutflowLayout1=newFlowLayout(); flowLayout1.setAlignment(FlowLayout.RIGHT); JPanelp1=newJPanel(flowLayout); JPanelp2=newJPanel(flowLayout); JPanelp3=newJPanel(); JPanelp4=newJPanel(); JPanelp5=newJPanel(flowLayout1); p1.add(newJLabel("行数：")); p1.add(tf1); p2.add(newJLabel("列数：")); p2.add(tf2); p1.setBackground(newColor(226,244,255)); p2.setBackground(newColor(226,244,255)); p3.setBackground(newColor(226,244,255)); p4.setBackground(newColor(226,244,255)); p.add(p3); p.add(p1); p.add(p2); p.add(p4); p5.add(b); p5.setBackground(newColor(196,227,248)); add(newJLabel(newImageIcon("maze.jpg")),BorderLayout.NORTH); add(p,BorderLayout.CENTER); add(p5,BorderLayout.SOUTH); setSize(345,250); setLocation(400,100); setVisible(true); b.addActionListener(newActionListener(){ publicvoidactionPerformed(ActionEvente){ newMazeGUI(Integer.parseInt(tf1.getText()),Integer.parseInt(tf2.getText())); setVisible(false); } }); addWindowListener(newWindowAdapter(){ publicvoidwindowClosing(WindowEvente){ System.exit(0); } }); }}3.3Maze.java3.3.1效果图Maze类绘制的墙、通路、路径、起点和终点的效果图如图3所示。图3墙、通路、路径、起点和终点3.3.2UML图Maze类创建的对象是MazeGUI类和Rollback类最重要的成员之一，代表迷宫。标明Maze类的主要成员变量、成员方法的UMl图如图4所示。图4Maze类的UML图以下是UML图中有关数据和方法的详细说明。成员变量mazeMap是int类型的二维数组，数组的元素的值表示迷宫对应位置的内容。若元素的值为0表示迷宫对应位置可通过，即为通路；若元素的值为1表示迷宫对应位置为墙；若元素的值为2表示迷宫对应位置为已经走过的足迹；若元素的值为3，表示迷宫对应位置是从栈中弹出的点，并且不能再次通过；若元素的值为4，表示迷宫对应位置为起点，保证起点不可通过。begin和end是Position类创建的对象，其存储了起点和终点在迷宫图形界面上的坐标信息。drawPos是Position类创建的对象，在迷宫图形界面上表现为一个方框，起到定位的作用，其存储了在设置起点、终点、障碍在迷宫图形界面的位置时当前的坐标信息。wallPic、roadPic、goPic、beginPic和endPic是Image类创建的对象，其内容分别为墙、通路、路径、起点和终点的图片。row和col是int类型的变量，其值分别表示迷宫数组的行数和列数。成员方法Maze(introw,intcol)是Maze类的构造方法，通过调用setMaze方法来创建maze对象，其参数row，col是从MazeGUI类中传来的参数。setMaze(introw,intcol)方法，maze对象可调用该方法完成迷宫数组的初始化操作：创建指定行数和列数的迷宫数组，将迷宫图形界面外围位置对应迷宫数组的元素的值设为1，将其余元素的值设为0。isPass(Positionp)方法，maze对象可调用该方法判断传入的参数p点周围的四个方向是否能通过，并返回一个整型数。根据p点坐标，确定该点在迷宫数组中的元素位置，然后再根据该位置四个方向上相邻位置元素的值判断该p点周围的四个方向是否能通过。若元素的值为0表示可以通过。对于返回值，若返回-1，表示p点四周没有通路（包括从栈中弹出的点）；若返回0，表示p点东方向有通路；若返回1，表示p点南方向有通路；若返回2，表示p点西方向有通路；若返回3，表示p点北方向有通路。mark(Positionp,intm)方法，maze对象可调用该方法将传入的参数p点在迷宫数组的对应位置的元素设为m。draw(Graphicsg)方法，maze对象可调用该方法根据迷宫数组元素的值来绘制墙、通路、路径图像和用于在迷宫图形界面定位的方框，此外该方法还根据begin和end中存储的坐标信息来绘制对应位置的起点和终点图像。setBegin(intx,inty)和setEnd(intx,inty)方法，maze对象可调用该方法根据传入的参数x，y来创建Position类的对象begin和end。3.3.3代码（Maze.java）packagemaze;importjava.awt.*;importjavax.swing.*;/***迷宫参数**/publicclassMaze{ int[][]mazeMap;//地图数据 Positionbegin;//起始坐标 Positionend;//结束坐标 PositiondrawPos=newPosition(1,1); ImagewallPic=newImageIcon("wall.jpg").getImage(); ImageroadPic=newImageIcon("road.jpg").getImage(); Imagea=newImageIcon("a.jpg").getImage(); ImagegoPic=newImageIcon("go.jpg").getImage(); ImageendPic=newImageIcon("end.jpg").getImage(); ImagebeginPic=newImageIcon("begin.jpg").getImage(); introw=0,col=0; publicMaze(introw,intcol){ this.row=row; this.col=col; mazeMap=newint[row][col]; for(inti=0;i<row;i++){ for(intj=0;j<col;j++){ if(i==0||j==0||j==col-1||i==row-1){//迷宫最外层设为墙 this.mazeMap[i][j]=1; }else{ this.mazeMap[i][j]=0; } } } } publicMaze(){ } publicvoidmark(Positionp,intm){//标记位置已走过 this.mazeMap[p.y][p.x]=m; } publicvoiddraw(Graphicsg){//绘制地图图片 for(inti=0;i<row;i++){ for(intj=0;j<col;j++){ if(begin!=null&&i==begin.y&&j==begin.x){//起点 g.drawImage(beginPic,j*50,24+i*50,50,50,null); }elseif(end!=null&&i==end.y&&j==end.x){//终点 g.drawImage(endPic,j*50,24+i*50,50,50,null); }elseif(this.mazeMap[i][j]==1){//墙壁 g.drawImage(wallPic,j*50,24+i*50,50,50,null); }elseif(this.mazeMap[i][j]==2){//已走过的路径 g.drawImage(goPic,j*50,24+i*50,50,50,null); }elseif(this.mazeMap[i][j]==3){//已走过的路径，消除脚印 g.drawImage(roadPic,j*50,24+i*50,50,50,null); }elseif(this.mazeMap[i][j]==5){//A*方法路径 g.drawImage(a,j*50,24+i*50,50,50,null); } else{//通道 g.drawImage(roadPic,j*50,24+i*50,50,50,null); } } } g.drawRect(drawPos.x*50,24+drawPos.y*50,50,50); } publicvoidresume(){//恢复迷宫 for(inti=0;i<row;i++){ for(intj=0;j<col;j++){ if(this.mazeMap[i][j]==2||this.mazeMap[i][j]==3){ this.mazeMap[i][j]=0; } } } } publicvoidsetEnd(intx,inty){ end=newPosition(x,y); } publicvoidsetBegin(intx,inty){ begin=newPosition(x,y); }}3．4MazeGUI.java3.4.1效果图MazeGUI类创建的迷宫图形界面窗口的效果图如图5所示。图5MazeGUI类创建的迷宫图形界面窗口的效果图3.4.2UML图MazeGUI类是Frame类的一个子类，创建的对象是Rollback类最重要的成员之一。该类负责创建迷宫图形窗口界面，方便用户在界面上设置起点、终点、障碍等并展现求解迷宫的过程。该类还包含两个内部类SolveThead、AThread，该内部类实现了runnable接口。标明Maze类的主要成员变量、成员方法的UMl图如图6所示。图6MazeGUI类的UML图以下是UML图中有关数据和方法的详细说明。成员变量obj是Object类型的对象，该对象用于充当线程问题中的同步锁。row、col是int类型的变量，用来设置值迷宫图形界面的大小（不是指长度和宽度）。offScreen是Image类的对象，用于双缓冲技术防止屏幕闪烁。maze是Maze类的对象。该对象是在MazeGUI类的构造方法中根据row和col的值来创建的。rollback是Rollback类的对象，该对象负责求解迷宫，并绘制人物在迷宫图形界面中的位置。t1、t2是Thread线程类的对象，该对象负责控制求解迷宫的线程，便于展现求解迷宫的过程。成员方法paint(Graphicsg)方法，该方法调用了maze对象的draw（Graphicsg）和rollback对象的draw（Graphicsg），分别绘制迷宫内容图像和人物图像。update(Graphicsg)MazeGUI(introw,intcol)是MazeGUI类的构造方法，负责完成创建迷宫图形界面窗口的初始化操作。初始化操作包括：根据row和col创建maze对象，并根据创建的maze对象和MazeGUI自身的一个引用来创建rollback对象；为迷宫图形窗口注册KeyEvent的事件监听器；设置窗口的大小，以及窗口在屏幕上显示的位置，设置菜单栏和菜单选项的内容，放入窗口中，并为菜单选项注册ActionEvent的事件监听器。threadSleep（）方法，在求解迷宫的过程结束时，MazeGUI类的对象可调用该方法暂停求解迷宫线程，使求解迷宫线程等待。具体来说是，求解迷宫线程拥有MazeGUI类的对象的监视器，当对象调用该方法时，放弃对此监视器的所有权并等待，直到其他线程通过调用notify方法，或notifyAll方法通知在此对象的监视器上等待的线程醒来。然后该线程将等到重新获得对监视器的所有权后才能继续执行。keyTyped(KeyEvente)方法为KeyListener接口中的抽象方法，必须要实现，但在本程序中没有实际用处，故在MazeGUI类中该方法为空方法；keyReleased(KeyEvente)方法为KeyListener接口中的抽象方法，必须要实现，但在本程序中没有实际用处，故在MazeGUI类中该方法为空方法；keyPressed（KeyEvente）方法为KeyListener接口中的抽象方法，必须要实现。该方法的操作如下：当按下键盘上的按键时，将会调用repaint（）方法。根据所按下键的键值分成一下几种情况：若按下键盘的Enter键，将会把迷宫图形界面中定位方框位置对应的迷宫数组的元素值改为1，maze对象将在该位置绘制墙的图像；若按下键盘的Delete键，将会把迷宫图形界面中定位方框位置对应的迷宫数组的元素值改为0，maze对象将在该位置绘制通路的图像；若按下键盘方向键的上键，将会把迷宫图形界面中定位方框上移一个单位；若按下键盘方向键的下键，将会把迷宫图形界面中定位方框下移一个单位；若按下键盘方向键的左键，将会把迷宫图形界面中定位方框左移一个单位；若按下键盘方向键的右键，将会把迷宫图形界面中定位方框右移一个单位；若按下键盘的Home键，将会调用maze对象的setBegin(intx,inty)方法，把当前定位方框所在位置的坐标传给setBegin(intx,inty)方法，创建Maze类中的begin对象，并且maze对象将在该位置绘制起点图像；若按下键盘的End键，将会调用maze对象的setEnd(intx,inty)方法，把当前定位方框所在位置的坐标传给setEnd(intx,inty)方法，创建Maze类中的end对象，并且maze对象将在该位置绘制终点图像；若按下键盘的F9键，如果迷宫图形界面没有设置起点或终点，将会提示设置起点或终点，否则不能演示求解迷宫，如果迷宫设置完毕，将启动求解迷宫线程，演示求解迷宫的过程；actionPerformed(ActionEvente)方法，当鼠标点击菜单选项时将把产生的事件传给该方法，鼠标点击菜单选项“退出”时，将会关闭窗口并退出程序；鼠标点击刷新地图时，将会清空迷宫里内容，让用户重新设置。3）内部类SolveThread内部类SolveThread实现了runnable接口，是在MazeGUI内部定义的一个线程类。该线程根据rollback.isOver()返回的值判断求解迷宫过程是否结束，若没有结束，则不断在求解过程中不断地使线程睡眠200毫秒，可使求解迷宫的过程能清楚地展现给用户，此外还调用rollback.forward()、rollback.back()等求解迷宫的核心算法，并调用repaint（）重绘。3.4.3代码（MazeGUI.java）packagemaze;importjava.awt.*;importjava.awt.event.*;importjavax.swing.*;/***迷宫图形界面**/@SuppressWarnings("serial")publicclassMazeGUIextendsFrameimplementsKeyListener,ActionListener{//迷宫GUI finalObjectobj=newObject();//锁对象 introw=0,col=0; ImageoffScreen=null; Mazemaze;//构建迷宫参数 Rollbackrollback; Astarastar; Threadt1=newThread(newSolveThread(),"SolveThread");//寻路进程，在初始化Thread类时，把目标对象传递给这个线程实例 Threadt2=newThread(newAThread(),"AThread"); publicvoidpaint(Graphicsg){//调用绘制地图的draw()方法和绘制人物位置的draw()方法 maze.draw(g); rollback.draw(g); } publicvoidupdate(Graphicsg){//双缓冲防止屏幕闪烁 if(offScreen==null){ offScreen=this.createImage(col*50,row*50); } Graphicsoffg=offScreen.getGraphics(); Colorc=offg.getColor(); offg.setColor(Color.BLUE); offg.fillRect(0,0,col*50,row*50); offg.setColor(c); paint(offg); g.drawImage(offScreen,0,0,null); } publicMazeGUI() { } publicMazeGUI(introw,intcol){//初始化窗体 this.setTitle("算法课程设计-求解迷宫问题"); this.setSize(col*50,row*50); this.setLocation(200,80); this.setResizable(false); this.addWindowListener(newWindowAdapter(){ publicvoidwindowClosing(WindowEvente){ System.exit(0); } }); this.row=row; this.col=col; maze=newMaze(row,col);//构建迷宫参数 rollback=newRollback(maze,this); this.setVisible(true); MenuBarmenuBar=newMenuBar(); MenufileMenu=newMenu("文件"); MenusettingMenu=newMenu("操作"); MenuItemexitItem=newMenuItem("退出"); MenuItemmapItem=newMenuItem("刷新地图"); MenuItemaItem=newMenuItem("A*算法寻找最短路径"); MenuItemhelpItem=newMenuItem("帮助"); fileMenu.add(exitItem); settingMenu.add(mapItem); settingMenu.add(aItem); settingMenu.add(helpItem); menuBar.add(fileMenu); menuBar.add(settingMenu); setMenuBar(menuBar); addKeyListener(this); exitItem.addActionListener(this); mapItem.addActionListener(this); aItem.addActionListener(this); helpItem.addActionListener(this); } privateclassSolveThreadimplementsRunnable{//提供一个实现借口Runnable接口的类的实例，作为一个线程的目标对象 publicvoidrun(){ while(!rollback.isOver()){//寻路结束后，线程结束 synchronized(obj){ try{ Thread.sleep(200); }catch(InterruptedExceptione){ e.printStackTrace(); } if(!rollback.forward()){ rollback.back(); } repaint(); } } } } privateclassAThreadimplementsRunnable{//展示用A*算法求解迷宫过程的线程 publicvoidrun(){ while(!astar.as.isEmpty()){ synchronized(obj){ try{ Thread.sleep(200); }catch(InterruptedExceptione){ e.printStackTrace(); } Apositiontemp=(Aposition)astar.as.top(); astar.as.pop(); maze.mazeMap[temp.y][temp.x]=5; rollback.curPos.x=temp.x; rollback.curPos.y=temp.y; } repaint(); if(astar.as.isEmpty())JOptionPane.showMessageDialog(null,"找到最短路径最短路径！"); } } } publicvoidkeyTyped(KeyEvente){ } publicvoidkeyReleased(KeyEvente){ } publicvoidkeyPressed(KeyEvente){ if(e.getKeyCode()==KeyEvent.VK_DELETE){ maze.mark(maze.drawPos,0); } elseif(e.getKeyCode()==KeyEvent.VK_ENTER){ maze.mark(maze.drawPos,1); } elseif(e.getKeyCode()==KeyEvent.VK_F9){ if(maze.begin==null){ JOptionPane.showMessageDialog(null,"起点没有设置"); }elseif(maze.end==null){ JOptionPane.showMessageDialog(null,"终点没有设置"); }elseif(t1.getState().equals(Thread.State.NEW)){//当没有线程处于运行态时 t1.start();//启动寻路线程 System.out.print("new"); }elseif(t1.getState().equals(Thread.State.TERMINATED)){//当该线程处于终止态时，又点击了F9，即重新演示 t1=newThread(newSolveThread(),"SolveThread");//新建线程 rollback.flush();//刷新 maze.resume();//恢复迷宫到初始状态 t1.start(); } else{//在寻路过程中，如果点击了“F9”按键 System.out.print("repeat"); rollback.flush();//清空栈，并把sprite中的curPos对象恢复到初试位置 maze.resume();//恢复迷宫到初始状态 repaint(); } } elseif(e.getKeyCode()==KeyEvent.VK_DOWN){ if(maze.drawPos.y+1>0&&maze.drawPos.y+1<row-1)//禁止定位方框移动到最外围的“墙”上 maze.drawPos.y=maze.drawPos.y+1; } elseif(e.getKeyCode()==KeyEvent.VK_UP){ if(maze.drawPos.y-1>0&&maze.drawPos.y-1<row-1) maze.drawPos.y=maze.drawPos.y-1; } elseif(e.getKeyCode()==KeyEvent.VK_RIGHT){ if(maze.drawPos.x+1>0&&maze.drawPos.x+1<col-1) maze.drawPos.x=maze.drawPos.x+1; } elseif(e.getKeyCode()==KeyEvent.VK_LEFT){ if(maze.drawPos.x-1>0&&maze.drawPos.x-1<col-1) maze.drawPos.x=maze.drawPos.x-1; } elseif(e.getKeyCode()==KeyEvent.VK_END){ maze.setEnd(maze.drawPos.x,maze.drawPos.y); } elseif(e.getKeyCode()==KeyEvent.VK_HOME){ maze.setBegin(maze.drawPos.x,maze.drawPos.y);//起点坐标 rollback.setCurPos(maze.drawPos.x,maze.drawPos.y);//设置回溯算法中的当前点 rollback.remember(rollback.curPos); } repaint(); } publicvoidactionPerformed(ActionEvente){ Stringes=e.getActionCommand(); if(es.equals("退出")){ System.exit(0); }elseif(es.equals("刷新地图")){ maze=newMaze(row,col); rollback=newRollback(maze,this); t2=newThread(newAThread(),"AThread"); repaint(); }elseif(es.equals("A*算法寻找最短路径")){ if(maze.end==null||maze.begin==null){ JOptionPane.showMessageDialog(null,"终点或终点没有设置！"); return; }elseif(t2.getState().equals(Thread.State.TERMINATED)){ JOptionPane.showMessageDialog(null,"最短路径已找到，请刷新地图！"); return; }elseif(t2.getState().equals(Thread.State.NEW)){ astar=newAstar(maze); astar.solve(); t2.start(); } }elseif(es.equals("帮助")){ JOptionPane.showMessageDialog(null,"Home：设置起点\nEnd：设置终点\nEnter：设置墙\nDelete：删除墙\nF9：演示\n"); } }} 3.5Position.java（图形界面坐标的存储结构）3.5.1UML图Position类创建的对象是Maze类、MazeGUI类和Rollback类最重要的成员之一。该类负责在Maze类、MazeGUI类和Rollback类之间传递消息，其对象存有当前位置的坐标信息。该类包含两个整型的成员变量x和y，记录当前位置在迷宫图形界面的横、纵坐标。标明Position类的主要成员变量、成员方法的UMl图如图7所示。图7Position类的UML图以下是UML图中有关数据和方法的详细说明。成员变量x、y是int类型的变量，标志迷宫图形界面的坐标。x代表图形界面的横坐标，但对应到迷宫数组中的是列，y代表图形界面的纵坐标，但对应到迷宫数组中的是行。2）成员方法Position(intx,inty)方法是Position类的构造方法。equals(Objecto)方法用于判断当前位置的o对象是否和调用该方法的Position类对象的内容相等。方法先判断o是否为Position类的实例，若是先强制转换则返回ture，否则返回false。3.5.2代码（Position.java）packagemaze;/***点坐标类**/publicclassPosition{ publicintx,y; publicPosition(intx,inty){ this.x=x; this.y=y; }publicPosition(){ } publicbooleanequals(Objecto){ if(o==null){ returnfalse; } if(!(oinstanceofPosition)){ returnfalse; } Positionp=(Position)o; returnthis.x==p.x&&this.y==p.y; }}3.6Stack.java(数据结构类型)3.6.1UML图Stack类创建的对象是Sprite类的最重要的成员之一。该类负责保存在求解迷宫过程中所走过的路径信息。该类包含一个内部类Node，定义了栈中存储的节点元素的类型。另外还含有一个整型成员变量n和一个Node类型的成员变量top，分别记录栈中元素的个数以及栈顶元素的信息。而Node类定义的是栈中节点的类型，包含当前节点的信息info（Object类型）和以及栈中下一个元素的引用next（相当在C语言中的指针，这儿类似与链式存储的栈）。标明Stack类的主要成员变量、成员方法的UMl图如图8所示。图8Stack类的UML图以下是UML图中有关数据和方法的详细说明。成员变量top是Node类的对象，表示栈定元素。n是int类型的变量，表示栈中元素的个数。成员方法push(Objecto)方法，Stack类对象可调用该方法，根据o对象和当前的top对象创建一个新的top变量，然后n自加。top()方法，将top对象的info作为返回值返回。pop()方法，当栈不为空时，将当前栈顶元素的info返回，并把next赋给top对象，n自减。isEmpty()方法，负责判断栈是否为空。3）内部类Node内部类Node代表栈中节点元素的类型，包含一个构造方法和两个成员变量info和是Object类型的变量，可转换为Position类型的变量；next是Node类型的变量，是栈顶元素的下一个元素的引用（相当于指针）。3.6.2代码（Stack.java）packagemaze;/***栈类**/publicclassStack{ privateNodetop;//节点为Node类型 privateintsize;//栈中节点数 publicStack(){//构造方法 top=null; size=0; } publicvoidpush(Objecto){ top=newNode(o,top); size++; } publicObjecttop(){ if(isEmpty())returnnull; Objecto=; returno; } publicvoidpop(){ if(isEmpty())return; else{ top=top.next; size--; return; } } publicbooleanisEmpty(){ returnsize==0; } privateclassNode{ publicObjectinfo; publicNodenext; publicNode(Objecto,Noden){//Node类构造方法 info=o; next=n; } }}3.7Rollback.java（核心算法——回溯法）3.7.1效果图Rollback类绘制人物的效果图如图9所示。图9人物图3.7.2UML图Rollback类创建的对象是是MazeGUI类最重要的成员之一。该类负责根据Maze类中的迷宫数组的信息采用回溯算法，控制并绘制人物在迷宫图形界面窗口中的位置。标明Rollback类的主要成员变量、成员方法的UMl图如图10所示。图10Rollback类的UML图以下是UML图中有关数据和方法的详细说明。1）成员变量curPos是Position类型的对象，该对象表示在求解迷宫过程中人物位置的点，同时也是栈顶元素。memory是Stack类型的对象，表示一个栈，而元素采用链式存储的结构。maze是Maze类型的对象，是MazeGUI类中maze对象的一个引用。mt是MazeGUI类型的对象，在Rollback类中是通过该变量来控制线程的。person是Image类型的对象，是所要绘制的人物图像。2）成员方法Rollback(Mazem,MazeGUImt)方法是Rollback类的构造方法。forward()方法，该方法根据maze对象的isPass（）方法的返回值来判断curPos周围是否有通路。若有，将curPos压入栈中，并把下一个通路的坐标赋给curPos的坐标，并标记该通路已走过。back（）方法，当curPos周围没有通路时，调用此方法获取栈顶元素中info域，若不空，则将curPos标记为从栈中弹出的点，并弹出栈顶元素，把info域赋给curPos，实现回溯。若为空，则表示栈中没有元素，此时已经回溯到起点，迷宫不存在可通的路径，使求解迷宫线程等待。isOver（）方法,该方法负责判断是否找到了终点。若curPos的坐标和maze.end的坐标相同则找到了终点，返回true，否则返回false。remember（Positionp）方法，该方法调用memory的push（）方法，将引用p压入栈中。draw(Graphicsg)方法，该方法负责在curPos点处绘制人物图像。setCurPos(intx,inty)方法，该方法根据x，y来设置curPos的坐标。3.7.3算法伪代码rollback对象back()方法rollback对象back()方法rollback对象forward()方法先将curPos（初始值为begin）压入stack中do｛mark()，即标记当前位置已走过，使对应位置的mazeMap[][]值为2；if（curPos周围有通路，即对应位置的mazeMap[][]值为0）｛选择一个有通路方向，修改curPos的坐标；将curPos压入栈中；If（curPos的坐标和end的坐标相同）结束；｝else｛stack.pop()，出栈；stack.top()取栈顶元素；If（该元素不为null）｛将curPos的坐标修改为该位置的坐标；｝else｛stack已空，为找到end；｝｝while（当stack不为null）3.7.4代码（Rollback.java）packagemaze;importjava.awt.*;importjavax.swing.*;/***回溯算法实现**/publicclassRollback{ PositioncurPos;//当前位置 Stackmemory;//路径堆栈 Mazemaze; MazeGUImt; Imageperson=newImageIcon("1.gif").getImage(); publicRollback(Mazem,MazeGUImt){ this.maze=m; this.mt=mt; this.memory=newStack(); } publicintisPass(Positionp){//判断周围的通道那些没走过（东南西北） intj=p.x; inti=p.y; if(maze.mazeMap[i][j+1]==0){ return0; } if(maze.mazeMap[i+1][j]==0){ return1; } if(maze.mazeMap[i][j-1]==0){ return2; } if(maze.mazeMap[i-1][j]==0){ return3; } return-1;//周围都无法通过 } publicbooleanforward(){//前进 this.maze.mark(this.curPos,2);//标记为已走过 intdirection=this.isPass(this.curPos); if(direction==-1){ returnfalse;//周围都无法通过时返回false } intx=this.curPos.x+(1-direction)%2; inty=this.curPos.y+(2-direction)%2; this.curPos.x=x; this.curPos.y=y; remember(this.curPos); returntrue; } publicvoidback(){//forward()返回false时执行该方法 this.maze.mark(this.curPos,3);//取消脚印 this.memory.pop();//出栈 Positionp=(Position)this.memory.top();//获取前一个位置 if(p!=null){ this.curPos.x=p.x;//将前一个位置设为当前位置 this.curPos.y=p.y; } elsereturn; } publicbooleanisOver(){//判断是否结束,包括找到终点和没找到终点两种情况 if(this.curPos.x==maze.end.x&&this.curPos.y==maze.end.y){ JOptionPane.showMessageDialog(null,"Congratulation,Pathfound!"); while(!this.memory.isEmpty()){//找到后，将栈清空 this.maze.mark((Position)this.memory.top(),2); this.memory.pop(); } returntrue; } elseif(this.memory.isEmpty()){//栈已为空，找不到出路 JOptionPane.showMessageDialog(null,"Sorry,Pathnotfound!"); returntrue; } returnfalse; } publicvoidremember(Positionp){//保存当前路径 this.memory.push(newPosition(p.x,p.y)); } publicvoiddraw(Graphicsg){//绘制人物的位置 if(curPos!=null){ g.drawImage(person,this.curPos.x*50,24+this.curPos.y*50,50,50,null); } } publicvoidflush(){//刷新，清空栈，并把sprite中的curPos对象恢复到初试位置 while(!this.memory.isEmpty()){ this.memory.pop(); } this.curPos.x=maze.begin.x; this.curPos.y=maze.begin.y; remember(this.curPos); } publicvoidsetCurPos(intx,inty){ this.curPos=newPosition(x,y); }}3.8Astar.java（核心算法——A*算法）3.8.1A*算法简介A*算法在人工智能中是一种典型的启发式搜索算法。启发式即启发式。对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。A*算法估价函数：f(n)=g(n)+h(n)g(n)——在状态空间中从初始节点到n节点的实际代价h(n)——从n到目标节点最佳路径的估计代价特殊地，当h(n)=0时，只需求出g(n)，即求出起点到任意节点n的最短路径，即Dijkstra算法。在求解迷宫问题中，用两个列表来保存探索过的解。开启列表——保存已经评估过，但没有走过的点关闭列表——保存已经走过的点3.8.2效果图Maze类绘制脚印的效果图如图11所示。图11脚印图3.8.3UML图Astar类创建的对象是是MazeGUI类最重要的成员之一。该类负责根据Maze类中的迷宫数组的信息采用A*算法，找到起点到终点的最短路径并打印出来。标明Astar类的主要成员变量、成员方法的UMl图如图12所示。图12Astar类的UML图以下是UML图中有关数据和方法的详细说明。1）成员变量maze是Maze类型的对象，是MazeGUI类中maze对象的一个引用。A*算法中要根据maze对象的mazeMap域中相关位置的值，来判断该点。as是Stack类型的对象，表示一个栈，而元素采用链式存储的结构。aMap是APosition类型的二维数组cur是APosition类型的对象，该对象表示用A*算法求解迷宫过程中当前探索的点。begin是APosition类型的对象，该对象表示A*算法中的起点，存有相关信息。end是APosition类型的对象，该对象表示A*算法中的终点，存有相关信息。open是一个LinkedList类型的列表，是java类库中常用的容器，用来存放Aposition类型的元素，相关的操作。close是一个LinkedList类型的列表，是java类库中常用的容器，用来存放Aposition类型的元素，相关的操作。direct是整型二维数组，存放二维单位方向向量。2）成员方法Astar(Mazem)方法是Astar类的构造方法。probe(APositioncur)方法是探索当期位置的点，根据maze.mazeMap[][]中的值探索cur周围方向的点，并计算这些点的相关信息保存起来。sort（）方法是将open表中的元素按F值从小到大排序。solve（）方法反映了A*算法的基本步骤，其中会调用probe方法。setH(APositionp)方法是求出p点的h值，采用哈曼顿方法，从当前点到终点之间水平和垂直的方格的数量总和。setG(APositionp)方法是求出p点的G值，向某个方向移动一格，累计G值加一。setF(APositionp)方法是求出p点的F值，F=H+G。3.8.4算法伪代码astar对象solve()方法astar对象solve()方法astar对象probe()方法while(open!=NULL)｛从open表中删除估价值f最小的节点，并赋给curPos；将curPos加入close表中；探索curPos周围的点aMap[][]；If（aMap[][]为通路）｛计算aMap[][]的估价值；将aMap[][]的前驱节点赋为curPos；将aMap[][]加入到open表中；｝elseif（aMap[][]为end）｛加end加入关闭列表中；跳出循环；｝elseif（aMap[][]已在关闭列表中）｛｝else｛if（curPos.g+1<aMap[][].g）将aMap[][]的父节点pre赋为curPos；｝sort()，将开启列表中各点按f值从小到大排序；｝3.8.4代码（Astar.java）packagemaze;importjava.util.*;importjavax.swing.JOptionPane;/***A*算法实现**/publicclassAstar{ Mazemaze; Stackas=newStack(); Aposition[][]aMap; Apositioncur;//当前点 Apositionbegin; Apositionend; LinkedList<Aposition>open=newLinkedList<Aposition>();//开启列表 LinkedList<Aposition>close=newLinkedList<Aposition>();//关闭列表 int[][]direction={{1,0},{0,1},{-1,0},{0,-1}};//方向数组，右下左上 publicAstar(Mazemaze){//构造方法 this.maze=maze; aMap=newAposition[maze.row][maze.col];//该二维数组的元素都为null this.begin=newAposition(maze.begin.x,maze.begin.y,null,0);//1:close,0:open this.end=newAposition(maze.end.x,maze.end.y,null,-1);//-1isend aMap[this.begin.y][this.begin.x]=this.begin; aMap[this.end.y][this.end.x]=this.end; open.add(this.begin);//将起点放入关闭列表 } publicvoidprobe(Apositioncur){//试探方法 for(inti=0;i<4;i++){ inttx=cur.x+direction[i][0]; intty=cur.y+direction[i][1]; if(maze.mazeMap[ty][tx]==0&&this.aMap[ty][tx]==null){//是通路，并且还不存在，引用为null aMap[ty][tx]=newAposition(tx,ty,cur,0);//使引用明确,并开启 setH(aMap[ty][tx]); setG(aMap[ty][tx]); setF(aMap[ty][tx]); open.add(aMap[ty][tx]);//加入到开启列表中 }elseif(aMap[ty][tx]!=null){//已存在的 if(close.contains(aMap[ty][tx])){}//已在关闭列表中则不处理 elseif(aMap[ty][tx].equals(this.end)){//若找到终点，将终点加入到关闭列表中 this.end.pre=cur; close.add(this.end); }else{ if(aMap[ty][tx].g>cur.g+1){//已在开启列表中，比较是否更优 aMap[ty][tx].pre=cur; setG(aMap[ty][tx]); setF(aMap[ty][tx]); } } } } sort(); //将开启列表排序 } publicvoidsort(){//根据F值从小到大排序 Apositiontemp; for(inti=0;i<open.size()-1;i++){ for(intj=i+1;j<open.size();j++){ if(open.get(i).f>open.get(j).f){ temp=open.get(i); open.set(i,open.get(j)); open.set(j,temp); } } } } publicvoidsolve(){//求解 Apositiontemp;//设置回滚对象 while(open.size()!=0){//当开启列表不为空时，循环 this.cur=(Aposition)open.poll();//取开启列表中F值最小的,并从开启列表中删除 close.add(this.cur);//加入到关闭列表中 this.cur.flag=1;//标记为关闭 probe(this.cur);//探索启发 if(close.contains(this.end)){ temp=this.end; while(temp!=null){ as.push(temp); temp=temp.pre; } return; } } JOptionPane.showMessageDialog(null,"Sorry,Pathnotfound!"); return; } publicvoidsetH(Apositionp){//求H值 p.h=Math.abs(this.end.x-p.x)+Math.abs(this.begin.y-p.y); } publicvoidsetG(Apositionp){//求G值 p.g=p.pre.g+1; } publicvoidsetF(Apositionp){//求F值 p.f=p.g+p.h; }}astar对象probe()方法astar对象probe()方法astar对象probe()方法3.9Aposition.java（A*算法存储结构）3.9.1UML图Aposition类是Position类的派生类，APosition类创建的对象是Astar类、MazeGUI类和Rollback类最重要的成员之一。该类负责在Astar类、MazeGUI类和Rollback类之间传递消息，其对象存有当前位置的坐标信息、A*算法的评估函数值、开关标记和父节点等。标明Astar类的主要成员变量、成员方法的UMl图如图13所示。图9-13Aposition类的UML图3.9.2代码（Aposition.java）packagemaze;/***A*算法点坐标类**/publicclassApositionextendsPosition{//继承了Position类 intf=0,g=0,h=0; intflag;//标记是否开启 Apositionpre; publicAposition(intx,inty,Apositionp,intflag){ super(x,y); this.pre=p;//前驱节点 this.flag=flag; }}4程序测试调试程序编码的过程中，我们遇到过各种问题，有的是编译时错误，还有的是运行时的异常。编译时错误主要是，对象未初始化。运行时异常主要包括空指针、数组越界等。在程序编码完成后，由