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

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

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@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