Вот как представляется мне данная генерация
import java.util.*;
public class Ellers
{
static final char MAZE_WALL = '#';
static final char MAZE_PATH = ' ';
static final int UNDETERMINED = -2;
static final int SET_WALL = -1;
int rows; //строки
int cols; //столбцы
int act_rows; //Текущий номер строки
int act_cols; //Текущий номер столбца
char[][] feild; //Поле лабиринта
int[] current; //текущая строка, за исключением наружных стен
int[] next; //следующая строка, за исключением наружных стен
int numSet; //Проверка на совпадение
private Random fRand;
private int fNext;
private int fNext2;
/* конструктор */
public Ellers (int nRows, int nCols)
{
act_rows = nRows;
act_cols = nCols;
rows = act_rows*2+1;
cols = act_cols*2+1;
feild = new char[rows][cols];
current = new int[act_cols*2-1];
next = new int[act_cols*2-1];
/* Sets the maze to filled */
for(int i =0; i<feild[0].length; i++){
for(int j=0; j<feild.length; j++){
feild[i][j] = MAZE_WALL;
}
}
for(int i=0; i<next.length; i++){
next[i] = UNDETERMINED;
}
/* Инициализация первой строки */
for(int i=0; i<current.length; i+=2){
current[i] = i/2+1;
if(i != current.length-1)
current[i+1] = SET_WALL;
}
numSet = current[current.length-1];
}
public void makeMaze()
{
setRand(new Random());
for(int q=0; q<act_rows-1; q++){ //для всех строк кроме последней
if(q != 0){
/* получим текущую строку из последней итерации*/
for(int i=0; i<current.length; i++){
current[i] = next[i];
next[i] = UNDETERMINED;
}
}
joinSets();
makeVerticalCuts();
/* заполним остальную часть следующей строки */
for(int j=0; j<current.length; j+=2){
if(next[j] == UNDETERMINED)
next[j] = ++numSet;
if(j != current.length-1)
next[j+1] = SET_WALL;
}
/* запишем текущую строку в поле */
for(int k=0; k<current.length; k++){
if(current[k] == SET_WALL){
feild[2*q+1][k+1] = MAZE_WALL;
feild[2*q+2][k+1] = MAZE_WALL;
}else{
feild[2*q+1][k+1] = MAZE_PATH;
if(current[k] == next[k]){
feild[2*q+2][k+1] = MAZE_PATH;
}
}
}
}
makeLastRow();
makeOpenings();
}
private void joinSets()
{
Random rand = new Random();
/* Случайные наборы */
for(int i=1; i<current.length-1; i+=2){ //проверка только где стены
/* Проверка на объединение:
* Имеют ли стену между ними,
* не являются ли частью одного набора
*Получаем случайный набор, при объединении
*/
if(current[i] == SET_WALL && current[i-1] != current[i+1]
&& rand.nextBoolean()){
current[i] = 0; //Убрать стену
int old = Math.max(current[i-1],current[i+1]);
fNext= Math.min(current[i-1],current[i+1]);
// Объединяем два набора в один
for(int j=0; j<current.length; j++){
if(current[j] == old)
current[j] = fNext;
}
}
}
}
/* Случайно выбрать вертикальные пути для каждого набора, убедившись,
* что есть по крайней мере 1 вертикальный путь в наборе
*/
private void makeVerticalCuts()
{
Random rand = new Random();
int begining; //Начало набора(Включительно)
int end; //Конец набор(Включительно)
boolean madeVertical; //Создание вертикального прохода
int i;
begining = 0;
do{
/* Поиск конца */
i=begining;
while(i<current.length-1 && current[i] == current[i+2]){
i+=2;
}
end = i;
//Наличие петли
madeVertical = false;
do{
for(int j=begining; j<=end; j+=2){
if(rand.nextBoolean()){
next[j] = current[j];
madeVertical = true;
}
}
}while(!madeVertical);
begining = end+2; //перейти к следующему набору в строке
}while(end != current.length-1);
}
private void makeLastRow()
{
/* Получение текущей строки */
for(int i=0; i<current.length; i++){
current[i] = next[i];
}
for(int i=1; i<current.length-1; i+=2){
if(current[i] == SET_WALL && current[i-1] != current[i+1]){
current[i] = 0;
int old = Math.max(current[i-1],current[i+1]);
fNext2= Math.min(current[i-1],current[i+1]);
// Объединяем два набора в один
for(int j=0; j<current.length; j++){
if(current[j] == old)
current[j] = fNext2;
}
}
}
/* Добавление последней строки */
for(int k=0; k<current.length; k++){
if(current[k] == SET_WALL){
feild[rows-2][k+1] = MAZE_WALL;
}else{
feild[rows-2][k+1] = MAZE_PATH;
}
}
}
public void makeOpenings(){
Random rand = new Random(); //два различных генераторов случайных чисел
Random rand2 = new Random();//на всякий случай
//случайное место для входа и выхода
int entrance_row = rand.nextInt(act_rows-1) * 2 +1;
int exit_row = rand2.nextInt(act_rows-1) * 2 +1;
//очистить место
feild[entrance_row][0] = MAZE_PATH;
feild[exit_row][cols-1] = MAZE_PATH;
}
public void printMaze()
{
for(int i=0; i<rows; i++){
for(int j=0; j<cols; j++){
System.out.print(feild[i][j]);
}
System.out.println();
}
}
public char[][] getMaze()
{
return feild;
}
public Random getRand() {
return fRand;
}
public void setRand(Random rand) {
fRand = rand;
}
}
Добавлено через 3 часа, 13 минут и 46 секунд:Собственно вот остальная часть программа, с поиском кратчайшего пути.
//Параметры
public class Mazes
{
static final int ROWS = 20;
static final int COLS = 20;
public static void main(String [] args)
{
System.out.println(Messages.Mazes_4);
Ellers ell = new Ellers(ROWS,COLS);
ell.makeMaze();
ell.printMaze();
System.out.println();
Solver ellSol = new Solver(ell.getMaze());
ellSol.solveMaze();
ellSol.printSolution();
//System.out.println(Messages.Mazes_4);
//System.out.println(Messages.Mazes_5);
}
}
//поиск кратчайшего пути
import java.util.*;
public class Solver {
char[][] maze; //Двумерный массив для представления лабиринта
ArrayDeque<Integer[]> path; //стек используется для отслеживания местоположения
int rows; //Строки
int cols; //Столбцы
public Solver(char[][] feild)
{
//инициализирует массив прохождение лабиринта и длины введенного массива
maze = new char[feild.length][feild[1].length];
//копирует содержимое входного массива в массив прохождения лабиринта
for(int i=0; i<feild.length; i++){
for(int j=0; j<feild[i].length; j++){
maze[i][j] = feild[i][j];
}
}
//установка строк и столбцов
rows = feild.length;
cols = feild[0].length;
//инициализируем стек, который отслеживает путь в лабиринте в большом размере
path = new ArrayDeque<Integer[]>(rows*cols);
}//конструктор конец )
//Возвращаем лабиринт
public char[][] getMaze()
{
return maze;
}
public void setInitialLocation()
{
Integer[] temp = new Integer[2]; //доступ
//перебор и поиск входа
for(int i=0; i<maze.length; i++)
{
//если он находит пустое место, это вход
if(maze[i][0] == ' '){
//набор текущего положения
temp[0] = i;
temp[1] = 0;
//устанавливаем указатель -
maze[temp[0]][temp[1]] = '-';
path.addFirst(temp);
}
}
}
public int canSolveUp()
{
Integer[] temp = new Integer[2]; //Массив для получения доступа
temp = path.peekFirst();
int nRow = temp[0]-1; //устанавливаем следующее местоположение
int nCol = temp[1];
//если рядом есть правильный путь, вернуть 1
if(nRow > 0){
if( maze[nRow][nCol] == ' '){
return 1;
}
}
return 0; //иначе 0
}
public int canSolveRight()
{
Integer[] temp = new Integer[2]; //получаем доступ
temp = path.peek();
int nRow = temp[0]; //переходим дальшн
int nCol = temp[1]+1;
//если рядом есть правильный путь, вернуть 1
if(nCol < cols){
if( maze[nRow][nCol] == ' '){
return 2;
}
}
return 0; //иначе 0
}
public int canSolveDown()
{
Integer[] temp = new Integer[2]; //проверям доступ
temp = path.peek();
int nRow = temp[0]+1; //переход дальше
int nCol = temp[1];
//если рядом есть правильный путь, вернуть 3
if(nRow < rows){
if( maze[nRow][nCol] == ' '){
return 3;
}
}
return 0; //иначе 0
}
public int canSolveLeft()
{
Integer[] temp = new Integer[2]; //проверяем доступ
temp = path.peek();
int nRow = temp[0]; //переходим дальше
int nCol = temp[1]-1;
//если рядом есть правильный путь, вернуть 4
if(nCol > 0){
if( maze[nRow][nCol] == ' '){
return 4;
}
}
return 0; //иначе 0
}
public int[] canSolve()
{
int[] cut = new int[4];
int place =0;
//проверка направления(ввех)
if(canSolveUp() != 0){
cut[place] = canSolveUp();
place++;
}
//проверка направления(вправо)
if(canSolveRight() != 0){
cut[place] = canSolveRight();
place++;
}
//проверка направления(вниз)
if(canSolveDown() != 0){
cut[place] = canSolveDown();
place++;
}
//проверка направления(влево)
if(canSolveLeft() != 0){
cut[place] = canSolveLeft();
place++;
}
//возвращаем ноль, если нет направления
if(place == 0){
for(int i = 0; i<4; i++){
cut[i] = 0;
}
return cut;
} else { //иначе уменьшить массив и вернуть его
int[] cancut = new int[place];
for(int i=0; i<place; i++){
cancut[i] = cut[i];
}
return cancut;
}
}
public void solveUp()
{
Integer[] current = path.peek(); //текущее положение
Integer[] temp = new Integer[2]; //получение следующего положения
int nRow = current[0]-1; //переход дальше
int nCol = current[1];
maze[nRow][nCol] = '-'; //устанавливаем указатель
temp[0] = nRow;
temp[1] = nCol;
path.addFirst(temp); //помещаем в стек, устанавливаем указатель -
}
public void solveRight()
{
Integer[] current = path.peek(); //получаем положение
Integer[] temp = new Integer[2]; //добавляем следующее
int nRow = current[0]; //переход дальше
int nCol = current[1]+1;
maze[nRow][nCol] = '-'; //устанавливаем указатель
temp[0] = nRow;
temp[1] = nCol;
path.addFirst(temp); //помещаем в стек, устанавливаем указатель -
}
public void solveDown()
{
Integer[] temp = new Integer[2]; //текущее положение
Integer[] current = path.peek(); //добавление следующего положения
int nRow = current[0]+1; //переход
int nCol = current[1];
maze[nRow][nCol] = '-'; //помещаем в стек, устанавливаем указатель -
temp[0] = nRow;
temp[1] = nCol;
path.addFirst(temp); //pushes the next location to the stack
}
public void solveLeft()
{
Integer[] temp = new Integer[2]; //текущее положение
Integer[] current = path.peek(); //добаление следующего положения
int nRow = current[0]; //переход
int nCol = current[1]-1;
maze[nRow][nCol] = '-'; //помещаем в стек, устанавливаем указатель -
temp[0] = nRow;
temp[1] = nCol;
path.addFirst(temp); //Добавляем в стек
}
public boolean nearExit()
{
Integer[] temp = new Integer[2];
temp = path.peek();
if(temp[1] == maze[0].length-2){
if(maze[temp[0]][temp[1]+1] == ' '){
return true;
}
}
return false;
}
public void goToExit()
{
Integer[] temp = new Integer[2]; //доступ к стеку
Integer[] current = path.peek(); //текущее положение
temp[0] = current[0]; //Выход справа
temp[1] = current[1]+1;
maze[temp[0]][temp[1]] = '-'; //устанавливаем указатель -
path.push(temp); //добавляем в стек
}
public void backTrack()
{
path.removeFirst();
}
public void solvePath()
{
Integer[] temp = new Integer[2]; //доступ к стеку
//если объекты в стеке
while(path.peek() != null){
temp = path.pop(); //текущее положение
maze[temp[0]][temp[1]] = '+'; //устанавливаем указатель +
}
//cleans up the maze
for(int i=0; i<rows; i++){
for(int j=0; j<cols; j++){
if(maze[i][j] == '-')
maze[i][j] = ' ';
}
}
}
public void solveMaze()
{
int[] solve_order; //хранит возможные ходы для каждого положения
setInitialLocation(); //поиск начала лабиринта
while( ! nearExit() ){
solve_order = canSolve(); /*получение возможных направлений*/
if(solve_order[0] == 0){ //если тупик
backTrack(); //идти назад и искать другое направление
}else{ //выбрать направление для решения
if(solve_order[0] == 1){
solveUp();
}else if(solve_order[0] == 2){
solveRight();
}else if(solve_order[0] == 3){
solveDown();
}else if(solve_order[0] == 4){
solveLeft();
}
}
}
goToExit(); //после выхода из цикла идем прямо
//если следующий - выход идем к нему
solvePath(); //весь путь
//устанавливаем указатель +
}
public char[][] getSolution()
{
return maze;
}
public void printSolution()
{
for(int i=0; i<rows; i++){
for(int j=0; j<cols; j++){
System.out.print(maze[i][j]);
}
System.out.println();
}
}
}
import org.eclipse.osgi.util.NLS;
public class Messages extends NLS {
private static final String BUNDLE_NAME= "messages"; //$NON-NLS-1$
public static String Mazes_0;
public static String Mazes_1;
public static String Mazes_2;
public static String Mazes_3;
public static String Mazes_4;
public static String Mazes_5;
public static String Mazes_6;
public static String Mazes_7;
static {
// initialize resource bundle
NLS.initializeMessages(BUNDLE_NAME, Messages.class);
}
private Messages() {
}
}
import acm.program.*;
import acm.graphics.*;
import java.awt.*;
public class Prog8 extends GraphicsProgram {
private static int rows;
private static int cols;
private static final char MAZE_WALL = '#';
public void run ()
{
rows=cols=20;
int numMazes = 0;
Ellers ell = new Ellers(rows,cols);
ell.makeMaze();
numMazes++;
/* отрисовка */
final double delta = (double)1.3*getWidth()/(7*cols);
double x = delta; //координаты в лаберинте
double y = delta;
char[][] maze=null;
for(int k=0; k<numMazes; k++){
if(k==0)
maze = ell.getMaze();
y=delta;
/*цикл.если требуется линия добавляем ее
*
*/
for(int i=0; i<maze.length; i++){
x = delta+(delta*2.2*cols*k); //всегда с первой колонный
//цикл по индексу каждой строки
//если индекс верный или ниже объединение рисуем стену
for(int j=0; j<maze[i].length; j++){
//Если только индекс MAZE_WALL, может быть стена
if(maze[i][j] == MAZE_WALL){
//Если индекс ниже MAZE_WALL
//то стена
if(i != maze.length-1){
if(maze[i+1][j] == MAZE_WALL){
GLine line = new GLine(x,y,x,y+delta);
line.setColor(Color.BLUE);
add(line);
}
}
//Если индекс с права то стена
if(j != maze[i].length-1){
if(maze[i][j+1] == MAZE_WALL){
GLine line = new GLine(x,y,x+delta,y);
line.setColor(Color.BLUE);
add(line);
}
}
}
x+=delta; //переход к следующей колонне
}
y+=delta; //Преход к следующей строке
}
}
}
}
Я попытался визуализировать с помощью acm, почему-то не выходит.В консоли выводит как лабиринт так и кратчайший путь, а в аплете только лабиринт. Помогите победить моё не понимание визуализации.
Добавлено через 12 минут и 4 секунды:Если дело дошло до визуализации, стало быть, с самой генерацией лабиринта проблем не возникло, только с графическим представлением результата?
Графически как-то вывожу, через AWT, до меня не доходит как сделать по шаговую визуализацию, а не так, что запустили прогу и на тебе лабиринт.
