Алгоритм створення лабіринту: відмінності між версіями
| [неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
Рядок 186:
/**
* Створює лабіринт з графу сітки, використовуючи <em>рандомізований пошук у глибину</em>.
*
* @author Armin Reichert
Рядок 193:
public static void main(String[] args) {
// Використання рекурсивної процедури:
System.out.println(maze(10, 10, 0, 0, true));
// Використання нерекурсивної процедури:
System.out.println(maze(10, 10, 0, 0, false));
}
/** Повертає лабіринт заданого розміру початкової генерації в даній позиції сітки. */
public static Grid maze(int numCols, int numRows, int startCol, int startRow, boolean recursive) {
Grid grid = new Grid(numCols, numRows);
Рядок 212:
}
/** Рекурсивна процедура, що проходить через сітку і створює лабіринт (остовне дерево). */
private static void traverseRecursive(Grid grid, int v, BitSet visited) {
visited.set(v);
Рядок 221:
}
/** Нерекурсивна процедура, що проходить через сітку і створює лабіринт (остовне дерево). */
private static void traverseUsingStack(Grid grid, int v, BitSet visited) {
Deque<<nowiki>Integer</nowiki>> stack = new ArrayDeque<>();
Рядок 241:
}
/** Повертає випадковий напрямок невідомому сусіду або {@code -1}. */
private static int unvisitedDir(Grid grid, int v, BitSet visited) {
int[] candidates = new int[4];
Рядок 263:
/**
* Реалізація сітки графу. Набір ребер представлений одним набором бітів.
*/
public class Grid {
/**
public static final int NORTH = 0, EAST = 1, SOUTH = 2, WEST = 3;
/**
public static final int[] OPPOSITE = { SOUTH, WEST, NORTH, EAST };
/*
public static final int[] X = { 0, 1, 0, -1 };
public static final int[] Y = { -1, 0, 1, 0 };
/** Індекс не представляє вершини. */
public static final int NO_VERTEX = -1;
/** Кількість стовпців сітки. */
public final int numCols;
/**
public final int numRows;
private BitSet edges;
/**
private int bit(int v, int dir) {
return 4 * v + dir;
}
/** Створює порожню сітку заданого розміру. */
public Grid(int numCols, int numRows) {
this.numCols = numCols;
Рядок 300:
}
/**
public int vertex(int col, int row) {
return numCols * row + col;
}
/**
public int col(int v) {
return v % numCols;
}
/**
public int row(int v) {
return v / numCols;
}
/** Повертає кількість (неорієнтованих) ребер. */
public int numEdges() {
return edges.cardinality() / 2;
}
/**
public void addEdge(int v, int dir) {
edges.set(bit(v, dir));
Рядок 326:
}
/**
public boolean hasEdge(int v, int dir) {
return edges.get(bit(v, dir));
Рядок 332:
/**
*
*/
public int neighbor(int v, int dir) {
Рядок 339:
}
/** Повертає текстове представлення цієї сітки. */
@Override
public String toString() {
| |||