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

@Navern · Регистрация: 01.10.2011

Студворк — интернет-сервис помощи студентам

Вообщем требуется сгенерировать лабиринт 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;   
}

@hepr · 25.10.2011, 21:29

Ну я бы сделал примерно так:
Есть матрица 12 на 12, начинаем в 0 0, и далее рекурсивная рандомная функция, то есть смотришь генерируешь число от 0 до 3, в какую сторону идти, если точка занята, то следующую смотришь, если все заняты, то функцию обрывается, и генерируешь её заново, и так пока функция не выйдет за пределы массива, то есть не найдет выход, ну и естественно в время путешествия отмечаешь нужные точки, а потом проходишься по готовой матрице и отмечаешь не отмеченные точки матрицей

@Navern · 25.10.2011, 22:14 **[ТС]**

Сообщение от hepr

Ну я бы сделал примерно так:
Есть матрица 12 на 12, начинаем в 0 0, и далее рекурсивная рандомная функция, то есть смотришь генерируешь число от 0 до 3, в какую сторону идти, если точка занята, то следующую смотришь, если все заняты, то функцию обрывается, и генерируешь её заново, и так пока функция не выйдет за пределы массива, то есть не найдет выход, ну и естественно в время путешествия отмечаешь нужные точки, а потом проходишься по готовой матрице и отмечаешь не отмеченные точки матрицей

Тут вот в чем лично у меня еще проблема. Не совсем понимаю как сотворить проверку на то, чтобы не организовывалось одно большое поле. Если просто смотреть занята следующая точка или нет. То поле всё равно будет получаться в некоторых случаях. А мне нужно только чтобы коридорчики были

@hepr · 25.10.2011, 22:20

Есть еще предложения перед тем как перейти на след точку, посмотри граничит ли она с другими, которые уже входят в путь, если да то выбираешь следующую точку, если таких точек нет, рекурсия обрывается

@Sum42 · 25.10.2011, 23:09

не из Дейтелов задачка?

@Navern · 25.10.2011, 23:17 **[ТС]**

Сообщение от Sum42

не из Дейтелов задачка?

Да оттуда. По учебнику занимаюсь. Стараюсь большую часть сам делать, но некоторое мне просто не дано наверное осилить.

@Navern · 27.10.2011, 10:34 **[ТС]**

Надеюсь что кто-нибудь еще сможет помочь, дать пару идей и прочее.

@ЯрославК · 22.02.2015, 20:50

Вводятся ширина и высота, лабиринт генерируется, и сам находит выход. Вам предлагается выбрать, просматривать, как ищется путь или нет.(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 · 18.04.2015, 23:03

А может кто пояснить если не трудно.Что делается в строчках с 53 по 85 в коде что привел ЯрославК? Пытаюсь разобраться в коде,понимаю что там вроде как "рисуются" линии прохода от входа до выхода,но не могу понять каким образом

. С 25й по 53юю как бы все понятно,что и как "рисуется",сначала рамка,потом вход\выход и 1ые точки.А вот потом,сколько ни сидел ни соображал,не могу врубиться

.И может у кого есть код с пояснениями,что и как строится?По книге Дейтела там просят сделать лабиринт в двумерном массиве,единственное что смог сделать,это дополнить этот код и скопировать лабиринт из одномерного массива что тут приводится в двумерный.Но все же хочется понять алгоритм.Поясните пожалуйста,кому не трудно.

@Liss29 · 26.02.2017, 03:41

Долго мучался, но кое что, вроде бы, получилось.

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;
                    }
                }
            }
        }
    }
}

Новые блоги и статьи Все статьи Все блоги /
Перемещение выделенных строк ТЧ из одного документа в другой Maks 30.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .	Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .	Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .
Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .

@hepr 63 / 35 / 13 Регистрация: 21.10.2010 Сообщений: 538
	25.10.2011, 21:29
	Ну я бы сделал примерно так: Есть матрица 12 на 12, начинаем в 0 0, и далее рекурсивная рандомная функция, то есть смотришь генерируешь число от 0 до 3, в какую сторону идти, если точка занята, то следующую смотришь, если все заняты, то функцию обрывается, и генерируешь её заново, и так пока функция не выйдет за пределы массива, то есть не найдет выход, ну и естественно в время путешествия отмечаешь нужные точки, а потом проходишься по готовой матрице и отмечаешь не отмеченные точки матрицей 0

@hepr 63 / 35 / 13 Регистрация: 21.10.2010 Сообщений: 538
	25.10.2011, 22:20
	Есть еще предложения перед тем как перейти на след точку, посмотри граничит ли она с другими, которые уже входят в путь, если да то выбираешь следующую точку, если таких точек нет, рекурсия обрывается 0

@Sum42 78 / 10 / 2 Регистрация: 11.10.2010 Сообщений: 88
	25.10.2011, 23:09
	не из Дейтелов задачка? 0

@Navern 4 / 4 / 0 Регистрация: 01.10.2011 Сообщений: 33
	27.10.2011, 10:34 [ТС]
	Надеюсь что кто-нибудь еще сможет помочь, дать пару идей и прочее. 0

@System16v 3 / 3 / 1 Регистрация: 19.02.2014 Сообщений: 115
	18.04.2015, 23:03
	А может кто пояснить если не трудно.Что делается в строчках с 53 по 85 в коде что привел ЯрославК? Пытаюсь разобраться в коде,понимаю что там вроде как "рисуются" линии прохода от входа до выхода,но не могу понять каким образом . С 25й по 53юю как бы все понятно,что и как "рисуется",сначала рамка,потом вход\выход и 1ые точки.А вот потом,сколько ни сидел ни соображал,не могу врубиться .И может у кого есть код с пояснениями,что и как строится?По книге Дейтела там просят сделать лабиринт в двумерном массиве,единственное что смог сделать,это дополнить этот код и скопировать лабиринт из одномерного массива что тут приводится в двумерный.Но все же хочется понять алгоритм.Поясните пожалуйста,кому не трудно. 0