每日算法 — 使用java实现迷宫生成与求解：随机Prim生成与SPFA最短路径

引言

迷宫生成与求解是算法领域的经典课题，涉及图论、搜索和随机过程等多个知识领域。常见的迷宫生成算法包括深度优先搜索（DFS）回溯法、Kruskal算法和Prim算法。其中，随机Prim算法（Randomized Prim’s Algorithm）生成的迷宫具有”少长直道、多短岔路”的特点，与Kruskal相比路径结构更加自然。而在求解方面，当迷宫中存在不同地形的通行代价（如沼泽、草地、石板路）时，传统的BFS不再适用，需要引入能够处理带权图的最短路径算法。本文将结合随机Prim算法生成带权重的完美迷宫，并使用SPFA（Shortest Path Faster Algorithm）求解从入口到出口的最优路径，展示从生成到求解的完整算法链条。

算法原理

随机Prim迷宫生成

将迷宫视为一个网格图，每个格子是一个节点，相邻格子之间有边相连。随机Prim算法的核心思想：

1. 初始化：从起始格子开始，将其标记为”已访问”
2. 边界集维护：维护一个”边界边”集合，包含所有一端已访问、另一端未访问的边
3. 随机扩展：从边界集中随机选择一条边，打通该边（将未访问端标记为已访问），并将新产生的边界边加入集合
4. 重复：直到所有格子都被访问

生成的迷宫是”完美迷宫”（Perfect Maze）：任意两点之间有且仅有一条简单路径，无环且无不可达区域。

SPFA最短路径算法

SPFA是Bellman-Ford算法的队列优化版本，适用于边权可正可负的图（本文仅使用正权）。

核心思想：
1. 使用队列维护待松弛的顶点
2. 每次从队列取出一个顶点，对其所有邻接边进行松弛操作
3. 如果某邻接顶点通过当前顶点可以获得更短路径，则更新其距离并将其入队
4. 使用计数数组检测负环（本文场景无负权边，可省略）

SPFA在稀疏图上的平均时间复杂度为O(E)，最坏情况O(VE)，对于网格图表现通常优于Dijkstra的堆实现。

Java实现

项目结构

src/
├── maze/
│   ├── Cell.java           // 迷宫格子
│   ├── Wall.java           // 墙壁/边
│   ├── Maze.java           // 迷宫数据结构与打印
│   └── TerrainType.java    // 地形类型与权重
├── generator/
│   └── RandomPrimGenerator.java // 随机Prim生成器
├── solver/
│   └── SPFASolver.java     // SPFA最短路径求解器
└── Main.java

TerrainType.java — 地形类型与通行权重

package maze;

/**
 * 迷宫地形类型枚举
 * 不同地形具有不同的通行代价（权重）
 */
public enum TerrainType {
    PATH(1, ' '),      // 通道：权重1，可通行
    WALL(0, '#'),      // 墙壁：权重0，不可通行（用极大值表示）
    SWAMP(5, '~'),     // 沼泽：权重5，通行缓慢
    GRASS(2, '"'),     // 草地：权重2
    STONE(1, '='),     // 石板：权重1，最优地形
    START(1, 'S'),     // 起点
    END(1, 'E');       // 终点

    private final int weight;   // 通行代价
    private final char symbol;  // 打印符号

    TerrainType(int weight, char symbol) {
        this.weight = weight;
        this.symbol = symbol;
    }

    public int getWeight() { return weight; }
    public char getSymbol() { return symbol; }

    /**
     * 判断该地形是否可通行
     */
    public boolean isPassable() {
        return this != WALL;
    }
}

Cell.java — 迷宫格子模型

package maze;

import java.util.*;

/**
 * 迷宫中的单个格子
 * 每个格子记录坐标、地形类型、以及四个方向的连通状态
 */
public class Cell {
    private final int row;
    private final int col;
    private TerrainType terrain;

    // 四个方向的墙壁状态：true表示有墙，false表示已打通
    private boolean northWall, southWall, eastWall, westWall;

    public Cell(int row, int col) {
        this.row = row;
        this.col = col;
        this.terrain = TerrainType.WALL;
        this.northWall = true;
        this.southWall = true;
        this.eastWall = true;
        this.westWall = true;
    }

    public int getRow() { return row; }
    public int getCol() { return col; }

    public TerrainType getTerrain() { return terrain; }
    public void setTerrain(TerrainType terrain) { this.terrain = terrain; }

    public boolean hasNorthWall() { return northWall; }
    public boolean hasSouthWall() { return southWall; }
    public boolean hasEastWall() { return eastWall; }
    public boolean hasWestWall() { return westWall; }

    public void removeNorthWall() { this.northWall = false; }
    public void removeSouthWall() { this.southWall = false; }
    public void removeEastWall() { this.eastWall = false; }
    public void removeWestWall() { this.westWall = false; }

    /**
     * 获取所有可通行的邻接格子（仅考虑墙壁状态）
     */
    public List<Cell> getNeighbors(Maze maze) {
        List<Cell> neighbors = new ArrayList<>();
        Cell[][] grid = maze.getGrid();
        int rows = grid.length;
        int cols = grid[0].length;

        if (!northWall && row > 0) neighbors.add(grid[row - 1][col]);
        if (!southWall && row < rows - 1) neighbors.add(grid[row + 1][col]);
        if (!westWall && col > 0) neighbors.add(grid[row][col - 1]);
        if (!eastWall && col < cols - 1) neighbors.add(grid[row][col + 1]);

        return neighbors;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Cell)) return false;
        Cell cell = (Cell) o;
        return row == cell.row && col == cell.col;
    }

    @Override
    public int hashCode() {
        return Objects.hash(row, col);
    }

    @Override
    public String toString() {
        return String.format("Cell(%d,%d)", row, col);
    }
}

Wall.java — 墙壁/边模型

package maze;

import java.util.Objects;

/**
 * 表示两个相邻格子之间的墙壁（边）
 * 用于随机Prim算法的边界集管理
 */
public class Wall {
    public final Cell cell1;  // 已访问侧的格子
    public final Cell cell2;  // 未访问侧的格子
    public final Direction direction; // cell1相对于cell2的方向

    public enum Direction {
        NORTH, SOUTH, EAST, WEST
    }

    public Wall(Cell cell1, Cell cell2, Direction direction) {
        this.cell1 = cell1;
        this.cell2 = cell2;
        this.direction = direction;
    }

    /**
     * 打通这面墙，建立两个格子之间的连通
     */
    public void remove() {
        switch (direction) {
            case NORTH:
                cell1.removeNorthWall();
                cell2.removeSouthWall();
                break;
            case SOUTH:
                cell1.removeSouthWall();
                cell2.removeNorthWall();
                break;
            case EAST:
                cell1.removeEastWall();
                cell2.removeWestWall();
                break;
            case WEST:
                cell1.removeWestWall();
                cell2.removeEastWall();
                break;
        }
        // 将未访问的cell2标记为通道
        if (cell2.getTerrain() == TerrainType.WALL) {
            cell2.setTerrain(TerrainType.PATH);
        }
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Wall)) return false;
        Wall wall = (Wall) o;
        // 不考虑方向的无序比较
        return (cell1.equals(wall.cell1) && cell2.equals(wall.cell2)) ||
               (cell1.equals(wall.cell2) && cell2.equals(wall.cell1));
    }

    @Override
    public int hashCode() {
        return Objects.hash(cell1, cell2) + Objects.hash(cell2, cell1);
    }
}

Maze.java — 迷宫数据结构与可视化

package maze;

import java.util.*;

/**
 * 迷宫数据结构
 * 提供网格管理、地形设置和ASCII可视化输出
 */
public class Maze {
    private final int rows;
    private final int cols;
    private final Cell[][] grid;
    private Cell startCell;
    private Cell endCell;

