Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Генерация лабиринта.  (Прочитано 7613 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Lady ALLA
Новенький

ru
Offline Offline

« : 23-06-2015 21:55 » 

Всем добра!Уважаемые, мне требуется выполнить визуализацию алгоритма Эйлера для генерации лабиринта(не в консоли), т.е продемонстрировать сам процесс генерации алгоритмом.А я что-то не могу понять с чего начать и куда идти  А черт его знает....Помогите советом, подзатыльником, пинком под ... Скромно так... и кто чем может, да бы направится мне в нужное русло.
Заранее спасибо!  Улыбаюсь
Записан
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #1 : 23-06-2015 22:10 » 

мне требуется выполнить визуализацию алгоритма Эйлера

Именно Эйлера, не Эллера?
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Lady ALLA
Новенький

ru
Offline Offline

« Ответ #2 : 23-06-2015 22:28 » 

Скорее Эллера(Eller), это мои трудности перевода)
Записан
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #3 : 23-06-2015 22:38 » 

Если дело дошло до визуализации, стало быть, с самой генерацией лабиринта проблем не возникло, только с графическим представлением результата?
Записан

Всего лишь неделя кодирования с последующей неделей отладки могут сэкономить целый час, потраченный на планирование программы. - Дж. Коплин.

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Lady ALLA
Новенький

ru
Offline Offline

« Ответ #4 : 24-06-2015 15:20 » 

Вот как представляется мне данная генерация

Код: (Java)
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 секунд:
Собственно вот остальная часть программа, с поиском кратчайшего пути.
Код: (Java)
//Параметры
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);
       
    }
}
Код: (Java)
//поиск кратчайшего пути
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();
        }
    }
}

 
Код: (Java)
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() {
        }
}
Код: (Java)
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, до меня не доходит как сделать по шаговую визуализацию, а не так, что запустили прогу и на тебе лабиринт.
« Последнее редактирование: 24-06-2015 18:34 от Lady ALLA » Записан
Lady ALLA
Новенький

ru
Offline Offline

« Ответ #5 : 25-06-2015 11:58 » 

Люди добрые, спасайте... .Тону, не получается визуализировать лабиринт (
Записан
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines