Это первая из нескольких планируемых статей, посвященных генерации и решению лабиринтов.
В этой статье речь пойдет о самом простом в реализации алгоритме генерации «идеального» лабиринта и его применении для поиска пути.
Мы рассмотрим алгоритм, основанный на бэктрекинге, позволяющий создавать лабиринты без циклов, имеющие единственный путь между двумя точками. Алгоритм не самый быстрый, довольно требователен к ресурсам, по сравнению с алгоритмом Эйлера или Крускала, но очень прост в реализации и позволяет создавать ветвистые лабиринты с очень длинными тупиковыми ответвлениями.
Заинтересовавшихся — прошу под кат.
В русскоязычном интернете очень мало информации по алгоритмам генерации лабиринтов, что и стало причиной для написания этой статьи.
Примеры кода на языке Си, а также полный исходный код проекта на GitHub доступны под лицензией GNU GPLv3.
Ссылки на англоязычные ресурсы и проект вы найдете в конце статьи.
Описание алгоритма
Замечание: предполагается, что изначально у каждой клетки есть стенки со всех четырех сторон, которые отделяют ее от соседних клеток.
1. Сделайте начальную клетку текущей и отметьте ее как посещенную.
2. Пока есть непосещенные клетки
??1. Если текущая клетка имеет непосещенных «соседей»
????1. Протолкните текущую клетку в стек
????2. Выберите случайную клетку из соседних
????3. Уберите стенку между текущей клеткой и выбранной
????4. Сделайте выбранную клетку текущей и отметьте ее как посещенную.
??2. Иначе если стек не пуст
????1. Выдерните клетку из стека
????2. Сделайте ее текущей
??3. Иначе
????1. Выберите случайную непосещенную клетку, сделайте ее текущей и отметьте как посещенную.
Вы, вероятно, заметили что при выполнении условия 3, готовый лабиринт вероятнее всего будет иметь изолированную область.
Это условие включено в алгоритм в порядке исключения, на практике при нормальной работе алгоритма и правильных исходных данных, оно не выполняется никогда.
Реализация
Как уже сказано выше, предполагается, что при начале работы алгоритма все клетки отделены стенками.
Иллюстрация работы алгоритма
?0. ?
? < — Начальная матрица.?1. ?
? < — Выбираем начальную точку стартовой.?2.1.?
? < — Перемещаемся к случайному непосещенному соседу, пока таковые есть.?2.2.?
? < — Непосещенных соседей нет. Возвращаемся назад по стеку, пока нет непосещенных соседей.?2.1.?
? < — Непосещенные соседи есть. Перемещаемся к случайному непосещенному соседу.?2. ?
? < — Нет непосещенных клеток. Лабиринт сгенерирован.Программный код
Приступаем к самому интересному.
Начнем действовать по порядку и сначала сгенерируем начальную матрицу, с которой будет работать алгоритм.
Для удобства условимся, что все типы клеток заданы в перечислении.
int maze[height][width]; //создаем матрицу - двумерный массив
for(i = 0; i < height; i++){
for(j = 0; j < width; j++){
if((i % 2 != 0 && j % 2 != 0) && //если ячейка нечетная по x и y,
(i < height-1 && j < width-1)) //и при этом находится в пределах стен лабиринта
maze[i][j] = CELL; //то это КЛЕТКА
else maze[i][j] = WALL; //в остальных случаях это СТЕНА.
}
}
Теперь, когда все приготовления сделаны, можно приступать к генерации.
typedef struct cell{ //структура, хранящая координаты клетки в матрице
unsigned int x;
unsigned int y;
} cell;
typedef struct cellString{
cell* cells;
unsigned int size;
} cellString;
Структуры значительно упростят жизнь при обмене информацией между функциями.
Отрывок кода, отвечающий за генерацию:
cell startCell = {1, 1}
cell currentCell = startCell;
cell neighbourCell;
do{
cellString Neighbours = getNeighbours(width, height, maze, startPoint, 2);
if(Neighbours.size != 0){ //если у клетки есть непосещенные соседи
randNum = randomRange(0, Neighbours.size-1);
neighbourCell = cellStringNeighbours.cells[randNum]; //выбираем случайного соседа
push(d.startPoint); //заносим текущую точку в стек
maze = removeWall(currentCell, neighbourCell, maze); //убираем стену между текущей и сосендней точками
currentCell = neighbourCell; //делаем соседнюю точку текущей и отмечаем ее посещенной
maze = setMode(d.startPoint, d.maze, VISITED);
free(cellStringNeighbours.cells);
}
else if(stackSize > 0){ //если нет соседей, возвращаемся на предыдущую точку
startPoint = pop();
}
else{ //если нет соседей и точек в стеке, но не все точки посещены, выбираем случайную из непосещенных
cellString cellStringUnvisited = getUnvisitedCells(width, height, maze);
randNum = randomRange(0, cellStringUnvisited.size-1);
currentCell = cellStringUnvisited.cells[randNum];
free(cellStringUnvisited.cells);
}
while(unvisitedCount() > 0);
Как видно, реализация алгоритма проста и абстрактна от теории, как говорится, «справится даже ребенок».
Чтобы не перегружать статью, код функций, используемых в вышеприведенном отрывке, под спойлером.
cellString getNeighbours(unsigned int width, unsigned int height, int** maze, cell c){
unsigned int i;
unsigned int x = c.x;
unsigned int y = c.y;
cell up = {x, y - distance};
cell rt = {x + distance, y};
cell dw = {x, y + distance};
cell lt = {x - distance, y};
cell d[4] = {dw, rt, up, lt};
unsigned int size = 0;
cellString cells;
cells.cells = malloc(4 * sizeof(cell));
for(i = 0; i < 4; i++){ //для каждого направдения
if(d[i].x > 0 && d[i].x < width && d[i].y > 0 && d[i].y < height){ //если не выходит за границы лабиринта
unsigned int mazeCellCurrent = maze[d[i].y][d[i].x];
cell cellCurrent = d[i];
if(mazeCellCurrent != WALL && mazeCellCurrent != VISITED){ //и не посещена\является стеной
cells.cells[size] = cellCurrent; //записать в массив;
size++;
}
}
}
cells.size = size;
return cells;
Функция removeWall убирает стенку между двумя клетками:
mazeMatrix removeWall(cell first, cell second, int** maze){
short int xDiff = second.x - first.x;
short int yDiff = second.y - first.y;
short int addX, addY;
cell target;
addX = (xDiff != 0) ? (xDiff / abs(xDiff)) : 0;
addY = (yDiff != 0) ? (yDiff / abs(yDiff)) : 0;
target.x = first.x + addX; //координаты стенки
target.y = first.y + addY;
maze[target.y][target.x] = VISITED;
return maze;
}
Сначала вычисляется значение разности координат второй и первой точек. Очевидно, значение может быть либо отрицательное, либо положительное, либо 0.
Надо найти такие координаты xy, чтобы при сложении их с координатами первой точки получались координаты стенки.
Так как мы точно знаем, что вектор разности между координатами стенки и первой точке равен либо (|1|, 0) либо (0, |1|), мы можем этим воспользоваться.
Таким образом, аддитив для x координаты при xDiff != 0 будет равен xDiff / |xDiff|, при xDiff = 0, нулю. Для y соответственно.
Получив аддитивы для x и y, мы легко вычисляем координаты стенки между первой и второй клетками и назначаем клетку по этим координатам посещенной.
Итак, теперь у нас есть генератор лабиринтов, который может строить запутанные лабиринты, размер которых ограничен только размером оперативной памяти.
В итоге, мы можем получить что-то такое:
? 500x500
Генерация работает, теперь дело за малым: найти в таком лабиринте выход.
Алгоритмов поиска пути несколько больше, чем алгоритмов генерации, и некоторые из них, если будет интерес читателей, я освещу в следующих статьях, но пока что будем довольствоваться тем, что есть, и «пройдем» лабиринт тем же алгоритмом.
И все еще сильнее упрощается, так как нам больше не надо убирать стенки.
Алгоритм поиска пути бэктрекингом:
1. Сделайте начальную клетку текущей и отметьте ее как посещенную.
2. Пока не найден выход
??1. Если текущая клетка имеет непосещенных «соседей»
????1. Протолкните текущую клетку в стек
????2. Выберите случайную клетку из соседних
????3. Сделайте выбранную клетку текущей и отметьте ее как посещенную.
??2. Иначе если стек не пуст
????1. Выдерните клетку из стека
????2. Сделайте ее текущей
??3. Иначе выхода нет
Выходной точкой, как и стартовой, может выступать любая точка лабиринта, не являющаяся стенкой.
Традиционно, выход должен быть «прижат» к одной из стенок, но по сути может находиться где угодно.
Все таки, в данном случае, «вход» и «выход» — всего лишь две точки, между которыми надо найти путь.
Критерий нахождения «выхода» очень прост: достаточно сравнить координаты текущей точки и координаты «выхода»: если они равны, путь между стартовой и выходной точками найден.
Посмотрим что вышло:
? 100x100
? 500x500
? 8000х8000
8000х8000 в оригинальном разрешении (16000px, 30мб):
yadi.sk/i/YS0ImN-PhoLcZ
yadi.sk/i/YZjzwPu5hoLcd
Вот и все, что нужно для самой простой реализации генератора случайных лабиринтов.
Для тех, кто заинтересовался, полный исходный код проекта на GitHub: Maze Generator and Solver (offscreen rendering)
В обоих проектах реализованы одни и те же алгоритмы, но первый рисует в памяти и выводит последовательность png-изображений, а второй на экране.
Сборка cd build && ../configure && make, если неудобно, в папке src есть файл-проект QtCreator'a.
Источники
1. Walter D. Pullen: Think Labyrinth.
2. Wikipedia: Maze generation algorithm.
Комментарии (26)
docker1
11.07.2015 19:39+2«Рисунки», которые получилось на решенных лабиринтах, отдалённо напоминают фрактал Мандельброта, если его приблизить. Красиво получилось.
sayber
11.07.2015 20:19Практически такой же алгоритм писал на PHP для расчета последовательности маршрута.
Только вот матрица смежности выходит краеугольным камнем.
ivanych
11.07.2015 20:55А где в этих лабиринтах вход и выход? Ну ладно, допустим, входом считаем точку, с которой начали генерировать. А какую точку считать выходом?
mersinvald Автор
11.07.2015 20:59По умолчанию входом всегда считается левая верхняя точка, а выходом — правая нижняя. А так, выбрать можно любые две точки и прикрутить соответствующую визуализацию, на алгоритм это никак не повлияет.
Речь идет о поиске пути между двумя любыми точками, а что это за точки — остается на усмотрение читателя)ivanych
11.07.2015 21:02Как любые? Как задать выход, скажем, в середине нижней стороны?
mersinvald Автор
11.07.2015 21:08Забыл упомянуть об этом, сейчас исправлю, спасибо.
Выходной точкой может быть любая точка, не являющаяся стеной. Хоть в центре, может там переход на другой уровень.
ivanych
11.07.2015 21:04Переформулирую предыдущий вопрос — правильно ли я понял, что в этих лабиринтах есть путь от любой точки до любой, и при этом он единственный?
mersinvald Автор
11.07.2015 21:17Да, лабиринт соответствует определению «идеального лабиринта» — ни циклов, ни изолированных областей, между двумя точками есть путь и притом только один.
UPD: Добавить циклов и вариативности прохождения довольно просто: достаточно выбить некоторое количество рандомных стенок.ivanych
11.07.2015 21:20Ок. А что на счет длины этого пути? Можно ли расположить вход и выход в соседних точках и при этом добиться, чтобы длина пути была примерно такая же, как между угловыми точками?
mersinvald Автор
11.07.2015 21:25Вы имеете в виду, можно ли задать длину пути между двумя точками?
Теоретически, да — построить сначала минимальное основное дерево нужной длины, представляющее собой путь между двумя точками, а потом достроить вокруг остальной лабиринт.
Практически — не пробовал, но учту, в следующей статье вместе с поиском в ширину постараюсь осветить этот момент.
PsyHaSTe
13.07.2015 18:02А можно поподробней, как задается выходная вершина? А то я так понял, что по алгоритму мы роем в случайном направлении до тех пор, пока можем, и только упершись так, что рыть больше некуда, возвращаемся и начинаем рыть уже ответвления. То есть конечная вершина может меняться в зависимости от рандома.
mersinvald Автор
13.07.2015 19:45+1Изначальное количество клеток на нулевом шаге не уменьшается после генерации.
??
Мы как имели 25 клеток в самом начале, отделенные стенками, так и будем их иметь после генерации. Соответственно, любые из них можно выбрать как начальную\конечную. Алгоритм покрывает все клетки и из любой из них можно пройти в любую. То есть остовное дерево от «входа» до «выхода» можно построить от любой клетки до любой.PsyHaSTe
13.07.2015 19:53Все равно не понял, Вы задали начальную вершину, рандом решил начертить такую вот карту.
Что мы дальше с ней делаем? Если карта уже готова, то выход очевидно не в правом нижнем углу, как хотелось бы. Потому что как алгоритм ищет путь именно до нужной вершины я не нашел, а судя по вашим утверждениям он это всё же делает.mersinvald Автор
13.07.2015 20:11+1Выход — всего лишь ТОЧКА. И она будет находиться там, где Вы захотите.
Это уже не относится к генерации. Хотите — делайте в левом углу, хотите — в точке, где происходит первый возврат по стеку.
Алгоритм поиска ищет путь от заданной начальной точки до заданной конечной.
В данном случае, я ставлю конец в самую дальнюю от выбранного мной входа точку, чтобы с большей степенью вероятности получить наиболее протяженный путь.
Несколькими комментариями выше я ответил на вопрос о контроле длинны пути от точки до точки.
grafmishurov
11.07.2015 21:14В английской Википедии есть и очень развернуто, предполагается, что созданиее лабиринта — это генерация остовного дерева (spanning tree), и несколько соответствующих алгоритмов генерации: поиск в глубину, алгоритм Крускала и алгоритм Прима и еще какие-то.
MichaelBorisov
11.07.2015 21:47Первая ссылка хорошая. Там рассмотрено много методов генерации лабиринтов. Рекомендую.
maaGames
12.07.2015 07:39+1Идеальный лабиринт, в котором клетка является «проходом» или «стеной»? Ну-ну.
Чтобы не быть голословным, отошлю вас к почти детской книжке Максима Мозгового «Занимательное программирование». Там неплохо объяснено, чем ваш вариант представления алгоритма плох.mersinvald Автор
12.07.2015 12:35Если там описываются альтернативные варианты представления лабиринта в памяти, с радостью подчерпну что-то новое.
Я нашел матрицу клеток самой оптимальной и удобной в использовании.
Опять же, идеальный он не потому что идеален эстетически, или с точки зрения сложности, просто определение такое.maaGames
12.07.2015 12:43Возьму на себя смелость скопировать фразу из главы о лабиринтах: «если разрушить любую стену в лабиринте, то образуется новая локация на месте разрушенной стены. При разрушении стены должен открываться проход, но никак не образовываться новая локация».
В принципе, это и на логическом уровне кажется очевидным. Но реализация как у вас, самая простая с точки зрения «рисования» лабиринта в блокноте.mersinvald Автор
12.07.2015 13:23Хорошо, я учту для будущих статей.
Я считал что это вопрос скорее визуализации, правда.
Хм… Тогда реализация сильно приблизится к теоретической базе графов, что и так планировалось. Отлично)ByGandalf
13.07.2015 19:26Я думаю что в Вашей структуре при сносе стенки не образуется новая локация, т.к. стенки у вас в массиве стоят на чётных местах.
В упомянутой же книге предполагалось, что и стена и локация выражается одним числом.
Или я не прав?mersinvald Автор
13.07.2015 19:39+1Образуется таки.
Алгоритм поиска, в текущем виде, считает все клетки равноправными(шаг равен одному).
То есть стенка при «сносе» заменяется клеткой, которая сразу отмечается посещенной, во избежании повторного прохода по ней.
Можно обойти это, используя шаг равный двум и проверяя есть ли стенка, как в функции removeWall. И соответственно отрисовывать только клетки, а стенки линиями по второй матрице, получаемой разложением по четности, но это уже лютые костыли и велосипеды…
Правильнее, и я так и буду делать в дальнейшем, использовать плотнее графы и работать непосредственно на матрице или списках смежности.
Igor_Sib
Ого, я написал практически такой же алгоритм. Только у меня не нужна матрица и ответвление может быть в любом месте. Так же если нужен другой тип лабиринта — не «один правильный путь к выходу и несколько ложных» а просто разветвленный лабиринт то это легко сделать немного модифицировав алгоритм. Надо просто рыть не один путь, а сразу в нескольких направлениях.