Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 42, средняя оценка - 4.83
Navern
4 / 4 / 0
Регистрация: 01.10.2011
Сообщений: 33
#1

Генерация случайного лабиринта - C++

25.10.2011, 20:24. Просмотров 5602. Ответов 9
Метки нет (Все метки)

Вообщем требуется сгенерировать лабиринт 12х12 с одним входом и выходом. Лабиринт представляется символьным массивом, где '#' - стенка, а '.' - путь, по которому можно пройти. Собственно у меня затык с пониманием как надо реализовать. Максимум что получилось по нормальному одну длинную дорожку вправо и вниз сделать. Всё остальное вместо лабиринта рисует некое поле.

Собственно первое что пришло в голову сделать рекурсивный вариант. Но он у меня получился крайне плохо. В основном нужны советы именно по алгоритму и в каком направлении думать. Готовый код не очень нужен

Примерный код(там внутри правда еще функция путешествия по лабиринту, она не совсем правильная, но я её представляю как дорабатывать, просто сначала надо сгенерировать лабиринт, чтобы все ошибки увидеть).

C++
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <iostream>
using std::cout;
using std::endl;
 
#include <cstdlib>
using std::rand;
using std::srand;
 
#include <ctime>
using std::time;
 
void printMaze( char [][12], int, int );  //prototype
 
//функция получает аргументы масив и точки начала пути
void mazeTraverse ( char maze [][12], int coordX, int coordY )
{
 
    for ( int i = 0; i < 100000000; i ++ ); //хоть какая то задержка
    printMaze (maze, coordX, coordY );
    cout << "\n\n";
 
   //основное условие выход из лабиринта
   //если лабиринт не имеет выхода, то там будет ходить вечно
   //это проблема. Я пока не знаю как решить, потому что не понимаю как иначе первый шаг делается.  
   //либо выход не должен быть в начале, но тогда мы отсекаем вариант, что в лабиринте нету выхода
   if ( coordX == 11 || coordY == 11 || coordX == 0 )
       return;  
    
    //базовый тип условия проверяется возможность хода и наличие стены с определенной стороны
    //шаг рекурсии
    if ( maze[coordX + 1][coordY] == '.')
       mazeTraverse(maze, coordX + 1, coordY );
    else if (maze[coordX][coordY + 1] == '.')
       mazeTraverse(maze, coordX, coordY + 1);
    else if ( maze[coordX - 1][coordY] == '.')
       mazeTraverse( maze, coordX - 1, coordY );
   else if (maze[coordX][coordY - 1] == '.')        
       mazeTraverse( maze, coordX, coordY - 1 );
    
    
}
 
//функция выводящая лабиринт на экран
//потом ввести параметр для масштабируемости
void printMaze ( char maze [][12], int posX, int posY)
{
 
   
   for ( int row = 0; row < 12; row++ )
    {
       for ( int column = 0; column < 12; column++)
        {  
           if ( row == posX && column == posY )
               cout << "X";
            else
              cout << maze[row][column];
        }
        
        cout << "\n";
    }
}
 
//функция генерирующая случайны лабиринт
//начальные точки задаются случайно вызывающей функцией
//изначально будет вызывать чтобы случайно сделать вход
void mazeGenerator ( char maze[][12], int coordX, int coordY)
{
   //нам нужно в полном стенок массиве нарисовать дорожку из точек. 
    //вопрос как это сделать используя случайные числа
    //возможно рекурсивно со случайными штуками
    maze[coordX][coordY] = '.';
    
    //не очень понимаю как сделать чтобы только один выход был
    if ( coordX + 1 < 12 && coordY + 1 < 12 && coordX - 1 >= 0)
    {  
       //переменная которая хранит варианты следующего хода получаемые случайно
        
      int varOfMove = rand() % 2;
        
      if ( varOfMove == 1 && coordX + 1 != '.')     
          mazeGenerator ( maze, coordX + 1, coordY);
        else if ( varOfMove == 0 && coordY + 1 != '.')
        mazeGenerator ( maze, coordX , coordY + 1);        
    }
    else
       return;
}
 
