-
Notifications
You must be signed in to change notification settings - Fork 0
/
RecursiveDivider.java
88 lines (77 loc) · 2.63 KB
/
RecursiveDivider.java
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
82
83
84
85
86
87
88
package maze;
import java.io.Serializable;
import java.util.Random;
/**
* Implements the recursive division algorithm. The algorithm starts with an
* empty space and recursively divides it into two with a randomly placed
* horizontal or vertical wall.
*/
public class RecursiveDivider extends Maze implements Serializable {
private static final long serialVersionUID = -6219935045687115436L;
private static final boolean HORIZONTAL = true;
private static final boolean VERTICAL = false;
private final Random rnd;
/**
* Sets the dimensions of the maze.
*
* @param width the width of the maze
* @param height the height of the maze
* @throws IllegalArgumentException if width or height is not positive
*/
public RecursiveDivider(int width, int height) {
super(width, height);
rnd = new Random();
}
@Override
public void generate() {
clear();
addBorder();
recursiveDivision(0, 0, getWidth(), getHeight());
}
private void recursiveDivision(int x, int y, int width, int height) {
if (width <= 1 || height <= 1) {
return;
}
int aw, ah;
int bx, by, bw, bh;
if (getOrientation(width, height) == HORIZONTAL) {
int tx = x + width, ty = y + height;
int wy = rnd.nextInt((ty - 1) - y) + y; // Picks a random location.
for (int wx = x; wx < tx; ++wx) { // Places the wall.
addWall(wx, wy, Direction.SOUTH);
}
removeWall(rnd.nextInt(tx - x) + x, wy, Direction.SOUTH); // Makes an opening.
bx = x;
by = wy + 1;
bw = width;
bh = ty - wy - 1;
aw = width;
ah = by - y;
} else { // Perpendicular version of the above.
int tx = x + width, ty = y + height;
int wx = rnd.nextInt((tx - 1) - x) + x;
for (int wy = y; wy < ty; ++wy) {
addWall(wx, wy, Direction.EAST);
}
removeWall(wx, rnd.nextInt(ty - y) + y, Direction.EAST);
bx = wx + 1;
by = y;
bw = tx - wx - 1;
bh = height;
aw = bx - x;
ah = height;
}
recursiveDivision(x, y, aw, ah);
recursiveDivision(bx, by, bw, bh);
}
/** Chooses wall orientation based on the dimensions of an area. */
private boolean getOrientation(int width, int height) {
if (width > 2 * height) {
return VERTICAL;
}
if (height > 2 * width) {
return HORIZONTAL;
}
return rnd.nextBoolean();
}
}