Главная

Создание 3D-лабиринта на Unity.

Лабиринты – очень увлекательная игра, покорившая миллионы.

Поделиться:
 

1+

Лабиринты могут быть 2D — в таком случае игрок может наглядно проложить свой маршрут, или же 3D, что делает игру более захватывающей. Только представьте VR-лабиринт, в котором вы бегаете в поисках выхода.

Image for post

После того как я углубился в тему вершин трехмерных примитивных объектов в Unity, я решил заняться проектом по созданию лабиринта на плоскости. Центры грида — это точки на плоскости, и соответственно вокруг них нанесены границы. В этой статье я попытаюсь объяснить создание трехмерного лабиринта переменного размера с использованием точек на плоскости в Unity.

Генерация лабиринта и алгоритм рекурсивного возврата

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

Я решил пойти легким путем и выбрал алгоритм, который автор описал наиболее детально — алгоритм поиска с возвратом. Вот объяснение алгоритма. Моя реализация очень похожа на реализацию на Ruby. Разница лишь в направлении движения ячейки. В моей реализации это NSWE и UpDownLeftRight.

Реализация алгоритма рекурсивного поиска с возвратом

Алгоритм реализован в классе RecursiveBacktracker.

В классе RecursiveBacktracker есть два типа гридов. Integer предназначен для создания лабиринта, а Cell — для отображения лабиринта. Еще можно добавить класс, отображающий лабиринт, но поскольку его функционал простой, то делать я этого не стал. Переменные ширины и высоты используются для создания целочисленной сетки.

Объект Cell состоит из информации о границах и центральном положении.

Enum направлений

Также я использую много enum`ов, которые упрощают конвертирование значений.

Во-первых, есть enum Direction, в котором хранятся битовые значения для каждого направления.

Есть еще enum Opposite, где хранятся значения противоположных направлений.

Enum`ы DirectionX и DirectionY предназначены для смещения индекса сетки. Для каждого направления они меняют значение индекса. Например, для движения (x, y) вверх это (x + 0, y + (- 1)), а для движения влево (x + (- 1), y + 0).

Чтобы получить в одном и том же направлении разные значения enum`ов, существуют функции изменения значений.

Подготовка лабиринта

Внешний объект может запросить лабиринт путем предоставления сетки функции GetNewMaze. Сначала устанавливаются значения границ сетки, затем сетки инициализируются по умолчанию. С помощью CarvePassagesFrom реализован алгоритм, и сетка задается значениями лабиринта. Значения CellGrid заполняются в FillMazeValues и возвращаются запрашиваемому классу как новый лабиринт.

Создание дефолтного грида

Сетка (с англ. grid) создается как матрица GridHeight * GridWidth, точно так же, как CellGrid. Начальное значение сетки равно 0, что означает, что она ранее не посещалась и в ней нет переходов. CellGrid инициализируется соответствующей позицией по координатам данной сетки в алгоритме.

Прокладывание путей по координатам

Алгоритм начинается с движения в случайном направлении от текущей точки. Поскольку посетить нужно каждое направление, список рандомизирован. Новые координаты рассчитываются с использованием значений оси направления. Если новая точка ранее не была посещена, к ней прокладывается путь. Так как есть путь к новой ячейке, есть и путь на противоположной стороне для новой ячейки.

Image for post

Прокладывание пути представлено побитовыми операциями. Например, точка имеет только проход влево, а это означает, что значение ячейки 8 (1000 в двоичной системе), нижняя ячейка проверяется и ранее она не посещалась. Путь проложен вниз, 8 (1000| 2 (0010) = 10 (1010). Теперь в ячейке есть проход как с нижней, так и с левой стороны. В новой ячейке теперь есть переход на верхнюю сторону — значение 0 (0000) | 1 (0001) = 1.

Значения в лабиринте

Здесь мы делаем 3 вещи:
1. Заполняем границы каждой ячейки.
2. Репрезентуем карту символами (как в исходном объяснении алгоритма).
3. Создаем битовое представление карты.

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

Побитовая операция И (&) между ячейкой и направлением уведомляет нас о том, есть ли проход в этом направлении или нет. Для (Grid [y] [x] & (int) Direction.Down) == 0) предположим, что Grid [y] [x] = 12 (1100), 12 & 1 (0010) = 0000. Это говорит о том, что там нет прохода в ячейке в направлении вниз, то есть там есть граница. К границам ячейки добавляется направление вниз. Также проверяется правильность направления клетки.

Image for post

По мере добавления границ к CellGrid представления добавляются к строковым переменным. Для отсутствия границы «», для отсутствия нижней границы «_», для отсутствия левой границы «», для левой границы «|». Каждая строка начинается с новой строки(\n). Значения ячеек также собраны в строку сопоставления для отладки лабиринта.

Генератор лабиринта

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

Этим классом создаются границы. BorderParent — это родительская трансформация для всех созданных границ.

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

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

Создание сетки

Матрица Vector3 создается для хранения значений положения точек на плоскости с правильным размером. Заполнение матрицы начинается слева, с самого верха. Первый индекс представляет ось y, а второй индекс представляет ось x.

Демонстрация лабиринта на игровой сцене

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

Image for post

У каждой границы есть отступ, чтобы оставить пространство для коридора вокруг точки. Если направление вверх, оно перемещается в положительном направлении по оси x, а если вниз — в отрицательном направлении. Если направление оставлено, граница перемещается в положительном направлении по оси z, а если вниз — в отрицательном направлении.

Создание demo UI

Image for post

На экране есть кнопка для создания случайного лабиринта при каждом нажатии и два текстовых элемента для отображения текущих значений ширины и высоты лабиринта. Событие onClick вызывает CreateNewMaze MazeGenerator.

Дальнейшие улучшения

Есть много способов улучшить этот проект. Вот некоторые из них:
• Увеличение предела сетки более чем 11 * 11.
• Применяя вращение в соответствии с вращением плоскости.
• Изменение размера лабиринта.
• Создание уменьшенных версий большого лабиринта и т. Д.

Вы можете посмотреть проект здесь.

Спасибо, ребята, за ваше внимание!

1+