每日算法 — 使用java实现魔法迷宫：递归分割随机生成与A*最短路径求解

引言

迷宫生成与求解是算法领域的经典问题，广泛应用于游戏地图设计、机器人路径规划等领域。本文将用Java实现一种优雅的迷宫生成算法——递归分割法（Recursive Division），以及高效的A*寻路算法来求解生成的迷宫。通过这个项目，你将深入理解分治策略在空间生成中的应用，以及启发式搜索在路径规划中的威力。

一、递归分割迷宫生成算法

1.1 算法思想

递归分割法的核心思想是：从一个完全开放的空间开始，递归地添加墙壁将其分割成更小的区域，同时在墙壁上随机开设通道，确保迷宫的连通性。

1.2 算法步骤

1. 初始状态：整个区域没有墙壁（全是通路）
2. 在当前区域随机选择一行和一列添加十字墙壁
3. 在十字墙壁的三边上各开一个通道（保留一边封闭以形成迷宫结构）
4. 对形成的四个子区域递归执行步骤2-3
5. 当区域足够小时停止分割

二、Java核心实现

import java.util.*;

/**
 * 迷宫单元格类型枚举
 */
enum CellType {
    WALL('#'),    // 墙壁
    PATH(' '),    // 通路
    START('S'),   // 起点
    END('E'),     // 终点
    VISITED('.'), // 已访问（用于显示搜索过程）
    SOLUTION('*');// 解决方案路径

    private final char symbol;

    CellType(char symbol) {
        this.symbol = symbol;
    }

    public char getSymbol() {
        return symbol;
    }
}

/**
 * 坐标点类
 */
class Point {
    int x, y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Point)) return false;
        Point p = (Point) o;
        return x == p.x && y == p.y;
    }

    @Override
    public int hashCode() {
        return x * 31 + y;
    }

    @Override
    public String toString() {
        return "(" + x + "," + y + ")";
    }
}

/**
 * 迷宫类
 * 使用递归分割法生成，支持A*寻路求解
 */
public class MagicMaze {
    private final int width;  // 迷宫宽度（必须是奇数）
    private final int height; // 迷宫高度（必须是奇数）
    private final CellType[][] grid;
    private final Random random;

    public MagicMaze(int width, int height) {
        // 确保宽度和高度为奇数，以便墙壁和通路交替排列
        this.width = width % 2 == 0 ? width + 1 : width;
        this.height = height % 2 == 0 ? height + 1 : height;
        this.grid = new CellType[this.height][this.width];
        this.random = new Random();

        initializeGrid();
        generateMaze(1, 1, this.width - 2, this.height - 2);

        // 设置起点和终点
        grid[1][1] = CellType.START;
        grid[this.height - 2][this.width - 2] = CellType.END;
    }

