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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
package sample3d;
import java.util.ArrayList;
public class _labyrinth {
private int width, depth;
private boolean[] field;
private int start_pos, start_dir, goal_pos;
public _labyrinth(int width, int depth) {
this.width = width;
this.depth = depth;
field = new boolean[width * depth];
start_pos = -1;
goal_pos = -1;
}
public int get_width() { return width; }
public int get_depth() { return depth; }
public boolean is_wall(int x, int z) {
return is_wall(get_pos(x, z));
}
public boolean is_wall(int pos) {
return pos == -1 || field[pos];
}
public void set_wall(int x, int z, boolean b_wall) {
set_wall(get_pos(x, z), b_wall);
}
public void set_wall(int pos, boolean b_wall) {
if (pos != -1) {
field[pos] = b_wall;
if (b_wall) {
if (pos == start_pos)
start_pos = -1;
else if (pos == goal_pos)
goal_pos = -1;
}
}
}
public int get_start_pos() { return start_pos; }
public void set_start_pos(int pos) {
if (pos != -1 && (field[pos] || pos == goal_pos)) return;
start_pos = pos;
}
public int get_start_dir() { return start_dir; }
public void set_start_dir(int dir) { start_dir = dir % 4; }
public int get_goal_pos() { return goal_pos; }
public void set_goal_pos(int pos) {
if (pos != -1 && (field[pos] || pos == start_pos)) return;
goal_pos = pos;
}
public int get_pos(int x, int z) {
return (is_out(x, z)) ? -1 : x + z * width;
}
public boolean is_out(int x, int z) {
return x < 0 || x >= width || z < 0 || z >= depth;
}
public interface _labyrinth_iterator {
public void call(int x, int z);
}
public void iter(_labyrinth_iterator iter) {
for (int x = 0; x < width; x++)
for (int z = 0; z < depth; z++)
iter.call(x, z);
}
public void create() {
ArrayList<Integer> pos_list = new ArrayList<>();
char[][] c_lab = new char[width][depth];
int[] dir_list = new int[4];
int[] v;
int dir, n;
int px, pz;
// 全てを壁にする
iter((x, z) -> c_lab[x][z] = 'w');
// スタート地点を設定。'f'は床(floor)
px = 0; pz = 0; c_lab[px][pz] = 'f';
// 穴掘り開始
while (true) {
// 掘られる方向を探す
n = 0;
for (dir = 0; dir < 4; dir++) {
if (serach_dir(c_lab, px, pz, dir, 2) == 'w')
dir_list[n++] = dir;
}
if (n > 0) { // 掘られる場合は
dir = dir_list[(int)(n * Math.random())];
// 足跡を付けながら掘る。'm'は印(mark)
v = dir_vectors[dir];
c_lab[px += v[0]][pz += v[1]] = 'm';
c_lab[px += v[0]][pz += v[1]] = 'f';
} else { // 掘られない場合は
// 行き止まりならゴール地点の候補に挙げる
for (dir = 3; dir >= 0 &&
serach_dir(c_lab, px, pz, dir, 1) != 'f'; dir--)
;
if (dir == -1)
pos_list.add(get_pos(px, pz));
// 足跡を探す
for (dir =3; dir >= 0 &&
serach_dir(c_lab, px, pz, dir, 1) != 'm'; dir--)
;
if (dir == -1) break; // なければ終了
// 足跡を消しながら戻る
v = dir_vectors[dir];
c_lab[px += v[0]][pz += v[1]] = 'f';
px += v[0];
pz += v[1];
}
}
// 壁の情報を設定
iter((x, z) -> set_wall(x, z, c_lab[x][z] == 'w'));
// スタートの設定
set_start_pos(get_pos(px, pz));
for (dir = 0; serach_dir(c_lab, px, pz, dir, 1) != 'f'; dir++)
;
set_start_dir(dir);
// ゴールの設定
set_goal_pos(pos_list.get((int)(pos_list.size() * Math.random())));
}
private int[][] dir_vectors = {
{ 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 }
};
private char serach_dir(char[][] c_lab, int x, int z, int dir, int step) {
int[] v = dir_vectors[dir];
x += step * v[0];
z += step * v[1];
// 迷宮の外なら'o'(out)
return is_out(x, z) ? 'o' : c_lab[x][z];
}
}