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

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

    Где же код?


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

    #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)-ый элемент массива. Также, обратите внимание на фигурные скобки после первичного ifelse относится именно к нему, а другой способ записать это мне неизвестен.

    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 комнат.

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

    image

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

    image

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

    image

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

    image

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

    image

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

    image
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 54

      +6
      Где же код?

      Всё очень хорошо, но тут скорее — «где же текст?», за картинки — спасибо, тема про крота — не раскрыта.
        0
        А ссылка на страницу в самом начале? Там весь алгоритм, вроде доступно расписан.
          0
          Не хотелось отвлекаться от сути, а после статьи желания вернуться в начало не было. Хотя заголовок у вас правильно передаёт мысль, но первый абзац читается в довольно чётком ключе: «продолжение алгоритма с упором на реализацию». Манипулировать читателем предупреждениями — бессмысленно, это просто ушло в игнор на автомате. Ну а поскольку никакого алгоритма не было, а была только реализация то закономерно: просмотреть наискосок и читать следующие вкладки браузера. Наверное, формально, вы — правы. За гифку в первой части, спасибо.
        +3
        Почему бы не использовать отступы в 16 символов или давайте сразу в 64. Никогда не понимал это странное желание растягивать код, что по горизонтали что по вертикали.
          +2
          По мне так 4 вполне хороший компромисс: 2 позиции для меня недостаточно выразительны, а 8 разрывают канву повествования. Но я-то и открывающую фигурную сношу, чтобы визуальное сопоставление с закрывающей было «автоматическим».
            +4
            Это нативные табы. По-умолчанию они шириной в 8 символов (что актуально для текста), на хабре просто в стилях не хватает указания корректного размера. Попробуйте сами в консоли запустить:
            document.body.style.tabSize = 4
            
              +8
              То есть лучше пробелы использовать, чтобы код выглядел везде одинаково?
                +16
                Ну началось…
                  +1
                  Лучше на сайте программистов корректно настроить табы
                0
                Код, конечно, ужасен — это медицинский факт, но отступы-то там же по 1 символу всего?
                +11

                Насчёт двойных if — почитайте про операцию &&, будете приятно удивлены (она не вычисляет второй аргумент, если достаточно первого)

                  0
                  Или чему еще меня не научили…
                  Спасибо, это важная информация!
                  +3
                  Также, обратите внимание на фигурные скобки после первичного if — else относится именно к нему, а другой способ записать это мне неизвестен.

                  Это у вас из питона такой ужасный стиль расстановки скобок? Со скобками пишется так:


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

                  или так


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

                  Иначе вы когда-нибудь запутаетесь и сделаете ошибку. В питоне компилятор отступы проверяет, а тут он вам ничего не подскажет.

                    +2
                    Это можно записать еще проще:

                    if (x == 1 || maze[y][x-2] == pass)
                          a += 1;
                    
                      –4
                      Нет, алгоритм будет убиваться возле стен.
                        +1
                        Я ничего не знаю про алгоритм, это просто логика. Если вы посмотрите на изначальное условие, то увидите, что выражение а += 1 выполнится в 2-х случаях: (x == 1) или (maze[y][x-2] == pass && х != 1). Во вторую часть условия можно попасть только тогда, когда х != 1, в противном случае мы попадаем в первую часть, поэтому проверять на x != 1 не имеет смысла.
                      –4
                      Просто привык не ставить скобки для одной операции. Да, питон портит людей.
                      +8
                      Ни фига себе неприлично простой. Я думал тут что-то в духе 10 PRINT CHR$(205.5+RND(1));: GOTO 10, а тут такие простыни кода…
                        0
                        О_о
                        Зачем вы это сделали? Теперь я не засну, пока не пойму, как оно работает…
                          0

                          В ASCII таблице Commodore64 на позициях 205 и 206 находились диагональные линии (вроде /и \ только под углом 45 градусов).


                          Эта программа просто выводит в случайном порядке либо одну линию, либо другую.

                            0
                            Была такая мысль, но тогда мне неочевидно, что должен получиться такой крависый связный рисунок.
                              0
                              Поблагодарим JTG за это
                                0
                                Спасибо, но я это загуглил сразу, как прочитал ваш первый комментарий, и всё равно неочевидно :)
                                0

                                Потому что линии стыкуются друг с другом. Просто попробуйте внимательно изучить скриншот или возьмите тетрадь в клеточку и нарисуйте несколько строк диагональных линий. Можно бросать монетку для истиной случайности :-)

                            +1
                            Сам алгоритм простой :). Просто студентов не учат как писать простые алгоритмы, что функция должна влезать на экран, декомпозиция и тому подобное. Или учат, но на последних курсах, которые студенты уже не посещают, так как на фултайме на php пишут :). Соответственно выглядит это как спагетти, черти какой уровень вложенности кода, почти вся логика в одном методе и т.д. Тоже самое можно написать гораздо проще и понятнее, но для этого нужно чтоб автору показали как это делать.
                              0
                              Не показали и не научили. Как и многому другому. Зато знаю (знал) правило двух третей для создания «эргономичной и внешне привлекательной» формы Windows. Которое было сформулировано в одном предложении без примера и иллюстрации. Но это уже другая история.
                                0
                                Ну, хороший программист не станет ждать, пока его научат. Более того, у хорошего программиста уже есть лучший учитель – интернет. Так что, гугл в зубы и вперед, новые знания ждут! :)
                            0

                            Кстати, не могу не вспомнить другой, ещё более простой алгоритм генерации лабиринтов:


                            1. Окружаем лабиринт стеной, внутри пока пусто.
                            2. Случайно выбираем "кирпич" с чётной координатой на одной из сторон.
                            3. Начинаем строить от него стену — причём сразу после кирпича пропускаем одну позицию (оставляем проход)
                            4. Повторяем 1-2 в случайном порядке для остальных "чётных" кирпичей на всех 4 стенах.

                            (Получается, что в первой стене будет проход у края, в перпендикулярной ей — у края и у первой стены и так далее)


                            Не помню, в какой книжке я его вычитал в детстве, но работал на бейсике на тогдашних машинках (8-битный проц 8080, 2 мегагерца тактовая, от 4 тактов на инструкцию — т.е. эдак на 4 порядка медленней нынешних) довольно шустро.
                            Хотя алгоритм несколько примитивный.

                              0
                              Метод рекурсивного деления (Recursive division method).
                                0

                                Не совсем: стена всегда строится от края до края лабиринта (что исключает рекурсию, там просто два цикла for).
                                Но действительно создаёт лишь подмножество множества лабиринтов, создаваемых методом рекурсивного деления.

                                  0

                                  То, что алгоритм можно переписать на циклы не отменяет того, что он работает так же, и, по сути, является тем же самым, что и Recursive Division =)

                                    0
                                    Там не «переписать» — там порядок построения стен другой и обрабатываемые объекты другие (не рассматриваются области, которые надо делить). Ну и алгоритм проще.
                                    Так что это — как сказать, что поиск в ширину является по сути тем же, что поиск в глубину :-)
                              +13
                              Генерация лабиринтов – прекрасная тема для изучения, для которой, в общем-то, код наименее важен. В этой статье кода значительно больше, чем самого алгоритма и его разбора.
                              Посему, вопрос к коммьюнити: стоит ли делать цикл статей по 11 «классическим» алгоритмам процедурной генерации лабиринтов? Есть ли люди, которым это интересно? (с картинками, объяснениями, гифками, кодом и печеньками)
                                +2
                                Простите, прочитал вашу предыдущую статью. И очень опечалился. Назвать алгоритм Эллера – неэффективным по памяти, это, конечно, сильно. Он способен генерировать бесконечно-большие гриды, так как смотрит только один ряд за проход. Ему вообще до лампочки, что там сверху и снизу. Единственное ограничение по памяти – хранения грида. Но и его можно оптимизировать, например, матрицой смежности.
                                  +1
                                  Да, мне уже говорили, что я его не очень правильно реализовал раз выходят такие накладки. Просто опять-таки, я связывался с лабиринтами, размерностью 150х150, что подразумевало использование типа ineger, а не byte. На тот момент это было серьезной проблемой, а использование массива 2х150 для работы и какой-нибудь булевый массив для сохранения я не додумался, пардон.
                                    0
                                    размерностью 150х150, что подразумевало использование типа ineger, а не byte.

                                    Честно говоря, не понял, почему у Вас размер поля с типом данных связан.
                                      0
                                      Как я понял, в алгоритме Эллера нужно было нумеровать ячейки, а после этого объединять их в группы случайным образом. Длинна 150 — 150 номеров, а byte в Pascal ограничен в размерах до 128. Опять-таки, поправьте если я где-то ошибаюсь.
                                        0
                                        А, теперь понял Вашу мысль. В таком случае да, 128 не хватит для нумерации грида.
                                          +3
                                          И да, пожалуйста, да, я прочитаю все статьи про все 11 алгоритмов и съем все печеньки :3. Вдохновения, времени и удачи вам на благое дело и поделитесь ссылкой если все-таки напишете.
                                          0
                                          AFAIK в паскале byte принимает значения 0..255
                                            0
                                            Спасибо, что заняли мои полчаса поиском старой программы (без иронии, я нашел много чего полезного поверх). Курсовая работала еще на старом алгоритме без проблем, веселье началось с лабиринтом 640х480. Гигантомания у меня в общем.
                                  • НЛО прилетело и опубликовало эту надпись здесь
                                      +1
                                      Обязательно напишите! Я с удовольствием прочитаю, для меня эта тема весьма интересна.
                                        +1
                                        Есть-есть. Тема очень интересная. Натыкался на сайт с огромной коллекцией разных описаний способов генерации (к сожалению потерял ссылку). Залип уже на одних картинках. Правда там были очень хитрые варианты.
                                          0
                                          Картинки могу покидать в ЛС :)
                                          А так, на английском языке отличные: ThinkLabyrinth, Buckblog, книжка Mazes for Programmers.
                                            0
                                            О, как раз первый, спасибо :)
                                            Собственно куча алгоритмов на английском если кому интересно.
                                              0
                                              По факту, алгоритмов там не куча. Там в целом очень много информации по теме :)
                                              Различные термины, объяснения, техники. Но это чисто справочник. Но сайт полезный, да.
                                                0
                                                На самом деле там интересен уже один только список алгоритмов. В котором есть и не прямоугольные, и вообще не имеющие явной сетки.
                                                  0
                                                  Если мы про те, что «Perfect Maze Creation Algorithms», то именно о них я и собираюсь писать. (разве что, опущу на первое время их вариации). Основная проблема в переводе термина bias – никак не могу подобрать аналог на русском языке :(
                                                    0
                                                    Самые интересные примеры там в разделе «классификация».
                                                    Очень интересно выглядят например cracks или sparseness. Правда для этого раздела описаний нет. :(
                                                      0
                                                      Если статьи понравятся людям, могу затронуть и тему различных гридов для лабиринтов в том числе. Гексагональные, круглые, разноформенные… ;)
                                                        0
                                                        Было бы неплохо. Из «неформатных» только на wiki видел интересный вариант на диаграмме Вороного.
                                        0
                                        Вот реализация похожая на ваш исходный алгоритм, но в ней случайный поиск свободной точки заменен на обычный перебор. Не требует искусственного ограничения итераций и работает, я полагаю, быстрее.

                                        #!/usr/bin/env python3
                                        
                                        import random
                                        import turtle
                                        import time
                                        
                                        m = 151
                                        n = 201
                                        
                                        all_directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
                                        
                                        t1 = time.time()
                                        
                                        maze = [[0] * n for i in range(m)]
                                        
                                        for i in range(m):
                                            maze[i][0] = 1
                                            maze[i][-1] = 1
                                        
                                        for j in range(n):
                                            maze[0][j] = 1
                                            maze[-1][j] = 1
                                        
                                        for i1 in range(2, m - 1, 2):
                                            for j1 in range(2, n - 1, 2):
                                                i, j = i1, j1
                                                while True:
                                                    directions = [d for d in all_directions
                                                                  if maze[i + 2 * d[0]][j + 2 * d[1]] == 0]
                                                    if not directions:
                                                        break
                                                    delta_i, delta_j = directions[random.randrange(len(directions))]
                                                    for _ in range(2):
                                                        maze[i][j] = 1
                                                        i += delta_i
                                                        j += delta_j
                                                maze[i][j] = 1
                                        
                                        t2 = time.time()
                                        print(t2 - t1, "sec")
                                        
                                        turtle.tracer(0, 0)
                                        t = turtle.Turtle()
                                        t.setundobuffer(None)
                                        t.hideturtle()
                                        t.color("blue")
                                        t.width(5)
                                        t.up()
                                        
                                        for i in range(2, m - 1):
                                            for j in range(2, n - 1):
                                                if maze[i][j]:
                                                    t.goto(-400 + 4 * j, 300 - 4 * i)
                                                    t.down()
                                                    t.forward(0)
                                                    t.up()
                                        
                                        t.screen.update()
                                        turtle.done()
                                        
                                          0
                                          Для вышеприведенного кода из-за метода перебора в лабиринте преобладают вертикальные линии. Должен отметить, что есть множество возможностей по «тонкой» настройке качества генерации. Например, можно перебирать координаты точек «роста» псевдослучайно (с помощью прибавления большого простого числа и взятия остатка от деления на число столбцов таблицы). Тогда общее число итераций останется прежним (~m*n/4), но избытка верикальных линий не будет. Можно еще до начала полного перебора выбрать небольшое число точек роста случайно, это совсем чуть-чуть замедлит алгоритм, но увеличит количество тройных ветвлений. Можно вначале выбрать несколько точек роста от границ лабиринта. В итоге получаются такие же запутанные лабиринты, как и у автора статьи, полностью заполненные и с фиксированным временем генерации.

                                          Вторая версия
                                          #!/usr/bin/env python3
                                          
                                          """
                                          Рандомизированный вариант построения лабиринта
                                          """
                                          
                                          import random
                                          import turtle
                                          import time
                                          
                                          ALL_DIRECTIONS = ((1, 0), (-1, 0), (0, 1), (0, -1))
                                          
                                          
                                          def create_maze(m, n):  # д.б. нечетные числа
                                          
                                              def grow_branch(maze, i, j):
                                                  while True:
                                                      directions = []
                                                      if i < m - 2 and maze[i + 2][j] == 0: directions.append((1, 0))
                                                      if i > 0 and maze[i - 2][j] == 0: directions.append((-1, 0))
                                                      if j < n - 2 and maze[i][j + 2] == 0: directions.append((0, 1))
                                                      if j > 0 and maze[i][j - 2] == 0: directions.append((0, -1))
                                                      if not directions:
                                                          break
                                                      delta_i, delta_j = directions[random.randrange(len(directions))]
                                                      for _ in range(2):
                                                          maze[i][j] = 1
                                                          i += delta_i
                                                          j += delta_j
                                                  maze[i][j] = 1
                                          
                                              maze = [[0] * n for _ in range(m)]
                                          
                                              for i in range(m):
                                                  maze[i][0] = 1
                                                  maze[i][-1] = 1
                                          
                                              for j in range(n):
                                                  maze[0][j] = 1
                                                  maze[-1][j] = 1
                                          
                                              m1 = (m + 1) // 2
                                              n1 = (n + 1) // 2
                                          
                                              # random branches at the border
                                              grow_branch(maze, 0, random.randrange(2, n - 1, 2))
                                              grow_branch(maze, m - 1, random.randrange(2, n - 1, 2))
                                              grow_branch(maze, random.randrange(2, m - 1, 2), 0)
                                              grow_branch(maze, random.randrange(2, m - 1, 2), n - 1)
                                          
                                              # more random branches
                                              for _ in range(max(m1, n1)):
                                                  i, j = random.randrange(0, m, 2), random.randrange(0, n, 2)
                                                  grow_branch(maze, i, j)
                                          
                                              # "randomized" iteration over all cells
                                              k = 0
                                              for _ in range(m1 * n1):
                                                  k = (k + 15485863) % (m1 * n1)  # prime number
                                                  i1, j1 = divmod(k, n1)
                                                  i, j = 2 * i1, 2 * j1
                                                  if maze[i][j] == 1:
                                                      # ветки растут лишь от уже существующих (удлинение)
                                                      grow_branch(maze, i, j)
                                          
                                              return maze
                                          
                                          
                                          def draw_maze(maze, m, n):
                                              turtle.tracer(0, 0)
                                              t = turtle.Turtle()
                                              t.setundobuffer(None)
                                              t.hideturtle()
                                              t.color("blue")
                                              t.up()
                                              dy = 600 / m
                                              dx = 800 / n
                                              t.width(min(dx, dy))
                                          
                                              for i in range(0, m, 2):
                                                  for j in range(0, n, 2):
                                                      if maze[i][j]:
                                                          if i < m - 1 and maze[i + 1][j]:
                                                              t.goto(dx * j - 400, 300 - dy * i)
                                                              t.down()
                                                              t.goto(dx * j - 400, 300 - dy * (i + 2))
                                                              t.up()
                                                          if j < n - 1 and maze[i][j + 1]:
                                                              t.goto(dx * j - 400, 300 - dy * i)
                                                              t.down()
                                                              t.goto(dx * (j + 2) - 400, 300 - dy * i)
                                                              t.up()
                                          
                                              t.screen.update()
                                              turtle.done()
                                          
                                          
                                          def main():
                                              # размеры лабиринта - нечетные числа
                                              m = 151
                                              n = 201
                                          
                                              t1 = time.time()
                                              maze = create_maze(m, n)
                                              t2 = time.time()
                                              print(t2 - t1, "sec")
                                          
                                              draw_maze(maze, m, n)
                                          
                                          
                                          main()
                                          


                                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                        Самое читаемое