В этой статье речь пойдет о самом простом в реализации алгоритме генерации «идеального» лабиринта и его применении для поиска пути.
Мы рассмотрим алгоритм, основанный на бэктрекинге, позволяющий создавать лабиринты без циклов, имеющие единственный путь между двумя точками. Алгоритм не самый быстрый, довольно требователен к ресурсам, по сравнению с алгоритмом Эйлера или Крускала, но очень прост в реализации и позволяет создавать ветвистые лабиринты с очень длинными тупиковыми ответвлениями.
Заинтересовавшихся — прошу под кат.
В русскоязычном интернете очень мало информации по алгоритмам генерации лабиринтов, что и стало причиной для написания этой статьи.
Примеры кода на языке Си, а также полный исходный код проекта на 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);
Как видно, реализация алгоритма проста и абстрактна от теории, как говорится, «справится даже ребенок».
Чтобы не перегружать статью, код функций, используемых в вышеприведенном отрывке, под спойлером.
Код функций
Функция getNeighbours возвращает массив непосещенных соседей клетки
Функция removeWall убирает стенку между двумя клетками:
Сначала вычисляется значение разности координат второй и первой точек. Очевидно, значение может быть либо отрицательное, либо положительное, либо 0.
Надо найти такие координаты xy, чтобы при сложении их с координатами первой точки получались координаты стенки.
Так как мы точно знаем, что вектор разности между координатами стенки и первой точке равен либо (|1|, 0) либо (0, |1|), мы можем этим воспользоваться.
Таким образом, аддитив для x координаты при xDiff != 0 будет равен xDiff / |xDiff|, при xDiff = 0, нулю. Для y соответственно.
Получив аддитивы для x и y, мы легко вычисляем координаты стенки между первой и второй клетками и назначаем клетку по этим координатам посещенной.
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, мы легко вычисляем координаты стенки между первой и второй клетками и назначаем клетку по этим координатам посещенной.
Итак, теперь у нас есть генератор лабиринтов, который может строить запутанные лабиринты, размер которых ограничен только размером оперативной памяти.
В итоге, мы можем получить что-то такое:
Лабиринты. Осторожно, трафик!
100x100
500x500
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
100x100
500x500
8000х8000
8000х8000 в оригинальном разрешении (16000px, 30мб):
yadi.sk/i/YS0ImN-PhoLcZ
yadi.sk/i/YZjzwPu5hoLcd
Вот и все, что нужно для самой простой реализации генератора случайных лабиринтов.
Для тех, кто заинтересовался, полный исходный код проекта на GitHub: Maze Generator and Solver (offscreen rendering)
Внимание!
OSMesa не поддерживается некоторыми драйверами на unix-based, а на Windows не поддерживается совсем, так что желающим, кому не повезло с ОС/железом, могу предложить ознакомиться со смежным проектом: Maze Generator and Solver
В обоих проектах реализованы одни и те же алгоритмы, но первый рисует в памяти и выводит последовательность png-изображений, а второй на экране.
Сборка cd build && ../configure && make, если неудобно, в папке src есть файл-проект QtCreator'a.
В обоих проектах реализованы одни и те же алгоритмы, но первый рисует в памяти и выводит последовательность png-изображений, а второй на экране.
Сборка cd build && ../configure && make, если неудобно, в папке src есть файл-проект QtCreator'a.
Источники
1. Walter D. Pullen: Think Labyrinth.
2. Wikipedia: Maze generation algorithm.