void mazeGenerator2 ( char maze [][12], int coordX, int coordY )
{
   //логика в том, что из нашей текущей точки
   //рисуются четыре линии случайной длины от 2 до 5 клеток
   //тут же будет проверка границ
   int drawPointForward = 2 + rand() % 4;
   int drawPointBack = 2 + rand() % 4;  
   int drawPointUp = 2 + rand() % 4;
   int drawPointDown = 2 + rand() % 4;
    
   if ( (drawPointForward + coordY) < 11 )
   {
      for ( int i = 0; i < drawPointForward; i++ )
         maze[coordX][coordY + i] = '.';
            
      mazeGenerator2( maze, coordX, coordY + drawPointForward );
   }
    
    if ( (coordY - drawPointBack) >= 0 )
    {
       for (int i = 0; i < drawPointBack; i++ )
           maze[coordX][coordY - i] = '.';
            
    }
    
    if ((coordX - drawPointUp) >= 0 )
    {
       for (int i = 0; i < drawPointUp; i++ )
           maze[coordX - i][coordY] = '.';
            
        mazeGenerator2( maze, coordX - drawPointUp, coordY );
    }
    
    if ( (coordX + drawPointDown) < 11 )
    {
       for (int i = 0; i < drawPointDown; i++ )
           maze[coordX + i][coordY] = '.';
    
       
    }
    
    
}
 
int main()
{
 
   srand(time(0));
   char arrayMaze[12][12];
    
    
    for ( int i = 0; i < 12; i++ )
    {
       for ( int j = 0; j < 12; j++ )
        {
           arrayMaze[i][j] = '#';  //заполняем весь массив "стенками"
        }
    }
    
    //находим точку  с которой стартует поход в лабиринте
    //при первом вызове вход случайно организуется в одной из ячеек
    //первого столбца
    mazeGenerator2( arrayMaze, 1 + rand() % 10, 0 );
    
    int start;
    for (start = 0; start < 12; start++ )
    {
       if ( arrayMaze[start][0] == '.' )
           break;
    }
    
    printMaze (arrayMaze, start, 0);
    
    return 0;   
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.10.2011, 20:24     Генерация случайного лабиринта
Посмотрите здесь:

Генерация лабиринта - C++
Разработать приложение, генерирующее лабиринт размером m x n клеток. Дополнительные условия: а) Вход и выход – произвольные клетки...

Генерация 6 свободного лабиринта - C++
#include &quot;stdio.h&quot; #include &quot;stdlib.h&quot; #include &quot;time.h&quot; int ShowMaze(int size, int**maze) { for (int i = 0; i &lt;= size; i++) ...

Генерация случайного числа - C++
Сори за вопрос может уже обсуждался не раз, но всё же возник. Как правильно сгенерировать число от 0 до 1 и какой тип данных лучше...

Генерация случайного числа - C++
Проблемма такова: в программе необходимо получить несколько чисел, от 1 до 255 (или max будет другим -- пока не важно). Стандартные...

Генерация случайного простого числа - C++
Добрый вечер всем! У меня такая проблемма. Необходимо чтобы сгенерировалось 2 простых случайных числа. Для этого я написал функцию с...

Генерация пятизначного случайного числа - C++
Нужно сгенерировать случайное число из пяти цифр и записать ее в переменную типа string. Пытаюсь 5 генерировать цифры в цикле, а как их...

