How to implement a maze using disjoint sets?

Question

Here's the DisjointSet class i use :

public class DisjointSet{
    public DisjointSet(int size){
        s = new int[size];
        for(int i = 0; i < size; ++i){
            s[i] = -1;
        }
    }

    public void union(int el1, int el2){
        int root1 = find(el1);
        int root2 = find(el2);
        if(root1 == root2){
            return;
        }

        if(s[root2] < s[root1]){
            s[root1] = root2;
        }
        else{
            if(s[root1] == s[root2]){
                --s[root1];
            }
            s[root2] = root1;
        }
    }

    public int find(int x){
        if(s[x] < 0){
            return x;
        }
        else{
            s[x] = find(s[x]);
            return s[x];
        }
    }

    private int[] s;
}

And here's my Maze class :

public class Maze
{
    public Vector<Wall> maze;
    public Vector<Room> graph;
    public Vector<Integer> path;

    public int LASTROOM;
    public int height;
    public int width;
    public Random generator;
    public DisjointSet ds;

    public int dsSize;

    public Maze(int w, int h, int seed)
    {
        width = w;
        height = h;
        dsSize = width * height;

        LASTROOM = dsSize-1;

        // Maze initialization with all walls
        maze = new Vector<Wall>();
        for(int i = 0; i < height; ++i)
        {
            for(int j = 0; j < width; ++j)
            {
                if(i > 0)
                    maze.add(new Wall(j+i*height, j+(i-1)*height));

                if(j > 0)
                    maze.add(new Wall(j+i*height, j-1+i*height));
            }
        }

        // Creation of the graph topology of the maze
        graph = new Vector<Room>();
        for(int i = 0; i < dsSize; ++i)
            graph.add(new Room(i));

        // Sort the walls of random way
        generator = new Random(seed);

        for(int i = 0; i < maze.size(); ++i)
        {
            //TODO
        }

        // Initialization of related structures
        ds = new DisjointSet(dsSize);
        path = new Vector<Integer>();
    }

    public void generate()
    {
        //TODO
    }

    public void solve()
    {
        //TODO
    }
}

I've been looking for a way to implement generate() and solve() along with the random sorting of the maze's walls for a long time now, and I can't seem to find any algorithm or implementation on the Internet to do this.

generate() should go through the permuted walls in the maze variable and destroy it if the two parts (rooms) connected by the wall are not already in the same set. The method should also add an edge in the room graph (each room has a list of adjacency named paths and the Room class has a variable id that identifies each graph's vertices).

solve() should solve the maze path and generate the vector of the Maze class containing the order of the rooms to go through to get to the exit. The first room is positionned at 0 and the last room is positionned at LASTROOM.

Note: Maze and Room constructors are as follow:

public Wall(int r1, int r2)
{
    room1 = r1;
    room2 = r2;
}

public Room(int i)
{
    id = i;
    distance = -1;
    paths = new Vector<Integer>();
}

If someone would be kind enough to suggest an implementation that would work in Java, I would greatly appreciate it, thank you.

Answer 1

First off, I really like the idea of mazes and have been working on a similar project in Java with generating Torus Mazes.

To generate your maze, you need to look at this key sentence:

... each room has a list of adjacency named paths and the Room class has a variable id that identifies each graph's vertices

What does this tell us? It tells us the data structure we need! When you are dealing with problems such as this; adjacent vectors connected by edges, you are undoubtedly going to be creating an adjacency list.

There are a few different ways that you can go about doing this, but by far the easiest (and arguably most efficient in this case), is to create an array of linked lists. This is an adjacency list that I created without using built-in structures from the Java libraries, but the same logic can be used if you choose to use the LinkedList<> built-in.

/*
 * The Node class creates individual elements that populate the 
 * List class. Contains indexes of the node's neighbors and their
 * respective edge weights
 */
class Node {
    public int top;
    public int topWeight;
    public int bottom;
    public int bottomWeight;
    public int left;
    public int leftWeight;
    public int right;
    public int rightWeight;
    public int numConnec;

    // Default constructor, ititializes neghbors to -1 by default and edge
    // weights to 0
    Node () {
        top    = -1;
        right  = -1;
        bottom = -1;
        left   = -1;
    }
} // End Node class


/*
 * The List class contains Nodes, which are linked to one another
 * to create a Linked List. Used as an adjacency list in the
 * UnionFind class
 */
 class List {
    public Node neighbors;

    // Default constructor
    List () {
        neighbors = new Node ();
    }

    /**
     * Generates valid edges for the node, also assigns a randomly generated weight to that edge
     * @param i         The row that the node exists on, used to generate outer-node edges
     * @param j         The index of the node in the maze from 0 to (2^p)^2 - 1
     * @param twoP      Represents the dimensions of the maze, used in calculating valid edges
     * @param choice    Randomly generated number to choose which edge to generate
     * @param weight    Randomly generated number to assign generated edge a weight
     * @return          If the assignment was done correctly, returns true. Else returns false.
     */
    public boolean validEdges (int i, int j, int twoP, int choice, int weight) {
        if (neighbors.numConnec < 4) {
            // Top
            if (choice == 0) {
                neighbors.top = generateTop(i, j, twoP);
                neighbors.topWeight = weight;
                neighbors.numConnec++;
            }

            // Right
            else if (choice == 1) {
                neighbors.right = generateRight(i, j, twoP);
                neighbors.rightWeight = weight;
                neighbors.numConnec++;
            }

            // Bottom
            else if (choice == 2) {
                neighbors.bottom = generateBottom(i, j, twoP);
                neighbors.bottomWeight = weight;
                neighbors.numConnec++;
            }

            // Left
            else if (choice == 3) {
                neighbors.left = generateLeft(i, j, twoP);
                neighbors.leftWeight = weight;
                neighbors.numConnec++;
            }
        }
        else {
            return false;
        }
        return true;
    }

    public int generateTop (int i, int j, int twoP) {
        int neighbor = 0;

        // Set the top neighbor
        if (i == 0) {
            neighbor = j + twoP * (twoP + (-1));
        }
        else {
            neighbor = j + (-twoP);
        }
        return neighbor;
    }

    public int generateRight (int i, int j, int twoP) {
        int neighbor = 0;

        // Set the right neighbor
        if (j == twoP * (i + 1) + (-1)) {
            neighbor = twoP * i;
        }
        else {
            neighbor = j + 1;
        }
        return neighbor;
    }

    public int generateBottom (int i, int j, int twoP) {
        int neighbor = 0;

        // Set the bottom neighbor
        if (i == twoP + (-1)) {
            neighbor = j - twoP * (twoP + (-1));
        }
        else {
            neighbor = j + twoP;
        }
        return neighbor;
    }

    public int generateLeft (int i, int j, int twoP) {
        int neighbor = 0;

        // Set the left neighbor
        if (j == twoP * i) {
            neighbor = twoP * (i + 1) + (-1);
        }
        else {
            neighbor = j + (-1);
        }
        return neighbor;
    }
} // End List class

To solve the maze, this sounds like a problem that an implementation of Dijkstra's Algorithm could tackle.

Dijkstra's works by starting at your first node to create the known set. You then identify the shortest path to the next edge and add that node to the known set. Each time you do look for the next shortest path, you add the distance traveled from the first node.

This process continues until all nodes are in the known set and the shortest path to your goal has been calculated.

Shortest Paths