基于JavaFX图形界面演示的迷宫创建与路径寻找

事情的起因是收到了一位网友的请求，他的java课设需要设计实现迷宫相关的程序——如标题概括。

我这边不方便透露相关信息，就只把任务要求写出来。

演示视频指路👉：

• 视频过审后就更新链接

完整代码链接🔎：

• 网盘：https://pan.baidu.com/s/12CFCecCb6iLu8kgBWhaBwg?pwd=abcd   提取码：abcd
• Github：xiao-qi-w/Maze: 基于JavaFX图形界面演示的迷宫创建与路径寻找 (github.com)

开发工具：IDEA 2020.3.1，SceneBuilder

基础要求
（1）概述：用 java 设计和实现一电脑鼠走迷宫的软件程序。本综合实践分算法设计和实现和界面展现两部分。
（2）第一部分：算法设计和实现部分
   迷宫地图生成算法的设计和实现
   自动生成迷宫：根据迷宫生成算法自动生成一定复杂度的迷宫地图。
   手动生成迷宫：根据文件中存储的固定数据生成迷宫地图。
   单路径寻找算法的设计与实现：找出迷宫中一条单一的通路。
   迷宫遍历算法的设计与实现：遍历迷宫中所有的可行路径。
   最短路径计算算法的设计与实现：根据遍历结果，找出迷宫中所有通路中的最短通路。
（3）第二部分：界面展示部分
   生成迷宫地图界面的设计与实现：根据生成的迷宫地图，用可视化的界面展现出来。
   界面布局的设计与实现：根据迷宫程序的总体需求，设计和实现合理的界面布局。
   相关迷宫生成过程和寻路算法在界面上的展现：将迷宫程序中的相关功能，跟界面合理结合，并采用一定的方法展现给用户，如通过动画展示等。
（4）总体任务要求
   具有判断通路和障碍的功能；
   走不通具备返回的能力（路径记忆）；
   能够寻找最短路径；
   程序不仅要实现相关算法，还需要具备基本的界面操作功能。
（5）任务分解
   迷宫的生成：手动生成或自动生成
   寻路：从任意给定点走到另外给定点
   遍历：遍历整个迷宫
   寻优：计算最短路径（计算等高表，按路径行规定走）
   相关界面设计和编程

看到这里相信各位已经对本程序有了初步的认知，而且上述要求中也对整体任务进行了分解，那么我们只需要挨个实现即可。实际上我们只需要做两件事，编写算法和使用图形界面展示算法。

有关图形界面的基础知识，推荐观看 B站UP蔡广 的视频（我基本是按照这个视频的知识点设计的）：JavaFX 桌面软件 PC 软件开发 基础入门_哔哩哔哩_bilibili

我们先来完成第一件事——算法的实现：

  假定观看文章的各位对本文出现的算法和数据结构有一定了解，所以这部分内容我并不对算法本身，如深度优先搜索DFS、广度优先搜索BFS以及所用到的数据结构，譬如栈、队列和链表做过多阐述，想要了解其原理与正确性的话请以加粗字体为关键词自行搜索。

  为了方便算法实现，定义全局变量dirs数组表示右下左上四个方向：int[][] dirs = new int[][] {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

  1. 迷宫的创建

  这里由于我之前做过C语言的迷宫程序，不重复造轮子，上链接：C语言实现一个走迷宫小游戏（深度优先算法）。

  当然我并没有全部照搬，只是采用了深度优先的思想。因为这几种生成算法都只能产生一条可行路径。为了体现遍历和寻优，我直接在迷宫中生成了一条大小合适的环路，并控制生成迷宫的复杂程度，这样一般情况下迷宫会有多条可行路径，示意图如下：

主要代码：

// 修饰迷宫地图
public void initMap() {
    //最外围层设为路径的原因，为了防止挖路时挖出边界，同时为了保护迷宫主体外的一圈墙体被挖穿
    for (int i = 0; i < L; i++) {
        map[i][0] = 1;
        map[0][i] = 1;
        map[i][L - 1] = 1;
        map[L - 1][i] = 1;
    }
    // 创造迷宫, (2, 2)为起点
    CreateMaze(inX, inY + 1);
    // 画迷宫的入口和出口
    for (int i = L - 3; i >= 0; i--) {
        if (map[i][L - 3] == 1) {
            map[i][L - 2] = 1;
            this.outX = i;
            break;
        }
    }
    map[inX][inY] = map[outX][outY] = 1;
    // 制造环路
    for (int i = 10; i < 31; i++) {
        map[i][10] = 1;
        map[10][i] = 1;
        map[i][30] = 1;
        map[30][i] = 1;
    }
    // 创建迷宫时会打乱方向顺序，这里还原方向数组
    dirs = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
}

// 构造迷宫地图
public void CreateMaze(int x, int y) {
    map[x][y] = ROUTE;
    int i, j;
    // 随机打乱方向顺序
    for (i = 0; i < 4; i++) {
        int r = random.nextInt(4);
        int temp = dirs[0][0];
        dirs[0][0] = dirs[r][0];
        dirs[r][0] = temp;
        temp = dirs[0][1];
        dirs[0][1] = dirs[r][1];
        dirs[r][1] = temp;
    }
    //向四个方向开挖
    for (i = 0; i < 4; i++) {
        int dx = x;
        int dy = y;
        //控制挖的距离，由rank来调整大小
        int range = 1 + random.nextInt(rank);
        while (range > 0) {
            //计算出将要访问到的坐标
            dx += dirs[i][0];
            dy += dirs[i][1];
            //排除掉回头路
            if (map[dx][dy] == ROUTE) {
                break;
            }
            //判断是否挖穿路径
            int count = 0, k;
            for (j = dx - 1; j < dx + 2; j++) {
                for (k = dy - 1; k < dy + 2; k++) {
                    //abs(j - dx) + abs(k - dy) == 1 确保只判断九宫格的四个特定位置
                    if (Math.abs(j - dx) + Math.abs(k - dy) == 1 && map[j][k] == ROUTE) {
                        count++;
                    }
                }
            }
            //count大于1表明墙体会被挖穿，停止
            if (count > 1)
                break;
            //确保不会挖穿时，前进
            range -= 1;
            map[dx][dy] = ROUTE;
        }
        //没有挖穿危险，以此为节点递归
        if (range <= 0) {
            CreateMaze(dx, dy);
        }
    }
}

  2. 单路径寻找算法

  为了和最短路径算法有所区分，这里采用深度优先搜索(DFS)算法。核心思想为从迷宫某一点出发，依次向四个方向进行访问，对已经访问过的点进行标记。越界、迷宫墙体和已经访问过的点不会被访问，如此往复递归，直到找到出口或者给定可行坐标结束递归，记录路径，代码实现如下：

单路径寻找算法

// DFS寻找可行路径
public void findWay(boolean[][] visit, int x, int y) {
    for (int k = 0; k < 4; ++k) {
        int nx = x + dirs[k][0];
        int ny = y + dirs[k][1];
        if (nx < 2 || nx > L - 3 || ny < 1 || ny > L - 2 || visit[nx][ny] || map[nx][ny] != ROUTE)
            continue;
        //来到新位置后, 进行标记
        map[nx][ny] = RIGHT;
        visit[nx][ny] = true;
        if (nx == outX && ny == outY) {
            //走到出口则结束搜索, 记录路径并返回
            LinkedList<Route> stack = new LinkedList<>();
            for (int i = 0; i < L; ++i) {
                for (int j = 0; j < L; ++j) {
                    if (map[i][j] > 1)
                        stack.push(new Route(i, j));
                }
            }
            stacks.add(stack);
            return;
        } else {
            //否则进行下一层递归
            findWay(visit, nx, ny);
        }
        // 不正确的路径需要还原
        map[nx][ny] = ROUTE;
    }
}

  3. 遍历迷宫算法

观察上述寻找单路经的算法，对其加以改造。由于visit数组的影响，在到达目标点后，目标点被设置为已访问过，不可能再次到达。所以我们去掉visit数组的限制，回溯所有可能的情况，一旦到达目标点我们就记录下这条路径，这样遍历算法也就完成了。由于受迷宫地图大小和环路的影响，实际要找到迷宫的所有可行路径是很耗时的，所以这部分演示时可以采取手动输入地图的方式，使迷宫的可行路径尽可能的少一些。下面给出具体实现：

遍历迷宫算法

// DFS遍历全部可行路径
public void findAllWay(int x, int y) {
    for (int k = 0; k < 4; ++k) {
        int nx = x + dirs[k][0];
        int ny = y + dirs[k][1];
        if (nx < 2 || nx > L - 3 || ny < 1 || ny > L - 2 || map[nx][ny] != ROUTE)
            continue;
        //来到新位置后,设置当前值为可行路径
        map[nx][ny] = RIGHT;
        if (nx == outX && ny == outY) {
            //走到出口则结束搜索，记录路径并返回
            LinkedList<Route> stack = new LinkedList<>();
            for (int i = 0; i < L; ++i) {
                for (int j = 0; j < L; ++j) {
                    if (map[i][j] > 1)
                        stack.push(new Route(i, j));
                }
            }
            stacks.add(stack);
        } else {
            //否则进行下一层递归
            findAllWay(nx, ny);
        }
        map[nx][ny] = ROUTE;
    }
}

  4. 最短路径算法

对于无向图两点间的最短路径问题，一般都是采用广度优先搜索(BFS)算法，正确性请自行了解。其思想为从起点出发，采用队列记录当前点能够访问到的点，将其标记为已访问，并不断重复这个过程至找到目标点，队列先进先出的特性保证了算法的正确性。为了记录最短路径，如果仍然采用标记的思想，那么由于算法的特性，最终记录的路径会多出来一些小分支，所以我采用自定义Route类记录坐标及其之间的联系。这里采用了链表的思想，即每个点指向他的上一步所在的点。具体实现如下：

最短路径算法

// BFS寻找最优路径
public void findBestWay() {
    // 辅助队列
    LinkedList<Route> queue = new LinkedList<>();
    // 放入起点
    queue.offer(new Route(inX, inY));
    // 访问标记，用于判断当前坐标是否曾走到过
    boolean[][] visit = new boolean[L][L];
    visit[inX][inY] = true;
    // 队列不为空 且 未找到终点
    while (!queue.isEmpty() && !visit[outX][outY]) {
        Route route = queue.poll();
        int cx = route.getX(), cy = route.getY();
        // 继续寻找
        for (int i = 0; i < 4; i++) {
            // 计算将要到达的坐标
            int nx = cx + dirs[i][0];
            int ny = cy + dirs[i][1];
            // 判断可行性
            if (nx > 1 && nx < L - 2 && ny > 0 && ny < L - 1 && map[nx][ny] == ROUTE && !visit[nx][ny]) {
                visit[nx][ny] = true;
                Route next = new Route(nx, ny, route);
                queue.offer(next);
                // 找到终点
                if (nx == outX && ny == outY) {
                    LinkedList<Route> stack = new LinkedList<>();
                    for (Route p = next; p != null; p = p.getPre()) {
                        stack.push(p);
                    }
                    stacks.add(stack);
                    break;
                }
            }
        }
    }
}

接下来是第二件事——图形界面的实现：

算法已经实现的差不多了，现在进行界面的绘制。这里仍然假定各位通过上面提到的视频，已经对JavaFX有一定的了解。

回想我们要实现的功能，手动或自动生成迷宫地图，自动的上面算法已经实现，手动的就需要绘制界面供我们输入。顺着这个思路，我们可以先设计一下交互逻辑，进而确定需要哪些界面，每个界面又对应哪些功能，我的设计方案如下：

以初始界面为例，我们可以通过SceneBuilder软件设计界面，然后保存为fxml文件，如下：

<?xml version="1.0" encoding="UTF-8"?>

<!-- 开始界面 -->
<?import javafx.scene.control.Button?>
<?import javafx.scene.control.Label?>
<?import javafx.scene.image.Image?>
<?import javafx.scene.image.ImageView?>
<?import javafx.scene.layout.AnchorPane?>
<?import javafx.scene.text.Font?>
<AnchorPane fx:id="rootStage"
            xmlns:fx="http://javafx.com/fxml/1"
            fx:controller="controllers.StartController"
            prefHeight="600.0" prefWidth="600.0">
    <children>
        <Label fx:id="title" text='迷宫鼠演示程序' layoutX='150' layoutY='10' prefWidth="300" prefHeight="50"
               alignment="CENTER">
            <font>
                <Font name="BOLD" size="40"/>
            </font>
        </Label>
        <ImageView fx:id="icon" pickOnBounds="true" preserveRatio="true" layoutX="210" layoutY="100">
            <image>
                <Image url="@../images/maze.png"/>
            </image>
        </ImageView>
        <Button fx:id='btn_manual' text='手动生成' layoutX='200' layoutY='350' onAction="#onManualClick" prefWidth="200"
                prefHeight="50"/>
        <Button fx:id='btn_auto' text='自动生成' layoutX='200' layoutY='450' onAction="#onAutoClick" prefWidth="200"
                prefHeight="50"/>
    </children>
</AnchorPane>

编写对应的控制器：

StartController.java

package controllers;

import javafx.fxml.FXML;
import javafx.fxml.FXMLLoader;
import javafx.scene.Parent;
import javafx.scene.Scene;
import javafx.scene.image.Image;
import javafx.scene.layout.AnchorPane;
import javafx.stage.Modality;
import javafx.stage.Stage;

import java.io.IOException;

/**
 * @Author 郭小柒w
 * @Date 2022/6/24 17:26
 * @Description 开始界面逻辑控制
 **/
public class StartController {
    @FXML
    private AnchorPane rootStage; // 父窗口面板

    /**
     * 手动生成按钮点击事件
     */
    public void onManualClick() {
        try {
            // 加载手动输入界面布局文件
            FXMLLoader loader = new FXMLLoader();
            loader.setLocation(getClass().getResource("/fxmls/input.fxml"));
            Parent root = loader.load();
            Scene scene = new Scene(root);
            // 设置stage
            Stage stage = new Stage();
            stage.setResizable(false);
            stage.getIcons().add(new Image("/images/maze.png"));
            stage.setScene(scene);
            // 设置父窗体
            stage.initOwner(rootStage.getScene().getWindow());
            // 设置除当前窗体外其他窗体均不可编辑
            stage.initModality(Modality.WINDOW_MODAL);
            stage.show();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    /**
     * 自动生成按钮点击事件
     */
    public void onAutoClick() {
        try {
            // 加载迷宫主界面布局文件
            FXMLLoader loader = new FXMLLoader();
            loader.setLocation(getClass().getResource("/fxmls/menu.fxml"));
            Parent root = loader.load();
            Scene scene = new Scene(root);
            // 获取Controller
            MenuController controller = loader.getController();
            // 进行迷宫初始化操作
            controller.initialize(new int[42][42], MenuController.AUTO, null);
            // 设置Stage
            Stage stage = new Stage();
            stage.setResizable(false);
            stage.getIcons().add(new Image("/images/maze.png"));
            stage.setScene(scene);
            // 设置父窗体
            stage.initOwner(rootStage.getScene().getWindow());
            // 设置除当前窗体外其他窗体均不可编辑
            stage.initModality(Modality.WINDOW_MODAL);
            stage.show();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public void initialize() {
        // TODO: 如有需要初始化的内容，请在此方法内完成
    }
}

对于手动输入和迷宫展示功能，可以采用合适的JavaFX控件，不再贴出具体代码，控制器和界面写法与上述一致。完整代码和实际演示视频见文章开头的链接。

---

—————————————————我———是———分———割———线————————————————

时间过得可真快呀！毕业后尝试工作了一段时间，这期间也有很多人来问那个C语言迷宫的问题。从那篇文章发布到现在已经两年整了，没想到最近还有机会把它翻新成图形界面表现出来。从我返校考试到放弃考研选择找工作，也已经是一年多以前。之前总是会觉得之后的人生会怎样怎样，设想过无数可能，觉得凭自己对这个专业的热爱总能在岗位上发光发热,，觉得工作是自己感兴趣的东西肯定不会苦闷，却未认识到现实跟想象的差距如此之大。找了份自以为绝对满意的工作，谁料想每天都重复着枯燥的单一工作内容。终于在深思熟虑后还是对之前的工作说拜拜啦，虽然跟老大说自己碰壁了还会回来，但心里不确定我是否真的愿意回去。再找到更心仪的工作之前，要更加努力啊。不放弃对未来的美好幻想，也不虚度了眼下的时光。勇敢的少年啊，快去创造奇迹吧！