    /**
     * 初始化网格：全部设为通路
     */
    private void initializeGrid() {
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                // 边界设为墙壁
                if (x == 0 || x == width - 1 || y == 0 || y == height - 1) {
                    grid[y][x] = CellType.WALL;
                } else {
                    grid[y][x] = CellType.PATH;
                }
            }
        }
    }

    /**
     * 递归分割生成迷宫
     * @param left 左边界
     * @param top 上边界
     * @param right 右边界
     * @param bottom 下边界
     */
    private void generateMaze(int left, int top, int right, int bottom) {
        int w = right - left + 1;
        int h = bottom - top + 1;

        // 停止条件：区域太小无法分割
        if (w < 3 || h < 3) {
            return;
        }

        // 选择随机的墙壁位置（必须是偶数索引，这样通道在奇数索引）
        int wallX = left + 1 + random.nextInt((w - 1) / 2) * 2;
        int wallY = top + 1 + random.nextInt((h - 1) / 2) * 2;

        // 在选定位置画十字墙壁
        drawCrossWall(left, top, right, bottom, wallX, wallY);

        // 对四个象限递归分割
        // 左上
        generateMaze(left, top, wallX - 1, wallY - 1);
        // 右上
        generateMaze(wallX + 1, top, right, wallY - 1);
        // 左下
        generateMaze(left, wallY + 1, wallX - 1, bottom);
        // 右下
        generateMaze(wallX + 1, wallY + 1, right, bottom);
    }

    /**
     * 在指定位置画十字墙壁，并在三边开口
     */
    private void drawCrossWall(int left, int top, int right, int bottom, int wallX, int wallY) {
        // 确定十字墙壁的四个端点
        int xStart = left;
        int xEnd = right;
        int yStart = top;
        int yEnd = bottom;

        // 画水平墙壁
        for (int x = xStart; x <= xEnd; x++) {
            grid[wallY][x] = CellType.WALL;
        }

        // 画垂直墙壁
        for (int y = yStart; y <= yEnd; y++) {
            grid[y][wallX] = CellType.WALL;
        }

        // 在十字的三边上开设通道
        // 四个方向：上、下、左、右，选择其中三个开设通道
        List<Integer> directions = new ArrayList<>(Arrays.asList(0, 1, 2, 3));
        Collections.shuffle(directions, random);

        // 开设三个通道，保留一个封闭
        for (int i = 0; i < 3; i++) {
            int dir = directions.get(i);
            createPassage(wallX, wallY, dir, left, top, right, bottom);
        }
    }

    /**
     * 在指定方向开设通道
     */
    private void createPassage(int wallX, int wallY, int direction, 
                               int left, int top, int right, int bottom) {
        int passageX = wallX;
        int passageY = wallY;

        switch (direction) {
            case 0: // 上：在垂直墙壁的上半部分随机开通道
                passageY = top + random.nextInt((wallY - top) / 2 + 1) * 2;
                break;
            case 1: // 下：在垂直墙壁的下半部分随机开通道
                passageY = wallY + 1 + random.nextInt((bottom - wallY) / 2 + 1) * 2;
                if (passageY > bottom) passageY = bottom;
                break;
            case 2: // 左：在水平墙壁的左半部分随机开通道
                passageX = left + random.nextInt((wallX - left) / 2 + 1) * 2;
                break;
            case 3: // 右：在水平墙壁的右半部分随机开通道
                passageX = wallX + 1 + random.nextInt((right - wallX) / 2 + 1) * 2;
                if (passageX > right) passageX = right;
                break;
        }

        grid[passageY][passageX] = CellType.PATH;
    }

    /**
     * 检查坐标是否在迷宫范围内
     */
    public boolean isValid(int x, int y) {
        return x >= 0 && x < width && y >= 0 && y < height;
    }

    /**
     * 检查坐标是否是通路
     */
    public boolean isPassable(int x, int y) {
        return isValid(x, y) && grid[y][x] != CellType.WALL;
    }

    /**
     * 获取起点坐标
     */
    public Point getStart() {
        return new Point(1, 1);
    }

    /**
     * 获取终点坐标
     */
    public Point getEnd() {
        return new Point(width - 2, height - 2);
    }

    /**
     * 打印迷宫
     */
    public void print() {
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                System.out.print(grid[y][x].getSymbol());
            }
            System.out.println();
        }
    }

    /**
     * 复制网格状态（用于标记搜索路径）
     */
    public CellType[][] getGridCopy() {
        CellType[][] copy = new CellType[height][width];
        for (int y = 0; y < height; y++) {
            System.arraycopy(grid[y], 0, copy[y], 0, width);
        }
        return copy;
    }

    public int getWidth() { return width; }
    public int getHeight() { return height; }
}

三、A*寻路算法实现

import java.util.*;

/**
 * A*寻路节点
 */
class AStarNode implements Comparable<AStarNode> {
    Point point;
    double g; // 从起点到当前节点的实际代价
    double h; // 从当前节点到终点的启发式估计代价
    AStarNode parent;

    public AStarNode(Point point, double g, double h, AStarNode parent) {
        this.point = point;
        this.g = g;
        this.h = h;
        this.parent = parent;
    }

    // f = g + h，总代价
    public double getF() {
        return g + h;
    }

    @Override
    public int compareTo(AStarNode other) {
        return Double.compare(this.getF(), other.getF());
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof AStarNode)) return false;
        AStarNode other = (AStarNode) o;
        return this.point.equals(other.point);
    }

    @Override
    public int hashCode() {
        return point.hashCode();
    }
}

/**
 * A*寻路求解器
 */
public class AStarSolver {

