Продолжение этой статьи об очень простом алгоритме генерации прямоугольных лабиринтов. В этой статье я приведу мою реализацию алгоритма на С++, а также покажу несколько дополнительных функций, которые породил мой скучающий . Если осмелитесь продолжить читать, убедитесь, что ознакомились с моей предыдущей статьей. Глянули? Молодцы, продолжаем.
Где же код?
Начнем с начала — подтягиваем стандартные библиотеки, объявляем функции.
#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(c){ // по две клетки в одном направлении за прыжок
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;
}
С опережающим объявлением справитесь. Успехов, пользуйтесь на здоровье.
Ах да,
Простой лабиринт без комнат.
Комнаты 5х5, демонстрируют старый баг — двери были только в двух позициях на стенах.
Комнаты 3х5, без свапа, двери адекватно распределены.
Комнаты 5х7, свап включен
Демонстрация гриба, без комнат…
… и с 70-ю свапнутыми комнатами 3х5.
Автор: BestMordaEver
