Генерация лабиринтов с использованием теории графов
Перевод моей статьи с HackerNoon.
В нашем предыдущем посте мы рассмотрели алгоритмы поиска путей в графах, которые по своей сути похожи на решение поиска выхода из лабиринта. Когда я делал карту для проекта Wall-E из прошлой статьи, я наткнулся на варианты построения лабиринтов. И чем больше я читал, тем дальше погружался в большой и увлекательный мир лабиринтов.
Ранее я не осознавал всю широту и глубину этой темы, и обнаружил, например, что лабиринты можно классифицировать семью различными способами, каждый из которых можно сгенерировать различными алгоритмами.
Кстати, я не нашел ни одной книги, которая бы всесторонне охватывала эту тему, и даже на странице Википедии нет систематического обзора. К счастью, я наткнулся на потрясающий ресурс, который охватывает различные типы и алгоритмы лабиринтов.
Я начал изучать различные классификации лабиринтов, включая размерные и гиперразмерные вариации, идеальные лабиринты и уникурсальные (unicursal) лабиринты, плоские и разреженные лабиринты и многое другое.
Как создать лабиринт
Моей основной целью было создать 2D карту, представляющую лабиринт.
Конечно, было заманчиво реализовать и сравнить различные алгоритмы генерации лабиринтов, но и задачу нужно было решить в короткий срок. Самое быстрое решение, которое я нашел, заключалось в случайном выборе соединенных ячеек сетки. В коде mazerandom именно это я и сделал. Эта микропрограмма (исходник из одного файла) создает сетку 20x20 ячеек и случайным образом соединяет их, используя обход в глубину (DFS). Другими словами, мы просто вырезаем проходы в сетке.
Если бы вы делали это вручную на бумаге, это выглядело бы примерно так:
Для обхода в глубину, мы представляем сетку ячеек как массив массивов и используем структуру данных стек. Полный код по ссылке Main.cpp, а тут рассмотрим его части:
```C++
vector<vector<int>> maze_cells; // A grid 20x20
stack<Coord> my_stack; // Stack to traverse the grid by DFS
my_stack.push(Coord(0, 0)); // Starting from very first cell
```
Во время обхода мы посещаем каждую ячейку в сетке и на каждой итерации помещаем (push_back) ее соседей в стек:
```C++
...
while (visitedCells < HORIZONTAL_CELLS * VERTICAL_CELLS)
{
vector<int> neighbours;
// Step 1: Create an array of neighbour cells that were not yet visited (from North, East, South and West).
// North is not visited yet?
if ((maze_cells[offset_x(0)][offset_y(-1)] & CELL_VISITED) == 0)
{
neighbours.push_back(0);
}
// East is not visited yet?
if ((maze_cells[offset_x(1)][offset_y(0)] & CELL_VISITED) == 0)
{
neighbours.push_back(1);
}
... // Do the same for West and South...
```
Далее помечаем узел как доступный (т.е. без стены между ячейками) с помощью CELL_PATH_S, CELL_PATH_N, CELL_PATH_W или CELL_PATH_E:
```C++
...
// If we have at least one unvisited neighbour
if (!neighbours.empty())
{
// Choose random neighbor to make it available
int next_cell_dir = neighbours[rand() % neighbours.size()];
// Create a path between the neighbour and the current cell
switch (next_cell_dir)
{
case 0: // North
// Mark it as visited. Mark connection between North and South in BOTH directions.
maze_cells[offset_x(0)][offset_y(-1)] |= CELL_VISITED | CELL_PATH_S;
maze_cells[offset_x(0)][offset_y(0)] |= CELL_PATH_N;
//
my_stack.push(Coord(offset_x(0), offset_y(-1)));
break;
case 1: // East
// Mark it as visited. Mark connection between East and West in BOTH directions.
maze_cells[offset_x(1)][offset_y(0)] |= CELL_VISITED | CELL_PATH_W;
maze_cells[offset_x(0)][offset_y(0)] |= CELL_PATH_E;
my_stack.push(Coord(offset_x(1), offset_y(0)));
break;
... // Do the same for West and South...
}
visitedCells++;
}
else
{
my_stack.pop();
}
...
```
Наконец, вызывается метод drawMaze, чтобы нарисовать лабиринт на экране с использованием библиотеки SFML. Он рисует стену между двумя ячейками, если текущая ячейка не отмечена как CELL_PATH_S, CELL_PATH_N, CELL_PATH_W или CELL_PATH_E.
Однако, этот алгоритм не гарантирует наличие решения в полученном лабиринте. Во многих случаях он создаст карту без четкого пути между двумя точками. Хотя эта случайность может быть интересной в некоторых случаях, в моей задаче нужно было что-то более прогнозируемое, т.к. я собирался сравнивать скорости поиска путей, а не факт наличия путей.
Единственный способ обеспечить наличие решения для лабиринта — использовать предопределенную структуру, которая соединяет каждую часть лабиринта каким-то образом.
Создание лабиринта с использованием теории графов
Самые известные алгоритмы генерации лабиринтов основаны на графах. Каждая ячейка является узлом в графе, и каждый узел должен иметь хотя бы одно соединение с другими узлами. Связный граф по условию гарантирует связность всех точек.
Как упоминалось ранее, лабиринты бывают разных форм. Например, "уникурсальные" лабиринты имеют только один-единственный вход, который также является и выходом. Другие лабиринты, наоборот, могут иметь множество решений. Однако сам процесс генерации часто начинается с создания "идеального" лабиринта. "Идеальный" лабиринт имеет один вход, один выход, не имеет петель, замкнутых контуров и недоступных областей, и гарантирует наличие ровно одного пути между любыми двумя ячейками (точками) лабиринта. Такой лабиринт имеет одно единственное решение (путь между входом и выходом).
Если использовать граф в качестве внутреннего представления нашего лабиринта, создание остовного дерева гарантирует наличие пути от начала до конца. В терминах компьютерных наук такой лабиринт можно описать как "остовное дерево над множеством ячеек или вершин".
Существует множество остовных деревьев, но цель состоит в том, чтобы обеспечить хотя бы одно решение от начала до конца, как показано на примере ниже:
На изображении выше показано только одно решение, но на самом деле существует несколько путей. Ни одна ячейка не изолирована и не является недостижимой. Так как же этого достичь?
Я обнаружил хорошо разработанную кодовую базу mazegenerator от @razimantv, которая это осуществляет, генерируя лабиринты в формате SVG-картинок.
Я сдедал форк репозитория и построил свое решение на нем. Благодарю @razimantv за элегантный ООП-дизайн, который позволяет легко "прикрутить" различные варианты вывода результатов.
Изначально, код из репозитория поддерживает разные виды лабиринтов, что мне не нужно было. Я немного упростил код, чтобы сосредоточиться исключительно на прямоугольных лабиринтах.
Схема программы для построения остовного дерева выглядит так:
```C++
/**
* \param algorithm Algorithm that is used to generate maze spanning tree.
*/
void MazeBase::GenerateMaze(SpanningtreeAlgorithmBase* algorithm)
{
// Generates entire maze spanning tree
auto spanningTreeEdges = algorithm->SpanningTree(_verticesNumber, _edgesList);
// Find a solution of a maze based on Graph DFS.
_Solve(spanningTreeEdges);
// Build a maze by removing unnecessary edges.
_RemoveBorders(spanningTreeEdges);
}
```
А визуализация с использованием библиотеки SFML находится в функции Draw. Я оставил оригинальный вариант генерации SVG-файлов, а также добавил моментальное отображение результата с помощью библиотеки SFML. Но самое главное, я могу генерировать текстовый файл с необходимым описанием карты (лабиринта) для моего Wall-E проекта.
Как видите, в нем есть ровно один вход и один выход в левом верхнем и правом нижнем углах. Это "идеальный лабиринт". Теперь я могу продолжить свои эксперименты в проекте Wall-E, а для вас доступен код на GitHub.
Удачи!
Комментарии
Отправить комментарий