    /**
     * 曼哈顿距离启发式函数
     * 仅适用于四方向移动（上、下、左、右）
     */
    public static double manhattanDistance(Point a, Point b) {
        return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
    }

    /**
     * 欧几里得距离启发式函数
     * 适用于八方向移动或对角线移动
     */
    public static double euclideanDistance(Point a, Point b) {
        return Math.sqrt(Math.pow(a.x - b.x, 2) + Math.pow(a.y - b.y, 2));
    }

    /**
     * A*寻路主算法
     * @param maze 迷宫对象
     * @param start 起点
     * @param end 终点
     * @return 从起点到终点的路径，若不可达则返回null
     */
    public static List<Point> solve(MagicMaze maze, Point start, Point end) {
        // 优先队列（按f值排序）
        PriorityQueue<AStarNode> openSet = new PriorityQueue<>();
        // 已访问集合
        Set<Point> closedSet = new HashSet<>();
        // 记录每个点的最优g值，用于快速查找
        Map<Point, Double> gScore = new HashMap<>();

        AStarNode startNode = new AStarNode(start, 0, manhattanDistance(start, end), null);
        openSet.add(startNode);
        gScore.put(start, 0.0);

        // 四个方向：上、下、左、右
        int[][] directions = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

        while (!openSet.isEmpty()) {
            AStarNode current = openSet.poll();

            // 到达终点
            if (current.point.equals(end)) {
                return reconstructPath(current);
            }

            closedSet.add(current.point);

            // 遍历邻居
            for (int[] dir : directions) {
                int nx = current.point.x + dir[0];
                int ny = current.point.y + dir[1];
                Point neighbor = new Point(nx, ny);

                // 检查是否可通行且未访问
                if (!maze.isPassable(nx, ny) || closedSet.contains(neighbor)) {
                    continue;
                }

                // 计算从起点经当前点到邻居的代价
                double tentativeG = current.g + 1; // 每步代价为1

                // 如果找到更优路径
                if (!gScore.containsKey(neighbor) || tentativeG < gScore.get(neighbor)) {
                    gScore.put(neighbor, tentativeG);
                    double h = manhattanDistance(neighbor, end);
                    AStarNode neighborNode = new AStarNode(neighbor, tentativeG, h, current);

                    // 如果邻居不在开放列表中，添加它
                    openSet.remove(neighborNode); // 先移除旧节点（如果存在）
                    openSet.add(neighborNode);
                }
            }
        }

        // 开放列表为空但未找到路径，说明不可达
        return null;
    }

    /**
     * 回溯重建路径
     */
    private static List<Point> reconstructPath(AStarNode endNode) {
        List<Point> path = new ArrayList<>();
        AStarNode current = endNode;
        while (current != null) {
            path.add(current.point);
            current = current.parent;
        }
        Collections.reverse(path);
        return path;
    }

    /**
     * 在迷宫上可视化路径
     */
    public static void printPath(MagicMaze maze, List<Point> path) {
        CellType[][] display = maze.getGridCopy();

        // 标记路径
        for (Point p : path) {
            if (display[p.y][p.x] != CellType.START && display[p.y][p.x] != CellType.END) {
                display[p.y][p.x] = CellType.SOLUTION;
            }
        }

        // 打印
        for (int y = 0; y < maze.getHeight(); y++) {
            for (int x = 0; x < maze.getWidth(); x++) {
                System.out.print(display[y][x].getSymbol());
            }
            System.out.println();
        }
    }

    /**
     * 比较A*与BFS的性能
     */
    public static void comparePerformance(MagicMaze maze, Point start, Point end) {
        long startTime, endTime;

        // A*搜索
        startTime = System.nanoTime();
        List<Point> astarPath = solve(maze, start, end);
        endTime = System.nanoTime();
        long astarTime = endTime - startTime;

        // BFS搜索
        startTime = System.nanoTime();
        List<Point> bfsPath = bfsSolve(maze, start, end);
        endTime = System.nanoTime();
        long bfsTime = endTime - startTime;

        System.out.println("===== 性能对比 =====");
        System.out.println("A* 路径长度: " + (astarPath != null ? astarPath.size() : "无解"));
        System.out.println("A* 耗时: " + astarTime / 1000 + " μs");
        System.out.println("BFS 路径长度: " + (bfsPath != null ? bfsPath.size() : "无解"));
        System.out.println("BFS 耗时: " + bfsTime / 1000 + " μs");
        System.out.println("速度比 (BFS/A*): " + String.format("%.2f", (double)bfsTime / astarTime));
    }

