-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathgenerates random mazes using the Depth-First Search algorithm
81 lines (65 loc) · 2.31 KB
/
generates random mazes using the Depth-First Search algorithm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
Java code that generates random mazes using the Depth-First Search algorithm:
import java.util.ArrayList;
import java.util.Random;
public class MazeGenerator {
private int width;
private int height;
private boolean[][] maze;
public MazeGenerator(int width, int height) {
this.width = width;
this.height = height;
this.maze = new boolean[width][height];
generateMaze();
}
private void generateMaze() {
Random random = new Random();
// Select a random starting cell
int x = random.nextInt(width);
int y = random.nextInt(height);
// Mark the starting cell as visited
maze[x][y] = true;
// Use depth-first search to generate the maze
ArrayList<int[]> stack = new ArrayList<>();
stack.add(new int[]{x, y});
while (!stack.isEmpty()) {
int[] current = stack.get(stack.size() - 1);
ArrayList<int[]> unvisitedNeighbors = getUnvisitedNeighbors(current[0], current[1]);
if (!unvisitedNeighbors.isEmpty()) {
int[] next = unvisitedNeighbors.get(random.nextInt(unvisitedNeighbors.size()));
stack.add(next);
maze[next[0]][next[1]] = true;
} else {
stack.remove(stack.size() - 1);
}
}
}
private ArrayList<int[]> getUnvisitedNeighbors(int x, int y) {
ArrayList<int[]> neighbors = new ArrayList<>();
if (x > 0 && !maze[x - 1][y]) {
neighbors.add(new int[]{x - 1, y});
}
if (x < width - 1 && !maze[x + 1][y]) {
neighbors.add(new int[]{x + 1, y});
}
if (y > 0 && !maze[x][y - 1]) {
neighbors.add(new int[]{x, y - 1});
}
if (y < height - 1 && !maze[x][y + 1]) {
neighbors.add(new int[]{x, y + 1});
}
return neighbors;
}
public boolean[][] getMaze() {
return maze;
}
public static void main(String[] args) {
MazeGenerator generator = new MazeGenerator(10, 10);
boolean[][] maze = generator.getMaze();
for (int i = 0; i < maze.length; i++) {
for (int j = 0; j < maze[i].length; j++) {
System.out.print(maze[i][j] ? " " : "# ");
}
System.out.println();
}
}
}