Генерация лабиринта алгоритмом Эллера в Unity

    Всем привет!

    Сегодня хотелось бы рассказать о том, как генерировать лабиринты алгоритмом Эллера, и о том, как сделать красивую 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’ы, но в любом случае в было бы необходимо пересчитать 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.

    Если кому-то была бы интересна подробнее тема генерации мешей, которая является важной частью решения — могу написать про это отдельной статьёй.
    • +23
    • 12,7k
    • 8
    Поделиться публикацией
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 8
    • 0
      На первой картинке есть ячейка, где маршрут образует замкнутый квадрат, по остальным скринам не похоже, что это по крайней мере типично. Я просто к тому, что независимо от сложности лабиринта, если у вас постоянно подобие коридора, то блуждание по такому очень утомляет, переодические открытые пространства добавляют разнообразия.
      • 0
        Согласен, но это вопрос того, как именно визуализировать лабиринт. Так как лабиринт — это граф, и в целом его можно визуализировать по разному — это самая простая трёхмерная визуализация (ну точнеее технически не самая простая — самая простая из кубиков, но там будет куча проблем в стиле артефактов освещения на стыках, кривой тайлинг материалов и как следствие невозможность использовать один материал и т.п.) Вообще если говорить о использовании в играх, то удобнее всего сделать определённый набор готовых ячеек, и подставлять их. В целом сгенерированная структура данных W4Maze позволяет это сделать без особого труда.

        А по поводу скриншотов и замкнутых квадратов (особенно если речь о 3д) Там их не должно быть и это скорее всего оптическая иллюзия благодаря тому, что у стен нет «верха» — я его не визуализировал. Поэтому если у вас есть юнити, то можете скачать проект с гитхаба и посмотреть на результат.
      • 0
        очень прошу никогда не использовать вместе желтый, зеленый и любой такой же светлый цвет лишь слегка отличающийся Red компонентой в RGB. В жизни эти цвета легко различить, но только не в виде этих тонких линий. Для меня на картинке они ВСЕ одного цвета, а ведь я не дальтоник, просто есть ухудшенное различение цвета и таких людей чуть-ли не 10%.
      • 0
        В целом можно было бы использовать и юнитёвые Quad’ы, но в любом случае в было бы необходимо пересчитать uv координаты для того, чтобы тайлинг материала на всех стенах был одинаковый и при этом можно было бы использовать один материал.

        Или использовать трипланарный шейдер, когда UV рассчитывается в мировых координатах по одной из 3 текстур, в зависимости от нормали к поверхности.
        • 0

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

          • 0
            Да как не особо поможет? Трипланар изначально рассчитан на тайлинг, а лабиринты обычно строятся по сетке, т.е. хорошо ложатся на автоматически рассчет UV. Руками UV делают если нужны кастомные префабы стен, но тогда и сам лабиринт набирают из них, а не генерят геометрию на лету.
            • 0
              Ну да, я понял, что ты прав. Так тоже можно.

              По поводу руками — тут не только поэтому, допустим ты используешь этот материал ещё где-то и тебе там не нужен трипланарный шейдер. Но в целом да, ты прав — один из вариантов.

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

        Самое читаемое