Генерация и решение лабиринта с помощью метода поиска в глубину по графу

В этой статье речь пойдет о самом простом в реализации алгоритме генерации «идеального» лабиринта и его применении для поиска пути.

Мы рассмотрим алгоритм, основанный на бэктрекинге, позволяющий создавать лабиринты без циклов, имеющие единственный путь между двумя точками. Алгоритм не самый быстрый, довольно требователен к ресурсам, по сравнению с алгоритмом Эйлера или Крускала, но очень прост в реализации и позволяет создавать ветвистые лабиринты с очень длинными тупиковыми ответвлениями.

Заинтересовавшихся — прошу под кат.

В русскоязычном интернете очень мало информации по алгоритмам генерации лабиринтов, что и стало причиной для написания этой статьи.
Примеры кода на языке Си, а также полный исходный код проекта на 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 возвращает массив непосещенных соседей клетки

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

Генерация работает, теперь дело за малым: найти в таком лабиринте выход.

Алгоритмов поиска пути несколько больше, чем алгоритмов генерации, и некоторые из них, если будет интерес читателей, я освещу в следующих статьях, но пока что будем довольствоваться тем, что есть, и «пройдем» лабиринт тем же алгоритмом.

И все еще сильнее упрощается, так как нам больше не надо убирать стенки.

Алгоритм поиска пути бэктрекингом:
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)

Внимание!

OSMesa не поддерживается некоторыми драйверами на unix-based, а на Windows не поддерживается совсем, так что желающим, кому не повезло с ОС/железом, могу предложить ознакомиться со смежным проектом: Maze Generator and Solver
В обоих проектах реализованы одни и те же алгоритмы, но первый рисует в памяти и выводит последовательность png-изображений, а второй на экране.
Сборка cd build && ../configure && make, если неудобно, в папке src есть файл-проект QtCreator'a.

Источники

1. Walter D. Pullen: Think Labyrinth.
2. Wikipedia: Maze generation algorithm.