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


本文链接http://www.jnnr.cn/news/163.html