Где же код?
Начнем с начала — подтягиваем стандартные библиотеки, объявляем функции.
#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.
Комментарии (54)
sba
15.01.2017 00:36+3Почему бы не использовать отступы в 16 символов или давайте сразу в 64. Никогда не понимал это странное желание растягивать код, что по горизонтали что по вертикали.
EndUser
15.01.2017 01:01+2По мне так 4 вполне хороший компромисс: 2 позиции для меня недостаточно выразительны, а 8 разрывают канву повествования. Но я-то и открывающую фигурную сношу, чтобы визуальное сопоставление с закрывающей было «автоматическим».
TheShock
15.01.2017 02:09+4Это нативные табы. По-умолчанию они шириной в 8 символов (что актуально для текста), на хабре просто в стилях не хватает указания корректного размера. Попробуйте сами в консоли запустить:
document.body.style.tabSize = 4
3aicheg
16.01.2017 07:05Код, конечно, ужасен — это медицинский факт, но отступы-то там же по 1 символу всего?
aamonster
15.01.2017 00:37+11Насчёт двойных if — почитайте про операцию &&, будете приятно удивлены (она не вычисляет второй аргумент, если достаточно первого)
michael_vostrikov
15.01.2017 07:13+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; }
Иначе вы когда-нибудь запутаетесь и сделаете ошибку. В питоне компилятор отступы проверяет, а тут он вам ничего не подскажет.
33pda
15.01.2017 17:04+2Это можно записать еще проще:
if (x == 1 || maze[y][x-2] == pass) a += 1;
BestMordaEver
15.01.2017 17:06-4Нет, алгоритм будет убиваться возле стен.
33pda
16.01.2017 06:32+1Я ничего не знаю про алгоритм, это просто логика. Если вы посмотрите на изначальное условие, то увидите, что выражение а += 1 выполнится в 2-х случаях: (x == 1) или (maze[y][x-2] == pass && х != 1). Во вторую часть условия можно попасть только тогда, когда х != 1, в противном случае мы попадаем в первую часть, поэтому проверять на x != 1 не имеет смысла.
BestMordaEver
15.01.2017 17:17-4Просто привык не ставить скобки для одной операции. Да, питон портит людей.
hdfan2
15.01.2017 09:46+8Ни фига себе неприлично простой. Я думал тут что-то в духе 10 PRINT CHR$(205.5+RND(1));: GOTO 10, а тут такие простыни кода…
VioletGiraffe
15.01.2017 15:26О_о
Зачем вы это сделали? Теперь я не засну, пока не пойму, как оно работает…lorc
15.01.2017 16:58В ASCII таблице Commodore64 на позициях 205 и 206 находились диагональные линии (вроде /и \ только под углом 45 градусов).
Эта программа просто выводит в случайном порядке либо одну линию, либо другую.
VioletGiraffe
15.01.2017 17:19Была такая мысль, но тогда мне неочевидно, что должен получиться такой крависый связный рисунок.
BestMordaEver
15.01.2017 17:22Поблагодарим JTG за это
VioletGiraffe
15.01.2017 17:30Спасибо, но я это загуглил сразу, как прочитал ваш первый комментарий, и всё равно неочевидно :)
lorc
15.01.2017 19:11Потому что линии стыкуются друг с другом. Просто попробуйте внимательно изучить скриншот или возьмите тетрадь в клеточку и нарисуйте несколько строк диагональных линий. Можно бросать монетку для истиной случайности :-)
elmal
15.01.2017 21:41+1Сам алгоритм простой :). Просто студентов не учат как писать простые алгоритмы, что функция должна влезать на экран, декомпозиция и тому подобное. Или учат, но на последних курсах, которые студенты уже не посещают, так как на фултайме на php пишут :). Соответственно выглядит это как спагетти, черти какой уровень вложенности кода, почти вся логика в одном методе и т.д. Тоже самое можно написать гораздо проще и понятнее, но для этого нужно чтоб автору показали как это делать.
BestMordaEver
15.01.2017 21:44Не показали и не научили. Как и многому другому. Зато знаю (знал) правило двух третей для создания «эргономичной и внешне привлекательной» формы Windows. Которое было сформулировано в одном предложении без примера и иллюстрации. Но это уже другая история.
RussDragon
15.01.2017 21:57Ну, хороший программист не станет ждать, пока его научат. Более того, у хорошего программиста уже есть лучший учитель – интернет. Так что, гугл в зубы и вперед, новые знания ждут! :)
aamonster
15.01.2017 11:38Кстати, не могу не вспомнить другой, ещё более простой алгоритм генерации лабиринтов:
- Окружаем лабиринт стеной, внутри пока пусто.
- Случайно выбираем "кирпич" с чётной координатой на одной из сторон.
- Начинаем строить от него стену — причём сразу после кирпича пропускаем одну позицию (оставляем проход)
- Повторяем 1-2 в случайном порядке для остальных "чётных" кирпичей на всех 4 стенах.
(Получается, что в первой стене будет проход у края, в перпендикулярной ей — у края и у первой стены и так далее)
Не помню, в какой книжке я его вычитал в детстве, но работал на бейсике на тогдашних машинках (8-битный проц 8080, 2 мегагерца тактовая, от 4 тактов на инструкцию — т.е. эдак на 4 порядка медленней нынешних) довольно шустро.
Хотя алгоритм несколько примитивный.DmitryMry
15.01.2017 18:06Метод рекурсивного деления (Recursive division method).
aamonster
15.01.2017 18:26Не совсем: стена всегда строится от края до края лабиринта (что исключает рекурсию, там просто два цикла for).
Но действительно создаёт лишь подмножество множества лабиринтов, создаваемых методом рекурсивного деления.RussDragon
16.01.2017 14:13То, что алгоритм можно переписать на циклы не отменяет того, что он работает так же, и, по сути, является тем же самым, что и Recursive Division =)
aamonster
16.01.2017 15:12Там не «переписать» — там порядок построения стен другой и обрабатываемые объекты другие (не рассматриваются области, которые надо делить). Ну и алгоритм проще.
Так что это — как сказать, что поиск в ширину является по сути тем же, что поиск в глубину :-)
RussDragon
15.01.2017 14:18+13Генерация лабиринтов – прекрасная тема для изучения, для которой, в общем-то, код наименее важен. В этой статье кода значительно больше, чем самого алгоритма и его разбора.
Посему, вопрос к коммьюнити: стоит ли делать цикл статей по 11 «классическим» алгоритмам процедурной генерации лабиринтов? Есть ли люди, которым это интересно? (с картинками, объяснениями, гифками, кодом и печеньками)RussDragon
15.01.2017 15:48+2Простите, прочитал вашу предыдущую статью. И очень опечалился. Назвать алгоритм Эллера – неэффективным по памяти, это, конечно, сильно. Он способен генерировать бесконечно-большие гриды, так как смотрит только один ряд за проход. Ему вообще до лампочки, что там сверху и снизу. Единственное ограничение по памяти – хранения грида. Но и его можно оптимизировать, например, матрицой смежности.
BestMordaEver
15.01.2017 17:10+1Да, мне уже говорили, что я его не очень правильно реализовал раз выходят такие накладки. Просто опять-таки, я связывался с лабиринтами, размерностью 150х150, что подразумевало использование типа ineger, а не byte. На тот момент это было серьезной проблемой, а использование массива 2х150 для работы и какой-нибудь булевый массив для сохранения я не додумался, пардон.
RussDragon
15.01.2017 17:26размерностью 150х150, что подразумевало использование типа ineger, а не byte.
Честно говоря, не понял, почему у Вас размер поля с типом данных связан.BestMordaEver
15.01.2017 17:32Как я понял, в алгоритме Эллера нужно было нумеровать ячейки, а после этого объединять их в группы случайным образом. Длинна 150 — 150 номеров, а byte в Pascal ограничен в размерах до 128. Опять-таки, поправьте если я где-то ошибаюсь.
RussDragon
15.01.2017 17:35А, теперь понял Вашу мысль. В таком случае да, 128 не хватит для нумерации грида.
BestMordaEver
15.01.2017 17:41+3И да, пожалуйста, да, я прочитаю все статьи про все 11 алгоритмов и съем все печеньки :3. Вдохновения, времени и удачи вам на благое дело и поделитесь ссылкой если все-таки напишете.
Anastasia_K
15.01.2017 18:14AFAIK в паскале byte принимает значения 0..255
BestMordaEver
15.01.2017 21:54Спасибо, что заняли мои полчаса поиском старой программы (без иронии, я нашел много чего полезного поверх). Курсовая работала еще на старом алгоритме без проблем, веселье началось с лабиринтом 640х480. Гигантомания у меня в общем.
nikolayz
15.01.2017 17:41+1Обязательно напишите! Я с удовольствием прочитаю, для меня эта тема весьма интересна.
DrZlodberg
15.01.2017 18:32+1Есть-есть. Тема очень интересная. Натыкался на сайт с огромной коллекцией разных описаний способов генерации (к сожалению потерял ссылку). Залип уже на одних картинках. Правда там были очень хитрые варианты.
RussDragon
15.01.2017 18:33Картинки могу покидать в ЛС :)
А так, на английском языке отличные: ThinkLabyrinth, Buckblog, книжка Mazes for Programmers.DrZlodberg
15.01.2017 18:42О, как раз первый, спасибо :)
Собственно куча алгоритмов на английском если кому интересно.RussDragon
15.01.2017 18:45По факту, алгоритмов там не куча. Там в целом очень много информации по теме :)
Различные термины, объяснения, техники. Но это чисто справочник. Но сайт полезный, да.DrZlodberg
15.01.2017 19:06На самом деле там интересен уже один только список алгоритмов. В котором есть и не прямоугольные, и вообще не имеющие явной сетки.
RussDragon
15.01.2017 19:08Если мы про те, что «Perfect Maze Creation Algorithms», то именно о них я и собираюсь писать. (разве что, опущу на первое время их вариации). Основная проблема в переводе термина bias – никак не могу подобрать аналог на русском языке :(
DrZlodberg
15.01.2017 19:17Самые интересные примеры там в разделе «классификация».
Очень интересно выглядят например cracks или sparseness. Правда для этого раздела описаний нет. :(RussDragon
15.01.2017 19:18Если статьи понравятся людям, могу затронуть и тему различных гридов для лабиринтов в том числе. Гексагональные, круглые, разноформенные… ;)
DrZlodberg
15.01.2017 19:19Было бы неплохо. Из «неформатных» только на wiki видел интересный вариант на диаграмме Вороного.
KomandirskieWTF
15.01.2017 21:56Вот реализация похожая на ваш исходный алгоритм, но в ней случайный поиск свободной точки заменен на обычный перебор. Не требует искусственного ограничения итераций и работает, я полагаю, быстрее.
#!/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()KomandirskieWTF
16.01.2017 01:15Для вышеприведенного кода из-за метода перебора в лабиринте преобладают вертикальные линии. Должен отметить, что есть множество возможностей по «тонкой» настройке качества генерации. Например, можно перебирать координаты точек «роста» псевдослучайно (с помощью прибавления большого простого числа и взятия остатка от деления на число столбцов таблицы). Тогда общее число итераций останется прежним (~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()
VaalKIA
Всё очень хорошо, но тут скорее — «где же текст?», за картинки — спасибо, тема про крота — не раскрыта.
BestMordaEver
А ссылка на страницу в самом начале? Там весь алгоритм, вроде доступно расписан.
VaalKIA
Не хотелось отвлекаться от сути, а после статьи желания вернуться в начало не было. Хотя заголовок у вас правильно передаёт мысль, но первый абзац читается в довольно чётком ключе: «продолжение алгоритма с упором на реализацию». Манипулировать читателем предупреждениями — бессмысленно, это просто ушло в игнор на автомате. Ну а поскольку никакого алгоритма не было, а была только реализация то закономерно: просмотреть наискосок и читать следующие вкладки браузера. Наверное, формально, вы — правы. За гифку в первой части, спасибо.