數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)java求解迷宮回溯法A算法

1、 算法與數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計(jì)課題：求解迷宮通路的圖形界面演示程序作者：吳昊 QQ：328035823目錄1.題目及需求分析42.概要設(shè)計(jì)43.詳細(xì)設(shè)計(jì)104.調(diào)試分析395.課程設(shè)計(jì)總結(jié)421題目及需求分析1.1題目編制一個(gè)求解迷宮通路的圖形界面演示程序。1.2需求分析輸入一個(gè)任意大小的迷宮，任設(shè)起點(diǎn)、終點(diǎn)、障礙，用棧求出一條走出迷宮的路徑，并顯示在屏幕上；根據(jù)用戶界面提示，用鍵盤輸入，Home鍵設(shè)置迷宮起點(diǎn)，End鍵設(shè)終點(diǎn)，上下左右箭頭鍵移動(dòng)，Enter鍵添加墻，Del鍵刪除墻，完成后按F9鍵演示，演示完畢后可F5刷新題圖，重新對(duì)地圖的起點(diǎn)、終點(diǎn)、障礙進(jìn)行設(shè)置，Esc鍵退出；本程序要求至少得出

2、一條成功的通路，也可求得全部路徑。此外，也可嘗試保存或載入測(cè)試文件（此功能不做強(qiáng)行要求）。當(dāng)未輸入起點(diǎn)時(shí)，消息顯示“Error： You must set the START.”；未輸入終點(diǎn)時(shí)，顯示“Error： You must set the END.”；找到路徑時(shí)，屏幕顯示足跡，并在消息框出現(xiàn)Path found，否則消去足跡，顯示Path not found。用戶可以通過(guò)界面上提供的菜單選項(xiàng)，選擇“幫助”查看操作說(shuō)明。（算法選優(yōu)）用戶可以通過(guò)界面上提供的菜單選項(xiàng)，選擇“A*算法求最短路徑”演示求解迷宮最短路徑。2.概要設(shè)計(jì)根據(jù)需求分析的用戶界面的設(shè)計(jì)要求，考慮到我們?cè)贘ava課程中學(xué)習(xí)

3、過(guò)GUI設(shè)計(jì)，對(duì)Java的GUI的比較熟悉，所以我們用Java語(yǔ)言來(lái)開發(fā)本項(xiàng)目。在設(shè)計(jì)求解迷宮的程序時(shí)，要求編寫8個(gè)Java源文件：Dialog.java、Maze.java、MazeGUI.java、Position.java、Rollback.java、stack.java、Astar.java和Aposition.java。該程序除了上述6個(gè)Java源文件所給出的類以外，還需呀Java系統(tǒng)提供的一些重要的類，如java.awt包中的容器類、畫圖類、事件類及監(jiān)聽(tīng)器接口、javax.swing包中的各種輕量組件類和java.lang包中線程類等。2.1 UML類圖程序的所用到的一些重要的類以

4、及之間的關(guān)聯(lián)關(guān)系如圖2-1所示。圖2-1 UML類圖2.2 Dialog.java(主類)Dialog.java(主類)是JDialog類的一個(gè)子類。該類負(fù)責(zé)創(chuàng)建提示用戶輸入迷宮大小的對(duì)話框，通過(guò)用戶輸入的參數(shù)來(lái)確定所要?jiǎng)?chuàng)建的迷宮圖形界面的窗口的大小。該類含有main方法，程序從該類開始執(zhí)行。Begin類的成員變量有JTextField、JButton、JFrame。Begin類的主要成員和成員方法的作用將在后面的詳細(xì)設(shè)計(jì)中闡述。2.3 Maze.javaMaze類創(chuàng)建的對(duì)象是MazeGUI類和Rollback類最重要的成員之一，代表迷宮。該類負(fù)責(zé)接收在迷宮窗口所設(shè)置起點(diǎn)、終點(diǎn)、障礙的位置參數(shù)

5、來(lái)繪制迷宮圖像并存儲(chǔ)迷宮結(jié)構(gòu)的信息。該類的主要成員變量有3種類型的對(duì)象：Position、Image以及存放整型數(shù)的二維數(shù)組。Maze類的主要成員和成員方法的作用將在后面的詳細(xì)設(shè)計(jì)中闡述。2.4 MazeGUI.javaMazeGUI類是Frame類的一個(gè)子類，創(chuàng)建的對(duì)象是Rollback類最重要的成員之一。該類負(fù)責(zé)創(chuàng)建迷宮圖形窗口界面，方便用戶在界面上設(shè)置起點(diǎn)、終點(diǎn)、障礙等并展現(xiàn)求解迷宮的過(guò)程。該類的主要成員變量有4種類型的對(duì)象：Maze、Rollback、Position和Thread。該類還包含一個(gè)內(nèi)部類SolveThread，該內(nèi)部類實(shí)現(xiàn)了runnable接口。MazeGUI類的主要成

6、員和成員方法的作用將在后面的詳細(xì)設(shè)計(jì)中闡述。2.5 Position.java（圖形界面坐標(biāo)的存儲(chǔ)結(jié)構(gòu)）Position類創(chuàng)建的對(duì)象是Maze類、MazeGUI類和Rollback類最重要的成員之一。該類負(fù)責(zé)在Maze類、MazeGUI類和Rollback類之間傳遞消息，其對(duì)象存有當(dāng)前位置的坐標(biāo)信息。該類包含兩個(gè)整型的成員變量x和y，記錄當(dāng)前位置在迷宮圖形界面的橫、縱坐標(biāo)。Position類的主要成員和成員方法的作用將在后面的詳細(xì)設(shè)計(jì)中闡述。2.6 Stack.java（數(shù)據(jù)類型結(jié)構(gòu)）為了體現(xiàn)算法與數(shù)據(jù)結(jié)構(gòu)的課程特點(diǎn)，我們并沒(méi)有用Java系統(tǒng)類庫(kù)中java.Util.Stack類，而是編寫了一

