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

Question

Write a program that generates mazes of arbitrary using the union-find algorithm. A simple algorithm size 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

/* Maze.java */ import java.util.*; import set.*; /** * The Maze class represents a maze in a rectangular grid. There is exactly * one path between any two points. **/ public class Maze { // Horizontal and vertical dimensions of the maze. protected int horiz; protected int vert; // Horizontal and vertical interior walls; each is true if the wall exists. protected boolean[][] hWalls; protected boolean[][] vWalls; // Object for generting random numbers. private static Random random; // Constants used in depth-first search (which checks for cycles in the // maze). private static final int STARTHERE = 0; private static final int FROMLEFT = 1; private static final int FROMRIGHT = 2; private static final int FROMABOVE = 3; private static final int FROMBELOW = 4; /** * Maze() creates a rectangular maze having "horizontalSize" cells in the * horizontal direction, and "verticalSize" cells in the vertical direction. * There is a path between any two cells of the maze. A disjoint set data * structure is used to ensure that there is only one path between any two * cells. **/ public Maze(int horizontalSize, int verticalSize) { int i, j; horiz = horizontalSize; vert = verticalSize; if ((horiz < 1) || (vert < 1) || ((horiz == 1) && (vert == 1))) { return; // There are no interior walls } // Create all of the horizontal interior walls. Initially, every // horizontal wall exists; they will be removed later by the maze // generation algorithm. if (vert > 1) { hWalls = new boolean[horiz][vert - 1]; for (j = 0; j

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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