# 迷宫地图最短路径规划 **Repository Path**: 253179517/labyrinth ## Basic Information - **Project Name**: 迷宫地图最短路径规划 - **Description**: 迷宫地图最短路径规划 - **Primary Language**: Unknown - **License**: MulanPSL-2.0 - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2024-10-05 - **Last Updated**: 2024-10-05 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # 基于BFS的迷宫地图最短路径规划 ## 1. 课题要求 关键词：路径规划、方向、算法 ### 1.1. 描述 为迷宫地图提供最短路径，每张图片都包含了起点（红色圆点）、终点（绿色圆点）和若干障碍物（深灰色区域）。路径从起点出发、到达终点，不可经过障碍物。 ### 1.2. 地图说明 + 白色区域：代表你可以自由通行的空地。 + 深灰色区域：代表障碍物，你无法穿越这些区域。 + 红色圆点：标记了你的起始位置。 + 绿色圆点：标记了你的目标终点位置。 地图样张： ![地图样张](doc/imgs/map-sample.png) ### 1.3. 目标 1. 算法选择：需要选择一种适合解决最短路径问题的算法，如Dijkstra算法、A*算法、广度优先搜索等。 2. 算法实现：根据选择的算法，编写代码来实现路径规划功能。代码能够接收迷宫地图的输入（可以是直接读取预处理后的数据，也可以是读取图片后转换为内部数据结构），并输出从起点到终点的最短路径图及其对应的距离。 3. 测试与验证：对每张地图图片使用他们的算法进行测试，确保算法能够正确找到最短路径，并输出路径和距离。 4. 报告撰写：撰写一份报告，说明选择的算法、算法的实现过程、测试结果以及任何遇到的挑战和解决方案。 ## 2. 课题报告 ### 2.1. 技术栈 + Java、Spring Boot、Spring MVC、Hutool等 + Vue、Element-ui、Canvas等 ### 2.2. 算法选择 对于迷宫中的最短路径问题，常见的算法有： + Dijkstra算法：适用于无负权边的加权图，可以找到两点之间的最短路径。 + A*算法：结合了Dijkstra算法和启发式搜索，通过评估函数（通常是当前节点到目标节点的估计距离加上已走过的路径长度）来指导搜索方向，通常比Dijkstra更快。 + 广度优先搜索（BFS）：适用于无权重图，可以找到两点之间的最短路径。 **（flag：实现上述所有算法。目前：未完成）** 选择BFS算法来解决迷宫最短路径问题，是因为它简单、可靠、高效，并且易于理解和实现。它能够保证找到最短路径，同时也为后续的算法学习提供了一个良好的基础。 ### 2.3. 算法实现 #### 2.3.1. 数据结构 ##### Point类 ```java /** * 坐标点 * @author ZWX */ public class Point { /** * x坐标 */ private int x; /** * y坐标 */ private int y; /** * 点类型 */ private PointEnum type; } ``` ##### PointEnum坐标类型 ```java /** * 点标识 * @author ZWX */ public enum PointEnum { /** * 白色区域：代表你可以自由通行的空地。 */ WHITE, /** * 深灰色区域：代表障碍物，你无法穿越这些区域。 */ GREY, /** * 红色圆点：标记了你的起始位置。 */ RED, /** * 绿色圆点：标记了你的目标终点位置。 */ GREEN; } ``` ##### Labyrinth迷宫类 ```java /** * 迷宫 * @author ZWX */ public class Labyrinth { /** * 迷宫长 */ private int length; /** * 迷宫宽 */ private int width; /** * 点数组 */ @NonNull private Point[][] points; /** * 起点 */ private Point start; /** * 终点 */ private Point end; } ``` #### 2.3.2. BFS算法实现 ##### 算法思路 1. 初始化：创建一个Queue来存储待探索的节点；创建一个二维boolean数组(visited)来记录哪些节点已经被访问过；将起点加入队列，并将其标记为已访问。 2. 循环处理Queue中的待探索节点：从队列中取出第一个节点作为当前节点；如果当前节点为终点，则停止搜索，并回溯重构路径，否则，继续探索当前节点的所有邻居节点（上、下、左、右）；如果邻居节点为访问过并且不是障碍物，则将其加入到Queue中，并标记为已访问，记录到达该节点的路径长度和前驱节点。 3. 回溯重构路径：从终点开始，通过前驱节点回溯到起点，记录下整个路径。 4. 返回结果：将重构的路径和路径长度封装成架构并返回。 ##### 代码实现 ```java import cn.hutool.core.date.DateUtil; import cn.hutool.core.date.TimeInterval; import lombok.extern.slf4j.Slf4j; import top.zhanglingxi.enums.PointEnum; import java.util.LinkedList; import java.util.Queue; /** * 广度优先算法 * * @author ZWX */ @Slf4j public class BFS implements ICalcShortestPath { /** * 步item */ static class StepItem { /** * 路径长度 */ int distance; /** * 坐标点 */ Point point; /** * 前驱步 */ StepItem prevStep; public StepItem(int distance, Point point, StepItem prevStep) { this.distance = distance; this.point = point; this.prevStep = prevStep; } @Override public String toString() { return "distance =" + distance + ", point x =" + point.getX() + ", point y =" + point.getY(); } } @Override public ShortestPath getShortestPath(Labyrinth labyrinth) { log.info("===== BFS开始计算迷宫最短路径 ====="); TimeInterval timer = DateUtil.timer(); // 最短路径结果 ShortestPath shortestPath = new ShortestPath(); // 迷宫长度 int length = labyrinth.getLength(); // 迷宫宽度 int width = labyrinth.getWidth(); // 点数组 Point[][] points = labyrinth.getPoints(); // 起点 Point start = labyrinth.getStart(); // 终点 Point end = labyrinth.getEnd(); // 初始化队列和已访问集合 Queue stepQueue = new LinkedList<>(); boolean[][] visited = new boolean[length][width]; // 将起点加入队列 StepItem startStep = new StepItem(0, start, null); stepQueue.add(startStep); visited[start.getX()][start.getY()] = true; while (!stepQueue.isEmpty()) { StepItem currentStep = stepQueue.poll(); if (currentStep.point.getType() == PointEnum.GREEN) { shortestPath.setDistance(currentStep.distance); shortestPath.setPoints(reconstructPath(currentStep)); break; } exploreNeighbors(currentStep, stepQueue, visited, points); } log.info("===== BFS计算迷宫最短路径完成 ====="); //花费毫秒数 long interval = timer.interval(); shortestPath.setTime(interval); return shortestPath; } /** * 用于从 StepItem 回溯并重建最短路径。 * @param step 待回溯步骤 * @return 最短路径 */ private Point[] reconstructPath(StepItem step) { LinkedList path = new LinkedList<>(); while (step != null) { path.addFirst(step.point); step = step.prevStep; } return path.toArray(new Point[0]); } /** * 用于探索当前点的邻居节点，并检查它们是否可以访问。 * @param currentStep 当前步骤 * @param queue 待访问队列 * @param visited 已访问集合 * @param points 迷宫 */ private void exploreNeighbors(StepItem currentStep, Queue queue, boolean[][] visited, Point[][] points) { int[] dx = {0, 1, 0, -1}; int[] dy = {1, 0, -1, 0}; for (int i = 0; i < 4; i++) { int newX = currentStep.point.getX() + dx[i]; int newY = currentStep.point.getY() + dy[i]; if (newX >= 0 && newX < points.length && newY >= 0 && newY < points[0].length && !visited[newX][newY] && points[newX][newY].getType() != PointEnum.GREY) { queue.add(new StepItem(currentStep.distance + 1, points[newX][newY], currentStep)); visited[newX][newY] = true; } } } } ``` ### 2.4. 其他算法实现 #### 2.4.1. Prim迷宫随机生成算法 ##### 算法思路 1. 初始化迷宫：创建一个二维数组来表示迷宫，其中每个单元格可以是一个点对象（Point），这个对象包含位置信息以及类型（墙或路径）。确保迷宫的长宽都是奇数，这样可以在迷宫内部形成网格状的路径。初始化迷宫，所有的点默认设置为墙。 2. 选择起始点：随机选择一个点作为起始点，并将其设置为路径（白色）。建立一个列表来存储待处理的点（候选点列表），这些点是与路径相邻的墙点。 3. 扩展路径：在每次迭代中，从候选点列表中随机选择一个点，并将其设置为路径。找到新添加路径点的邻居，如果这些邻居中有路径点，则随机选择一个邻居路径点，并且在这两个点之间创建一条连接（即把它们之间的墙设为路径）。将新路径点周围的墙点（只要它们还没有被访问过）加入到候选点列表中。重复上述步骤，直到候选点列表为空。 4. 边界处理：确保在选择邻居时不会超出迷宫的边界。确保只有当一个墙点至少有一侧是路径时才将其添加到候选点列表中。 5. 完成迷宫生成：当候选点列表为空时，迷宫生成完成。 ##### 代码实现 ```java import cn.hutool.core.util.RandomUtil; import top.zhanglingxi.enums.PointEnum; import java.util.ArrayList; import java.util.List; import java.util.stream.Collectors; /** * Prim算法生成迷宫 * @author ZWX */ public class PrimGenerateLabyrinth implements IGenerateLabyrinth { @Override public Point[][] generateLabyrinth(int length, int width) { // 参数校验 if (length < 2 || length % 2 == 0) { throw new IllegalArgumentException("length必须大于1并且为奇数！"); } if (width < 2 || width % 2 == 0) { throw new IllegalArgumentException("width必须大于1并且为奇数！"); } // 长 路点个数 int a = (length - 1) / 2; // 宽 路点个数 int b = (width - 1) / 2; // 初始化迷宫 Point[][] labyrinth = new Point[length][width]; // 待选路点列表 // 将整个地图初始化为墙 for (int i = 0; i < length; i++) { for (int j = 0; j < width; j++) { labyrinth[i][j] = new Point(i, j, PointEnum.GREY); } } // 随机选择一个路点，将它变成路，并将它四周的路点加入进待选路点（列表） int aRandom = RandomUtil.randomInt(a); int bRandom = RandomUtil.randomInt(b); // 路点x坐标 int roadPointX = aRandom * 2 + 1; // 路点y坐标 int roadPointY = bRandom * 2 + 1; // Point point = labyrinth[roadPointX][roadPointY]; Point point = labyrinth[1][1]; point.setType(PointEnum.WHITE); List toBeSelectedRoadPoints = new ArrayList<>(getAroundRoadPointList(labyrinth, point)); // 当待选路点（列表）不为空时 while (!toBeSelectedRoadPoints.isEmpty()) { // 从待选路点中随机选一个路点A，变成路点并移出待选路点（列表） Point roadPointA = toBeSelectedRoadPoints.remove(RandomUtil.randomInt(toBeSelectedRoadPoints.size())); roadPointA.setType(PointEnum.WHITE); List aroundRoadPointList = getAroundRoadPointList(labyrinth, roadPointA); // 将A与它四周的随机一个已经变成路的路点B打通(将A变成路，将A和B中间的墙点变成路) List roadPointList = aroundRoadPointList.stream() .filter(item -> item.getType() == PointEnum.WHITE) .collect(Collectors.toList()); Point roadPointB = roadPointList.get(RandomUtil.randomInt(roadPointList.size())); // 判断路点B的位置 // 路点B在路点A的右侧 if (roadPointB.getX() - roadPointA.getX() == 2) { labyrinth[roadPointB.getX() - 1][roadPointB.getY()].setType(PointEnum.WHITE); } // 路点B在路点A的左侧 if (roadPointB.getX() - roadPointA.getX() == -2) { labyrinth[roadPointB.getX() + 1][roadPointB.getY()].setType(PointEnum.WHITE); } // 路点B在路点A的下面 if (roadPointB.getY() - roadPointA.getY() == 2) { labyrinth[roadPointB.getX()][roadPointB.getY() - 1].setType(PointEnum.WHITE); } // 路点B在路点A的上面 if (roadPointB.getY() - roadPointA.getY() == -2) { labyrinth[roadPointB.getX()][roadPointB.getY() + 1].setType(PointEnum.WHITE); } // 将A四周不是路的路点加入到待选路点 List wellPointList = aroundRoadPointList.stream() .filter(item -> item.getType() != PointEnum.WHITE) .collect(Collectors.toList()); for (Point wellPoint : wellPointList) { if (!toBeSelectedRoadPoints.contains(wellPoint)) { toBeSelectedRoadPoints.add(wellPoint); } } } return labyrinth; } /** * 获取路点周围的所有路点 * @param labyrinth 迷宫 * @param point 路点 * @return 该路点周围的所有路点 */ private List getAroundRoadPointList(Point[][] labyrinth, Point point) { int length = labyrinth.length; int width = labyrinth[0].length; int roadPointX = point.getX(); int roadPointY = point.getY(); ArrayList aroundRoadPointList = new ArrayList<>(); // 左 路点 if (roadPointX - 2 > 0) { aroundRoadPointList.add(labyrinth[roadPointX - 2][roadPointY]); } // 右 路点 if (roadPointX + 2 < length) { aroundRoadPointList.add(labyrinth[roadPointX + 2][roadPointY]); } // 上 路点 if (roadPointY - 2 > 0) { aroundRoadPointList.add(labyrinth[roadPointX][roadPointY - 2]); } // 下 路点 if (roadPointY + 2 < width) { aroundRoadPointList.add(labyrinth[roadPointX][roadPointY + 2]); } return aroundRoadPointList; } } ``` ### 2.5. 后端接口 #### 2.5.1. 生成迷宫 ```shell URL：/generate/labyrinth 请求方式：Get 请求参数：迷宫高度，迷宫宽度 返回结果：迷宫地图（二维坐标数组） ``` #### 2.5.2. 上传迷宫 ```shell URL：/generate/labyrinth/upload/csv 请求方式：Post 请求参数：CSV文件 返回结果：迷宫地图（二维坐标数组） ``` #### 2.5.3. 下载迷宫(CSV) ```shell URL：/generate/labyrinth/download/csv 请求方式：Get 请求参数：无 返回结果：迷宫地图CSV文件 ``` #### 2.5.4. 绘制路线(BFS) ```shell URL：/calc/shortest/path 请求方式：Post 请求参数：起点坐标，终点坐标 返回结果：路径长度和最短路线 ``` ### 2.6. 前端展示 #### 2.6.1. 前端页面 为方便迷宫地图和最短路径规划的可视化展示，使用Vue + Canvas等前端技术编写页面，页面如下： ![前端页面](doc/imgs/front-page.png) #### 2.6.2. 生成迷宫 ![生成迷宫](doc/imgs/generate-labyrinth.png) #### 2.6.3. 上传迷宫 ![上传迷宫](doc/imgs/upload-labyrinth.png) #### 2.6.4. 下载迷宫 ![下载迷宫](doc/imgs/download-labyrinth.png) #### 2.6.5. 刷新迷宫 清除迷宫上的起点、终点和最短路线 #### 2.6.6. 设置起点 ![设置起点](doc/imgs/set-start.png) #### 2.6.7. 设置终点 ![设置终点](doc/imgs/set-end.png) #### 2.6.8. 绘制路线（BFS） ![绘制路线（BFS）](doc/imgs/draw-bfs.png) ### 2.7. 项目部署 #### 2.7.1. 前端部署 进入`deploy/ui`文件夹，运行命令：`start nignx`，启动nginx #### 2.7.2. 后端部署 进入`deploy`文件夹，运行命令：`java -jar labyrinth.jar`，启动后端 #### 2.7.3. 访问网站 访问(http://localhost:81/map-edit)