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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 42, средняя оценка - 4.83
Navern
4 / 4 / 0
Регистрация: 01.10.2011
Сообщений: 33
25.10.2011, 20:24     Генерация случайного лабиринта #1
Вообщем требуется сгенерировать лабиринт 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
 Аватар для hepr
60 / 32 / 5
Регистрация: 21.10.2010
Сообщений: 538
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
 Аватар для hepr
60 / 32 / 5
Регистрация: 21.10.2010
Сообщений: 538
25.10.2011, 22:20     Генерация случайного лабиринта #4
Есть еще предложения перед тем как перейти на след точку, посмотри граничит ли она с другими, которые уже входят в путь, если да то выбираешь следующую точку, если таких точек нет, рекурсия обрывается
Sum42
 Аватар для 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;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.04.2015, 23:03     Генерация случайного лабиринта
Еще ссылки по теме:

C++ Генерация случайного числа
C++ Генерация 6 свободного лабиринта
Генерация пятизначного случайного числа C++

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

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

Текущее время: 10:56. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru