每日算法 — 使用java实现迷宫生成与求解：Wilson随机游走均匀生成与双向A*搜索

可莉爸爸 AI算法

引言

迷宫生成与路径求解是图论与搜索算法的经典应用场景。传统的DFS递归回溯算法虽然高效，但生成的迷宫存在明显的方向性偏好；Prim算法生成的迷宫分支较多但缺乏长线 corridors。本文引入Wilson随机游走算法，该算法基于循环消除随机游走，能够生成在统计意义上均匀随机的迷宫——即所有可能的生成树被采样的概率相等。同时，本文使用双向A*搜索进行求解，从起点和终点同时扩展搜索 frontier，显著减少 explored 节点数量。

核心算法原理

Wilson随机游走算法

Wilson算法是生成均匀随机生成树（Uniform Spanning Tree, UST）的经典算法，由David Wilson于1996年提出。其核心思想是循环消除随机游走（Loop-Erased Random Walk, LERW）：

  1. 从网格中随机选择一个已加入生成树的顶点集合$S$（初始可任选一个根节点）
  2. 从任意不在$S$中的顶点$u$出发，执行随机游走，直到命中$S$中的某个顶点
  3. 在游走过程中，如果路径形成循环，立即消除该循环（只保留循环首次到达的顶点之后的部分）
  4. 将消除循环后的路径加入生成树，路径上的所有顶点并入$S$
  5. 重复步骤2-4，直到所有顶点都加入$S$

Wilson算法的精妙之处在于：由LERW构建的生成树在数学上被证明是所有生成树上的均匀分布，不存在任何结构性偏向。

双向A*搜索

A搜索通过启发式函数$f(n) = g(n) + h(n)$指导搜索方向，其中$g(n)$为从起点到$n$的实际代价，$h(n)$为从$n$到终点的估计代价。双向A同时从起点和终点运行两个A*搜索，当两个 frontier 相交时即找到最优路径。

双向A*的关键在于：
– 正向搜索使用$h_1(n) = \text{Manhattan}(n, \text{goal})$
– 反向搜索使用$h_2(n) = \text{Manhattan}(n, \text{start})$
– 相遇条件：当某个节点被两个方向同时扩展时，路径 found
– 实际最优性保证：$f_{min} = \min(f_{forward}, f_{backward})$作为上界

Java实现

项目结构

src/
├── maze/
│   ├── Maze.java             // 迷宫数据结构
│   ├── WilsonGenerator.java  // Wilson生成算法
│   └── BidirectionalAStar.java // 双向A*求解
└── demo/
    └── MazeDemo.java         // 演示主程序

迷宫数据结构

package maze;

import java.util.*;

/**
 * 基于单元格墙的迷宫表示（单元格间有墙=不可通行，无墙=可通行）
 */
public class Maze {
    public static final int WALL = 1;
    public static final int PATH = 0;

    private final int rows, cols;
    private final int[][] grid;    // 奇数索引为单元格，偶数索引为墙
    private final Random rand;

    public Maze(int rows, int cols, long seed) {
        // 实际网格大小：单元格间夹墙
        this.rows = rows * 2 + 1;
        this.cols = cols * 2 + 1;
        this.grid = new int[this.rows][this.cols];
        this.rand = new Random(seed);
        // 初始化全部为墙
        for (int[] row : grid) Arrays.fill(row, WALL);
    }

    /**
     * 设置单元格为路径
     */
    public void setCell(int r, int c, int value) {
        grid[r * 2 + 1][c * 2 + 1] = value;
    }

    public int getCell(int r, int c) {
        return grid[r * 2 + 1][c * 2 + 1];
    }

    /**
     * 打通两个相邻单元格之间的墙
     */
    public void removeWall(int r1, int c1, int r2, int c2) {
        int wallR = (r1 + r2) + 1; // 因为单元格在grid中的行是 r*2+1
        int wallC = (c1 + c2) + 1;
        grid[wallR][wallC] = PATH;
    }

    public int getLogicalRows() { return (rows - 1) / 2; }
    public int getLogicalCols() { return (cols - 1) / 2; }
    public int[][] getGrid() { return grid; }
    public Random getRandom() { return rand; }