7、個(gè)通用的Stack存儲(chǔ)結(jié)構(gòu)。Stack類創(chuàng)建的對(duì)象是Rollback類的最重要的成員之一。該類負(fù)責(zé)保存在求解迷宮過(guò)程中所走過(guò)的路徑信息。該類包含一個(gè)內(nèi)部類Node，定義了棧中存儲(chǔ)的節(jié)點(diǎn)元素的類型。另外還含有一個(gè)整型成員變量n和一個(gè)Node類型的成員變量top，分別記錄棧中元素的個(gè)數(shù)以及棧頂元素的信息。而Node類定義的是棧中節(jié)點(diǎn)的類型，包含當(dāng)前節(jié)點(diǎn)的信息info（Object類型）和以及棧中下一個(gè)元素的引用next（相當(dāng)在C語(yǔ)言中的指針）。Stack類的主要成員和成員方法的作用將在后面的詳細(xì)設(shè)計(jì)中闡述。2.7 Rollback.java（核心算法回溯算法）Rollback類創(chuàng)建的對(duì)象是是Maz

8、eGUI類最重要的成員之一。該類負(fù)責(zé)根據(jù)Maze類中的迷宮數(shù)組的信息采用回溯算法，控制并繪制人物在迷宮圖形界面窗口中的位置。該類的主要成員變量有4種類型的對(duì)象：Maze、MazeGUI、Position和Stack。Rollback類的主要成員和成員方法的作用將在后面的詳細(xì)設(shè)計(jì)中闡述。2.8 Astar.java（核心算法A*算法）Astar類創(chuàng)建的對(duì)象是是MazeGUI類最重要的成員之一。該類負(fù)責(zé)根據(jù)Maze類中的迷宮數(shù)組的信息采用A*算法，找到起點(diǎn)到終點(diǎn)的最短路徑并打印出來(lái)。該類的主要成員變量有4種類型的對(duì)象：Maze、APosition、Stack和LinkedList。Astar類的主

9、要成員和成員方法的作用將在后面的詳細(xì)設(shè)計(jì)中闡述。2.9 Aposition（A*算法的存儲(chǔ)結(jié)構(gòu)）Aposition類是Position類的派生類，APosition類創(chuàng)建的對(duì)象是Astar類、MazeGUI類和Rollback類最重要的成員之一。該類負(fù)責(zé)在Astar類、MazeGUI類和Rollback類之間傳遞消息，其對(duì)象存有當(dāng)前位置的坐標(biāo)信息、A*算法的評(píng)估函數(shù)值、開關(guān)標(biāo)記和父節(jié)點(diǎn)等。APosition類的主要成員和成員方法的作用將在后面的詳細(xì)設(shè)計(jì)中闡述。2.9事件跟蹤圖2.9.1用戶啟動(dòng)迷宮圖形界面圖2-2 用戶啟動(dòng)迷宮圖形界面2.9.2用戶設(shè)置迷宮參數(shù)圖2-3 用戶設(shè)置迷宮參數(shù)2.9.

10、3回溯法求解迷宮圖2-4 回溯法求解迷宮3.詳細(xì)設(shè)計(jì)3.1 工程文件視圖3.2 Dialog.java(主類)3.2.1 效果圖Dialog創(chuàng)建的對(duì)話框效果如圖1所示。圖1 Dialog創(chuàng)建的對(duì)話框?qū)ο?.2.2 UML圖Dialog類是javax.swing包中JDialog的一個(gè)子類，標(biāo)明該類的主要成員變量和方法的UML圖如圖2所示。圖2 Dialog類的UMl圖以下是UML圖中有關(guān)數(shù)據(jù)和方法的詳細(xì)說(shuō)明。成員變量tf1、tf2是JTextField類創(chuàng)建的文本框。用來(lái)接收用戶輸入的設(shè)置迷宮的大小參數(shù)，即行和列的數(shù)目。當(dāng)用戶沒(méi)有輸入時(shí)，tf1、tf2的默認(rèn)文本內(nèi)容為10。b是JButton類

11、創(chuàng)建的按鈕，名字為“生成迷宮”。b被放置在對(duì)話框的右下角。b還為自己注冊(cè)了ActionEvent的事件監(jiān)聽(tīng)器。當(dāng)點(diǎn)擊按鈕時(shí)，根據(jù)tf1、tf2的文本內(nèi)容創(chuàng)建一個(gè)MazeGUI的對(duì)象，生成迷宮圖形界面窗口。2）成員方法Dialog()是構(gòu)造方法，負(fù)責(zé)完成對(duì)話框的初始化操作。初始化操作包括：將內(nèi)容為 列數(shù)： 的JLabel對(duì)象、內(nèi)容為 列數(shù)： 的JLabel對(duì)象、tf1、tf2、b添加到對(duì)話框中，并設(shè)置對(duì)話框的布局，設(shè)置背景顏色，設(shè)置對(duì)話框的標(biāo)題為“課程設(shè)計(jì)-求解迷宮”。另外還為對(duì)話框注冊(cè)了WindowEvent的事件監(jiān)聽(tīng)器。main(String srgd)方法是程序運(yùn)行的入口方法。3.2.3