    /**
     * BFS求解（用于对比）
     */
    public static List<Point> bfsSolve(MagicMaze maze, Point start, Point end) {
        Queue<Point> queue = new LinkedList<>();
        Map<Point, Point> parent = new HashMap<>();
        Set<Point> visited = new HashSet<>();

        queue.add(start);
        visited.add(start);

        int[][] directions = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

        while (!queue.isEmpty()) {
            Point current = queue.poll();

            if (current.equals(end)) {
                return reconstructBfsPath(parent, start, end);
            }

            for (int[] dir : directions) {
                int nx = current.x + dir[0];
                int ny = current.y + dir[1];
                Point neighbor = new Point(nx, ny);

                if (maze.isPassable(nx, ny) && !visited.contains(neighbor)) {
                    visited.add(neighbor);
                    parent.put(neighbor, current);
                    queue.add(neighbor);
                }
            }
        }

        return null;
    }

    private static List<Point> reconstructBfsPath(Map<Point, Point> parent, Point start, Point end) {
        List<Point> path = new ArrayList<>();
        Point current = end;
        while (!current.equals(start)) {
            path.add(current);
            current = parent.get(current);
        }
        path.add(start);
        Collections.reverse(path);
        return path;
    }
}

四、完整运行示例

/**
 * 魔法迷宫主程序
 */
public class MagicMazeApp {
    public static void main(String[] args) {
        // 创建21x21的迷宫
        System.out.println("=== 生成魔法迷宫 ===\n");
        MagicMaze maze = new MagicMaze(21, 21);

        System.out.println("迷宫结构：");
        maze.print();

        Point start = maze.getStart();
        Point end = maze.getEnd();
        System.out.println("\n起点: " + start + ", 终点: " + end);

        // 使用A*求解
        System.out.println("\n=== A*寻路求解 ===");
        List<Point> path = AStarSolver.solve(maze, start, end);

        if (path != null) {
            System.out.println("找到路径！步数: " + path.size());
            System.out.println("\n路径可视化（*表示路径）：");
            AStarSolver.printPath(maze, path);

            // 打印详细路径
            System.out.println("\n详细路径坐标：");
            for (int i = 0; i < path.size(); i++) {
                System.out.print(path.get(i));
                if (i < path.size() - 1) System.out.print(" -> ");
                if ((i + 1) % 5 == 0) System.out.println();
            }
            System.out.println();
        } else {
            System.out.println("未找到路径！");
        }

        // 性能对比
        System.out.println("\n=== 性能对比测试 ===");
        AStarSolver.comparePerformance(maze, start, end);

        // 大规模测试
        System.out.println("\n=== 大规模迷宫测试（51x51）===");
        MagicMaze largeMaze = new MagicMaze(51, 51);
        Point largeStart = largeMaze.getStart();
        Point largeEnd = largeMaze.getEnd();

        long t1 = System.nanoTime();
        List<Point> largePath = AStarSolver.solve(largeMaze, largeStart, largeEnd);
        long t2 = System.nanoTime();

        System.out.println("迷宫大小: 51x51");
        System.out.println("A*寻路耗时: " + (t2 - t1) / 1000 + " μs");
        System.out.println("路径长度: " + (largePath != null ? largePath.size() : "无解"));
    }
}

五、算法分析

其中n为格子数，b为分支因子，d为解深度，V和E分别为图的顶点数和边数。

六、总结与扩展

本文实现了递归分割迷宫生成法和A*寻路算法。递归分割法生成的迷宫具有独特的”房间”结构，与DFS回溯法生成的长走廊风格形成鲜明对比。

扩展方向：
1. 多种生成算法对比：实现Prim算法、Kruskal算法、DFS回溯法生成迷宫并比较风格差异
2. 3D迷宫：将算法扩展到三维空间
3. 动态迷宫：实现会随时间变化的迷宫
4. 多目标寻路：在迷宫中寻找经过多个检查点的最优路径