电脑迷宫鼠
功能实现
1. 迷宫的生成
-
自动生成迷宫
算法介绍:网上有着各种各样的迷宫生成算法,我只是用了一种迷宫的生成算法-->prim算法
该算法并不复杂,请自行到哔哩哔哩上找讲解视频进行学习,在这里展示一下java语言的实现方式
// 迷宫的行数和列数 private void prim(int row, int col){ //成员变量 row = row == 0 ? 59 : row; col = col == 0 ? 59 : col; // 移动的四个方向 int[][] go = new int[][]{ {-2,0}, {0,2}, {2,0}, {0,-2} }; // 存放待选路点 LinkedList<int[]> list = new LinkedList<>(); // 最后生成的迷宫,成员变量 maze[1][1] = 0; for (int[] way : go) { int x = way[0] + 1; int y = way[1] + 1; if(x > 0 && x < row - 1 && y > 0 && y < col - 1){ list.add(new int[]{x,y}); } } while (!list.isEmpty()){ // 随机选择到的路点 A int rand = random.nextInt(list.size()); int[] next = list.get(rand); // A 附近已经变成路点的B List<int[]> ran = new LinkedList<>(); // A 附近没有变成路点的位置 List<int[]> notRan = new LinkedList<>(); for (int[] way : go) { int x = way[0] + next[0]; int y = way[1] + next[1]; // 判断是否为合法位置 if(x > 0 && x < row - 1 && y > 0 && y < col - 1 ){ if(maze[x][y] == 0){ // 是路点 ran.add(new int[]{x,y}); }else { // 不是路点 notRan.add(new int[]{x,y}); } } } // 从B中随机选择一个路点,与A打通 int[] B = ran.get(random.nextInt(ran.size())); // 将A 附近的(随机)路点 之间打通 // A 变成 0 maze[next[0]][next[1]] = 0; // 先将B 变成 0 maze[B[0]][B[1]] = 0; // 将A与B之间的墙打碎 if(next[0] == B[0]){ // 同行 // 中间的数字变成 0 int k = next[1] > B[1] ? next[1] - 1 : next[1] + 1; maze[B[0]][k] = 0; }else { // 同列 // 中间的数字变成 0 int k = next[0] > B[0] ? next[0] - 1 : next[0] + 1; maze[k][B[1]] = 0; } // 将A 删除 并将A附近的非路点添加进来 list.remove(rand); for (int[] ints : notRan) { int i = 0; for (; i < list.size(); i++) { int[] have = list.get(i); if(have[0] == ints[0] && have[1] == ints[1])break; } if(i == list.size()){ list.add(ints); } } } }
-
手动生成迷宫
先自动生成几个,自己改变一些其中的位置即可。
这里介绍如何将文件里的迷宫转换为二维数组
// 形参是文件名 private int[][] createMazeByTxt(File file) { // 默认迷宫的大小是59*59 int[][] lab = new int[59][59]; try { // 文件的读取有多种方式,可自行尝试 BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(new FileInputStream(file))); // 读取一行,1,1,1,1,1,1,1,1,1,1,1,……1,1,1,1(这是在文件中的格式) String line = bufferedReader.readLine(); if (line != null) { for (int i = 0; i < 59; i++) { String[] numbers = line.split(","); for (int j = 0; j < 59; j++) { // 将字符串转换为数字存储在迷宫的二维数组里 lab[i][j] = Integer.parseInt(numbers[j]); } // 继续读下一行 line = bufferedReader.readLine(); } } // 关闭资源 bufferedReader.close(); } catch (IOException e) { // 文件未找到异常 System.out.println("文件未找到……"); } return lab; }
2. 迷宫的寻路
-
方法介绍:深度优先搜索(一条路走到黑,撞了南墙就返回,能行就收集,不行就放弃)
-
代码展示
// 遍历迷宫时的方向 private int[][] ways = new int[][]{ {-1, 0}, {0, 1}, {1, 0}, {0, -1} }; // 寻找到多条合适的路,从头到尾 private void dfs(List<int[]> list, int x, int y, int ex, int ey) { // 走到终点了,进行结果的收集 if (x == ex && y == ey) { // 将尾结点添加到集合里 list.add(new int[]{x, y}); List<int[]> path = new LinkedList<>(list); // paths是成员变量,用来收集所有结果 paths.add(path); // 删除尾结点,回溯 list.remove(list.size() - 1); return; } // 在当前节点的四个方向进行探索 for (int[] ways : go) { int goX = ways[0] + x; int goY = ways[1] + y; // 要前往的节点是否合法 if (goX > 0 && goX < ROW - 1 && goY > 0 && goY < COL - 1 && maze[goX][goY] == 0) { //集合里添加节点 list.add(new int[]{x, y}); // 标记一下,避免下次还会进来,造成死循环 maze[x][y] = 2; // 前往下一个节点 dfs(list, goX, goY, ex, ey); // 回溯 maze[x][y] = 0; list.remove(list.size() - 1); } } }
-
注意:这里其实可以看做实现了迷宫的遍历,(毕竟找到了所有的路),如果是单一路径,可以利用随机数选一条进行展示。遍历有些许的不同。
3. 迷宫的遍历
- 这里迷宫的遍历是按照我的理解来实现的,就是将迷宫寻路的过程可视化,即展示鼠是如何一步一步找到站点的。不难发现,老鼠找到终点的过程全部保存在了成员变量paths里面,只需要将其中的结点展示在界面上的颜色改变,既可以达到想要的效果。但问题也会随之而来,遍历结束后,界面上大约有一半被改变了颜色,非常难看,那么我想到的解决方法是将错误的位置的颜色改回来,即将回溯的过程也展示给读者。
- 代码展示
// 这里涉及到多线程的知识,因为我也是突击学习,其中很多也并不理解,大家凑合着看
private void findSuperDfs() {
Task<List<int[]>> task = new Task<List<int[]>>() {
@Override
protected List<int[]> call() throws Exception {
// 一个私有方法,将界面的地图颜色恢复成开始的样子(黑白)
paint();
List<int[]> list = new LinkedList<>();
// 这里是一个深度优先搜素,与上一个方法类似,只不过该方法在找到一条路径的情况下就结束了
// 找到的路径保存在list里
superDfs(list,1,1,ROW - 2,COL - 2);
int k = 0;
for (int[] ints : list) {
// 因为在遍历时maze的部分值被改为了2
// 将标记的坐标改回原来的值
maze[ints[0]][ints[1]] = 0;
k++;
//将坐标输出到控制台上
System.out.print(Arrays.toString(ints) + " ");
// 换行
if((k + 1) % 10 == 0)
System.out.println();
}
System.out.println("集合的长度为:" +list.size());
// 可视化过程
info.clear();//info是界面的一个组件,用来展示遍历的过程
for (int i = 0; i < list.size(); i++) {
int[] ints = list.get(i);
//info的展示内容进行定期清空
if (info != null && info.getText() != null && info.getText().length()>1000) {
info.clear();
}
if(i > 0){
// 判断第i号位置的坐标是不是已经出现过,是就返回那个坐标,不是就返回-1
int v = isValid(list,i);
if(v != -1){//有重复,
//在界面上输出信息
info.appendText("回退" + "\n");
//将两个重复坐标间的坐标颜色进行改变(倒叙)
for (int j = i - 1; j >= v; j--){
// map集合放着坐标和坐标在list集合里的位置
//相同位置的坐标在map里只有一个
if(map.size() > 0 && map.containsKey(j)){
int[] re = map.remove(j);
//让当前的线程睡一觉,看起来寻路过程比较平滑
Thread.sleep(35);
//该方法将re[0] * COL + re[1]位置上的颜色改为Color.WHITE。
reFresh(re[0] * COL + re[1],Color.WHITE);
}
}
}
}
// map里放入当前的坐标即在list集合中的位置
map.put(i,ints);
int x = ints[0];
int y = ints[1];
//睡一觉
Thread.sleep(35);
//该方法将x * COL + y位置上的颜色改为Color.PURPLE
reFresh(x * COL + y,Color.PURPLE);
info.appendText("到达" + Arrays.toString(ints) + "\n");
}
System.out.println("可视化过程结束了");
return list;
}
};
Thread thread = new Thread(task,"supDfs");
paint();
//开启任务
thread.start();
}
可以看见有许多的重复位置,说明两个重复位置之间的都是错误的位置(进行回溯了),想要将其展示在界面上的颜色改回来(倒叙)
4. 界面展示
-
因为用到了SenceBuilder图形化工具,所以方法都写在了Controller里。
手动创建迷宫
-
自动创建迷宫
-
遍历时