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
|
package net.caraus.labyrinth;
import java.util.ArrayList;
import java.util.Random;
public final class KruskalMaze {
private Maze theMaze;
private int[][] mark;
public KruskalMaze(int width, int height) {
this.theMaze = new Maze(width, height);
}
private void breakWall(Wall wall) {
if (wall.delta().x() == -1) {
this.theMaze.at(wall.xy()).leftWall(false);
} else if (wall.delta().x() == 1) {
this.theMaze.at(wall.xy().x() + 1, wall.xy().y()).leftWall(false);
} else if (wall.delta().y() == -1) {
this.theMaze.at(wall.xy()).upWall(false);
} else {
this.theMaze.at(wall.xy().x(), wall.xy().y() + 1).upWall(false);
}
}
public boolean isConnected(Point start, Point finish) {
this.mark = new int[this.theMaze.width()][this.theMaze.height()]; // Метки локаций.
for (int x = 0; x < this.theMaze.width(); ++x) {
for (int y = 0; y < this.theMaze.height(); ++y) {
this.mark[x][y] = 0;
}
}
this.mark[start.x()][start.y()] = 1;
return solve(start, finish);
}
private boolean solve(Point start, Point finish) {
// Используем алгоритм волновой трассировки.
int n = 1;
// Локации со следующим N.
ArrayList<Point> locations = new ArrayList<>();
locations.add(start);
do {
ArrayList<Point> nextLocations = new ArrayList<>();
// Посетить локации, помеченные числом N.
for (var nLocation : locations) {
// Просмотр соседей.
for (int i = 0; i < 4; ++i) {
var neighbour = new Point(nLocation.x() + Maze.DX[i], nLocation.y() + Maze.DY[i]);
if (this.theMaze.canGo(nLocation, i) && this.mark[neighbour.x()][neighbour.y()] == 0) {
// Локация доступна и помечена нулем.
// Есть шанс найти решения.
nextLocations.add(neighbour);
this.mark[neighbour.x()][neighbour.y()] = n + 1;
if (neighbour.x() == finish.x() && neighbour.y() == finish.y()) {
return true;
}
}
}
}
locations = nextLocations;
++n;
} while (!locations.isEmpty());
return false;
}
public Maze generate() {
final var wallCount = (this.theMaze.width() - 1) * this.theMaze.height()
+ (this.theMaze.height() - 1) * this.theMaze.width();
ArrayList<Wall> walls = new ArrayList<>(wallCount);
ArrayList<Double> temp = new ArrayList<>(wallCount);
var random = new Random();
// Заполнение массива Temp случайными числами.
for (int i = 0; i < wallCount; ++i) {
temp.add(random.nextDouble());
}
// Заполнение массива стен.
// Сначала все горизонтальные.
for (var i = 1; i < this.theMaze.width(); ++i) {
for (var j = 0; j < this.theMaze.height(); ++j) {
walls.add(new Wall(new Point(i, j), new Point(-1, 0)));
}
}
// Затем все вертикальные.
for (var i = 0; i < this.theMaze.width(); ++i) {
for (var j = 1; j < this.theMaze.height(); ++j) {
walls.add(new Wall(new Point(i, j), new Point(0, -1)));
}
}
for (var i = 0; i < wallCount; ++i) {
for (var j = i; j < wallCount; ++j) {
// Перемешиваем массив стен.
if (temp.get(i) > temp.get(j)) {
var tempr = temp.get(i);
temp.set(i, temp.get(j));
temp.set(j, tempr);
var tempw = walls.get(i);
walls.set(i, walls.get(j));
walls.set(j, tempw);
}
}
}
var locations = this.theMaze.width() * this.theMaze.height();
int i = 0;
while (locations > 1) {
var curWall = walls.get(i);
++i;
if (!isConnected(curWall.xy(), curWall.end())) {
breakWall(curWall);
--locations;
}
}
return this.theMaze;
}
}
|
