实验三 迷宫生成和自动寻路

一、 实验要求
1、迷宫随机生成
2、玩家走迷宫，留下足迹
3、系统用A*算法寻路，输出路径 

二、前期准备
解决迷宫问题要用到两个算法，深度优先遍历（DFS）生成迷宫，A*算法寻路。那么首先要对这两种算法有清晰的了解。 

1.深度优先遍历（DFS）
 基于深度优先遍历的随机迷宫生成，我自己的理解简而言之可以分为以下几步：
a. 建立一张地图，用二维数组表示，地图上全是障碍物。然后再创建一个用来表示每个格子是否被访问过的二维数组。再创建一个用来表示路径的栈结构。
b.随机选择地图上的一点，为了方便我初始点直接取的是左上角即坐标表示为(0,0)的格子。终点的话因为不涉及到交互就暂时没有。
c.查找当前格子的邻接格（注意，这里的邻接格子都是还未被访问的）。随机选择一个邻接格子为下一 格，当前格移动到下一格，标记当前格为已访问，将当前格压入路径栈中。一直重复第三步操作。
d.在第三步操作中，如果当前格子不存在可访问的邻接格，则将栈顶的元素弹出，即退回上一步操作，如果栈为空，则结束程序，打印结果。

2.A*算法
公式表示为: f(n)=g(n) h(n),
其中， f(n) 是从初始状态经由状态n到目标状态的代价估计，
g(n) 是在状态空间中从初始状态到状态n的实际代价，
h(n) 是从状态n到目标状态的最佳路径的估计代价。
(对于路径搜索问题，状态就是图中的节点，代价就是距离)
 

1.  
   import java.util.ArrayList;
2.  
   import java.util.List;
3.  
    