12、代碼（Dialog.java）package maze;import java.awt.*;import java.awt.event.*;import javax.swing.*;/* * 啟動(dòng)窗口 * */SuppressWarnings(serial)public class Dialog extends JDialog private JTextField tf1=new JTextField(10,10);private JTextField tf2=new JTextField(10,10);private JButton b=new JButton(生成迷宮);public st

13、atic void main(String srgd)tryThread.sleep(300);catch(Exception e)e.printStackTrace();new Dialog();public Dialog()setTitle(課程設(shè)計(jì)-求解迷宮);setLayout(new BorderLayout();JPanel p=new JPanel(new GridLayout(4,1);FlowLayout flowLayout=new FlowLayout();flowLayout.setAlignment(FlowLayout.LEFT);flowLayout.setHga

14、p(10);FlowLayout flowLayout1=new FlowLayout();flowLayout1.setAlignment(FlowLayout.RIGHT);JPanel p1=new JPanel(flowLayout);JPanel p2=new JPanel(flowLayout);JPanel p3=new JPanel();JPanel p4=new JPanel();JPanel p5=new JPanel(flowLayout1);p1.add(new JLabel( 行數(shù)： );p1.add(tf1);p2.add(new JLabel( 列數(shù)： );p2.

15、add(tf2);p1.setBackground(new Color(226,244,255);p2.setBackground(new Color(226,244,255);p3.setBackground(new Color(226,244,255);p4.setBackground(new Color(226,244,255);p.add(p3);p.add(p1);p.add(p2);p.add(p4);p5.add(b);p5.setBackground(new Color(196,227,248);add(new JLabel(new ImageIcon(maze.jpg),Bo

16、rderLayout.NORTH);add(p,BorderLayout.CENTER);add(p5,BorderLayout.SOUTH);setSize(345, 250);setLocation(400, 100);setVisible(true);b.addActionListener(new ActionListener()public void actionPerformed(ActionEvent e)new MazeGUI(Integer.parseInt(tf1.getText(), Integer.parseInt(tf2.getText();setVisible(fal

17、se););addWindowListener(new WindowAdapter()public void windowClosing(WindowEvent e)System.exit(0););3.3 Maze.java3.3.1 效果圖Maze類繪制的墻、通路、路徑、起點(diǎn)和終點(diǎn)的效果圖如圖3所示。圖3 墻、通路、路徑、起點(diǎn)和終點(diǎn)3.3.2 UML圖Maze類創(chuàng)建的對(duì)象是MazeGUI類和Rollback類最重要的成員之一，代表迷宮。標(biāo)明Maze類的主要成員變量、成員方法的UMl圖如圖4所示。圖4 Maze類的UML圖以下是UML圖中有關(guān)數(shù)據(jù)和方法的詳細(xì)說(shuō)明。成員變量mazeMap是in

18、t類型的二維數(shù)組，數(shù)組的元素的值表示迷宮對(duì)應(yīng)位置的內(nèi)容。若元素的值為0表示迷宮對(duì)應(yīng)位置可通過(guò)，即為通路；若元素的值為1表示迷宮對(duì)應(yīng)位置為墻；若元素的值為2表示迷宮對(duì)應(yīng)位置為已經(jīng)走過(guò)的足跡；若元素的值為3，表示迷宮對(duì)應(yīng)位置是從棧中彈出的點(diǎn)，并且不能再次通過(guò)；若元素的值為4，表示迷宮對(duì)應(yīng)位置為起點(diǎn)，保證起點(diǎn)不可通過(guò)。begin和end是Position類創(chuàng)建的對(duì)象，其存儲(chǔ)了起點(diǎn)和終點(diǎn)在迷宮圖形界面上的坐標(biāo)信息。drawPos是Position類創(chuàng)建的對(duì)象，在迷宮圖形界面上表現(xiàn)為一個(gè)方框，起到定位的作用，其存儲(chǔ)了在設(shè)置起點(diǎn)、終點(diǎn)、障礙在迷宮圖形界面的位置時(shí)當(dāng)前的坐標(biāo)信息。wallPic、roadPi

19、c、goPic、beginPic和endPic是Image類創(chuàng)建的對(duì)象，其內(nèi)容分別為墻、通路、路徑、起點(diǎn)和終點(diǎn)的圖片。row和col是int類型的變量，其值分別表示迷宮數(shù)組的行數(shù)和列數(shù)。成員方法Maze(int row,int col)是Maze類的構(gòu)造方法，通過(guò)調(diào)用setMaze方法來(lái)創(chuàng)建maze對(duì)象，其參數(shù)row，col是從MazeGUI類中傳來(lái)的參數(shù)。setMaze(int row,int col)方法，maze對(duì)象可調(diào)用該方法完成迷宮數(shù)組的初始化操作：創(chuàng)建指定行數(shù)和列數(shù)的迷宮數(shù)組，將迷宮圖形界面外圍位置對(duì)應(yīng)迷宮數(shù)組的元素的值設(shè)為1，將其余元素的值設(shè)為0。isPass(Position

20、p)方法，maze對(duì)象可調(diào)用該方法判斷傳入的參數(shù)p點(diǎn)周圍的四個(gè)方向是否能通過(guò)，并返回一個(gè)整型數(shù)。根據(jù)p點(diǎn)坐標(biāo)，確定該點(diǎn)在迷宮數(shù)組中的元素位置，然后再根據(jù)該位置四個(gè)方向上相鄰位置元素的值判斷該p點(diǎn)周圍的四個(gè)方向是否能通過(guò)。若元素的值為0表示可以通過(guò)。對(duì)于返回值，若返回-1，表示p點(diǎn)四周沒(méi)有通路（包括從棧中彈出的點(diǎn)）；若返回0，表示p點(diǎn)東方向有通路；若返回1，表示p點(diǎn)南方向有通路；若返回2，表示p點(diǎn)西方向有通路；若返回3，表示p點(diǎn)北方向有通路。mark(Position p,int m)方法，maze對(duì)象可調(diào)用該方法將傳入的參數(shù)p點(diǎn)在迷宮數(shù)組的對(duì)應(yīng)位置的元素設(shè)為m。draw(Graphics g)

21、方法，maze對(duì)象可調(diào)用該方法根據(jù)迷宮數(shù)組元素的值來(lái)繪制墻、通路、路徑圖像和用于在迷宮圖形界面定位的方框，此外該方法還根據(jù)begin和end中存儲(chǔ)的坐標(biāo)信息來(lái)繪制對(duì)應(yīng)位置的起點(diǎn)和終點(diǎn)圖像。setBegin(int x,int y)和setEnd(int x,int y)方法，maze對(duì)象可調(diào)用該方法根據(jù)傳入的參數(shù)x，y來(lái)創(chuàng)建Position類的對(duì)象begin和end。3.3.3 代碼（Maze.java）package maze;import java.awt.*;import javax.swing.*;/* * 迷宮參數(shù) * */public class Maze int mazeMap;

22、/地圖數(shù)據(jù)Position begin;/起始坐標(biāo)Position end;/結(jié)束坐標(biāo)Position drawPos=new Position(1,1);Image wallPic=new ImageIcon(wall.jpg).getImage();Image roadPic=new ImageIcon(road.jpg).getImage();Image a=new ImageIcon(a.jpg).getImage();Image goPic=new ImageIcon(go.jpg).getImage();Image endPic=new ImageIcon(end.jpg).get

23、Image();Image beginPic=new ImageIcon(begin.jpg).getImage();int row=0,col=0;public Maze(int row,int col)this.row=row;this.col=col;mazeMap=new introwcol;for(int i=0;irow;i+)for(int j=0;jcol;j+)if(i=0|j=0|j=col-1|i=row-1)/迷宮最外層設(shè)為墻this.mazeMapij=1;else this.mazeMapij=0;public Maze()public void mark(Posi

24、tion p,int m)/標(biāo)記位置已走過(guò)this.mazeMapp.yp.x=m;public void draw(Graphics g)/繪制地圖圖片for(int i=0;irow;i+)for(int j=0;jcol;j+)if(begin!=null&i=begin.y&j=begin.x)/起點(diǎn)g.drawImage(beginPic,j*50, 24+i*50, 50, 50,null);else if(end!=null&i=end.y&j=end.x)/終點(diǎn)g.drawImage(endPic,j*50, 24+i*50, 50, 50,null);else if(this

25、.mazeMapij = 1)/墻壁g.drawImage(wallPic,j*50, 24+i*50, 50, 50,null);else if(this.mazeMapij = 2)/已走過(guò)的路徑g.drawImage(goPic,j*50, 24+i*50, 50, 50,null);else if(this.mazeMapij = 3)/已走過(guò)的路徑，消除腳印g.drawImage(roadPic,j*50, 24+i*50, 50, 50,null);else if(this.mazeMapij = 5)/A*方法路徑g.drawImage(a,j*50, 24+i*50, 50,

26、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);public void resume()/恢復(fù)迷宮for(int i=0;irow;i+)for(int j=0;j0&maze.drawPos.y+10&maze.drawPos.y-10&maze.drawPos.x+10&maze.drawPos.x-1col-1)maze.drawPos.x=maze.drawPos.x-1;else if(e.getKeyCo

27、de()=KeyEvent.VK_END)maze.setEnd(maze.drawPos.x, maze.drawPos.y);else if(e.getKeyCode()=KeyEvent.VK_HOME)maze.setBegin(maze.drawPos.x, maze.drawPos.y);/起點(diǎn)坐標(biāo)rollback.setCurPos(maze.drawPos.x, maze.drawPos.y);/設(shè)置回溯算法中的當(dāng)前點(diǎn)rollback.remember(rollback.curPos);repaint();public void actionPerformed(ActionEv

28、ent e)String es=e.getActionCommand();if(es.equals(退出)System.exit(0);else if(es.equals(刷新地圖)maze=new Maze(row,col);rollback=new Rollback(maze,this);t2 = new Thread(new AThread(),AThread);repaint();else if(es.equals(A*算法尋找最短路徑)if(maze.end=null|maze.begin=null)JOptionPane.showMessageDialog(null, 終點(diǎn)或終點(diǎn)沒(méi)

29、有設(shè)置！);return ;else if(t2.getState().equals(Thread.State.TERMINATED)JOptionPane.showMessageDialog(null, 最短路徑已找到，請(qǐng)刷新地圖！);return ;else if(t2.getState().equals(Thread.State.NEW)astar=new Astar(maze);astar.solve();t2.start();else if(es.equals(幫助)JOptionPane.showMessageDialog(null, Home：設(shè)置起點(diǎn)nEnd：設(shè)置終點(diǎn)nEnte

30、r：設(shè)置墻nDelete：刪除墻nF9：演示n);3.5 Position.java（圖形界面坐標(biāo)的存儲(chǔ)結(jié)構(gòu)）3.5.1 UML圖Position類創(chuàng)建的對(duì)象是Maze類、MazeGUI類和Rollback類最重要的成員之一。該類負(fù)責(zé)在Maze類、MazeGUI類和Rollback類之間傳遞消息，其對(duì)象存有當(dāng)前位置的坐標(biāo)信息。該類包含兩個(gè)整型的成員變量x和y，記錄當(dāng)前位置在迷宮圖形界面的橫、縱坐標(biāo)。標(biāo)明Position類的主要成員變量、成員方法的UMl圖如圖7所示。圖7 Position類的UML圖以下是UML圖中有關(guān)數(shù)據(jù)和方法的詳細(xì)說(shuō)明。成員變量x、y是int類型的變量，標(biāo)志迷宮圖形界面的坐

31、標(biāo)。x代表圖形界面的橫坐標(biāo)，但對(duì)應(yīng)到迷宮數(shù)組中的是列，y代表圖形界面的縱坐標(biāo)，但對(duì)應(yīng)到迷宮數(shù)組中的是行。2）成員方法Position(int x, int y)方法是Position類的構(gòu)造方法。equals(Object o)方法用于判斷當(dāng)前位置的o對(duì)象是否和調(diào)用該方法的Position類對(duì)象的內(nèi)容相等。方法先判斷o是否為Position類的實(shí)例，若是先強(qiáng)制轉(zhuǎn)換則返回ture，否則返回false。3.5.2 代碼（Position.java）package maze;/* * 點(diǎn)坐標(biāo)類 * */public class Positionpublic int x, y;public Posit

32、ion(int x, int y)this.x = x;this.y = y; public Position () public boolean equals(Object o)if(o = null)return false;if(!(o instanceof Position)return false;Position p =(Position) o;return this.x = p.x & this.y = p.y;3.6 Stack.java (數(shù)據(jù)結(jié)構(gòu)類型)3.6.1 UML圖Stack類創(chuàng)建的對(duì)象是Sprite類的最重要的成員之一。該類負(fù)責(zé)保存在求解迷宮過(guò)程中所走過(guò)的路徑信息。

33、該類包含一個(gè)內(nèi)部類Node，定義了棧中存儲(chǔ)的節(jié)點(diǎn)元素的類型。另外還含有一個(gè)整型成員變量n和一個(gè)Node類型的成員變量top，分別記錄棧中元素的個(gè)數(shù)以及棧頂元素的信息。而Node類定義的是棧中節(jié)點(diǎn)的類型，包含當(dāng)前節(jié)點(diǎn)的信息info（Object類型）和以及棧中下一個(gè)元素的引用next（相當(dāng)在C語(yǔ)言中的指針，這兒類似與鏈?zhǔn)酱鎯?chǔ)的棧）。標(biāo)明Stack類的主要成員變量、成員方法的UMl圖如圖8所示。圖8 Stack類的UML圖以下是UML圖中有關(guān)數(shù)據(jù)和方法的詳細(xì)說(shuō)明。成員變量top是Node類的對(duì)象，表示棧定元素。n是int類型的變量，表示棧中元素的個(gè)數(shù)。成員方法push(Object o)方法，St

34、ack類對(duì)象可調(diào)用該方法，根據(jù)o對(duì)象和當(dāng)前的top對(duì)象創(chuàng)建一個(gè)新的top變量，然后n自加。top()方法，將top對(duì)象的info作為返回值返回。pop()方法，當(dāng)棧不為空時(shí)，將當(dāng)前棧頂元素的info返回，并把next賦給top對(duì)象，n自減。isEmpty()方法，負(fù)責(zé)判斷棧是否為空。3）內(nèi)部類Node內(nèi)部類Node代表?xiàng)Ｖ泄?jié)點(diǎn)元素的類型，包含一個(gè)構(gòu)造方法和兩個(gè)成員變量info和是Object類型的變量，可轉(zhuǎn)換為Position類型的變量；next是Node類型的變量，是棧頂元素的下一個(gè)元素的引用（相當(dāng)于指針）。3.6.2 代碼（Stack.java）package maze;/* * 棧類 *

35、 */public class Stack private Node top;/節(jié)點(diǎn)為Node類型private int size;/棧中節(jié)點(diǎn)數(shù)public Stack()/構(gòu)造方法top=null;size=0;public void push(Object o)top=new Node(o,top);size+;public Object top()if(isEmpty()return null;Object o=;return o;public void pop()if(isEmpty() return ;elsetop=top.next;size-;return ;public boo

36、lean isEmpty()return size=0;private class Nodepublic Object info;public Node next;public Node(Object o,Node n)/Node類構(gòu)造方法info=o;next=n;3.7 Rollback.java（核心算法回溯法）3.7.1 效果圖Rollback類繪制人物的效果圖如圖9所示。圖9 人物圖3.7.2 UML圖Rollback類創(chuàng)建的對(duì)象是是MazeGUI類最重要的成員之一。該類負(fù)責(zé)根據(jù)Maze類中的迷宮數(shù)組的信息采用回溯算法，控制并繪制人物在迷宮圖形界面窗口中的位置。標(biāo)明Rollback類

37、的主要成員變量、成員方法的UMl圖如圖10所示。圖10 Rollback類的UML圖以下是UML圖中有關(guān)數(shù)據(jù)和方法的詳細(xì)說(shuō)明。1）成員變量curPos是Position類型的對(duì)象，該對(duì)象表示在求解迷宮過(guò)程中人物位置的點(diǎn)，同時(shí)也是棧頂元素。memory是Stack類型的對(duì)象，表示一個(gè)棧，而元素采用鏈?zhǔn)酱鎯?chǔ)的結(jié)構(gòu)。maze是Maze類型的對(duì)象，是MazeGUI類中maze對(duì)象的一個(gè)引用。mt是MazeGUI類型的對(duì)象，在Rollback類中是通過(guò)該變量來(lái)控制線程的。person是Image類型的對(duì)象，是所要繪制的人物圖像。2）成員方法Rollback(Maze m, MazeGUI mt)方法是R

38、ollback類的構(gòu)造方法。forward()方法，該方法根據(jù)maze對(duì)象的isPass（）方法的返回值來(lái)判斷curPos周圍是否有通路。若有，將curPos壓入棧中，并把下一個(gè)通路的坐標(biāo)賦給curPos的坐標(biāo)，并標(biāo)記該通路已走過(guò)。back（）方法，當(dāng)curPos周圍沒(méi)有通路時(shí)，調(diào)用此方法獲取棧頂元素中info域，若不空，則將curPos標(biāo)記為從棧中彈出的點(diǎn)，并彈出棧頂元素，把info域賦給curPos，實(shí)現(xiàn)回溯。若為空，則表示棧中沒(méi)有元素，此時(shí)已經(jīng)回溯到起點(diǎn)，迷宮不存在可通的路徑，使求解迷宮線程等待。isOver（）方法,該方法負(fù)責(zé)判斷是否找到了終點(diǎn)。若curPos的坐標(biāo)和maze.end的

39、坐標(biāo)相同則找到了終點(diǎn)，返回true，否則返回false。remember（Position p）方法，該方法調(diào)用memory的push（）方法，將引用p壓入棧中。draw(Graphics g)方法，該方法負(fù)責(zé)在curPos點(diǎn)處繪制人物圖像。setCurPos(int x,int y)方法，該方法根據(jù)x，y來(lái)設(shè)置curPos的坐標(biāo)。3.7.3 算法偽代碼rollback對(duì)象back()方法rollback對(duì)象forward()方法先將curPos（初始值為begin）壓入stack中domark()，即標(biāo)記當(dāng)前位置已走過(guò)，使對(duì)應(yīng)位置的mazeMap值為2；if（curPos周圍有通路，即對(duì)應(yīng)位

40、置的mazeMap值為0） 選擇一個(gè)有通路方向，修改curPos的坐標(biāo)； 將curPos壓入棧中； If（curPos的坐標(biāo)和end的坐標(biāo)相同） 結(jié)束； elsestack.pop()，出棧； stack.top()取棧頂元素；If（該元素不為null） 將curPos的坐標(biāo)修改為該位置的坐標(biāo)； else stack已空，為找到end；while（當(dāng)stack不為null）3.7.4 代碼（Rollback.java）package maze;import java.awt.*;import javax.swing.*;/* * 回溯算法實(shí)現(xiàn) * */public class Rollback

41、Position curPos;/當(dāng)前位置Stack memory;/路徑堆棧Maze maze;MazeGUI mt;Image person=new ImageIcon(1.gif).getImage();public Rollback(Maze m, MazeGUI mt)this.maze = m;this.mt = mt;this.memory = new Stack();public int isPass(Position p)/判斷周圍的通道那些沒(méi)走過(guò)（東南西北）int j=p.x;int i=p.y;if(maze.mazeMapij+1=0)return 0;if(maze.

42、mazeMapi+1j=0)return 1;if(maze.mazeMapij-1=0)return 2;if(maze.mazeMapi-1j=0)return 3;return -1; /周圍都無(wú)法通過(guò)public boolean forward()/前進(jìn)this.maze.mark(this.curPos,2);/標(biāo)記為已走過(guò)int direction = this.isPass(this.curPos);if(direction = -1)return false;/周圍都無(wú)法通過(guò)時(shí)返回falseint x = this.curPos.x +(1 - direction) % 2;i

43、nt y = this.curPos.y +(2 - direction) % 2;this.curPos.x = x;this.curPos.y = y;remember(this.curPos);return true;public void back()/forward()返回false時(shí)執(zhí)行該方法this.maze.mark(this.curPos,3);/取消腳印this.memory.pop();/出棧Position p = (Position) this.memory.top();/獲取前一個(gè)位置if(p != null)this.curPos.x = p.x;/將前一個(gè)位置設(shè)

44、為當(dāng)前位置this.curPos.y = p.y;else return ;public boolean isOver()/判斷是否結(jié)束,包括找到終點(diǎn)和沒(méi)找到終點(diǎn)兩種情況if(this.curPos.x=maze.end.x&this.curPos.y=maze.end.y)JOptionPane.showMessageDialog(null, Congratulation,Path found!);while(!this.memory.isEmpty()/找到后，將棧清空this.maze.mark(Position) this.memory.top(), 2);this.memory.po

45、p();return true;else if(this.memory.isEmpty()/棧已為空，找不到出路JOptionPane.showMessageDialog(null, Sorry,Path not found!);return true;return false;public void remember(Position p)/保存當(dāng)前路徑this.memory.push(new Position(p.x, p.y);public void draw(Graphics g)/繪制人物的位置if(curPos!=null)g.drawImage(person,this.curPo

46、s.x*50,24+this.curPos.y*50,50,50,null);public void flush()/刷新，清空棧，并把sprite中的curPos對(duì)象恢復(fù)到初試位置while(!this.memory.isEmpty()this.memory.pop();this.curPos.x=maze.begin.x;this.curPos.y=maze.begin.y;remember(this.curPos);public void setCurPos(int x,int y)this.curPos=new Position(x,y);3.8 Astar.java（核心算法A*算法

47、）3.8.1 A*算法簡(jiǎn)介A*算法在人工智能中是一種典型的啟發(fā)式搜索算法。 啟發(fā)式即啟發(fā)式。對(duì)每一個(gè)搜索的位置進(jìn)行評(píng)估，得到最好的位置，再?gòu)倪@個(gè)位置進(jìn)行搜索直到目標(biāo)。 A*算法估價(jià)函數(shù)：f(n) =g(n) +h(n)g(n)在狀態(tài)空間中從初始節(jié)點(diǎn)到n節(jié)點(diǎn)的實(shí)際代價(jià) h(n)從n到目標(biāo)節(jié)點(diǎn)最佳路徑的估計(jì)代價(jià) 特殊地，當(dāng)h(n)=0時(shí)，只需求出g(n)，即求出起點(diǎn)到任意節(jié)點(diǎn)n的最短路徑，即Dijkstra算法。 在求解迷宮問(wèn)題中，用兩個(gè)列表來(lái)保存探索過(guò)的解。 開啟列表保存已經(jīng)評(píng)估過(guò)，但沒(méi)有走過(guò)的點(diǎn) 關(guān)閉列表保存已經(jīng)走過(guò)的點(diǎn) 3.8.2效果圖Maze類繪制腳印的效果圖如圖11所示。圖11 腳印圖3

48、.8.3 UML圖Astar類創(chuàng)建的對(duì)象是是MazeGUI類最重要的成員之一。該類負(fù)責(zé)根據(jù)Maze類中的迷宮數(shù)組的信息采用A*算法，找到起點(diǎn)到終點(diǎn)的最短路徑并打印出來(lái)。標(biāo)明Astar類的主要成員變量、成員方法的UMl圖如圖12所示。圖12 Astar類的UML圖以下是UML圖中有關(guān)數(shù)據(jù)和方法的詳細(xì)說(shuō)明。1）成員變量maze是Maze類型的對(duì)象，是MazeGUI類中maze對(duì)象的一個(gè)引用。A*算法中要根據(jù)maze對(duì)象的mazeMap域中相關(guān)位置的值，來(lái)判斷該點(diǎn)。as是Stack類型的對(duì)象，表示一個(gè)棧，而元素采用鏈?zhǔn)酱鎯?chǔ)的結(jié)構(gòu)。aMap是APosition類型的二維數(shù)組cur是APosition類

49、型的對(duì)象，該對(duì)象表示用A*算法求解迷宮過(guò)程中當(dāng)前探索的點(diǎn)。begin是APosition類型的對(duì)象，該對(duì)象表示A*算法中的起點(diǎn)，存有相關(guān)信息。end是APosition類型的對(duì)象，該對(duì)象表示A*算法中的終點(diǎn)，存有相關(guān)信息。open是一個(gè)LinkedList類型的列表，是java類庫(kù)中常用的容器，用來(lái)存放Aposition類型的元素，相關(guān)的操作。close是一個(gè)LinkedList類型的列表，是java類庫(kù)中常用的容器，用來(lái)存放Aposition類型的元素，相關(guān)的操作。direct是整型二維數(shù)組，存放二維單位方向向量。2）成員方法Astar(Maze m)方法是Astar類的構(gòu)造方法。probe

50、(APosition cur)方法是探索當(dāng)期位置的點(diǎn)，根據(jù)maze.mazeMap中的值探索cur周圍方向的點(diǎn)，并計(jì)算這些點(diǎn)的相關(guān)信息保存起來(lái)。sort（）方法是將open表中的元素按F值從小到大排序。solve（）方法反映了A*算法的基本步驟，其中會(huì)調(diào)用probe方法。setH(APosition p)方法是求出p點(diǎn)的h值，采用哈曼頓方法，從當(dāng)前點(diǎn)到終點(diǎn)之間水平和垂直的方格的數(shù)量總和。setG(APosition p)方法是求出p點(diǎn)的G值，向某個(gè)方向移動(dòng)一格，累計(jì)G值加一。setF(APosition p)方法是求出p點(diǎn)的F值，F(xiàn)=H+G。3.8.4 算法偽代碼astar對(duì)象solve()方

51、法astar對(duì)象probe()方法while(open!=NULL)從open表中刪除估價(jià)值f最小的節(jié)點(diǎn)，并賦給curPos；將curPos加入close表中；探索curPos周圍的點(diǎn)aMap；If（aMap為通路） 計(jì)算aMap的估價(jià)值； 將aMap的前驅(qū)節(jié)點(diǎn)賦為curPos； 將aMap加入到open表中；else if（aMap為end） 加end加入關(guān)閉列表中；跳出循環(huán)；else if（aMap已在關(guān)閉列表中）else if（curPos.g+1 aMap.g）將aMap的父節(jié)點(diǎn)pre賦為curPos；sort()，將開啟列表中各點(diǎn)按f值從小到大排序；3.8.4代碼（Astar.jav

52、a）package maze;import java.util.*;import javax.swing.JOptionPane;/* * A*算法實(shí)現(xiàn) * */public class Astar Maze maze;Stack as=new Stack();Aposition aMap;Aposition cur;/當(dāng)前點(diǎn)Aposition begin;Aposition end;LinkedList open=new LinkedList();/開啟列表LinkedList close=new LinkedList();/關(guān)閉列表int direction=1,0,0,1,-1,0,0,

53、-1;/方向數(shù)組，右下左上public Astar(Maze maze)/構(gòu)造方法this.maze=maze;aMap=new Apositionmaze.rowmaze.col;/該二維數(shù)組的元素都為nullthis.begin=new Aposition(maze.begin.x,maze.begin.y,null,0);/1:close,0:openthis.end=new Aposition(maze.end.x,maze.end.y,null,-1);/-1 is endaMapthis.begin.ythis.begin.x=this.begin;aMapthis.end.yth

54、is.end.x=this.end;open.add(this.begin);/將起點(diǎn)放入關(guān)閉列表public void probe(Aposition cur)/試探方法for(int i=0;icur.g+1)/已在開啟列表中，比較是否更優(yōu) aMaptytx.pre=cur; setG(aMaptytx); setF(aMaptytx); sort();/將開啟列表排序public void sort()/根據(jù)F值從小到大排序Aposition temp;for(int i=0;iopen.size()-1;i+)for(int j=i+1;jopen.get(j).f)temp=open

55、.get(i);open.set(i,open.get(j);open.set(j,temp);public void solve() /求解Aposition temp;/設(shè)置回滾對(duì)象while(open.size()!=0)/當(dāng)開啟列表不為空時(shí)，循環(huán)this.cur=(Aposition)open.poll();/取開啟列表中F值最小的,并從開啟列表中刪除close.add(this.cur);/加入到關(guān)閉列表中this.cur.flag=1;/標(biāo)記為關(guān)閉probe(this.cur);/探索啟發(fā)if(close.contains(this.end)temp=this.end;while(

56、temp!=null)as.push(temp);temp=temp.pre;return ;JOptionPane.showMessageDialog(null, Sorry,Path not found!);return ;public void setH(Aposition p)/求H值p.h=Math.abs(this.end.x-p.x)+Math.abs(this.begin.y-p.y);public void setG(Aposition p)/求G值p.g=p.pre.g+1;public void setF(Aposition p)/求F值p.f=p.g+p.h;astar

57、對(duì)象probe()方法astar對(duì)象probe()方法3.9 Aposition.java（A*算法存儲(chǔ)結(jié)構(gòu)）3.9.1 UML圖Aposition類是Position類的派生類，APosition類創(chuàng)建的對(duì)象是Astar類、MazeGUI類和Rollback類最重要的成員之一。該類負(fù)責(zé)在Astar類、MazeGUI類和Rollback類之間傳遞消息，其對(duì)象存有當(dāng)前位置的坐標(biāo)信息、A*算法的評(píng)估函數(shù)值、開關(guān)標(biāo)記和父節(jié)點(diǎn)等。標(biāo)明Astar類的主要成員變量、成員方法的UMl圖如圖13所示。圖9-13 Aposition類的UML圖3.9.2代碼（Aposition.java）package maz

58、e;/* * A*算法點(diǎn)坐標(biāo)類 * */public class Aposition extends Position/繼承了Position類int f=0,g=0,h=0;int flag;/標(biāo)記是否開啟Aposition pre;public Aposition(int x,int y,Aposition p,int flag)super(x,y);this.pre=p;/前驅(qū)節(jié)點(diǎn)this.flag=flag;4程序測(cè)試調(diào)試程序編碼的過(guò)程中，我們遇到過(guò)各種問(wèn)題，有的是編譯時(shí)錯(cuò)誤，還有的是運(yùn)行時(shí)的異常。編譯時(shí)錯(cuò)誤主要是，對(duì)象未初始化。運(yùn)行時(shí)異常主要包括空指針、數(shù)組越界等。在程序編碼完成后，

59、由我們的測(cè)試人員進(jìn)行測(cè)試時(shí)（程序功能測(cè)試，黑盒測(cè)試），也發(fā)現(xiàn)了很多問(wèn)題，有的不符合需求分析中的要求，有的是用戶非正常操作引起的。以下是程序測(cè)試中遇到的一些問(wèn)題。4.1消除腳印問(wèn)題本問(wèn)題主要是不符合需求分析中的要求，即找不到路徑時(shí)沒(méi)有消除腳印，還有在找不到出路返回時(shí)也沒(méi)有消除腳印。調(diào)試：在棧頂元素出棧時(shí)，為了區(qū)分該位置已經(jīng)走過(guò)，即mazeMap中相應(yīng)的值不為0，又要繪制出通路的圖像。于是在出棧時(shí)，將該點(diǎn)位置mazeMap的值變?yōu)?，而在mazeMap值為1和3的點(diǎn)都繪制通路圖像，即可解決問(wèn)題。調(diào)試結(jié)果：解決。4.2 定位方框越界 本問(wèn)題主要是由用戶非正常操作引起的，即定位方框能移到迷宮外圍的墻上

60、，不符合設(shè)計(jì)人員的本意。截圖如下。 圖14 定位方框越界問(wèn)題截圖調(diào)試：在actionPerformed方法中，按上下左右代碼前增加坐標(biāo)判斷的語(yǔ)句，防止定位方框越界。調(diào)試結(jié)果：解決。4.3 求解迷宮過(guò)程中，畫面閃爍不定本問(wèn)題是影響程序美觀，即在求解迷宮過(guò)程中，畫面閃爍。調(diào)試：查找資料，運(yùn)用雙緩沖技術(shù)，增加數(shù)行代碼幾個(gè)解決，此代碼為javaGUI設(shè)計(jì)中的常用固定代碼。這也正是MazeGUI類中Image類型的變量offScreen存在的原因。public void update(Graphics g)/雙緩沖防止屏幕閃爍if(offScreen = null)offScreen = this.cr