javaalgorithmrandommaze

My implementation of Eller algorithm for maze generation doesn't generate random enough mazes. Am I doing something wrong?

They basically are extremely similar with just minor differences, I followed this pseudo-code I found online, (I understand the algorithm itself I tried it on paper and it works so does my code but I am just not satisfied with how similar the mazes generated are) Pseudo-code:

  1. Step 1: Initialize the first row.
  2. Step 2: For each column in that row, if it doesn't have a cell, create one and add it to its own set. Each cell in the row should be part of a set at this point.
  3. Step 3: Going from left to right, if the current cell and the next cell are in different sets, randomly decide to connect to the next cell. If they connect, merge the cells' sets together.
  4. Step 4: Initialize the next row. For each set in the current row, connect downward for at least one cell per set, adding that cell to the set it connected from.
  5. Step 5: Move to the next row and repeat steps 2 through 4.
  6. Step 6: When on the last row, repeat step 3 but remove the randomness, always connecting to the next cell if it's in a different set. Don't make any downward connections.

My code (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;
    }
}

These are 3 mazes generated by my implementation of the algorithm, note that I enlarge the grid to display both walls and paths so the maze size is (m2+1)(n2+1), first is 33 grid, 45, 6*4(all before enlarging) sorry for my poor english and bad presentation of my problem.

I added the new part to the code, it works well now.

Solution

  • I found what's wrong, check every cell in current row, if that cell belongs to a set that has only 1 element or if the cell belongs to a set that doesn't have a connection to the next row then you must connect that cell with the cell below it in the next row, otherwise you can randomly decide whether or not to connect the current cell with a cell below it. so to implement that I did the following:

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

    I added a flag variable called checkerBelow and initialize it to 0, if it is 0 then we connect the current cell with the cell below it and flip checkerBelow to 1, otherwise we randomly decide whether or not to connect the current cell with the cell below it. I also added another conditional,(note that first I check if I am at the last cell, if I am then I can't compare the last cell with the cell after it in the same row) if the current cell and the cell after it belong to different sets, then I will flip checkerBelow to 0, to make sure that the following set has connection to the next row. and the result is a truly randomized maze (I displayed the maze in a GUI this time instead of just printing it to the terminal) example 1:100x100 grid example 2:100x100 grid

    Again I apologize for my bad english , and thank you very much to the wonderful people in the comment section who helped me. Eid-Mubarak!