Неприлично простая реализация неприлично простого алгоритма генерации лабиринта

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

Где же код?

Начнем с начала — подтягиваем стандартные библиотеки, объявляем функции.

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

С опережающим объявлением справитесь. Успехов, пользуйтесь на здоровье.

Ах да, картиночки.

Посмотреть

Лабиринты 59х111, 30-40 комнат.

Простой лабиринт без комнат.



Комнаты 5х5, демонстрируют старый баг — двери были только в двух позициях на стенах.



Комнаты 3х5, без свапа, двери адекватно распределены.



Комнаты 5х7, свап включен



Демонстрация гриба, без комнат…



… и с 70-ю свапнутыми комнатами 3х5.