    public Maze(int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
        this.grid = new Cell[rows][cols];
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                grid[r][c] = new Cell(r, c);
            }
        }
    }

    public Cell[][] getGrid() { return grid; }
    public int getRows() { return rows; }
    public int getCols() { return cols; }

    public Cell getCell(int row, int col) {
        return grid[row][col];
    }

    public void setStart(int row, int col) {
        startCell = grid[row][col];
        startCell.setTerrain(TerrainType.START);
    }

    public void setEnd(int row, int col) {
        endCell = grid[row][col];
        endCell.setTerrain(TerrainType.END);
    }

    public Cell getStart() { return startCell; }
    public Cell getEnd() { return endCell; }

    /**
     * 在通道上随机设置不同地形（沼泽、草地、石板）
     * 增加路径选择的策略性
     */
    public void randomizeTerrain(Random rand, double swampProb, double grassProb) {
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                Cell cell = grid[r][c];
                if (cell.getTerrain() == TerrainType.PATH) {
                    double p = rand.nextDouble();
                    if (p < swampProb) {
                        cell.setTerrain(TerrainType.SWAMP);
                    } else if (p < swampProb + grassProb) {
                        cell.setTerrain(TerrainType.GRASS);
                    } else {
                        cell.setTerrain(TerrainType.STONE);
                    }
                }
            }
        }
    }

    /**
     * 获取两个相邻格子之间移动的权重
     */
    public int getMoveWeight(Cell from, Cell to) {
        // 权重 = 目标格子的地形权重
        return to.getTerrain().getWeight();
    }

    /**
     * 打印迷宫（ASCII可视化）
     * @param path 可选的路径高亮
     */
    public void printMaze(List<Cell> path) {
        Set<Cell> pathSet = new HashSet<>();
        if (path != null) pathSet.addAll(path);

        // 打印上边界
        for (int c = 0; c < cols; c++) {
            System.out.print("+---");
        }
        System.out.println("+");

        for (int r = 0; r < rows; r++) {
            // 打印格子内容和垂直墙
            System.out.print("|");
            for (int c = 0; c < cols; c++) {
                Cell cell = grid[r][c];
                char symbol = pathSet.contains(cell) ? '*' : cell.getTerrain().getSymbol();
                System.out.print(" " + symbol + " ");
                if (cell.hasEastWall() && c < cols - 1) {
                    System.out.print("|");
                } else if (c < cols - 1) {
                    System.out.print(" ");
                }
            }
            System.out.println("|");

            // 打印水平墙
            if (r < rows - 1) {
                System.out.print("+");
                for (int c = 0; c < cols; c++) {
                    Cell cell = grid[r][c];
                    if (cell.hasSouthWall()) {
                        System.out.print("---+");
                    } else {
                        System.out.print("   +");
                    }
                }
                System.out.println();
            }
        }

        // 打印下边界
        for (int c = 0; c < cols; c++) {
            System.out.print("+---");
        }
        System.out.println("+");
    }

    /**
     * 简化打印（不带边界墙，只显示地形和路径）
     */
    public void printSimple(List<Cell> path) {
        Set<Cell> pathSet = new HashSet<>();
        if (path != null) pathSet.addAll(path);

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                Cell cell = grid[r][c];
                if (pathSet.contains(cell)) {
                    System.out.print(" * ");
                } else {
                    System.out.print(" " + cell.getTerrain().getSymbol() + " ");
                }
            }
            System.out.println();
        }
    }
}

RandomPrimGenerator.java — 随机Prim迷宫生成器

package generator;

import maze.*;
import java.util.*;

/**
 * 基于随机Prim算法的迷宫生成器
 *
 * 算法步骤：
 * 1. 随机选择一个起始格子，标记为已访问
 * 2. 将起始格子的所有邻接墙加入"边界墙集合"
 * 3. 当边界墙集合非空时：
 *    a. 随机从边界墙集合中选择一面墙
 *    b. 如果该墙连接一个未访问格子，则打通该墙，标记新格子为已访问
 *    c. 将新格子的所有邻接墙加入边界墙集合
 *    d. 从边界墙集合中移除已处理的墙
 * 4. 所有格子都被访问后，迷宫生成完成
 */
