- Depth-first search;
- Randomized Kruskal's algorithm;
- Randomized Prim's algorithm;
- and so on.
See Wikipedia for more information.
The goal here is to design a "perfect" maze:
- There are no cycles;
- There is a unique path from the start cell in the maze to the end cell.
Here I use randomized Kruskal's algorithm with a disjoint set data structure to perform union method. It works in the following way:
- Create a list of all walls that potentially can be destroyed;
- Randomly choose a wall index;
- Union the two adjacent cells that are separated by the wall;
- Repeat until all cells are in the same set.
The union method acts like knocking down the wall, i.e., if two cells are in the same set, they are connected. When all cells are in the same set, there must be one path from the start cell to the end cell. Moreover, since every time we union two cells that are in different sets, there is no path between the cell before union, and since after the union, no other wall will be knocked down between these two cells, so there will be a unique path from any cell to another cell in the maze. Thus fulfill the "perfect" maze requirement.
public class Maze {
private int[] grid;
private int rows;
private int columns;
private Maze(int rows, int columns) {
//using 1D array to represent cells
//index / columns = row in the maze
//index % columns = col in the maze
this.grid = new int[rows * columns];
//one cell is surrounded by walls in four directions
//initially create cells with all walls up
Arrays.fill(grid, UP | RIGHT | DOWN | LEFT);
this.rows = rows;
this.columns = columns;
}
private static final int UP = 1;
private static final int RIGHT = 2;
private static final int DOWN = 4;
private static final int LEFT = 8;
public static Maze createRandomMaze(int rows, int columns) {
Maze maze = new Maze(rows, columns);
//create all walls that potentially can be broken
List walls = new ArrayList();
for (int row = 0; row < rows; row++) {
for (int col = 0; col < columns; col++) {
if (row > 0)
//cell = row * columns + col
//cell / columns = row
//cell % columns = col
// represent the grid in the maze
//the upper wall of the lower cell is the lower wall of the upper cell
// the left wall of the right cell is the right wall of the left cell
//so we only need to consider two directions
walls.add(new Wall(row * columns + col, UP));
if (col > 0)
walls.add(new Wall(row * columns + col, LEFT));
}
}
DisjointSet diset = new ArrayDisjointSet(rows * columns);
//Object for generating random numbers
Random rand = new Random();
while (diset.size() > 1) {
//get an index randomly
int wallIndex = rand.nextInt(walls.size());
int cell1 = walls.get(wallIndex).cell;
int cell2 = (walls.get(wallIndex).direction == UP) ?
cell1 - columns ://choose the cell and the one above it, break the upper wall
cell1 - 1;//choose the one left to it, break the left wall
//if there is no path between two cells
//i.e., they are not in the same set
if (diset.find(cell1) != diset.find(cell2)) {
if (walls.get(wallIndex).direction == UP) {
//break the upper wall of cell1
//which is also the lower wall of cells2
maze.grid[cell1] ^= UP;
maze.grid[cell2] ^= DOWN;
}
else {
maze.grid[cell1] ^= LEFT;
maze.grid[cell2] ^= RIGHT;
}
diset.union(cell1, cell2);
}
//the wall is knocked down, dead, disappeared, over...
walls.remove(wallIndex);
}
return maze;
}
public static class Wall {
private final int cell;
private final int direction;
public Wall(int cell, int direction) {
this.cell = cell;
this.direction = direction;
}
}
}
The result of a 30 by 30 grids:
The source code can be found on my Github: https://github.com/shirleyyoung0812/mazeDFS.git
To people who devote their lives to the dream they have.
