Cześć, mam za zadanie wygenerować labirynt, najlepiej przy pomocy MST, bo akurat jestem w temacie grafów.
Tutaj obrazek jak to ma wyglądać:
Tutaj jak działa algorytm:
Problemem jest to, że zarówno na filmiku, jak i w innych źródłach, sposób ten nie bierze pod uwagę ścian do rozmiaru labiryntu. Jak można zauważyć w przykładzie, który wrzuciłem, wygląda to inaczej - ściana i ścieżka mają taką samą grubość - jedno i drugie jest brane pod uwagę licząc rozmiar labiryntu.
W pierwszej kolejności zrobiłem graf jak na filmiku, czyli dla labiryntu np. 7x9 graf 63 wierzchołków. Oczywiście tak się tutaj nie da. Zauważyłem, że w takim przypadku każdy punkt labiryntu ("kwadracik" lub " ") powinien być reprezentowany przez krawędź, nie wierzchołek. Jako, że nie miałem już pomysłu jak to zaimplementować i byłem zmęczony myśleniem nad tym, podejrzałem rozwiązania innych użytkowników i wybrałem zrozumiałą dla mnie w największym stopniu, co wrzucam poniżej. Byłbym wdzięczny, gdyby ktoś wyjaśnił mi fragmenty kodu, których nie rozumiem (co one robią, po co) lub wyjaśnił koncepcję tego kodu, co pozwoli mi napisać po swojemu. Ewentualnie jakieś alternatywne rozwiązanie, tylko żadne skomplikowane cuda, bo jak widać, nie jestem zbyt zaawansowany.
public class Edge {
private final int node1;
private final int node2;
public Edge(int node1, int node2) {
this.node1 = node1;
this.node2 = node2;
}
public int getNode1() {
return node1;
}
public int getNode2() {
return node2;
}
}
public class Maze {
private final int gridHeight;
private final int gridWidth;
private final int matrixHeight;
private final int matrixWidth;
private final int numberOfNodes;
private final int[][] adjacencyMatrix;
private final int[][] maze;
private final Random random = new Random();
private final List<Edge> edges = new ArrayList<>();
private final List<int[][]> edgesCoordinates = new ArrayList<>();
public Maze(int height, int width) {
this.gridHeight = height;
this.gridWidth = width;
this.maze = new int[gridHeight][gridWidth];
//dlaczego wierzchołków grafu ma być 2 razy mniej niż elementów w docelowym labiryncie? - element tj. kwadracik i " "
this.matrixHeight = height % 2 == 0 ? (this.gridHeight - 1) / 2 : this.gridHeight / 2;
this.matrixWidth = width % 2 == 0 ? (this.gridWidth - 1) / 2 : this.gridWidth / 2;
this.numberOfNodes = matrixHeight * matrixWidth;
this.adjacencyMatrix = new int[numberOfNodes][numberOfNodes];
generateMaze();
}
private void generateMaze() {
generateAdjacencyMatrix();
primsAlgorithm();
mapEdgesToCoordinates();
createTunnels();
createEntranceAndExit();
}
private void generateAdjacencyMatrix() {
for (int i = 0; i < numberOfNodes; i++) {
int widthIterator = 1;
for (int j = 0; j < numberOfNodes; j++) {
if (i == j) {
adjacencyMatrix[i][j] = 0;
continue;
}
if ((j == i + 1 && widthIterator != matrixWidth) || j == i + matrixWidth) {
adjacencyMatrix[i][j] = random.nextInt(9) + 1;
}
if (widthIterator == matrixWidth) {
widthIterator = 1;
} else {
widthIterator++;
}
adjacencyMatrix[j][i] = adjacencyMatrix[i][j];
}
}
}
private void primsAlgorithm() {
boolean[] inMST = new boolean[numberOfNodes];
inMST[0] = true;
while (edges.size() < numberOfNodes - 1) {
int min = Integer.MAX_VALUE;
int rowWithMin = -1, columnWithMin = -1;
for (int row = 0; row < numberOfNodes; row++) {
for (int column = 0; column < numberOfNodes; column++) {
if (adjacencyMatrix[row][column] < min && adjacencyMatrix[row][column] != 0 && isValidEdge(row, column, inMST)) {
min = adjacencyMatrix[row][column];
rowWithMin = row;
columnWithMin = column;
}
}
}
if (rowWithMin != -1 && columnWithMin != -1) {
edges.add(new Edge(rowWithMin, columnWithMin));
inMST[columnWithMin] = inMST[rowWithMin] = true;
}
}
for (int row = 0; row < numberOfNodes; row++) {
for (int column = 0; column < numberOfNodes; column++) {
if (adjacencyMatrix[row][column] != 0) {
adjacencyMatrix[row][column] = 1;
}
}
}
}
private boolean isValidEdge(int u, int v, boolean[] inMST) {
if (u == v)
return false;
if (!inMST[u] && !inMST[v])
return false;
else if (inMST[u] && inMST[v])
return false;
return true;
}
//tutaj nic nie rozumiem, nie wiem nawet co to jest
//zamienia krawędzie na elementy labiryntu? ścieżki lub ściany? ale i tak nie rozumiem
private void mapEdgesToCoordinates() {
for (Edge edge : edges) {
int rowCoordinateNode1 = edge.getNode1() / matrixWidth;
int columnCoordinateNode1 = edge.getNode1() % matrixWidth;
int rowCoordinateNode2 = edge.getNode2() / matrixWidth;
int columnCoordinateNode2 = edge.getNode2() % matrixWidth;
edgesCoordinates.add(new int[][]{{rowCoordinateNode1, columnCoordinateNode1}, {rowCoordinateNode2, columnCoordinateNode2}});
}
}
// tutaj tworzy ścieżki, tj. " "? wnioskuję z nazwy funkcji, bo nie wiem co się tu dzieje
// nawet jeśli, to myślałem, że algorytm Prima robi całą robotę w tej kwestii
private void createTunnels() {
for (int[][] edgeCoordinate : edgesCoordinates) {
int rowCoordinateNode1 = 2 * edgeCoordinate[0][0] + 1 ;
int columnCoordinateNode1 = 2 * edgeCoordinate[0][1] + 1;
int rowEdgeCoordinate = edgeCoordinate[0][0] + edgeCoordinate[1][0] + 1;
int columnEdgeCoordinate = edgeCoordinate[0][1] + edgeCoordinate[1][1] + 1;
int rowCoordinateNode2 = 2 * edgeCoordinate[1][0] + 1;
int columnCoordinateNode2 = 2 * edgeCoordinate[1][1] + 1;
maze[rowCoordinateNode1][columnCoordinateNode1] = 1;
maze[rowEdgeCoordinate][columnEdgeCoordinate] = 1;
maze[rowCoordinateNode2][columnCoordinateNode2] = 1;
}
if (gridWidth % 2 == 0) {
for (int i = 0; i < gridHeight; i++) {
maze[i][gridHeight - 2] = maze[i][gridHeight - 3];
}
}
if (gridHeight % 2 == 0) {
for (int i = 0; i < gridWidth; i++) {
maze[gridHeight - 2][i] = maze[gridHeight - 3][i];
}
}
}
private void createEntranceAndExit() {
for (int i = 2; i < gridHeight; i++) {
if (maze[i][1] == 1) {
maze[i][0] = 1;
break;
}
}
for (int i = gridHeight - 1; i > 0; i--) {
if (maze[i][gridWidth - 2] == 1) {
maze[i][gridWidth - 1] = 1;
break;
}
}
}
public void printMaze() {
for (int row = 0; row < gridHeight; row++) {
for (int column = 0; column < gridWidth; column++) {
System.out.print(maze[row][column] == 1 ? " " : "\u2588\u2588");
}
System.out.println();
}
}
}