Генерация случайного числа с плавающей чточкой - C++
Добрый день. Подскажите как генерировать случайное число типа float или double. Обычно использую rand(), но она подходит только для целых,...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
hepr
61 / 33 / 5
Регистрация: 21.10.2010
Сообщений: 539
25.10.2011, 21:29     Генерация случайного лабиринта #2
Ну я бы сделал примерно так:
Есть матрица 12 на 12, начинаем в 0 0, и далее рекурсивная рандомная функция, то есть смотришь генерируешь число от 0 до 3, в какую сторону идти, если точка занята, то следующую смотришь, если все заняты, то функцию обрывается, и генерируешь её заново, и так пока функция не выйдет за пределы массива, то есть не найдет выход, ну и естественно в время путешествия отмечаешь нужные точки, а потом проходишься по готовой матрице и отмечаешь не отмеченные точки матрицей
Navern
4 / 4 / 0
Регистрация: 01.10.2011
Сообщений: 33
25.10.2011, 22:14  [ТС]     Генерация случайного лабиринта #3
Цитата Сообщение от hepr Посмотреть сообщение
Ну я бы сделал примерно так:
Есть матрица 12 на 12, начинаем в 0 0, и далее рекурсивная рандомная функция, то есть смотришь генерируешь число от 0 до 3, в какую сторону идти, если точка занята, то следующую смотришь, если все заняты, то функцию обрывается, и генерируешь её заново, и так пока функция не выйдет за пределы массива, то есть не найдет выход, ну и естественно в время путешествия отмечаешь нужные точки, а потом проходишься по готовой матрице и отмечаешь не отмеченные точки матрицей
Тут вот в чем лично у меня еще проблема. Не совсем понимаю как сотворить проверку на то, чтобы не организовывалось одно большое поле. Если просто смотреть занята следующая точка или нет. То поле всё равно будет получаться в некоторых случаях. А мне нужно только чтобы коридорчики были
hepr
61 / 33 / 5
Регистрация: 21.10.2010
Сообщений: 539
25.10.2011, 22:20     Генерация случайного лабиринта #4
Есть еще предложения перед тем как перейти на след точку, посмотри граничит ли она с другими, которые уже входят в путь, если да то выбираешь следующую точку, если таких точек нет, рекурсия обрывается
Sum42
78 / 10 / 2
Регистрация: 11.10.2010
Сообщений: 87
25.10.2011, 23:09     Генерация случайного лабиринта #5
не из Дейтелов задачка?
Navern
4 / 4 / 0
Регистрация: 01.10.2011
Сообщений: 33
25.10.2011, 23:17  [ТС]     Генерация случайного лабиринта #6
Цитата Сообщение от Sum42 Посмотреть сообщение
не из Дейтелов задачка?
Да оттуда. По учебнику занимаюсь. Стараюсь большую часть сам делать, но некоторое мне просто не дано наверное осилить.
Navern
4 / 4 / 0
Регистрация: 01.10.2011
Сообщений: 33
27.10.2011, 10:34  [ТС]     Генерация случайного лабиринта #7
Надеюсь что кто-нибудь еще сможет помочь, дать пару идей и прочее.
ЯрославК
2 / 2 / 0
Регистрация: 22.02.2015
Сообщений: 10
22.02.2015, 20:50     Генерация случайного лабиринта #8
Вводятся ширина и высота, лабиринт генерируется, и сам находит выход. Вам предлагается выбрать, просматривать, как ищется путь или нет.(yes/no). Удачи
C++
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include <iostream>
#include <math.h>
#include <cmath>
#include <string>
#include <ctime>
#include <windows.h> 
#include <stdio.h>
using namespace std;
int main(){
    HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
    SetConsoleTextAttribute(hConsole, (WORD)((0 << 4) | 11));
    setlocale(0, "rus");
    srand(time(0));
    string b[1000],t="p";
    int a = 1, c[1000], c1 = 2, n, k = 0,ii=0,oo=0;
    while (ii % 2 == 0 || oo % 2 == 0 || ii < 5 || oo < 5 || (ii + 2)*(oo + 2) >= 1000 || oo>70){
        cout << "Введите нечетную высоту,ширену, рекомендовано 15 27." << endl << "Самая жесть 23 37: ";
        cin >> ii >> oo;
        if (ii < 5) cout << "Маленикая высота!!!" << endl;
        if (oo < 5) cout << "Маленикая ширина!!!" << endl;
        if ((ii + 2)*(oo + 2) >= 1000) cout << "Слишком большой лабиринт" << endl;
        if (oo>70)cout << "Слишком большая ширина" << endl;
        if (oo % 2 == 0 || ii % 2 == 0)cout << "Числа должны быть нечетными!!" << endl;
    }
    ii += 2;
    oo += 2;
    for (int x = 0; x < ii*oo; x++){
        b[x] = " ";
        if (x < oo)b[x] = "#";
        if (x>ii*oo-oo-1)b[x] = "#";
        if (x % oo == 0)b[x] = "#";
        if (x % oo == oo-1)b[x] = "#";
    }
    while (a%2==1)
       a = rand() % (oo-4)+oo*ii-oo+2;
    b[a] = ".";
    b[a-oo] = ".";
    a = 1;
    while (a%2==1)
       a = rand() % (oo-4)+2;
    b[a] = ".";
    b[a+oo] = ".";
    a += oo*2;
    cout << 1;
    while (c1>1){
        int a1 = a;
        if (k < 15){
            c[c1] = a;
            c1++;
        }
        b[a] = ".";
        k = 0;
        while (a1 == a && k<15){
            n = rand() % 4 + 1;
            if (n == 1 && b[a + 2] ==" ")a++;
            if (n == 2 && b[a + oo*2] ==" ")a += oo;
            if (n == 3 && b[a - oo*2] ==" " )a -= oo;
            if (n == 4 && b[a - 2] ==" ")a--;
            k++;
        }
        if (k == 15){
            c[c1 - 1] = 0;
            c1 -= 2;
            a = c[c1];
            c1++;
        }
        if (a>0)
            b[a] = ".";
        if (a < 0)
            c1 = 0;
        if (k < 15){
            if (n == 1)a++;
            if (n == 2)a += oo;
            if (n == 3)a -= oo;
            if (n == 4)a--;
            b[a] = ".";
        }
    }
    b[oo*2] = "#";
    for (int x = 0; x < oo*ii; x++){
        if (b[x] == "#")b[x] = "";
        if (b[x] == " ")b[x] = "#";
        if (x>oo * 2||x<oo)
             if (b[x] == ".")b[x] = " ";
    }
    system("CLS");
    for (int x = 0; x < oo*ii; x++){
        cout << b[x];
        if (x % oo == oo-1)
            cout << endl;
    }
    //Прохождение
    int a1,a2,m[1000],j,h=0;
    c1 = 0;
    cout << "Хотите следить за прохождением лабиринта? ";
    while (h==0){
        cin >> t;
        if (t == "yes"){
            h = 1;
            j = 0;
        }
        if (t == "no"){
            h = 1;
            j = 1;
        }
    }
    k = j;
    for (int x = 0; x < oo; x++){
        for (int y = 0; y < oo*ii; y++)
            b[y] = b[y + 1];
    }
    for (int x = 0; x < oo;x++)
        if (b[x] == ".")
            a = x;
    for (int x = oo*(ii-3)-1; x < oo*(ii-2); x++)
        if (b[x] == " ")
            a1 = x;
    for (int x = 0; x < 1000; x++)
        c[x] = 0;
       b[a] = ".";
    while (a != a1){
        if (k == 0){
            system("CLS");
            for (int x = 0; x < oo*ii; x++){
                cout << b[x];
                if (x % oo == oo - 1)
                    cout << endl;
            }
            Sleep(150);
        }
        n = 0;
        a2 = a;
        while (a2 == a){
            n++;
            k = j;
            if (n == 1 && b[a - oo] ==" "&&a - oo>0&&m[a-oo]!=666)a -= oo;
            if (n == 2 && b[a - 1] == " "&&m[a -1] != 666)a--;
            if (n == 3 && b[a + 1] == " "&&m[a +1] != 666)a++;
            if (n == 4 && b[a + oo] == " "&&m[a + oo] != 666)a += oo;
            if (n == 5){
                k = 1;
                n = 0;
                c1--;
                b[a] = " ";
                m[a] = 666;
                c1--;
                a = c[c1];
                c1++;
            }
        }
        b[a] = ".";
        c[c1] = a;
        c1++;
    
    }
    system("CLS");
    for (int x = 0; x < oo*ii; x++){
        if (b[x] == ".")
            SetConsoleTextAttribute(hConsole, (WORD)((0 << 4) | 14));
        cout << b[x];
        if (x % oo == oo - 1)
            cout << endl;
        SetConsoleTextAttribute(hConsole, (WORD)((0 << 4) | 11));
    }
    return 0;
}
System16v
3 / 3 / 0
Регистрация: 19.02.2014
Сообщений: 115
18.04.2015, 23:03     Генерация случайного лабиринта #9
А может кто пояснить если не трудно.Что делается в строчках с 53 по 85 в коде что привел ЯрославК? Пытаюсь разобраться в коде,понимаю что там вроде как "рисуются" линии прохода от входа до выхода,но не могу понять каким образом . С 25й по 53юю как бы все понятно,что и как "рисуется",сначала рамка,потом вход\выход и 1ые точки.А вот потом,сколько ни сидел ни соображал,не могу врубиться .И может у кого есть код с пояснениями,что и как строится?По книге Дейтела там просят сделать лабиринт в двумерном массиве,единственное что смог сделать,это дополнить этот код и скопировать лабиринт из одномерного массива что тут приводится в двумерный.Но все же хочется понять алгоритм.Поясните пожалуйста,кому не трудно.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.02.2017, 03:41     Генерация случайного лабиринта
Еще ссылки по теме:

Генерация случайного числа каждую секунду - C++
Нужно каждую секунду генерировать случайное число. Ниже мой код, который выполняет задачу, но функция слип останавливает весь процесс и в...

Запись текста и генерация случайного числа - C++
Собственно задача такая: записать строки с рандомными числовым значением в некоторое количество создаваймых файлов. Файлы создаются без...

Генерация случайного числа больше нуля, но меньше единицы - C++
Всем привет. Подскажите, как можно генерировать псевдослучайное число больше нуля, но меньше единицы. При этом количество цифр после...

Генерация случайного четырехзначного числа без цифр, больших 7 и 0 - C++
Нужно сгенерировать случайное четырехзначные число без цифр, больших 7 и 0. Пишу вот такой код: Но он ничего не выводится....

Выход из лабиринта - C++
Всем привет, возник вопрос по поводу лабиринта. Посмотрев форум не нашел такого же задания. Суть - написать программу, с помощью которой...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Liss29
23 / 12 / 2
Регистрация: 18.11.2012
Сообщений: 484
Завершенные тесты: 1
26.02.2017, 03:41     Генерация случайного лабиринта #10
Долго мучался, но кое что, вроде бы, получилось.
C++
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
82
83
84
85
86
87
88
89
90
bool tst(char** m, const int row, int j)
{
    int newRow;
    newRow = row - 1;
    //?????????? ??????, ??? ???????? ?????????? ?????
    if(m[newRow][j + 1] == '#' && m[newRow][j - 1] == '#' || m[newRow][j - 1] == '.' && m[newRow][j + 1] == '#')
    {
        return true;
    }
    else 
    {
        return false;
    }
}
void mazeGenerator(char** maze, const int row, const int col)
{
    enum STEP{YES, NO};
    srand(time(0));
    int i, j;
    
    for(i = 0; i < row; i++)
    {
        if(i == 0 || i == row - 1)
        {
            for(j = 0; j < row; j++)
            {
                maze[i][j] = '#';
            }
        }
        //===================================
        else if(i == 1)
        {
            for(j = 0; j < col; j++)
            {
                if(j == 0 || j == col - 1)
                {
                    maze[i][j] = '#';
                    continue;
                }
                else if(j > 0 && j < col - 1)
                {
                    if((rand() & 1) == YES)
                    {
                        maze[i][j] = '#';
                        continue;
                    }
                    else 
                    {
                        maze[i][j] = '.';
                        continue;
                    }
                }
            }
        }
        //========================================
        else if(i > 1 && i < row - 1)
        {   
            for(j = 0; j < col; j++)
            {
                if(j == 0 || j == col - 1)
                {
                    maze[i][j] = '#';
                    continue;
                }   
                else if(j > 0 && j < col - 1)
                {   
                    if((rand() & 1) == YES)
                    {
                        if(tst(maze, i, j))
                        {
                            maze[i][j++] = '.';
                            maze[i][j] = '#';
                            continue;
                        }
                        else 
                        {
                            maze[i][j] = '#';
                            continue;
                        }
                    }
                    else 
                    {
                        maze[i][j] = '.';
                        continue;
                    }
                }
            }
        }
    }
}
Yandex
Объявления
26.02.2017, 03:41     Генерация случайного лабиринта
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru