Maze Generation - Kruskal's Algorithm

https://courses.cs.washington.edu/courses/cse326/07su/prj2/kruskal.html

http://codehowtos.blogspot.com/2011/04/building-maze.html
Now, lets think of a maze as a grid of cells. For cells X and Y, you can reach from X to Y through the winding maze if there is a continuous route without walls between the two. So, lets start with a maze in which each cell has all its 4 walls built. The goal is to get a maze in which there is exactly 1 way to get from any cell X to any cell Y. Now lets add the data structure into the image. We start with a Disjoint-set that has a group for each of the cells. Each turn we destroy a wall between 2 cells that belong to different groups. This way we open exactly 1 passage between each of the cells in one group to each in the other. We know we've finished when there is exactly one group in the set.

For those who like algorithms, this is actually an implementation of the Kruskal algorithm for finding Minimal Spanning Trees in graphs (if you take the grid cells as vertices and the walls as edges).
You can read more here: http://en.wikipedia.org/wiki/Kruskal%27s_algorithm
or you can look at some boos here: Books on Algorithms on Amazon

Maze createRandomMaze(int rows, int columns) { Maze maze = new Maze(rows, columns); // create all walls List<Wall> walls = maze.getAllInnerWalls(); // remove all the walls you can DisjointSet diset = new DisjointSet(rows*columns); while (diset.size() > 1) { int wallIndex = random.nextInt(walls.size()); int cell1 = walls.get(wallIndex).cell1; int cell2 = walls.get(wallIndex).cell2; if (diset.find(cell1) != diset.find(cell2)) { // we can remove the wall maze.removeWall(walls.get(wallIndex)); diset.join(cell1, cell2); } walls.remove(wallIndex); } return maze; }
http://www.algostructure.com/specials/maze.php

This algorithm is a randomized version of Kruskal's algorithm.

1. Create a list of all walls, and create a set for each cell, each containing just that one cell.
2. For each wall, in some random order:
   1. If the cells divided by this wall belong to distinct sets:
      1. Remove the current wall.
      2. Join the sets of the formerly divided cells.

There are several data structures that can be used to model the sets of cells. An efficient implementation using a disjoint-set data structure can perform each union and find operation on two sets in nearly constant amortized time, so the running time of this algorithm is essentially proportional to the number of walls available to the maze.

It matters little whether the list of walls is initially randomized or if a wall is randomly chosen from a nonrandom list, either way is just as easy to code.

https://github.com/njrahman/Maze/blob/master/src/generation/MazeBuilderKruskal.java

 protected void generatePathways() {
  board = new int[width][height];
  int counter = 1;       
  
  for (int i = 0; i < width; i++){  //creates a 2d array and fills it with unique numbers for each index
   for (int j = 0; j < height; j++){
    board[i][j] = counter;
    counter++;
   }
  }
 
  final ArrayList<Wall> candidates = new ArrayList<Wall>(); //creates an array list because the number of walls changes with difficulty so the list may need to expand
  createListOfWalls(candidates);         // fills array list using the method
  
  while(!candidates.isEmpty()){     // While the list of walls is not empty                                              
   
   Wall currWall = extractWallFromCandidateSetRandomly(candidates); // grab a random wall
   int currX = currWall.getX();                                     // grab that wall's x coordinate
   int currY = currWall.getY();                                     // grab that wall's y coordinate
   int neighX = currWall.getNeighborX();                            // grab neighbor's x coordinate
   int neighY = currWall.getNeighborY();        // grab neighbor's y coordinate
   
   if (neighX >= 0 && neighY >= 0 && neighX < width && neighY < height){   // makes sure that the neighbor is in bounds
    if (board[currX][currY] != board[neighX][neighY]){                  // if the values of the current index and its neighbor are not equal
     changeNeighborValue(currWall, currX, currY, neighX, neighY);  // then update the neighbor's value to that of the current index
    }
   }
  }
 }
 
 /**
  * This method takes in the coordinates of a wall and its neighbor, deletes the wall
  * and then updates the board array so that the neighbor and all indices in the array
  * with the same value as the neighbor are changed to the value of the current index.
  * 
  * 
  * @param wall
  * @param currX
  * @param currY
  * @param neighX
  * @param neighY
  */
 private void changeNeighborValue(Wall wall, int currX, int currY, int neighX, int neighY){ // the integer values are passed because if you take them after the deletion of the wall then they change
  
  cells.deleteWall(wall); // self explanatory(deletes from both sides)
  
  int current = board[currX][currY];   //stores indices,
  int neighbor = board[neighX][neighY];
  
  for (int i = 0; i < width; i++){  // for all of the indices with the value of the neighbor, it changes them to the value of the current
   for (int j = 0; j < height; j++){
    if (board[i][j] == neighbor){
     board[i][j] = current;
    }
   }
  }
 }
  
 /**
  * Pick a random position in the list of candidates, remove the candidate from the list and return it
  * @param candidates
  * @return candidate from the list, randomly chosen
  */
 private Wall extractWallFromCandidateSetRandomly(ArrayList<Wall> candidates) {
  return candidates.remove(random.nextIntWithinInterval(0, candidates.size()-1)); 
 }
 /**
  * Simply goes through all the walls in the maze and adds them to a list if they are not borders.
  * @param walls
  */
 private void createListOfWalls(ArrayList<Wall> walls) {
  
  for (int i = 0; i < width; i++){
   for (int j = 0; j < height; j++){
    for (CardinalDirection cd : CardinalDirection.values()) {
     Wall wall = new Wall(i, j, cd);
     if (cells.canBreak(wall)){        // If the wall is not a border, it is added to the list
      walls.add(wall);
     }
    }
   }
  }
 }

https://github.com/njrahman/Maze/blob/master/src/generation/Wall.java

https://weblog.jamisbuck.org/2011/1/3/maze-generation-kruskal-s-algorithm.html

Kruskal’s algorithm is a method for producing a minimal spanning tree from a weighted graph. The algorithm I’ll cover here is actually a randomized version of Kruskal’s; the original works something like this:

1. Throw all of the edges in the graph into a big burlap sack. (Or, you know, a set or something.)
2. Pull out the edge with the lowest weight. If the edge connects two disjoint trees, join the trees. Otherwise, throw that edge away.
3. Repeat until there are no more edges left.

The randomized algorithm just changes the second step, so that instead of pulling out the edge with the lowest weight, you remove an edge from the bag at random. Making that change, the algorithm now produces a fairly convincing maze.

Let’s walk through an example manually, to see how the process works in practice.

An example

For this example, I’ll use a simple 3×3 grid. I’ve assigned each cell a letter, indicating which set it belongs to.

A	B	C
D	E	F
G	H	I

The algorithm is straightforward: simply select an edge at random, and join the cells it connects if they are not already connected by a path. We can know if the cells are already connected if they are in the same set. So, let’s choose the edge between (2,2) and (2,3). The cells are in different sets, so we join the two into a single set and connect the cells:

A	B	C
D	E	F
G	E	I

Let’s do a few more passes of the algorithm, to get to the interesting part:

A A C D E F G E I

A A C D E C G E I

A A C D E C G E E

A A C D E C E E E

Here’s where things start to move fast. Note what happens when the edge between (2,1) and (2,2) is pulled from the bag:

A	A	C
D	A	C
A	A	A

The two trees, A and E, were joined into one set, A, implying that any cell in A is reachable from any other cell in A. Let’s try joining (1,2) and (1,3) now:

A	A	C
A	A	C
A	A	A

Now, consider the edges (1,1)–(1,2) and (1,2)–(2,2). Neither of these has been drawn from the bag yet. What would happen if one of them were? Well, in both cases, the cells on either side of the edge belong to the same set. Connecting the cells in either case would result in a cycle, so we discard the edge and try again.

After a one more pass, we’ll have:

A	A	A
A	A	A
A	A	A

The algorithm finishes when there are no more edges to consider (which, in this case, is when there is only a single set left). And the result is a perfect maze!

Implementation

Implementing Kruskal’s algorithm is straightforward, but for best results you need to find a very efficient way to join sets. If you do it like I illustrated above, assigning a set identifier to each cell, you’ll need to iterate on every merge, which will be expensive. Using trees to represent the sets is much faster, allowing you to merge sets efficiently simply by adding one tree as a subtree of the other. Testing whether two cells share a set is done by comparing the roots of their corresponding trees.

Once you have the tree data structure, the algorithm is extremely straightforward. Begin by initializing the grid (which will represent the maze itself), and the sets (one per cell):

1 2	grid = Array.new(height) { Array.new(width, 0) } sets = Array.new(height) { Array.new(width) { Tree.new } }

Note that it would probably be more efficient to join the two representations, but I’ve split them apart for clarity.

Then, build the list of edges. Here I’m representing each edge as one of its end-points, and a direction: