Лабиринты - это непредсказуемые части игрового процесса, если они двухмерные, вы можете увидеть и проложить путь наверху. Если вы можете увидеть весь лабиринт выше в 3D, вы можете сделать то же самое, что катать мяч в лабиринте. В частности, представьте себе VR-игру, в которой вы пробегаете по лабиринту, чтобы найти выход.
После того, как я погрузился в сферу вершин на трехмерных примитивных объектах в Unity, я решил заняться проектом по созданию лабиринта на плоскости. Центры пояса - это точки на плоскости, и соответственно границы обведены вокруг них. В этом уроке я пытаюсь объяснить создание трехмерного лабиринта переменного размера с использованием точек на плоскости в Unity.
Генерация лабиринта и алгоритм рекурсивного возврата
Как я уже упоминал выше, после того, как на нем была плоскость и точки (поиск точек на плоскости, реализация, использованная в этом проекте), я начал задаваться вопросом, как с их помощью создать лабиринт. С помощью быстрых алгоритмов генерации лабиринтов в Google я наткнулся на эту великую коллекцию алгоритмов генерации лабиринтов, написанных Джеймисом Баком. В списке около 11 алгоритмов и демонстраций.
Я пошел по короткому пути и выбрал ранее любимый автором алгоритм создания лабиринта - алгоритм рекурсивного обратного отслеживания. Вот объяснение алгоритма в его блоге. Моя реализация очень параллельна реализации на Ruby. Самая большая разница - это направление движения ячейки. В моей реализации это N, S, W, E и Up, Down, Left, Right.
Реализация алгоритма рекурсивного поиска с возвратом
Алгоритм реализован в классе RecursiveBacktracker.
В классе RecursiveBacktracker есть два типа сеток. Целочисленный один для создания лабиринта, а Cell один для отображения лабиринта. Может быть класс, показывающий лабиринт, но, поскольку его функциональность проста, он не был создан. Переменные ширины и высоты используются для создания целочисленной сетки.
Объект Cell состоит из информации о его границах и его центральном положении.
Перечисления направлений
При разработке используются многочисленные переменные enum для облегчения передачи значений действий.
Во-первых, у нас есть перечисление Direction, которое содержит битовые значения для каждого направления.
Существует противоположное перечисление, так как название предполагает, что значения противоположных направлений меняются местами.
Перечисления DirectionX и DirectionY предназначены для перемещения индекса сетки. Для каждого направления они соответственно меняют значение индекса. Например, для перемещения (x, y) вверх это (x + 0, y + (- 1)), для перемещения влево это (x + (- 1), y + 0) в списке списка.
Чтобы получить в одном и том же направлении разные значения из разных перечислений, существуют функции изменения значений.
Подготовка лабиринта
Внешний объект может запросить лабиринт, предоставив сетку функции GetNewMaze алгоритма. Сначала устанавливаются значения границ сетки, затем сетки инициализируются по умолчанию. С помощью CarvePassagesFrom реализуется алгоритм, и сетка задается значениями лабиринта. Значения CellGrid заполняются в FillMazeValues и возвращаются запрашиваемому классу как новый лабиринт.
Создание сеток по умолчанию
Сетка создается как матрица GridHeight * GridWidth, а также как CellGrid. Начальное значение сетки равно 0, что означает, что она ранее не посещалась и в ней нет переходов. CellGrid инициализируется соответствующим положением по координатам данной сетки в алгоритме.
Вырезание переходов по координатам
Алгоритм начинается с движения в случайном направлении от текущей точки. Поскольку каждое направление необходимо посетить, список составлен случайным образом. Новые координаты рассчитываются с использованием значений оси направления. Если новая точка ранее не была посещена, к ней вырезается проход. Поскольку есть проход к новой ячейке, есть проход на противоположной стороне для новой ячейки.
Резьба прохода представлена поразрядно. Например, точка имеет только переход влево, что составляет значение ячейки 8 (1000 бит), нижняя ячейка проверяется, и она не была посещена ранее. Переход прорублен вниз, 8 (1000) | 2 (0010) = 10 (1010). Теперь в камере есть проход как с нижней, так и с левой стороны. В новой ячейке теперь есть переход на верхнюю сторону со значением 0 (0000) | 1 (0001) = 1.
Ценности, наполненные лабиринтом
Здесь мы делаем 3 вещи: заполняем границы каждой ячейки, отображаем карту в символах (как объяснено в исходном посте об алгоритме) и создаем побитовое представление значения карты. Мне нравится использовать последнее в качестве упражнения для мозга. Его много использовали для отладки карт.
В первую очередь добавляются границы справа и снизу. Потому что нижняя граница одной ячейки ниже верхней границы ячейки. Избегаем дублирования при добавлении границ. Поскольку добавляются только правая и нижняя границы, сначала добавляются левая и верхняя границы лабиринта отдельными шагами.
Побитовая операция И (&) между ячейкой и направлением дает нам, есть ли проход в этом направлении или нет. Для (Grid [y] [x] & (int) Direction.Down) == 0) предположим, что Grid [y] [x] = 12 (1100), 12 & 1 (0010) = 0000. Он говорит, что там в ячейке нет прохода в направлении вниз, значит, там есть граница. К границам ячейки добавляется направление вниз. То же самое проверяется на правильность направления клетки.
Когда границы добавляются к CellGrid, представления добавляются к строковым переменным. Без нижней границы «», без нижней границы «_», без левой границы «», левой границы «|» добавлен. Каждая строка начинается с новой строки. Значения ячеек также собраны в строку сопоставления, чтобы показать и отладить лабиринт.
Генератор лабиринта
В этом классе задается размер лабиринта, лабиринт задается алгоритму, и созданный лабиринт отображается на игровую сцену.
Границы создаются этим классом. BorderParent - это родительское преобразование для всех созданных границ.
Создание лабиринта
Во-первых, все ранее установленные переменные очищаются или устанавливаются с новыми значениями. Затем создается сетка с координатами правильного размера, размера, показанного на сцене, запрошенного лабиринта и трехмерного лабиринта, показанного на сцене.
Создание сетки
Матрица Vector3 создается для хранения значений положения точек на плоскости с правильным размером. Заполнение матрицы начинается слева, с самого верха. Первый индекс представляет ось y, а второй индекс представляет ось x.
Отображение лабиринта на игровой сцене
Создаются два куба, которые являются вертикальной и горизонтальной границами каждой точки лабиринта. Затем каждая ячейка проходит итерацию. Если границы ячейки включают границу в направлении вверх или вниз, устанавливается горизонтальная граница, в противном случае - вертикальная граница.
У каждой границы есть отступ, чтобы оставить пространство для коридора вокруг точки. Если направление вверх, оно перемещается в положительном направлении по оси x, а если оно вниз, оно перемещается в отрицательном направлении. Если направление оставлено, граница перемещается в положительном направлении по оси z, а если вниз - в отрицательном направлении.
Создание демонстрационного пользовательского интерфейса
На экране есть кнопка для создания случайного лабиринта при каждом нажатии и два текстовых элемента для отображения текущих значений ширины и высоты лабиринта. Событие onClick кнопки вызывает CreateNewMaze MazeGenerator.
Обновление: создание префаба случайного лабиринта в режиме воспроизведения редактора в Unity
Во время поиска информации о создании лабиринтов я наткнулся на комментарий Reddit, в котором утверждалось, что люди создают лабиринты, но никогда не показывают, как их спасти. Этот комментарий побудил меня поработать над этим, и по результатам работы родился видеоурок, представленный ниже.
Дальнейшие улучшения
Вы знаете, что проект может быть кроличьей ноской, как этот. Есть много способов улучшить этот проект. Такие как:
- Увеличение лимита сетки более 11 * 11,
- Применяя вращение в соответствии с вращением плоскости,
- Изменение размера лабиринта,
- Создание уменьшенных версий большого лабиринта и т. Д.
Вы можете найти проект здесь.
Первоначально опубликовано на сайте http://sscriptiee.wordpress.com 16 августа 2019 г.