public class RandomPrimGenerator {
    private final Random rand;

    public RandomPrimGenerator(Random rand) {
        this.rand = rand;
    }

    /**
     * 生成指定大小的完美迷宫
     * @param rows 行数
     * @param cols 列数
     * @return 生成的迷宫对象
     */
    public Maze generate(int rows, int cols) {
        Maze maze = new Maze(rows, cols);
        boolean[][] visited = new boolean[rows][cols];
        List<Wall> frontier = new ArrayList<>();

        // 1. 随机选择起始格子
        int startRow = rand.nextInt(rows);
        int startCol = rand.nextInt(cols);
        Cell startCell = maze.getCell(startRow, startCol);
        startCell.setTerrain(TerrainType.PATH);
        visited[startRow][startCol] = true;

        // 2. 将起始格子的邻接墙加入边界集
        addWallsToFrontier(maze, startCell, visited, frontier);

        // 3. 主循环：扩展迷宫直到边界集为空
        while (!frontier.isEmpty()) {
            // 随机选择一面边界墙
            int idx = rand.nextInt(frontier.size());
            Wall wall = frontier.get(idx);
            frontier.remove(idx);

            // 检查该墙是否连接未访问格子
            Cell unvisited = visited[wall.cell1.getRow()][wall.cell1.getCol()] ? wall.cell2 : wall.cell1;

            if (!visited[unvisited.getRow()][unvisited.getCol()]) {
                // 打通这面墙
                wall.remove();
                visited[unvisited.getRow()][unvisited.getCol()] = true;

                // 将新格子的邻接墙加入边界集
                addWallsToFrontier(maze, unvisited, visited, frontier);
            }
        }

        // 4. 设置起点和终点
        maze.setStart(0, 0);
        maze.setEnd(rows - 1, cols - 1);

        return maze;
    }

    /**
     * 将格子的所有邻接墙（连接未访问格子的）加入边界集
     */
    private void addWallsToFrontier(Maze maze, Cell cell, boolean[][] visited, List<Wall> frontier) {
        int r = cell.getRow();
        int c = cell.getCol();
        int rows = maze.getRows();
        int cols = maze.getCols();

        // 北
        if (r > 0 && !visited[r - 1][c]) {
            frontier.add(new Wall(cell, maze.getCell(r - 1, c), Wall.Direction.NORTH));
        }
        // 南
        if (r < rows - 1 && !visited[r + 1][c]) {
            frontier.add(new Wall(cell, maze.getCell(r + 1, c), Wall.Direction.SOUTH));
        }
        // 西
        if (c > 0 && !visited[r][c - 1]) {
            frontier.add(new Wall(cell, maze.getCell(r, c - 1), Wall.Direction.WEST));
        }
        // 东
        if (c < cols - 1 && !visited[r][c + 1]) {
            frontier.add(new Wall(cell, maze.getCell(r, c + 1), Wall.Direction.EAST));
        }
    }
}

SPFASolver.java — SPFA最短路径求解器

package solver;

import maze.*;
import java.util.*;

/**
 * SPFA（Shortest Path Faster Algorithm）最短路径求解器
 * Bellman-Ford算法的队列优化版本
 *
 * 适用场景：带权图的最短路径，本文中用于求解带地形权重的迷宫最优路径
 *
 * 算法步骤：
 * 1. 初始化：起点距离为0，其他点为无穷大
 * 2. 起点入队
 * 3. 当队列非空时：
 *    a. 取出队首顶点u
 *    b. 遍历u的所有邻接顶点v
 *    c. 如果 dist[u] + weight(u,v) < dist[v]，则更新dist[v]，v入队
 * 4. 队列为空时结束，dist即为最短距离
 */
public class SPFASolver {

    /**
     * SPFA求解结果
     */
    public static class PathResult {
        public final List<Cell> path;      // 最短路径上的格子列表
        public final int totalWeight;      // 路径总权重
        public final int relaxCount;       // 松弛操作次数（用于分析算法效率）
        public final boolean reachable;    // 是否可达

        public PathResult(List<Cell> path, int totalWeight, int relaxCount, boolean reachable) {
            this.path = path;
            this.totalWeight = totalWeight;
            this.relaxCount = relaxCount;
            this.reachable = reachable;
        }
    }

    /**
     * 在迷宫中求解从起点到终点的最短路径
     * @param maze 迷宫对象
     * @return 路径结果
     */
    public static PathResult solve(Maze maze) {
        Cell start = maze.getStart();
        Cell end = maze.getEnd();

        if (start == null || end == null) {
            throw new IllegalStateException("迷宫未设置起点或终点");
        }

        int rows = maze.getRows();
        int cols = maze.getCols();

        // 距离数组：dist[r][c] 表示从起点到(r,c)的最短距离
        int[][] dist = new int[rows][cols];
        for (int[] row : dist) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        dist[start.getRow()][start.getCol()] = 0;

        // 前驱数组：用于回溯路径
        Cell[][] predecessor = new Cell[rows][cols];

        // 入队次数统计（用于检测负环，本文场景无负权，仅作计数）
        int[][] count = new int[rows][cols];

        // SPFA队列
        ArrayDeque<Cell> queue = new ArrayDeque<>();
        boolean[][] inQueue = new boolean[rows][cols];

        queue.offer(start);
        inQueue[start.getRow()][start.getCol()] = true;

        int relaxCount = 0;

        while (!queue.isEmpty()) {
            Cell u = queue.poll();
            inQueue[u.getRow()][u.getCol()] = false;

            // 遍历u的所有可通行邻接格子
            for (Cell v : u.getNeighbors(maze)) {
                if (!v.getTerrain().isPassable()) continue;

                int weight = maze.getMoveWeight(u, v);
                int newDist = dist[u.getRow()][u.getCol()] + weight;

                // 松弛操作
                if (newDist < dist[v.getRow()][v.getCol()]) {
                    dist[v.getRow()][v.getCol()] = newDist;
                    predecessor[v.getRow()][v.getCol()] = u;
                    relaxCount++;

                    if (!inQueue[v.getRow()][v.getCol()]) {
                        queue.offer(v);
                        inQueue[v.getRow()][v.getCol()] = true;
                        count[v.getRow()][v.getCol()]++;
                    }
                }
            }
        }

        // 检查终点是否可达
        if (dist[end.getRow()][end.getCol()] == Integer.MAX_VALUE) {
            return new PathResult(Collections.emptyList(), -1, relaxCount, false);
        }

        // 回溯构建路径
        List<Cell> path = new ArrayList<>();
        Cell current = end;
        while (current != null) {
            path.add(current);
            current = predecessor[current.getRow()][current.getCol()];
        }
        Collections.reverse(path);

        return new PathResult(path, dist[end.getRow()][end.getCol()], relaxCount, true);
    }

    /**
     * 对比测试：同时运行SPFA和BFS（BFS将所有权重视为1）
     * 展示带权路径与无权路径的差异
     */
    public static void compareWithBFS(Maze maze) {
        // SPFA结果
        PathResult spfaResult = solve(maze);
        System.out.println("SPFA最短路径：");
        System.out.println("  总权重: " + spfaResult.totalWeight);
        System.out.println("  步数: " + spfaResult.path.size());
        System.out.println("  松弛次数: " + spfaResult.relaxCount);

        // BFS结果（无权，所有边权重为1）
        PathResult bfsResult = solveUnweighted(maze);
        System.out.println("\nBFS最短路径（无权）：");
        System.out.println("  步数: " + bfsResult.path.size());

        if (spfaResult.path.size() != bfsResult.path.size()) {
            System.out.println("\n注意：带权最优路径与最少步数路径不同！");
            System.out.println("SPFA路径考虑了地形权重，可能步数更多但总代价更小。");
        }
    }

    /**
     * 无权BFS求解（所有移动权重视为1）
     */
    private static PathResult solveUnweighted(Maze maze) {
        Cell start = maze.getStart();
        Cell end = maze.getEnd();
        int rows = maze.getRows();
        int cols = maze.getCols();

        boolean[][] visited = new boolean[rows][cols];
        Cell[][] predecessor = new Cell[rows][cols];
        ArrayDeque<Cell> queue = new ArrayDeque<>();

        queue.offer(start);
        visited[start.getRow()][start.getCol()] = true;

        while (!queue.isEmpty()) {
            Cell u = queue.poll();
            if (u.equals(end)) break;

            for (Cell v : u.getNeighbors(maze)) {
                if (!v.getTerrain().isPassable()) continue;
                if (!visited[v.getRow()][v.getCol()]) {
                    visited[v.getRow()][v.getCol()] = true;
                    predecessor[v.getRow()][v.getCol()] = u;
                    queue.offer(v);
                }
            }
        }

        List<Cell> path = new ArrayList<>();
        Cell current = end;
        while (current != null) {
            path.add(current);
            current = predecessor[current.getRow()][current.getCol()];
        }
        Collections.reverse(path);

        return new PathResult(path, path.size() - 1, 0, !path.isEmpty());
    }
}

Main.java — 完整演示

import generator.RandomPrimGenerator;
import maze.*;
import solver.SPFASolver;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Random rand = new Random(42);
        int rows = 15;
        int cols = 25;

        System.out.println("=== 迷宫生成与SPFA最短路径求解演示 ===\n");

        // 1. 生成迷宫
        System.out.println("1. 使用随机Prim算法生成 " + rows + "x" + cols + " 迷宫...");
        RandomPrimGenerator generator = new RandomPrimGenerator(rand);
        Maze maze = generator.generate(rows, cols);

        // 2. 随机设置地形权重
        System.out.println("2. 随机设置地形（沼泽~权重5，草地\"权重2，石板=权重1）...");
        maze.randomizeTerrain(rand, 0.15, 0.30);

        // 3. 打印迷宫
        System.out.println("\n3. 生成的迷宫（S=起点, E=终点, #=墙, ~=沼泽, \"=草地, ==石板, *=路径）：");
        maze.printSimple(null);

        // 4. SPFA求解最短路径
        System.out.println("\n4. SPFA求解带权最短路径...");
        SPFASolver.PathResult result = SPFASolver.solve(maze);

        if (result.reachable) {
            System.out.println("   路径找到！总权重=" + result.totalWeight +
                "，步数=" + result.path.size() + "，松弛次数=" + result.relaxCount);

            // 5. 打印带路径的迷宫
            System.out.println("\n5. 带最优路径的迷宫：");
            maze.printSimple(result.path);

            // 6. 与BFS对比
            System.out.println("\n6. SPFA vs BFS对比：");
            SPFASolver.compareWithBFS(maze);
        } else {
            System.out.println("   警告：终点不可达！");
        }
    }
}

算法复杂度分析

在网格图中，V ≈ rows × cols，E ≈ 2V，因此：
– Prim生成：O(V log V) 实际运行时间
– SPFA：O(V) 平均情况，最坏O(V²)

总结

本文构建了一套完整的迷宫生成与求解算法体系：

1. 随机Prim生成：相比DFS回溯法，Prim生成的迷宫岔路更短、路径更曲折，趣味性更高；相比Kruskal，Prim是从单点向外扩展，生成的迷宫具有更强的”中心辐射”特征
2. 地形权重系统：在通道上引入沼泽、草地、石板等不同地形，使最短路径问题从单纯的”步数最少”升级为”总代价最小”，增加了策略深度
3. SPFA求解：在带权网格图上，SPFA利用队列优化避免了Bellman-Ford的冗余松弛，实际运行效率通常接近Dijkstra，且实现更简洁

该框架可进一步扩展：引入多起点/多终点、动态变化的迷宫（随时间改变地形权重）、或A*启发式搜索加速大规模迷宫的求解，为游戏开发提供坚实的算法基础。