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

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

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

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

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

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; } 

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

В итоге, мы можем получить что-то такое:

Лабиринты. Осторожно, трафик!

  100×100

  500×500

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

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

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

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

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

Решенные лабиринты. Траффик!

Красным обозначен путь, голубым — посещенные клетки.
  100×100

  500×500

  8000х8000

8000х8000 в оригинальном разрешении (16000px, 30мб):
yadi.sk/i/YS0ImN-PhoLcZ
yadi.sk/i/YZjzwPu5hoLcd

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

Для тех, кто заинтересовался, полный исходный код проекта на GitHub: Maze Generator and Solver (offscreen rendering)

Источники

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

ссылка на оригинал статьи http://habrahabr.ru/post/262345/