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

image

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

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

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

В русскоязычном интернете очень мало информации по алгоритмам генерации лабиринтов, что и стало причиной для написания этой статьи.
Примеры кода на языке Си, а также полный исходный код проекта на GitHub доступны под лицензией GNU GPLv3.
Ссылки на англоязычные ресурсы и проект вы найдете в конце статьи.

Описание алгоритма

Замечание: предполагается, что изначально у каждой клетки есть стенки со всех четырех сторон, которые отделяют ее от соседних клеток.

1. Сделайте начальную клетку текущей и отметьте ее как посещенную.
2. Пока есть непосещенные клетки
  1. Если текущая клетка имеет непосещенных «соседей»
    1. Протолкните текущую клетку в стек
    2. Выберите случайную клетку из соседних
    3. Уберите стенку между текущей клеткой и выбранной
    4. Сделайте выбранную клетку текущей и отметьте ее как посещенную.
  2. Иначе если стек не пуст
    1. Выдерните клетку из стека
    2. Сделайте ее текущей
  3. Иначе
    1. Выберите случайную непосещенную клетку, сделайте ее текущей и отметьте как посещенную.

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

Реализация

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

Иллюстрация работы алгоритма

 0.    image  < — Начальная матрица.

 1.    image  < — Выбираем начальную точку стартовой.

 2.1. image  < — Перемещаемся к случайному непосещенному соседу, пока таковые есть.

 2.2. image  < — Непосещенных соседей нет. Возвращаемся назад по стеку, пока нет непосещенных соседей.

 2.1. image  < — Непосещенные соседи есть. Перемещаемся к случайному непосещенному соседу.

 2.    image  < — Нет непосещенных клеток. Лабиринт сгенерирован.

Программный код

Приступаем к самому интересному.

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

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
image
  500x500
image

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

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

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

Алгоритм поиска пути бэктрекингом:
1. Сделайте начальную клетку текущей и отметьте ее как посещенную.
2. Пока не найден выход
  1. Если текущая клетка имеет непосещенных «соседей»
    1. Протолкните текущую клетку в стек
    2. Выберите случайную клетку из соседних
    3. Сделайте выбранную клетку текущей и отметьте ее как посещенную.
  2. Иначе если стек не пуст
    1. Выдерните клетку из стека
    2. Сделайте ее текущей
  3. Иначе выхода нет

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

Критерий нахождения «выхода» очень прост: достаточно сравнить координаты текущей точки и координаты «выхода»: если они равны, путь между стартовой и выходной точками найден.

Посмотрим что вышло:

Решенные лабиринты. Траффик!
Красным обозначен путь, голубым — посещенные клетки.
  100x100
image

image
  500x500
image

image
  8000х8000
image

image

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.
Метки:
Поделиться публикацией
Похожие публикации
Комментарии 26
  • +1
    Ого, я написал практически такой же алгоритм. Только у меня не нужна матрица и ответвление может быть в любом месте. Так же если нужен другой тип лабиринта — не «один правильный путь к выходу и несколько ложных» а просто разветвленный лабиринт то это легко сделать немного модифицировав алгоритм. Надо просто рыть не один путь, а сразу в нескольких направлениях.
    • +2
      «Рисунки», которые получилось на решенных лабиринтах, отдалённо напоминают фрактал Мандельброта, если его приблизить. Красиво получилось.
      • 0
        Практически такой же алгоритм писал на PHP для расчета последовательности маршрута.
        Только вот матрица смежности выходит краеугольным камнем.
        • 0
          А почему список смежности не использовали? Он же экономичней.
          • +1
            Потому что тогда только постигал эту науку =)
        • 0
          А где в этих лабиринтах вход и выход? Ну ладно, допустим, входом считаем точку, с которой начали генерировать. А какую точку считать выходом?
          • 0
            По умолчанию входом всегда считается левая верхняя точка, а выходом — правая нижняя. А так, выбрать можно любые две точки и прикрутить соответствующую визуализацию, на алгоритм это никак не повлияет.
            Речь идет о поиске пути между двумя любыми точками, а что это за точки — остается на усмотрение читателя)
            • 0
              Как любые? Как задать выход, скажем, в середине нижней стороны?
              • 0
                Забыл упомянуть об этом, сейчас исправлю, спасибо.
                Выходной точкой может быть любая точка, не являющаяся стеной. Хоть в центре, может там переход на другой уровень.
              • 0
                Переформулирую предыдущий вопрос — правильно ли я понял, что в этих лабиринтах есть путь от любой точки до любой, и при этом он единственный?
                • 0
                  Да, лабиринт соответствует определению «идеального лабиринта» — ни циклов, ни изолированных областей, между двумя точками есть путь и притом только один.
                  UPD: Добавить циклов и вариативности прохождения довольно просто: достаточно выбить некоторое количество рандомных стенок.
                  • 0
                    Ок. А что на счет длины этого пути? Можно ли расположить вход и выход в соседних точках и при этом добиться, чтобы длина пути была примерно такая же, как между угловыми точками?
                    • 0
                      Вы имеете в виду, можно ли задать длину пути между двумя точками?
                      Теоретически, да — построить сначала минимальное основное дерево нужной длины, представляющее собой путь между двумя точками, а потом достроить вокруг остальной лабиринт.
                      Практически — не пробовал, но учту, в следующей статье вместе с поиском в ширину постараюсь осветить этот момент.
                      • 0
                        Да. Спасибо, буду ждать продолжения.
                • 0
                  А можно поподробней, как задается выходная вершина? А то я так понял, что по алгоритму мы роем в случайном направлении до тех пор, пока можем, и только упершись так, что рыть больше некуда, возвращаемся и начинаем рыть уже ответвления. То есть конечная вершина может меняться в зависимости от рандома.
                  • +1
                    Изначальное количество клеток на нулевом шаге не уменьшается после генерации.

                      image

                    Мы как имели 25 клеток в самом начале, отделенные стенками, так и будем их иметь после генерации. Соответственно, любые из них можно выбрать как начальную\конечную. Алгоритм покрывает все клетки и из любой из них можно пройти в любую. То есть остовное дерево от «входа» до «выхода» можно построить от любой клетки до любой.
                    • 0
                      Все равно не понял, Вы задали начальную вершину, рандом решил начертить такую вот карту.
                      image
                      Что мы дальше с ней делаем? Если карта уже готова, то выход очевидно не в правом нижнем углу, как хотелось бы. Потому что как алгоритм ищет путь именно до нужной вершины я не нашел, а судя по вашим утверждениям он это всё же делает.
                      • +1
                        Выход — всего лишь ТОЧКА. И она будет находиться там, где Вы захотите.
                        Это уже не относится к генерации. Хотите — делайте в левом углу, хотите — в точке, где происходит первый возврат по стеку.

                        Алгоритм поиска ищет путь от заданной начальной точки до заданной конечной.

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

                        Несколькими комментариями выше я ответил на вопрос о контроле длинны пути от точки до точки.
              • 0
                В английской Википедии есть и очень развернуто, предполагается, что созданиее лабиринта — это генерация остовного дерева (spanning tree), и несколько соответствующих алгоритмов генерации: поиск в глубину, алгоритм Крускала и алгоритм Прима и еще какие-то.
                • 0
                  Первая ссылка хорошая. Там рассмотрено много методов генерации лабиринтов. Рекомендую.
                  • +1
                    Идеальный лабиринт, в котором клетка является «проходом» или «стеной»? Ну-ну.
                    Чтобы не быть голословным, отошлю вас к почти детской книжке Максима Мозгового «Занимательное программирование». Там неплохо объяснено, чем ваш вариант представления алгоритма плох.
                    • 0
                      Если там описываются альтернативные варианты представления лабиринта в памяти, с радостью подчерпну что-то новое.
                      Я нашел матрицу клеток самой оптимальной и удобной в использовании.
                      Опять же, идеальный он не потому что идеален эстетически, или с точки зрения сложности, просто определение такое.
                      • 0
                        Возьму на себя смелость скопировать фразу из главы о лабиринтах: «если разрушить любую стену в лабиринте, то образуется новая локация на месте разрушенной стены. При разрушении стены должен открываться проход, но никак не образовываться новая локация».
                        В принципе, это и на логическом уровне кажется очевидным. Но реализация как у вас, самая простая с точки зрения «рисования» лабиринта в блокноте.
                        • 0
                          Хорошо, я учту для будущих статей.
                          Я считал что это вопрос скорее визуализации, правда.

                          Хм… Тогда реализация сильно приблизится к теоретической базе графов, что и так планировалось. Отлично)
                          • 0
                            Я думаю что в Вашей структуре при сносе стенки не образуется новая локация, т.к. стенки у вас в массиве стоят на чётных местах.
                            В упомянутой же книге предполагалось, что и стена и локация выражается одним числом.
                            Или я не прав?
                            • +1
                              Образуется таки.
                              Алгоритм поиска, в текущем виде, считает все клетки равноправными(шаг равен одному).
                              То есть стенка при «сносе» заменяется клеткой, которая сразу отмечается посещенной, во избежании повторного прохода по ней.

                              Можно обойти это, используя шаг равный двум и проверяя есть ли стенка, как в функции removeWall. И соответственно отрисовывать только клетки, а стенки линиями по второй матрице, получаемой разложением по четности, но это уже лютые костыли и велосипеды…
                              Правильнее, и я так и буду делать в дальнейшем, использовать плотнее графы и работать непосредственно на матрице или списках смежности.

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