Непристойно проста реалізація непристойно простого алгоритму генерації лабіринту

Продовження цієї статті про дуже простий алгоритм генерації прямокутних лабіринтів. У цій статті я наведу мою реалізацію алгоритму на С++, а також покажу кілька додаткових функцій, які породив мій нудьгуючий мозок. Якщо наважитеся продовжити читати, переконайтеся, що ознайомилися з моєї попередньої статті. Глянули? Молодці, продовжуємо.

Де ж код?
Почнемо з початку — підтягуємо стандартні бібліотеки, оголошуємо функції.

#include < iostream>
#include < cstdlib>
#include<ctime>
using namespace std;
bool deadend(int, int, int**, int, int); // Допоміжна функція, що визначає тупики
void visual(int**, int, int); // Зображення результату з допомогою консольної графіки
void mazemake(int**, int, int); // Власне алгоритм
const int wall = 0, pass = 1;

Все ще дуже просто, як я і люблю. В main ми зможемо визначити габарити лабіринту в змінних height width (нагадую, що розміри лабіринту виключно непарні, витрати алгоритму). Ці параметри можна винести за межі main і зробити їх константами або просто глобальними змінними, програма від цього не постраждає.

int main(){

srand((unsigned)time(NULL));

int height = 21, width = 21;

int** maze = new int*[height]; 
for(int i = 0; i < height; i++)
maze[i] = new int[width];

mazemake(maze, height, width);

visual(maze,height,width);

for(int i = 0; i < height; i++) 
delete[] maze[i];
delete[] maze;

return 0;
}

Власне, ось і весь main. Весь лабіринт без проблем зберігається в двовимірний динамічний масив, з яким ми і працюємо. Після виконання функції mazemake, масив maze зберігається готовий лабіринт, в якому 0 — це стіна, а 1 — це прохід.
Продовжимо, функція deadend, шукає безвихідні ситуації для крота — коли на всі чотири напрямки вже є проходи.

bool deadend(int x, int y, int** maze, int height, int width){
int a = 0;

if(x != 1){
if(maze[y][x 2] == pass)
a+=1;
}
else a+=1;

if(y != 1){
if(maze[y 2][x] == pass)
a+=1;
}
else a+=1;

if(x != width-2){
if(maze[y][x+2] == pass)
a+=1;
}
else a+=1;

if(y != height-2){
if(maze[y+2][x] == pass)
a+=1;
}
else a+=1;

if(a == 4)
return 1;
else
return 0;
}

Трохи deadend. Ця функція повертає значення true якщо кріт в глухому куті, інакше — false. Чому двічі if, а не логічне І? Дуже просто — перша перевірка на присутність поруч зовнішньої непроникною стіни. Непроникна вона з кількох причин — ми так зробили, вибравши саме ці габарити, відповідно виділили пам'ять для масиву (управління пам'яттю, аняня ^>^), так і не дуже-то перевіриш (-1)-й елемент масиву. Також, зверніть увагу на фігурні дужки після первинного if else відноситься саме до нього, а інший спосіб записати це мені невідомий.

void visual(int** maze, int height, int width){
for(int i = 0; i < height; i++){
for(int j = 0; j < width; j++)
switch(maze[i][j]){
case wall: cout<<"0 "; break;
case pass: cout<<" "; break;
}
cout<<endl;
}
cout<<endl; 
}

Що ще потрібно для щастя? Наступна зупинка — mazemake.