4.  
   class AStart {
5.  
   public static int[][] NODES;//定义一个迷宫单元数组
6.  
   public int STEP = 10;//设每一步的权值为10
7.  
   private ArrayList<Node> openList = new ArrayList<Node>();//维护一个开放列表
8.  
   private ArrayList<Node> closeList = new ArrayList<Node>();//维护一个关闭列表
9.  
    
10.  
    public AStart() {
11.  
    NODES=Maze.LabId;//初始化迷宫单元为新生成的对应地图，把Maze2类里面生成的地图传给NODES，再在此地图基础上用A*算法寻路径
12.  
    Node startNode = new Node(1, 1);//起点
13.  
    Node endNode = new Node(19, 19);//终点
14.  
    Node parent = findPath(startNode, endNode); //父节点
15.  
    ArrayList<Node> arrayList = new ArrayList<Node>();
16.  
    while (parent != null) {
17.  
    arrayList.add(new Node(parent.x, parent.y));
18.  
    parent = parent.parent;
19.  
    }
20.  
     
21.  
    //打印有路径的地图，在控制台输出查看
22.  
    System.out.println("\n" "打印有路径的地图:");
23.  
    for (int i = 0; i < NODES.length; i ) {
24.  
    for (int j = 0; j < NODES.length; j ) {
25.  
    if (exists(arrayList, i, j)) {
26.  
    NODES[i][j]=2;//标记关闭列表里的方格为2，为了方便后面在界面画系统寻路路径
27.  
    }
28.  
    System.out.print(NODES[i][j] " ");
29.  
    }
30.  
    System.out.println();
31.  
    }
32.  
    }
33.  
     
34.  
    //寻找开放列表里F值最小的节点的方法
35.  
    public Node findMinFNodeInOpneList() {
36.  
    Node tempNode = openList.get(0);
37.  
    for (Node node : openList) {
38.  
    if (node.F < tempNode.F) {
39.  
    tempNode = node;
40.  
    }
41.  
    }
42.  
    return tempNode;
43.  
    }
44.  
     
45.  
    //遍历当前节点上下左右四个邻居的方法，
46.  
    public ArrayList<Node> findNeighborNodes(Node currentNode) {
47.  
    ArrayList<Node> arrayList = new ArrayList<Node>();
48.  
    // 只考虑上下左右，不考虑斜对角
49.  
    int topX = currentNode.x;
50.  
    int topY = currentNode.y - 1;
51.  
    if (canReach(topX, topY) && !exists(closeList, topX, topY)) {
52.  
    arrayList.add(new Node(topX, topY));
53.  
    }
54.  
    int bottomX = currentNode.x;
55.  
    int bottomY = currentNode.y 1;
56.  
    if (canReach(bottomX, bottomY) && !exists(closeList, bottomX, bottomY)) {
57.  
    arrayList.add(new Node(bottomX, bottomY));
58.  
    }
59.  
    int leftX = currentNode.x - 1;
60.  
    int leftY = currentNode.y;
61.  
    if (canReach(leftX, leftY) && !exists(closeList, leftX, leftY)) {
62.  
    arrayList.add(new Node(leftX, leftY));
63.  
    }
64.  
    int rightX = currentNode.x 1;
65.  
    int rightY = currentNode.y;
66.  
    if (canReach(rightX, rightY) && !exists(closeList, rightX, rightY)) {
67.  
    arrayList.add(new Node(rightX, rightY));
68.  
    }
69.  
    return arrayList;
70.  
    }
71.  
     
72.  
     
73.  
    //判断此处坐标是否可达，若超界或者是墙则不可达
74.  
    public boolean canReach(int x, int y) {
75.  
    if (x >=0 && x < NODES.length && y >=0 && y < NODES.length && NODES[x][y]==1) {
76.  
    return true;
77.  
    }
78.  
    return false;
79.  
    }
80.  
     
81.  
     
82.  
    //A*寻路过程
83.  
    public Node findPath(Node startNode, Node endNode) {
84.  
    openList.add(startNode);// 把起点加入 open list
85.  
    while (openList.size() > 0) {
86.  
    Node currentNode = findMinFNodeInOpneList();// 遍历 open list ，查找 F值最小的节点，把它作为当前要处理的节点
87.  
    openList.remove(currentNode);// 从open list中移除
88.  
    closeList.add(currentNode);// 把这个节点移到 close list
89.  
    ArrayList<Node> neighborNodes = findNeighborNodes(currentNode);
90.  
    for (Node node : neighborNodes) {//遍历四个邻居
91.  
    if (exists(openList, node)) {
92.  
    foundPoint(currentNode, node);
93.  
    } else {
94.  
    notFoundPoint(currentNode, endNode, node);
95.  
    }
96.  
    }
97.  
    if (find(openList, endNode) != null) {
98.  
    return find(openList, endNode);//找到终点了并返回
99.  
    }
100.  
     }
101.  
     return find(openList, endNode);
102.  
     }
103.  
      
104.  
     //在列表里可以找到节点后的情况
105.  
     private void foundPoint(Node tempStart, Node node) {
106.  
     int G = calcG(tempStart, node);
107.  
     if (G < node.G) {
108.  
     node.parent = tempStart;
109.  
     node.G = G;
110.  
     node.calcF();
111.  
     }
112.  
     }
113.  
      
114.  
     //在节点里找不到节点的情况
115.  
     private void notFoundPoint(Node tempStart, Node end, Node node) {
116.  
     node.parent = tempStart;
117.  
     node.G = calcG(tempStart, node);
118.  
     node.H = calcH(end, node);
119.  
     node.calcF();
120.  
     openList.add(node);
121.  
     }
122.  
      
123.  
      
124.  
     //计算G值的方法
125.  
     private int calcG(Node start, Node node) {
126.  
     int G = STEP;
127.  
     int parentG = node.parent != null ? node.parent.G : 0;
128.  
     return G parentG;
129.  
     }
130.  
      
131.  
     //计算H值的方法
132.  
     private int calcH(Node end, Node node) {
133.  
     int step = Math.abs(node.x - end.x) Math.abs(node.y - end.y);
134.  
     return step * STEP;
135.  
     }
136.  
      
137.  
     //找到终点的方法
138.  
     public static Node find(List<Node> nodes, Node point) {
139.  
     for (Node n : nodes)
140.  
     if ((n.x == point.x) && (n.y == point.y)) {
141.  
     return n;
142.  
     }
143.  
     return null;
144.  
     }
145.  
      
146.  
     //下面两个是exist方法的重载，判断不同参数情况时节点是否在列表里
147.  
     public static boolean exists(List<Node> nodes, Node node) {
148.  
     for (Node n : nodes) {
149.  
     if ((n.x == node.x) && (n.y == node.y)) {
150.  
     return true;
151.  
     }
152.  
     }
153.  
     return false;
154.  
     }
155.  
      
156.  
     public static boolean exists(List<Node> nodes, int x, int y) {
157.  
     for (Node n : nodes) {
158.  
     if ((n.x == x) && (n.y == y)) {
159.  
     return true;
160.  
     }
161.  
     }
162.  
     return false;
163.  
     }
164.  
      
165.  
     //节点类，定义了每一个节点的属性
166.  
     public static class Node {
167.  
     public Node(int x, int y) {
168.  
     this.x = x;
169.  
     this.y = y;
170.  
     }
171.  
     public int x;
172.  
     public int y;
173.  
     public int F;
174.  
     public int G;
175.  
     public int H;
176.  
      
177.  
     public void calcF() {
178.  
     this.F = this.G this.H;
179.  
     }
180.  
     public Node parent;
181.  
     }
182.  
     }

1.  
   import java.util.Random;
2.  
    
3.  
   public class Maze {
4.  
   public static int row = 10;// 初始地图有路的迷宫单元行数
5.  
   public static int column = 10;// 初始地图有路的迷宫单元列数
6.  
   public static int r = 2 * row 1;// 迷宫单元行数，保证是奇数
7.  
   public static int c = 2 * column 1;// 迷宫单元列数，保证是奇数
8.  
   public static int[][] LabId;// 存放迷宫的数组,迷宫单元数组
9.  
   Random rand = new Random();
10.  
     
11.  
    public Maze() {
12.  
    LabId = new int[r][c];
13.  
    System.out.println("初始化地图:");
14.  
    for (int i = 0; i < r; i ) {
15.  
    for (int j = 0; j < c; j ) {
16.  
    LabId[i][j] = 0;// 将所有格子都设为墙, 0 为墙 1为路
17.  
    if (i % 2 == 1 && j % 2 == 1)// 将奇数行奇数列设为路，1为路，0为墙
18.  
    LabId[i][j] = 1;
19.  
    System.out.print(LabId[i][j] " ");// 打印初始化地图，在控制台输出查看
20.  
    }
21.  
    System.out.println();
22.  
    }
23.  
     
24.  
    // 调用深度优先搜索算法
25.  
    accLabDFS();
26.  
    System.out.println("\n" "深度优先算法生成的迷宫:");
27.  
    for (int i = 0; i < r; i ) {
28.  
    for (int j = 0; j < c; j ) {
29.  
    System.out.print(LabId[i][j] " ");// 打印生成的深度优先算法生成的迷宫，在控制台输出查看
30.  
    }
31.  
    System.out.println();
32.  
    }
33.  
    }
34.  
     
35.  
    // 实现深度优先算法
36.  
    public void accLabDFS() {
37.  
    int[] lab;// 访问队列
38.  
    int count = row * column;// 所有的迷宫单元数，不包括墙
39.  
    lab = new int[count];
40.  
    for (int i = 0; i < count; i )
41.  
    lab[i] = 0;// 设置所有单元都为未访问过的，0表示未访问过，1表示已访问过
42.  
    for (int v = 0; v < count; v ) {// 从第0个点开始遍历
43.  
    if (lab[v] != 1) {// 如果该单元还未被访问，则递归调用深度优先算法遍历
44.  
    DFS(lab, v);
45.  
    }
46.  
    }
47.  
    }
48.  
     
49.  
     
50.  
    // 使用DFS算法,借助递归思想访问某一顶点v,找v点附近且未被访问的点w,在找w附近未被访问的点(循环...),直到没有继续能找下去的点,
51.  
    // 依次退回最近被访问的点,如果还有该顶点的其他邻居没有被访问,就从邻居点开始继续搜索,把相邻的部分格子打通
52.  
    public void DFS(int[] LabG, int v) {
53.  
    LabG[v] = 1;// 访问顶点
54.  
    int[] neighbor = { v row, v - row, v - 1, v 1 };// 该点的四个邻居 上下左右
55.  
    int[] offR = { 0, 0, -1, 1 }, offC = { 1, -1, 0, 0 };// Row上个方向的偏移 Column上各方向的偏移，上下左右
56.  
    int[] tag = { -1, -1, -1, -1 };// 记录打通位置
57.  
    int n = 0;// 打通的次数
58.  
    while (n < 4) {// 上下左右四个方向都遍历，
59.  
    int i = rand.nextInt(4);// 随机打通一个方向
60.  
    if (tag[i] == 1)
61.  
    continue;// 进入下一轮循环
62.  
    tag[i] = 1;// 打通墙，设为1
63.  
    n ;
64.  
    int w = neighbor[i];// 定义一个该方向上的邻居
65.  
    if (w > LabG.length - 1 || w < 0)
66.  
    continue; // w不存在,即该方向上没有邻居
67.  
     
68.  
    // 取出现在的v点的位置
69.  
    int x = v % row;
70.  
    int y = v / row;
71.  
     
72.  
    // 遍历到四个边界时再往边界方向就没有邻居了，进入下一轮循环
73.  
    if (i == 0 && y == column - 1)
74.  
    continue;// 上方向
75.  
    if (i == 1 && y == 0)
76.  
    continue;// 下方向
77.  
    if (i == 2 && x == 0)
78.  
    continue;// 左方向
79.  
    if (i == 3 && x == row - 1)
80.  
    continue;// 右方向
81.  
     
82.  
    // 如果该点有未访问的邻居，则把该点与其邻居间的墙打通，即相邻的格子中间的位置放1
83.  
    if (LabG[w] == 0) {
84.  
    LabId[2 * x 1 offR[i]][2 * y 1 offC[i]] = 1;
85.  
    DFS(LabG, w);// 递归
86.  
    }
87.  
    }
88.  
    }
89.  
    }

