Создание лабиринтов

Лабиринты

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

Когда я приступил к созданию карты лабиринта для проекта Wall-E, я изначально ожидал найти быстрый и простой способ выполнить эту задачу. Однако я быстро оказался поглощенным обширным и увлекательным миром лабиринтов и лабиринтов.

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

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

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

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

Как создать лабиринт

Моя основная цель – сгенерировать двухмерную карту, представляющую собой лабиринт.

Хотя было бы заманчиво реализовать различные алгоритмы генерации лабиринтов для их сравнения, я также хотел использовать более эффективный подход. Самое быстрое решение, которое я нашел, заключалось в случайном выборе соединенных ячеек. Именно это я сделал с помощью mazerandom. Это приложение в одном файле создает таблицу сетки из 20 x 20 ячеек, а затем случайным образом соединяет их, используя обход в глубину (DFS). Другими словами, мы просто вырезаем проходы в сетке.

Если бы вы делали это вручную на бумаге, оно выглядело бы примерно так:

Для реализации этого алгоритма мы применяем обход в глубину к сетке ячеек. Давайте посмотрим, как это делается в Main.cpp.

Как обычно, мы представляем сетку ячеек в виде массива массивов, и для обхода в глубину мы используем стек:

Мы посещаем каждую ячейку в сетке и помещаем ее соседей в стек для глубокого обхода:

Наиболее сложная логика заключается в отметке узла как достижимого (т.е. без стены между ними) с помощью CELL_PATH_S, CELL_PATH_N, CELL_PATH_W или CELL_PATH_E:

Наконец, вызывается метод drawMaze для отрисовки лабиринта на экране с использованием библиотеки SFML. Он рисует стену между двумя ячейками, если текущая ячейка не помечена как CELL_PATH_S, CELL_PATH_N, CELL_PATH_W или CELL_PATH_E.

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

Единственный способ обеспечить решение лабиринта – использовать предопределенную структуру, которая соединяет каждую часть лабиринта каким-либо образом.

Создание лабиринта с использованием графовой теории

Хорошо известные алгоритмы генерации лабиринтов основаны на графах. Каждая ячейка является узлом в графе, и каждый узел должен иметь хотя бы одно соединение с другими узлами.

Как уже упоминалось ранее, лабиринты представлены во многих формах. Некоторые, называемые “однопроходными” лабиринтами, действуют как лабиринты с одним входом, который также является выходом. У других может быть несколько решений. Однако процесс генерации часто начинается с создания “идеального” лабиринта.

“Идеальный” лабиринт, также известный как простой лабиринт, не имеет петель, замкнутых контуров и недоступных областей. Из любой точки внутри него есть ровно один путь к любой другой точке. Лабиринт имеет единственное, решаемое решение.

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

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

Может существовать несколько остовных деревьев, но цель состоит в том, чтобы обеспечить по крайней мере одно решение от начала до конца, как показано на приведенном ниже примере:

На изображении выше изображено только одно решение, но на самом деле есть несколько путей. Ни одна ячейка не является изолированной и недоступной. Итак, как нам это удалось?

Я обнаружил хорошо разработанное кодовое базовое множество mazegenerator от @razimantv, которое выполняет это, генерируя лабиринты в формате файлов SVG.

Поэтому я сделал форк репозитория и основал свое решение на нем. Большое спасибо @razimantv за элегантный объектно-ориентированный дизайн, который позволил мне настраивать результаты для создания визуально привлекательных изображений с использованием библиотеки SFML или генерировать текстовый файл с необходимым описанием карты для моего проекта Wall-E.

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

Однако я сохранил поддержку различных алгоритмов для построения остовного дерева.

Также я добавил комментарии во всем коде для более легкого понимания, так что мне не нужно объяснять каждую деталь здесь. Основной конвейер можно найти в \mazegenerator\maze\mazebaze.cpp:

Я внес визуализацию с использованием графической библиотеки SFML, благодаря простой функции _Draw_. При этом алгоритмом для создания остовного дерева по умолчанию является DFS, но доступны несколько других алгоритмов в качестве опций. Результатом является удобная утилита, генерирующая прямоугольные “идеальные” лабиринты и отображающая их на экране:

Как видите, он содержит ровно один вход и один выход в левом верхнем и правом нижнем углах. Код все еще генерирует файл SVG, что является приятным дополнением (хотя это и является основной функцией исходного кода).

Теперь я могу продолжить свои эксперименты в проекте Wall-E, и оставляю вас здесь, надеясь, что вы вдохновитесь исследовать этот увлекательный мир лабиринтов и отправитесь в свое собственное путешествие. Оставайтесь на связи!