void mazemake(int** maze, int height, int width){
int x, y, c, a; 
bool b;

for(int i = 0; i < height; i++) // Масив заповнюється землею-нуликами
for(int j = 0; j < width; j++)
maze[i][j] = wall;

x = 3; y = 3; a = 0; // Точка приземлення крота і лічильник
while(a < 10000){ // Так, вибачте, милиці, інакше є, але лінь
maze[y][x] = pass; a++;
while(1){ // Нескінченний цикл, який переривається тільки тупиком
c = rand()%4; // Нагадую, що кріт прориває
switch©{ // по дві клітини в одному напрямку за стрибок
case 0: if(y != 1)
if(maze[y 2][x] == wall){ // Вгору
maze[y-1][x] = pass;
maze[y 2][x] = pass;
y-=2;
}
case 1: if(y != height-2) 
if(maze[y+2][x] == wall){ // Вниз
maze[y+1][x] = pass;
maze[y+2][x] = pass;
y+=2;
}
case 2: if(x != 1)
if(maze[y][x 2] == wall){ // Наліво
maze[y][x-1] = pass;
maze[y][x 2] = pass;
x-=2;
}
case 3: if(x != width-2)
if(maze[y][x+2] == wall){ // Направо
maze[y][x+1] = pass;
maze[y][x+2] = pass;
x+=2;
}
}
if(deadend(x,y,maze,height,width)
break;
}

if(deadend(x,y,maze,height,width) / / Витягуємо крота з глухого кута
do{
x = 2*(rand()%((width-1)/2))+1;
y = 2*(rand()%((height-1)/2))+1;
}
while(maze[y][x] != pass);
} // На цьому і все.
}

Занадто просто? Загалом-то так, так і є. До непристойності просто. Тут є все ті ж подвійні if, з тієї ж причини. Навіть поскаржитися нема на що. Хіба що милицю у вигляді лічильника. Якщо він ранить ваші почуття — ласкаво просимо в другу главу нашої розповіді.

Фічі і штуки-дрюки

Кімнати

Ми навчили ссавець робити нам лабіринт. Чому б це створення не змусити зробити нам пару кімнат? Адже ми підступні лиходії-вчені і не знаємо куди подіти бідних тваринок.
Якщо ми хочемо мати можливість робити кімнати і визначати їх параметри, то код трохи змінюється то тут, то там. Кімнати теж мають непарні розміри.

void mazemake(int**, int, int, int, int, int); // Більш розширене оголошення функції
const int wall = 0, pass = 1, room = 4; // Нова константа
...
int height = 59, width = 111, k = 30; // Ми включили параметр кількості кімнат
int rheight = 7, rwidth = 5; // Розміри кімнати
...
void mazemake(int** maze, int height, int width, int k, int rheight, int rwidth){
int x, y, c, a;
bool b, swap = 1;
for(int i = 0; i < height; i++)
for(int j = 0; j < width; j++)
maze[i][j] = wall;

rheight--; rwidth--; // Виключно для зручності

for(int l = 0; l < k; l++){ // Генерація кімнат
b = 1; 
while(b){
do{ // Точка-центр кімнати
if(rwidth%4 == 0) // Кімнати, з різною делимостью на 4 поводяться 
x = 2*(rand()%(width/2))+1; // по різному, уніфікуємо
else
x = 2*(rand()%(width/2))+2;
if(rheight%4 == 0) 
y = 2*(rand()%(height/2))+1;
else
y = 2*(rand()%(height/2))+2;
}
while(x < (rwidth+2) || x > (width-rwidth-2) || 
y < (rheight+2) || y > (height-rheight-2));

b = 0; // Кімнати не повинні торкатися
for(int i = (y-rheight-2); i < (y+rheight+2); i++)
for(int j = (x-rwidth-2); j < (x+rwidth+2); j++)
if(maze[i][j] == room)
b = 1;

if(b)
continue;

for(int i = (y-rheight/2); i < (y+rheight/2+1); i++) // Розкопки кімнати
for(int j = (x-rwidth/2); j < (x+rwidth/2+1); j++)
maze[i][j] = room;

c = rand()%4; // Двері в кімнату, визначаємо в яку стіну
// Нижня, верхня, права і ліва відповідно
// Нагромадження у вигляді rand()... потрібно для того, щоб двері стояла в різних
// місцях стіни
if(c == 0) maze[y+rheight/2+1][x-rwidth/2+2*(rand()%(rwidth/2+1))] = room;
if(c == 1) maze[y-rheight/2-1][x-rwidth/2+2*(rand()%(rwidth/2+1))] = room;
if(c == 2) maze[y-rheight/2+2*(rand()%(rheight/2+1))][x+rwidth/2+1] = room;
if(c == 3) maze[y-rheight/2+2*(rand()%(rheight/2+1))][x-rwidth/2-1] = room;
// swap відповідає за можливість повертати кімнату на 90°
if(swap){
rheight += rwidth;
rwidth = rheight - rwidth;
rheight -= rwidth;
} // Ось так справжні мужики змінюють змінні значеннями
}
}
...
int deadend(int x, int y, int** maze, int height, int width){
int a = 0; // У deadend тепер потрібно враховувати те, що в кімнату ми не можемо стрибнути

if(x != 1){
if(maze[y][x 2] == pass || 
maze[y][x 2] == room)
a+=1;
}
else a+=1;
...


Гриб

Хм… Ні, не солідно. Грибоподібний алгоритм пошуку шляху в ідеальних лабіринтах. Ось так краще. Ладно, менше слів, більше коду.

...
void shroom(int**, int, int); 
const int wall = 0, pass = 1, liveshroom = 2, deadshroom = 3, room = 4, start = 5, finish = 6;
int main(){

srand((unsigned)time(NULL));

int height = 59, width = 111, k = 30; // Грибний алгоритм безпечно працює з кімнатами -
int rheight = 7, rwidth = 5; // він їх ігнорує

int** maze = new int*[height]; 

for(int i = 0; i < height; i++)
maze[i] = new int[width];

mazemake(maze, height, width, k, rheight, rwidth); 

visual(maze,height,width);

maze[1][1] = start; 
maze[height-2][width-2] = finish;
shroom(maze,height,width); // Гриб не змінює архітектуру лабіринту, але залишає слід
visual(maze,height,width); // між стартом і фінішем

for(int i = 0; i < height; i++) 
delete[] maze[i];
delete[] maze;

return 0;
... 
void shroom(int** maze, int height, int width){
int x, y;

for(int i = 0; i < height; i++) // Пошук старту
for(int j = 0; j < width; j++)
if(maze[i][j] == start){
x = j; y = i;
}

while(maze[y][x] != finish){ // Умова виходу - гриб знайшов фініш
maze[y][x] = liveshroom; // Заражаем прохід
// Гриб шукає прохід праворуч, ліворуч, вниз і вгору послідовно,
// він може пересуватися тільки по порожніх коридорах
if(maze[y][x+1] == pass){ 
maze[y][x+1] = liveshroom;
x+=2;
continue;
}

if(maze[y][x-1] == pass){ 
maze[y][x-1] = liveshroom;
x-=2;
continue;
}

if(maze[y+1][x] == pass){
maze[y+1][x] = liveshroom;
y+=2;
continue;
}

if(maze[y-1][x] == pass){ 
maze[y-1][x] = liveshroom;
y-=2;
continue;
}

if(maze[y][x+1] != pass && // Якщо гриб не може рухатися - вона вмирає, 
maze[y][x-1] != pass && // ведуча головка гриба (x, y) повертається на найближчий 
maze[y+1][x] != pass && // живої гриб
maze[y-1][x] != pass){
maze[y][x] = deadshroom;

if(maze[y][x+1] == liveshroom){ 
maze[y][x+1] = deadshroom;
x+=2;
continue;
}

if(maze[y][x-1] == liveshroom){ 
maze[y][x-1] = deadshroom;
x-=2;
continue;
}

if(maze[y+1][x] == liveshroom){ 
maze[y+1][x] = deadshroom;
y+=2;
continue;
}

if(maze[y-1][x] == liveshroom){ 
maze[y-1][x] = deadshroom;
y-=2;
continue;
}
}
}

for(int i = 0; i < height; i++) // Мертвий гриб розкладається, не залишаючи сліду в лабіринті
for(int j = 0; j < width; j++)
if(maze[i][j] == deadshroom)
maze[i][j] = pass;
}
}

Чесно, навіть нічого сказати. Просто знаходимо єдиний шлях між точками і показуємо. Хіба що в visual додати case liveshroom: cout<<".* "; break;

Не милиця

Якщо вам дуже не сподобався лічильник в основному алгоритмі, то ось вам чудова альтернатива — функція перевірки, яка запускається у сто разів циклів:

...
x = 3; y = 3; a = 0;
while(1){
a++;
if(a%100 == 0)
if(ended(maze, height, width)
break;
maze[y][x] = pass;
...
bool ended(int** maze, int height, int width){
bool b = 1;

for(int i = 1; i < (height - 1); i += 2)
for(int j = 1; j < (width - 1); j += 2)
if(maze[i][j] == wall)
b = 0;
return b;
}

З випереджаючим оголошенням впораєтеся. Успіхів, користуйтеся на здоров'я.
Ах так, картиночкиЛабіринти 59х111, 30-40 кімнат.
Простий лабіринт без кімнат.
image
Кімнати 5х5, демонструють старий баг — двері були тільки у двох позиціях на стінах.
image
Кімнати 3х5, без свапа, двері адекватно розподілені.
image
Кімнати 5х7, свапо включений
image
Демонстрація гриба, без кімнат…
image
… і з 70-ю свапнутыми кімнатами 3х5.
image

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.