我对迷宫生成的 Eller 算法的实现没有生成足够随机的迷宫。我做错了什么吗？

Question

它们基本上非常相似，只有细微差别，我遵循了我在网上找到的这个伪代码，（我理解算法本身，我在纸上试过了，它有效，我的代码也有效，但我只是对迷宫的相似程度不满意生成的） 伪代码：

1. 第一步：初始化第一行。
2. 第 2 步：对于该行中的每一列，如果它没有单元格， 创建一个并将其添加到自己的集合中。行中的每个单元格应该是 在这一点上的一部分。
3. 第三步：从左到右，如果当前单元格和下一个单元格 单元格在不同的集合中，随机决定连接到下一个 细胞。如果它们连接，则将单元格的集合合并在一起。
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;
    }
}

对不起，我的英语不好，我的问题也不好。

我在 System.nanotime() 的随机生成器中添加了一个种子，但没有别的。

Answer 1

问题似乎出在初始化

Random

的地方：

        for (int i = 0; i < this.r - 1; i++) {
            for (int j = 0; j < this.c - 1; j++) {
                Random rand = new Random(System.nanoTime());

这是为每个具有非常相似种子的细胞重新初始化随机生成器，使其随机性降低。相反，它应该在函数开始时初始化一次。

Answer 2

我发现出了什么问题，检查当前行中的每个单元格，如果该单元格属于一个只有 1 个元素的集合，或者如果该单元格属于一个与下一行没有连接的集合，那么您必须连接该单元格与其下方的单元格在下一行，否则您可以随机决定是否将当前单元格与其下方的单元格连接。所以为了实现我做了以下事情：

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;
                }
            }

我添加了一个标志变量叫 checkerBelow 并初始化为 0，如果为 0 则我们将当前单元格与其下方的单元格连接并将 checkerBelow 翻转为 1，否则我们随机决定是否将当前单元格与其下方的单元格连接在它下面。我还添加了另一个条件，（请注意，首先我检查我是否在最后一个单元格，如果我在，那么我无法将最后一个单元格与它之后的单元格在同一行中进行比较）如果当前单元格和之后的单元格它属于不同的集合，然后我会将 checkerBelow 翻转为 0，以确保下面的集合与下一行有连接。结果是一个真正随机的迷宫（这次我在 GUI 中显示了迷宫，而不是仅仅将它打印到终端） 例子一： 例子2：

再次为我的英语不好道歉，非常感谢评论区的好心人帮助我。开斋节！