Return to Revisions

Intro

Still working on PathFinding.java. This time I concentrate on three private methods of GridModel that are responsible for generating random perfect mazes. A maze is perfect if for each two cells in the maze there is only and exactly one route.

How it looks like:

A random perfect maze in a 2D grid graph.

Code

private void drawViaDFS(Random rnd) {
 int rows = height;
 int cols = width;
 if (height % 2 == 0) {
 rows--;
 }
 if (width % 2 == 0) {
 cols--;
 }
 int roomCols = (cols - 1) / 2; // Number of "rooms" horizontally.
 int roomRows = (rows - 1) / 2; // Number of "rooms" vertically.
 boolean[][] visited = new boolean[roomRows]
 [roomCols];
 // Pick a random room (mapped to grid coords: rr -> 2 * rr + 1):
 int rr = rnd.nextInt(roomRows); 
 int cc = rnd.nextInt(roomCols);
 // Carve the inital room from its wall:
 carveCell(cc, rr);
 // Initialize DFS stack:
 Deque<int[]> stack = new ArrayDeque<>();
 visited[rr][cc] = true;
 stack.push(new int[]{ cc, rr });
 // 4-neighbor moves in room space
 int[] deltaRowOffsets = { -1, 0, 1, 0 };
 int[] deltaColOffsets = { 0, 1, 0, -1 };
 int[] directionIndices = { 0, 1, 2, 3 };
 while (!stack.isEmpty()) {
 int[] cur = stack.peek();
 int c0 = cur[0];
 int r0 = cur[1];
 // Fisher–Yates shuffle:
 for (int i = 3; i > 0; i--) {
 int j = rnd.nextInt(i + 1);
 int t = directionIndices[i];
 directionIndices[i] = directionIndices[j];
 directionIndices[j] = t;
 }
 boolean moved = false;
 for (int directionIndex : directionIndices) {
 int r1 = r0 + deltaRowOffsets[directionIndex]; 
 int c1 = c0 + deltaColOffsets[directionIndex];
 if (0 <= r1 
 && r1 < roomRows 
 && 0 <= c1 
 && c1 < roomCols 
 && !visited[r1][c1]) {
 // Carve passage between rooms (r0, c0) and (r1, c1):
 carveBetween(c0, 
 r0,
 c1,
 r1);
 carveCell(c1, r1);
 visited[r1][c1] = true;
 stack.push(new int[]{ c1, r1 });
 moved = true;
 break;
 }
 }
 if (!moved) {
 stack.pop();
 }
 }
}
private void carveCell(int roomX, int roomY) {
 int x = 2 * roomX + 1;
 int y = 2 * roomY + 1;
 setCellType(x, y, CellType.FREE);
}
private void carveBetween(int roomX0,
 int roomY0,
 int roomX1,
 int roomY1) {
 int cellX0 = 2 * roomX0 + 1;
 int cellY0 = 2 * roomY0 + 1;
 int cellX1 = 2 * roomX1 + 1;
 int cellY1 = 2 * roomY1 + 1;
 int x = (cellX0 + cellX1) / 2;
 int y = (cellY0 + cellY1) / 2;
 setCellType(x, y, CellType.FREE);
}

Critique request

My primary concern this time is the code readability and variable naming.