实验内容：
- 迷宫游戏是非常经典的游戏，在该题中要求随机生成一个迷宫，并求解迷宫。
2. 要求查找并理解迷宫生成的算法，并尝试用两种不同的算法来生成随机的迷宫。
3.要求迷宫游戏支持玩家走迷宫，和系统走迷宫路径两种模式。玩家走迷宫，通过键盘方向键控制，并在行走路径上留下痕迹；系统提示迷宫路径要求基于A*算法实现，输出玩家当前位置到迷宫出口的最优路径。设计交互友好的游戏图形界面。
一、思路选择
迷宫由一个一个格子组成，要求从入口到出口只有一条路径，这种结构和树相契合的，从根节点到每一个子节点都只有一条路径。假设入口是根节点，出口是树中的某个子节点，那么，从根节点到该子节点的路径便是出口路径。
所以如果把树全部覆盖所有的格子，也就把树变成了迷宫，另外还要求树的父节点和子节点必须是界面上相邻的格子，在界面显示时，父节点和子节点之间共用的边不画，其他的边都画出来，就能画出一个迷宫。
二、树的表示
假设像写二叉树一样实现这棵树，那么每个树节点里就要存储一个坐标（X,Y）表示一个格子，另外还要存储四个指针。指针中有的为空，有的不为空，不为空的指针指向子节点，子节点保存邻居格子的坐标。这样做最大的问题是无法判定是否所有的格子都在树中。也许还要用一个二维数组作标志数组。
假如用二维数组表示迷宫的格子。每个数组元素存储一个指向父节点的引用，这样也可以形成一个虚拟的树。于是就用一个N*N的二维数组，表示N*N个格子，每个数组元素(Lattice)中有一个指向父节点的引用(father)。另外，为了能方便的获取格子的坐标，还要保存坐标信息。
三、树的构造
首先选定一个格子作为根节点。为了让迷宫的形状够随机，选择随机生成一个坐标作为根节点。其实，选择确定的一个坐标也可以。
然后，又使用了一种随机扫描的方法，每次扫描在当前树中找一个节点，看它的邻居格子是否在树中，如果还没在树中，就将该邻居格子加入树中，如果已在树中，就看下一个邻居格子，如果该节点所有邻居格子都在树中了，就找下一个节点，继续同样的操作。另外为了让迷宫生成的随机，扫描的起始位置是随机的就可以了。
四、自动寻路
随机选择一个格子作为根节点，从它开始随机地深度搜索前进，开出一条路来，直到无路可走了，退回一步，换另一条路，再走到无路可走，回退一步，换另一条……如此循环往复，直到完全无路可走
// 构建随机树，创建迷宫
private void createMaze() {
// 随机选一个格子作为树的根
Random random = new Random();
int rx = Math.abs(random.nextInt()) % NUM;
int ry = Math.abs(random.nextInt()) % NUM;
// 深度优先遍历
Stack s = new Stack();
Lattice p = maze[rx][ry];
Lattice neis[] = null;
s.push(p);
while (!s.isEmpty()) {
p = s.pop();
p.setFlag(Lattice.INTREE);
neis = getNeis(p);
int ran = Math.abs(random.nextInt()) % 4;
for (int a = 0; a <= 3; a++) {
ran++;
ran %= 4;
assert neis != null;
if (neis[ran] == null || neis[ran].getFlag() == Lattice.INTREE)
continue;
s.push(neis[ran]);
neis[ran].setFather(p);
}
}
}
五、迷宫制作
主要是用到g.drawLine()方法，制作迷宫大小，以及迷宫的墙和物体猪的插入，方法不局限于这一个方法，还有很多也可以实现
// 画迷宫
protected void paintComponent(Graphics g) {
super.paintComponent(g);
// 画NUM*NUM条黑线
for (int i = 0; i <= NUM; i++) {
g.drawLine(padding + i * width, padding, padding + i * width, padding + NUM * width);
}
for (int j = 0; j <= NUM; j++) {
g.drawLine(padding, padding + j * width, padding + NUM * width, padding + j * width);
}
// 使用背景色，在有路径的格子之间画边，把墙抹掉
g.setColor(this.getBackground());
for (int i = NUM - 1; i >= 0; i--) {
for (int j = NUM - 1; j >= 0; j--) {
Lattice f = maze[i][j].getFather();
if (f != null) {
int fx = f.getX(), fy = f.getY();
clearFence(i, j, fx, fy, g);
}
}
}
// 画左上角的入口
g.drawLine(padding, padding + 1, padding, padding + width - 1);
int last = padding + NUM * width;
// 画右下角出口
g.drawLine(last, last - 1, last, last - width + 1);
// 画猪
picture.pig2.paintIcon(this, g, getCenterX(pigY) - width / 3, getCenterY(pigX) - width / 3);
if (drawPath)
drawPath(g);
}
六、结果展示