1.  
   import java.awt.Color;
2.  
   import java.awt.Font;
3.  
   import java.awt.Graphics;
4.  
   import java.awt.event.KeyEvent;
5.  
   import java.awt.event.KeyListener;
6.  
   import java.awt.event.MouseEvent;
7.  
   import java.awt.event.MouseListener;
8.  
   import java.awt.image.BufferedImage;
9.  
   import java.io.File;
10.  
    import java.io.IOException;
11.  
    import javax.imageio.ImageIO;
12.  
    import javax.swing.JButton;
13.  
    import javax.swing.JPanel;
14.  
     
15.  
    public class Panel extends JPanel implements MouseListener, KeyListener{
16.  
     
17.  
    Maze M = new Maze();//定义一个Maze类对象，生成地图
18.  
    AStart A = new AStart();//定义一个AStart类，画出迷宫路径
19.  
     
20.  
    private JPanel jp = new JPanel();
21.  
    private JButton answer = new JButton("显示路径");
22.  
    private JButton hide = new JButton("隐藏路径");
23.  
    private JButton reset = new JButton("地图更新");
24.  
    private JButton exit = new JButton("退出游戏");
25.  
    private JButton start = new JButton("开始游戏");
26.  
    BufferedImage wall = null;
27.  
    BufferedImage bj = null;
28.  
    BufferedImage victory = null;
29.  
    BufferedImage my = null;
30.  
     
31.  
    int myx = 1;// 定义角色横坐标并初始化
32.  
    int myy = 1;// 定义角色纵坐标
33.  
    int endx;// 定义终点横纵坐标
34.  
    int endy;
35.  
    boolean isStarted = false;
36.  
    boolean isVictory = false;
37.  
    boolean ans = false;// 用于显示路径
38.  
     
39.  
    public Panel() throws IOException {
40.  
    this.setName("小熊猫走迷宫");// 设置标题
41.  
    this.setLayout(null);
42.  
    answer.setBounds(470, 130, 90, 30);
43.  
    hide.setBounds(470, 210, 90, 30);
44.  
    reset.setBounds(470, 290, 90, 30);
45.  
    exit.setBounds(470, 370, 90, 30);
46.  
    start.setBounds(470, 450, 90, 30);
47.  
    answer.addMouseListener(this);
48.  
    hide.addMouseListener(this);
49.  
    reset.addMouseListener(this);
50.  
    exit.addMouseListener(this);
51.  
    start.addMouseListener(this);
52.  
    start.addKeyListener(this);
53.  
    this.add(jp);
54.  
    this.add(start);
55.  
    this.add(answer);
56.  
    this.add(hide);
57.  
    this.add(reset);
58.  
    this.add(exit);
59.  
    wall = ImageIO.read(new File("images/Wall.png"));// 放墙的图片
60.  
    bj = ImageIO.read(new File("images/bj.png"));// 放窗口背景图片
61.  
    my = ImageIO.read(new File("images/my.png"));// 放小熊猫的图片
62.  
    victory=ImageIO.read(new File("images/victory.jpg"));
63.  
    try {
64.  
    victory=ImageIO.read(new File("images/victory.jpg"));
65.  
    } catch (IOException e) {
66.  
    e.printStackTrace();
67.  
    }
68.  
    }
69.  
     
70.  
    // 画组件
71.  
    public void paintComponent(Graphics g) {
72.  
    super.paintComponent(g);
73.  
    g.fillRect(20, 80, 420, 420);
74.  
    g.drawImage(bj, 0, 0, this);
75.  
    g.setColor(Color.green);
76.  
    g.setFont(new Font("宋体", Font.CENTER_BASELINE, 40));
77.  
    g.drawString("小狗走迷宫", 120, 50);
78.  
     
79.  
    // 画迷宫
80.  
    for (int i = 0; i < M.LabId.length; i ) {
81.  
    for (int j = 0; j < M.LabId[0].length; j ) {
82.  
    if (M.LabId[i][j] == 0) {
83.  
    g.drawImage(wall, 20 i * 20, 80 j * 20, this);
84.  
    }
85.  
    }
86.  
    }
87.  
     
88.  
    // 画A*路径
89.  
    if (ans) {
90.  
    g.setColor(Color.green);
91.  
    for (int i = 0; i < A.NODES.length; i ) {
92.  
    for (int j = 0; j < A.NODES[0].length; j ) {
93.  
    if (A.NODES[i][j] == 2) {
94.  
    g.fillOval(20 20 * i, 80 20 * j, 18, 18);
95.  
    }
96.  
    }
97.  
    }
98.  
    }
99.  
     
100.  
     g.setColor(Color.white);
101.  
     g.fillRect(40, 100, 20, 20);// 画起点
102.  
     g.fillRect(400, 460, 20, 20);// 画终点
103.  
     g.drawImage(my, 20 20 * myx, 80 20 * myy, this);// 画角色
104.  
      
105.  
     // 判断是否到达终点
106.  
     if (this.myx ==19 && this.myy ==19) {
107.  
     isVictory = true;
108.  
     }
109.  
      
110.  
     // 画游戏胜利界面
111.  
     if (isVictory) {
112.  
     g.drawImage(victory, 60,180, this);// 画角色
113.  
     }
114.  
     }
115.  
      
116.  
     // 鼠标监听
117.  
     @Override
118.  
     public void mouseClicked(MouseEvent e) {
119.  
     if (e.getSource().equals(answer)) {
120.  
     ans = true;
121.  
     isVictory=false;
122.  
     }
123.  
     if (e.getSource().equals(hide)) {
124.  
     ans = false;
125.  
     isVictory=false;
126.  
     }
127.  
     if (e.getSource().equals(reset)) {
128.  
     ans = false;
129.  
     isVictory=false;
130.  
     myx = 1;
131.  
     myy = 1;
132.  
     try {
133.  
     new Panel();
134.  
     } catch (IOException ex) {
135.  
     ex.printStackTrace();
136.  
     }
137.  
     }
138.  
     if (e.getSource().equals(exit)) {
139.  
     System.exit(0);
140.  
     }
141.  
     if (e.getSource().equals(start)) {
142.  
     ans = false;
143.  
     isVictory=false;
144.  
     myx = 1;// 开始游戏，角色从起点开始出发
145.  
     myy = 1;
146.  
     }
147.  
     repaint();
148.  
     }
149.  
      
150.  
     // 键盘监听
151.  
     @Override
152.  
     public void keyTyped(KeyEvent e) {
153.  
     }
154.  
     @Override
155.  
     public void keyPressed(KeyEvent e) {
156.  
     int k = e.getKeyCode();
157.  
     if (k == KeyEvent.VK_SPACE) {
158.  
     System.out.print("按下空格");
159.  
     }
160.  
     if (k == KeyEvent.VK_LEFT && A.NODES[myx - 1][myy] != 0 && myx - 1 >= 1) {
161.  
     myx--;
162.  
     }
163.  
     if (k == KeyEvent.VK_RIGHT && A.NODES[myx 1][myy] != 0 && myx 1 <= 21) {
164.  
     myx ;
165.  
     }
166.  
     if (k == KeyEvent.VK_UP && A.NODES[myx][myy - 1] != 0 && myy - 1 >= 1) {
167.  
     myy--;
168.  
     }
169.  
     if (k == KeyEvent.VK_DOWN && A.NODES[myx][myy 1] != 0 && myy 1 <= 21) {
170.  
     myy ;
171.  
     }
172.  
     repaint();
173.  
     }
174.  
     @Override
175.  
     public void keyReleased(KeyEvent e) {
176.  
     }
177.  
     @Override
178.  
     public void mousePressed(MouseEvent e) {
179.  
     }
180.  
     @Override
181.  
     public void mouseReleased(MouseEvent e) {
182.  
     }
183.  
     @Override
184.  
     public void mouseEntered(MouseEvent e) {
185.  
     }
186.  
     @Override
187.  
     public void mouseExited(MouseEvent e) {
188.  
     }
189.  
     }

1.  
   import java.awt.*;
2.  
   import java.io.IOException;
3.  
   import javax.swing.JFrame;
4.  
   public class Test {
5.  
   public static void main(String[] args) throws IOException {
6.  
   JFrame frame = new JFrame();//新建窗口
7.  
   int width = Toolkit.getDefaultToolkit().getScreenSize().width;// 取得屏幕宽度
8.  
   int height = Toolkit.getDefaultToolkit().getScreenSize().height;// 取得屏幕高度
9.  
   frame.setSize(600, 600);// 设置窗体大小
10.  
    frame.setLocation((width - 600) / 2, (height - 600) / 2);// 设置窗体出现大小
11.  
    frame.setResizable(false);// 设置窗体大小不可变
12.  
    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);// 设置窗体关闭方式
13.  
    frame.add(new Panel());
14.  
    frame.setFocusable(true);//为屏幕添加焦点
15.  
    frame.setVisible(true);// 设置窗体可视
16.  
    frame.requestFocus();
17.  
    }
18.  
    }

这篇好文章是转载于：学新通技术网