Eller算法迷宫生成实现随机性不足问题排查与解决

我依据网上获取的Eller算法伪代码实现了Java版本的迷宫生成程序，已理解算法逻辑且通过纸面验证确认算法可行，程序可正常运行，但生成的迷宫相似度极高，随机性未达预期。

参考伪代码 #

1. 步骤1：初始化第一行。
2. 步骤2：遍历该行的每一列，若该列无单元格则创建一个并将其加入自身集合，确保该行每个单元格均属于一个集合。
3. 步骤3：从左到右遍历，若当前单元格与下一个单元格属于不同集合，则随机决定是否连接二者；若连接则合并两个集合。
4. 步骤4：初始化下一行，针对当前行的每个集合，至少向下连接一个单元格，并将该单元格加入原集合。
5. 步骤5：移动到下一行，重复步骤2至步骤4。
6. 步骤6：处理最后一行时，重复步骤3但移除随机性，若当前单元格与下一个单元格属于不同集合则始终连接，不建立向下连接。

Java实现代码 #

import java.util.*;

public class MazeGeneratorEller {
    private int[][] grid; // The grid representing the maze
    private int[] tiles; // The tiles used to represent walls and paths
    private int r; // The number of rows in the maze
    private int c; // The number of columns in the maze
    private int[] disjointedSet; // The disjoint set data structure used to keep track of connected components

    public MazeGeneratorEller(int m, int n, int[] tile) {
        this.r = m;
        this.c = n;
        this.grid = new int[m * 2 + 1][n * 2 + 1];
        this.tiles = tile.clone();
        this.disjointedSet = new int[m * n];
        Arrays.fill(this.disjointedSet, -1);
    }

    class Vertex {
        int x;
        int y;

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

        public String toString() {
            return "(" + this.x + "," + this.y + ")";
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == null || this.getClass() != obj.getClass())
                return false;
            if (this == obj)
                return true;
            Vertex test = (Vertex) obj;
            return this.x == test.x && this.y == test.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(this.x, this.y);
        }
    }

    class Edge {
        Vertex from;
        Vertex to;

        Edge(Vertex x, Vertex y) {
            this.from = x;
            this.to = y;
        }

        public String toString() {
            return this.from + "<->" + this.to;
        }
    }

    HashMap<Vertex, Integer> map = new HashMap<Vertex, Integer>();
    ArrayList<Edge> solution = new ArrayList<Edge>();

    // Adds all the vertices to the map
    private void addVertices() {
        int index = 0;
        for (int i = 0; i < this.r; i++) {
            for (int j = 0; j < this.c; j++)
                this.map.put(new Vertex(i, j), index++);
        }
    }

    // Finds the root of the disjoint set that f belongs to
    private int find(int f) {
        if (this.disjointedSet[f] < 0) {
            return f;
        } else {
            this.disjointedSet[f] = find(this.disjointedSet[f]);
            return this.disjointedSet[f];
        }
    }

    // Merges the disjoint sets that the two vertices of the edge belong to
    private void union(Edge e) {
        int x = find(this.map.get(e.from));
        int y = find(this.map.get(e.to));
        if (x != y) {
            this.solution.add(e);
            if (this.disjointedSet[x] <= this.disjointedSet[y]) {
                this.disjointedSet[x] += this.disjointedSet[y];
                this.disjointedSet[y] = x;
            } else {
                this.disjointedSet[y] += this.disjointedSet[x];
                this.disjointedSet[x] = y;
            }
        }
    }

    // Generates the maze
    public int[][] generateMaze() {
        addVertices();
        for (int i = 0; i < this.r - 1; i++) {
            for (int j = 0; j < this.c - 1; j++) {
                Random rand = new Random(System.nanoTime());
                Vertex k = new Vertex(i, j);
                if (find(this.map.get(k)) == find(this.map.get(new Vertex(i, j + 1))))
                    continue;
                int choose = rand.nextInt(4);
                if (choose == 1)
                    union(new Edge(k, new Vertex(i, j + 1)));
            }
//start of new part
            int checkerBelow = 0;
            for (int j = 0; j < this.c; j++) {
                if (checkerBelow == 0) {
                    union(new Edge(new Vertex(i, j), new Vertex(i + 1, j)));
                    checkerBelow = 1;
                } else {
                    int choose = rand.nextInt(2);
                    if (choose == 1) {
                        union(new Edge(new Vertex(i, j), new Vertex(i + 1, j)));
                    }
                }
                if (j == this.c - 1)
                    continue;
                if (find(this.map.get(new Vertex(i, j))) != find(this.map.get(new Vertex(i, j + 1)))) {
                    checkerBelow = 0;
                }
            }
//end of new part
        }
        for (int j = 0; j < this.c - 1; j++) {
            union(new Edge(new Vertex(this.r - 1, j), new Vertex(this.r - 1, j + 1)));
        }//The algorithm ends here. The rest is just filling the grid.
        // Fill the grid array with walls and paths
        for (int i = 0; i < this.grid.length; i++)
            Arrays.fill(this.grid[i], this.tiles[1]);
        for (Edge e : this.solution) {
            int x1 = e.from.x * 2 + 1;
            int y1 = e.from.y * 2 + 1;
            int x2 = e.to.x * 2 + 1;
            int y2 = e.to.y * 2 + 1;
            this.grid[x1][y1] = this.tiles[0];
            this.grid[x2][y2] = this.tiles[0];
            this.grid[(x1 + x2) / 2][(y1 + y2) / 2] = this.tiles[0];
        }
        return this.grid;
    }
}

迷宫生成效果 #

生成的3个迷宫示例（注：为显示墙壁与路径，网格已放大，原始迷宫尺寸分别为33、45、6*4）：

问题解决 #

目前已新增代码片段，问题已解决。

内容的提问来源于stack exchange，提问作者ambolakabloa