Всем привет!
Сегодня хотелось бы рассказать о том, как генерировать лабиринты алгоритмом Эллера, и о том, как сделать красивую 3д визуализацию в Unity, чтобы потом использовать её в своих играх. Также немного рассказать о том, как можно настроить пост обработку внутри данного решения. И по традиции ссылка GitHub с самим генератором.
Алгоритм Эллера — это достаточно популярный алгоритм генерации “идеальных” (между двумя точками существует единственный путь) лабиринтов, так как он один из самых быстрых и генерирует “интересные” лабиринты. “Интересными” они получаются за счёт того, что этот алгоритм не базируется на поиске остовного дерева в графе в следствии чего реже генерирует фрактальные структуры. В том числе одним из плюсов алгоритма является то, что он позволяет генерировать лабиринты бесконечного размера за линейное время.
Алгоритм базируется на том, что мы объединяем ячейки лабиринта в разные множества, а в последнем шаге алгоритма объединяем их в одно общем множество. Ячейки находятся в одном множестве — если от одной ячейки можно дойти до другой. Изначально все стены лабиринта подняты, так что все ячейки находятся в разных множествах.
Я видел множество различных описаний самого алгоритма (даже на хабре), поэтому не буду делать этого ещё раз, а вкратце напишу описание своей имплементации.
Сам алгоритм состоит из 3-ёх основных шагов.
В цикле:
1. Обрабатываем строку, случайным образом объединяя ячейки в строке принадлежащие разным множествам.
private void CreateRow(W4Maze maze, int rowNum)
{
for(int i = 0; i < maze.ColumnCount - 1; i++)
{
var cell = maze.GetCell(i, rowNum);
var nextCell = maze.GetCell(i + 1, rowNum);
if (cell.Set != nextCell.Set)
{
if (UnityEngine.Random.Range(0, 2) > 0)
{
RemoveHorizonWallBetweenCells(
maze,
cell,
nextCell,
rowNum);
}
}
}
}
2. Проходим по той же строке и случайным образом объединяем ячейки из строки выше с нашей строкой (с некоторыми ограничениями)
private void CreateVerticalConnections(
W4Maze maze,
int rowNum)
{
bool removeVertical = false;
bool isAddedVertical = false;
for (int i = 0; i < maze.ColumnCount - 1; i++)
{
W4Cell cell = maze.GetCell(i, rowNum);
W4Cell nextCell = maze.GetCell(i + 1, rowNum);
W4Cell topCell = maze.GetCell(i, rowNum + 1);
if (cell.Set != nextCell.Set)
{
if (!isAddedVertical)
{
RemoveVerticalWall(cell, topCell);
}
isAddedVertical = false;
}
else
{
removeVertical = Random.Range(0, 2) > 0;
if (removeVertical)
{
RemoveVerticalWall(cell, topCell);
isAddedVertical = true;
}
}
}
CheckLastVertical(maze, rowNum, isAddedVertical);
}
Последним шагом:
Обрабатываем последнюю строку объединяя ячейки из разных множеств
private void CreateLastRow(W4Maze maze)
{
int y = maze.RowCount - 1;
for(int i = 0; i < maze.ColumnCount - 1; i++)
{
var cell = maze.GetCell(i, y);
var nextCell = maze.GetCell(i + 1, y);
if(cell.Set != nextCell.Set)
{
RemoveHorizonWallBetweenCells(
maze,
cell,
nextCell,
y);
}
}
}
В целом это и есть алгоритм.
Лабиринт нужно в чём-то хранить. В моём решении есть 2 структуры для хранения лабиринтов.
W4Maze — который по сути представляет из себя массив ячеек 16-ти типов по количеству поднятых стен. Сама ячейка W4Cell хранит в себе просто 4 bool поля, которые говорят о том, какие стены подняты. Эта структура удобна для генерации лабиринта алгоритмом Эллера и удобна для сериализации.
Но с другой стороны она совершенно неудобна для генерации стен. Идея в том, что у лабиринта стены должны обладать толщиной, для того чтобы реализовать подобный алгоритм удобны именно графовые структуры. Для этого была заведена структура MazeGraph и реализовано преобразование из W4Maze в него. Кроме того, для удобства, в нём было создано 2 списка — путей и стен. В итоге написав простенькую визуализацию с помощью Gizmos мы получаем такой лабиринт. Желтый — это стены, а зелёный — это пути.
В целом уже неплохо, но в стенах и путях слишком много лишних узлов, что будет неудобно в дальнейшем для генерации трёхмерной визуализации, так что мы их упрощаем. Это позволит сгенерировать меньше мешей и избежать артефактов освещения на стыках.
private void ProcessWallEdges()
{
for(int i = 0; i < _WallEdges.Count; i++)
{
for(int j = i + 1; j < _WallEdges.Count; j++)
{
var edge1 = _WallEdges[i];
var edge2 = _WallEdges[j];
if (Mathf.Abs(edge1.Normal.x)
== Mathf.Abs(edge2.Normal.x)
&& Mathf.Abs(edge1.Normal.y)
== Mathf.Abs(edge2.Normal.y))
{
if (Edge.IsCanMerge(edge1, edge2))
{
var edge = Edge.Merge(edge1, edge2);
_WallEdges.Remove(edge1);
_WallEdges.Remove(edge2);
_WallEdges.Remove(edge);
_WallEdges.Insert(i, edge);
j = i;
}
}
}
}
}
Остальное уже дело техники. У меня написан свой инструмент для генерации плоскостей класс MeshTools с самой простой триангуляцией (так как мы знаем порядок добавления точек) В целом можно было бы использовать и юнитёвые Quad’ы, но в любом случае в 3д был было бы необходимо пересчитать uv координаты для того, чтобы тайлинг материала на всех стенах был одинаковый и при этом можно было бы использовать один материал. Более подробно можно посмотреть по ссылке на GitHub.
Итак, лабиринт построен, правильно выставлены uv-шки. Теперь хочется показать простейший пример возможности пост процессинга на примере автоматической расстановки света. Для этого я создал класс LightPlacer и тут нам снова пригодится лабиринт W4Maze. Алгоритм пост обработки довольно простой. Мы просто задаём уровни освещённости, переводим тип ячейки в int и принимаем решение, ставить источник света или нет.
public GameObject SetUpLights(
W4Maze maze,
float height)
{
GameObject lights = new GameObject();
for(int i = 0; i < maze.ColumnCount; i++)
{
for(int j = 0; j < maze.RowCount; j++)
{
var cell = maze.GetCell(i, j);
if(cell.ToInt() < (int) _LightLevel)
{
var lightGo = CreatePointLight();
lightGo.transform.position = new Vector3(
i ,
height * 0.9f,
j);
}
}
}
return lights;
}
public enum LightLevel : byte
{
Low = 3,
Medium = 5,
High = 10,
VeryHigh = 16
}
И вот наш финальный лабиринт!
С помощью подобной пост обработки можно расставлять декали, врагов, ловушки, да и всё что угодно.
Спасибо за внимание! Кому хочется ознакомится с решением подробнее ссылка на GitHub.
Если кому-то была бы интересна подробнее тема генерации мешей, которая является важной частью решения — могу написать про это отдельной статьёй.
Автор: Григорий Дядиченко
