Write a program that generates mazes of arbitrary size using the union-find algo

Question

Write a program that generates mazes of arbitrary size using the union-find algorithm. A simple algorithm to generate the maze is to start by creating an N times M grid of cells separated by walls on all sides, except for entrance and exit. Then continually choose a wall randomly, and knock it down if the cells are not already connected to each other. If we repeat the process until the starting and ending cells are connected, we have a maze. It is better to continue knocking down the walls until every cell is reachable from every cell as this would generate more false leads in the maze. Test you algorithm by creating a 10 times 10 grid and print all the walls that have been knocked down. Draw the resulting maze (hand-drawing is acceptable)

Explanation / Answer

Ans:Maze creation using union finde algorithm:

// disjoint class

public class DisjointSet {

// size array

private int[] set;

private int[] sizes;

private int size;

public DisjointSet(int size) {

  

this.set = new int[size];

// loop starts

for (int i = 0; i < size; i++) { this.set[i] = i; }

this.sizes = new int[size];

for (int i = 0; i < size; i++) { this.sizes[i] = 1; }

this.size = size;

}

// finds

public int find(int item) {

int root = item;

// for finding the root

while (set[root] != root) {

root = set[root];

}

//shortens the paths

int curr = item;

while (set[curr] != root) {

set[curr] = root;

}

return root;

}

// joins

public int join(int item1, int item2) {

int group1 = find(item1);

int group2 = find(item2);

// decrement the size

--size;

// condition for sizes

if (sizes[group1] > sizes[group2]) {

// group 1

set[group2] = group1;

// group1 plus group n2

sizes[group1] += sizes[group2];

// returns group 1

return group1;

// if not then

} else {

set[group1] = group2;

sizes[group2] += sizes[group1];   

return group2;

}

}

}

  

// maze creation class

Maze createRandomMaze(int rows, int columns) {

  

Maze maze = new Maze(rows, columns);

// walls creation

List<Wall> walls = maze.getAllInnerWalls();

// for rem oving walls

// diset should be disjoint of rows*columns

DisjointSet diset = new DisjointSet(rows*columns);

// size greater than 1

while (diset.size() > 1) {

// wallindex

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)) {

//

maze.removeWall(walls.get(wallIndex));

diset.join(cell1, cell2);

}

walls.remove(wallIndex);

}

return maze;

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.