    /**
     * 打印迷宫到控制台
     */
    public void print() {
        for (int[] row : grid) {
            for (int cell : row) {
                System.out.print(cell == WALL ? "██" : "  ");
            }
            System.out.println();
        }
    }
}

Wilson随机游走生成器

package maze;

import java.util.*;

/**
 * Wilson随机游走算法生成均匀随机迷宫
 */
public class WilsonGenerator {

    /**
     * 生成迷宫主方法
     */
    public static void generate(Maze maze) {
        int rows = maze.getLogicalRows();
        int cols = maze.getLogicalCols();
        Random rand = maze.getRandom();

        // 所有单元格的坐标集合
        Set<String> allCells = new HashSet<>();
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                allCells.add(r + "," + c);
                maze.setCell(r, c, Maze.PATH); // 先标记所有单元格为路径
            }
        }

        // 已加入生成树的集合
        Set<String> inTree = new HashSet<>();

        // 随机选择根节点
        int rootR = rand.nextInt(rows);
        int rootC = rand.nextInt(cols);
        inTree.add(rootR + "," + rootC);

        // 逐步将其他节点加入生成树
        while (inTree.size() < rows * cols) {
            // 选择一个不在树中的起始点
            String start = null;
            for (String cell : allCells) {
                if (!inTree.contains(cell)) {
                    start = cell;
                    break;
                }
            }
            if (start == null) break;

            String[] parts = start.split(",");
            int curR = Integer.parseInt(parts[0]);
            int curC = Integer.parseInt(parts[1]);

            // 执行循环消除随机游走
            List<String> path = loopErasedRandomWalk(curR, curC, inTree, rows, cols, rand);

            // 将路径加入生成树
            for (int i = 0; i < path.size() - 1; i++) {
                String[] p1 = path.get(i).split(",");
                String[] p2 = path.get(i + 1).split(",");
                int r1 = Integer.parseInt(p1[0]), c1 = Integer.parseInt(p1[1]);
                int r2 = Integer.parseInt(p2[0]), c2 = Integer.parseInt(p2[1]);

                maze.removeWall(r1, c1, r2, c2);
                inTree.add(path.get(i));
            }
            inTree.add(path.get(path.size() - 1));
        }
    }

    /**
     * 循环消除随机游走：从起点出发随机游走，直到命中树中节点，期间消除所有循环
     */
    private static List<String> loopErasedRandomWalk(int startR, int startC,
                                                      Set<String> inTree,
                                                      int rows, int cols,
                                                      Random rand) {
        // 记录访问顺序，用于检测循环
        Map<String, Integer> visitIndex = new HashMap<>();
        List<String> path = new ArrayList<>();

        int curR = startR, curC = startC;
        String key = curR + "," + curC;
        visitIndex.put(key, 0);
        path.add(key);

        while (!inTree.contains(key)) {
            // 获取所有合法邻居
            List<int[]> neighbors = new ArrayList<>();
            int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
            for (int[] d : dirs) {
                int nr = curR + d[0], nc = curC + d[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
                    neighbors.add(new int[]{nr, nc});
                }
            }

            // 随机选择邻居
            int[] next = neighbors.get(rand.nextInt(neighbors.size()));
            curR = next[0];
            curC = next[1];
            key = curR + "," + curC;

            if (visitIndex.containsKey(key)) {
                // 检测到循环！消除循环部分
                int loopStart = visitIndex.get(key);
                // 移除loopStart之后的所有节点
                while (path.size() > loopStart + 1) {
                    String removed = path.remove(path.size() - 1);
                    visitIndex.remove(removed);
                }
            } else {
                visitIndex.put(key, path.size());
                path.add(key);
            }
        }

        return path;
    }
}

双向A*求解器

package maze;

import java.util.*;

/**
 * 双向A*搜索求解迷宫最短路径
 */
public class BidirectionalAStar {

    private static class Node {
        int r, c;
        double g, f;
        Node parent;

        Node(int r, int c, double g, double h, Node parent) {
            this.r = r; this.c = c; this.g = g;
            this.f = g + h;
            this.parent = parent;
        }
    }

    /**
     * 求解从起点到终点的最短路径
     * @return 路径上的坐标列表，若无解返回空列表
     */
    public static List<int[]> solve(Maze maze, int startR, int startC, int goalR, int goalC) {
        int rows = maze.getLogicalRows();
        int cols = maze.getLogicalCols();

        // 正向搜索：起点 -> 终点
        PriorityQueue<Node> openForward = new PriorityQueue<>(Comparator.comparingDouble(n -> n.f));
        // 反向搜索：终点 -> 起点
        PriorityQueue<Node> openBackward = new PriorityQueue<>(Comparator.comparingDouble(n -> n.f));

        boolean[][] closedForward = new boolean[rows][cols];
        boolean[][] closedBackward = new boolean[rows][cols];

        Node[][] nodesForward = new Node[rows][cols];
        Node[][] nodesBackward = new Node[rows][cols];

        Node startNode = new Node(startR, startC, 0, heuristic(startR, startC, goalR, goalC), null);
        Node goalNode = new Node(goalR, goalC, 0, heuristic(goalR, goalC, startR, startC), null);

        openForward.add(startNode);
        openBackward.add(goalNode);
        nodesForward[startR][startC] = startNode;
        nodesBackward[goalR][goalC] = goalNode;

        Node meetingForward = null, meetingBackward = null;
        double bestPathLen = Double.MAX_VALUE;

        while (!openForward.isEmpty() && !openBackward.isEmpty()) {
            // 选择 frontier 较小的一方进行扩展
            if (openForward.peek().f <= openBackward.peek().f) {
                Node current = openForward.poll();
                if (closedForward[current.r][current.c]) continue;
                closedForward[current.r][current.c] = true;

                // 检查是否与反向搜索相遇
                if (nodesBackward[current.r][current.c] != null) {
                    double total = current.g + nodesBackward[current.r][current.c].g;
                    if (total < bestPathLen) {
                        bestPathLen = total;
                        meetingForward = current;
                        meetingBackward = nodesBackward[current.r][current.c];
                    }
                }

                expand(maze, current, openForward, closedForward, nodesForward, goalR, goalC, true);
            } else {
                Node current = openBackward.poll();
                if (closedBackward[current.r][current.c]) continue;
                closedBackward[current.r][current.c] = true;

                // 检查是否与正向搜索相遇
                if (nodesForward[current.r][current.c] != null) {
                    double total = current.g + nodesForward[current.r][current.c].g;
                    if (total < bestPathLen) {
                        bestPathLen = total;
                        meetingForward = nodesForward[current.r][current.c];
                        meetingBackward = current;
                    }
                }

                expand(maze, current, openBackward, closedBackward, nodesBackward, startR, startC, false);
            }

            // 当两个 frontier 的最小f值之和 >= 当前最优路径时停止
            if (meetingForward != null &&
                openForward.peek().f + openBackward.peek().f >= bestPathLen) {
                break;
            }
        }

        if (meetingForward == null) return Collections.emptyList();
        return reconstructPath(meetingForward, meetingBackward);
    }

    /**
     * 扩展节点邻居
     */
    private static void expand(Maze maze, Node current,
                               PriorityQueue<Node> open, boolean[][] closed,
                               Node[][] nodes, int targetR, int targetC,
                               boolean isForward) {
        int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
        for (int[] d : dirs) {
            int nr = current.r + d[0];
            int nc = current.c + d[1];

            // 检查是否可通行（通过墙检测）
            if (!isPassable(maze, current.r, current.c, nr, nc)) continue;
            if (nr < 0 || nr >= maze.getLogicalRows() || nc < 0 || nc >= maze.getLogicalCols()) continue;
            if (closed[nr][nc]) continue;

            double newG = current.g + 1;
            double h = heuristic(nr, nc, targetR, targetC);

            if (nodes[nr][nc] == null || newG < nodes[nr][nc].g) {
                Node neighbor = new Node(nr, nc, newG, h, current);
                nodes[nr][nc] = neighbor;
                open.add(neighbor);
            }
        }
    }

    /**
     * 检查两个逻辑单元格之间是否可通行
     */
    private static boolean isPassable(Maze maze, int r1, int c1, int r2, int c2) {
        int[][] grid = maze.getGrid();
        int wallR = (r1 + r2) + 1;
        int wallC = (c1 + c2) + 1;
        return grid[wallR][wallC] == Maze.PATH;
    }

    private static double heuristic(int r1, int c1, int r2, int c2) {
        return Math.abs(r1 - r2) + Math.abs(c1 - c2); // Manhattan距离
    }

    /**
     * 从相遇点双向回溯重建路径
     */
    private static List<int[]> reconstructPath(Node forward, Node backward) {
        List<int[]> path = new ArrayList<>();
        // 正向路径：从起点到相遇点
        Node curr = forward;
        while (curr != null) {
            path.add(0, new int[]{curr.r, curr.c});
            curr = curr.parent;
        }
        // 反向路径：从相遇点的父节点到终点
        curr = backward.parent;
        while (curr != null) {
            path.add(new int[]{curr.r, curr.c});
            curr = curr.parent;
        }
        return path;
    }
}

演示主程序

package demo;

import maze.Maze;
import maze.WilsonGenerator;
import maze.BidirectionalAStar;
import java.util.List;

/**
 * 迷宫生成与求解演示
 */
public class MazeDemo {
    public static void main(String[] args) {
        final int ROWS = 15;
        final int COLS = 25;

        // 使用Wilson算法生成均匀随机迷宫
        Maze maze = new Maze(ROWS, COLS, 42L);
        WilsonGenerator.generate(maze);

        System.out.println("=== Wilson Uniform Random Maze ===");
        maze.print();

        // 使用双向A*求解
        int startR = 0, startC = 0;
        int goalR = ROWS - 1, goalC = COLS - 1;
        List<int[]> path = BidirectionalAStar.solve(maze, startR, startC, goalR, goalC);

        System.out.println("\n=== Bidirectional A* Path ===");
        System.out.println("Path length: " + path.size());
        for (int[] p : path) {
            System.out.printf("(%d,%d) -> ", p[0], p[1]);
        }
        System.out.println("END");
    }
}

算法复杂度分析

Wilson生成算法

指标 复杂度 说明
期望时间 $O(N \cdot \tau)$ $N$为单元格数，$\tau$为命中时间（与图结构相关）
最坏时间 $O(N^3)$ 每次LERW可能遍历大量节点
空间 $O(N)$ 存储路径与访问标记

对于$R \times C$的矩形网格，Wilson算法的期望运行时间为$O(N \cdot \log N)$，其中$N = R \times C$。虽然比DFS的$O(N)$慢，但生成的迷宫在统计性质上更优。

双向A*搜索

指标 复杂度 说明
时间 $O(b^{d/2})$ $b$为分支因子，$d$为最优路径长度
单向A* $O(b^d)$ 双向搜索理论上减少指数级节点
空间 $O(b^{d/2})$ 存储两个 frontier

算法对比

生成算法 时间复杂度 均匀性 长走廊比例 实现难度
DFS递归回溯 $O(N)$ 差（有偏） 高 简单
Prim算法 $O(N \log N)$ 较差 低 中等
Kruskal算法 $O(N \log N)$ 中等 中等 中等
Wilson算法 $O(N \log N)$ 完美均匀 中等 中等

扩展方向

  1. Aldous-Broder算法：另一种UST生成算法，基于简单随机游走（无需循环消除），实现更简单但运行时间$O(N \cdot \tau_{hit})$通常更长。
  2. 增量A（D Lite）：动态环境下（迷宫部分变化）高效重新规划路径。
  3. 多Agent路径规划：在迷宫中协调多个智能体的无冲突路径。
  4. 三维迷宫扩展：将算法推广到三维网格，用于洞穴生成或建筑布局。

总结

本文使用Java实现了Wilson随机游走迷宫生成算法与双向A求解算法。Wilson算法通过循环消除随机游走保证了生成树在所有可能生成树上的均匀分布，消除了传统算法的结构性偏向。双向A则从两个方向同时搜索，将时间复杂度从$O(b^d)$降低到$O(b^{d/2})$，是求解大规模迷宫的高效策略。两者结合，为迷宫生成与求解提供了一套既理论严谨又工程实用的解决方案。

Tagged with: