blob: 73a2f2557277bb1778d40098fcf8eb2f988edd53 (
plain)
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
|
package net.caraus.labyrinth;
import com.badlogic.gdx.graphics.glutils.ShapeRenderer;
import java.util.ArrayList;
import java.util.HashSet;
public final class RecursiveSolve extends Thread {
private Maze maze;
private Point start;
private Point finish;
private boolean[][] visited;
// Результирующий маршрут.
private ArrayList<Point> path;
public RecursiveSolve(Maze maze, Point start, Point finish) {
this.maze = maze;
this.start = start;
this.finish = finish;
this.visited = new boolean[this.maze.width()][this.maze.height()];
this.path = new ArrayList<>(this.maze.width() * this.maze.height() + 1);
for (var column: this.visited) {
for (var y = 0; y < column.length; ++y) {
column[y] = false;
}
}
}
private boolean solve(Point nLocation) throws InterruptedException {
this.visited[nLocation.x()][nLocation.y()] = true; // Пометить локацию как посещенную.
synchronized(this) {
this.path.add(nLocation); // Добавить ее в описание маршрута.
}
Thread.sleep(500);
// Если финишная локация найдена, конец алгоритма.
if (this.finish.equals(nLocation)) {
return true;
}
for (var i = 0; i < 4; ++i) {
// Если дорожка свободна, идем по ней.
var neighbour = new Point(nLocation.x() + Maze.DX[i], nLocation.y() + Maze.DY[i]);
if (maze.canGo(nLocation, i) && !this.visited[neighbour.x()][neighbour.y()]) {
// Если решение найдено, конец алгоритма.
if (solve(neighbour)) {
return true;
}
}
}
synchronized(this) {
this.path.remove(this.path.size() - 1);
}
return false;
}
@Override
public void run() {
try {
solve(this.start);
} catch (InterruptedException e) {
}
}
private void drawPoint(ShapeRenderer shape, Point nLocation) {
final float markSize = 20.0f;
final float halfMark = Maze.CELL_SIZE / 2 - markSize / 2;
shape.ellipse((nLocation.x() + 1) * Maze.CELL_SIZE + halfMark,
(this.maze.height() - nLocation.y()) * Maze.CELL_SIZE + halfMark,
markSize, markSize);
}
synchronized public void draw(ShapeRenderer shape) {
for (var point: this.path) {
drawPoint(shape, point);
}
}
}
|
