Процедурная генерация планов помещений


    Что делает крупный разработчик игр, когда ему нужно состряпать много помещений для игрового мира? Нанимает кучу художников. Что делает ленивый/бедный/одинокий разработчик игр в такой же ситуации? Пишет процедурный генератор, который выполняет за него всю грязную работу.

    По процедурной генерации планов помещений есть много, очень много статей. Вот ещё пяток ссылок на статьи. Только исходников ни к одной из них нет.

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

    Если хотите, то можете почитать оригинальную статью, но суть примерно следующая:
    • Всё пространство разбито на клетки наподобие сетки в архитектурных планах.
    • Внешние стены уже существуют и подаются на вход программе.
    • Есть список комнат, которые нужно разместить на плане.
    • Комнаты имеют параметр «желаемый размер» и коэффициенты притяжения друг к другу
    • Точки рождения комнат раскидываются по плану случайным образом, возможно с помощью некоей примерной карты.
    • Затем каждая точка начинает прямоугольно расти пока не достигнет определённых для неё размеров.
    • Когда все прямоугольники выросли, комнаты начинают расти в форме буквы L до тех пор, пока это возможно.
    • Оставшееся свободное место пристёгивается к соседям.

    Комнаты растут по одной стенке за раз, чтобы избежать наползания стен и комнат друг на друга. Стенка выбирается из самых больших стен комнаты, если есть одинаковые — берётся случайная. Наибольшая стена берётся для того, чтобы рост площади комнат был максимальным, и они были «пухлыми».

    Теперь про мою реализацию. Я не стал пока заморачиваться с реалистичностью планировки, коэффициентами и размерами комнат — это всё украшательства, я работал над основным алгоритмом, всё остальное можно быстро добавить. Также в статье говорится о специальных проверках, предотвращающих появление П-образных комнат, я не стал их делать, не вижу ничего плохого в таких комнатах. Также я не расставлял коридоры, двери и окна, это отдельная тема, и их расстановка может зависеть от генерации всего остального здания.

    Самым сложным было выбрать принцип роста комнат и способ хранения данных о них и здании. Один и тот же результат можно получить с помощью клеточных автоматов или даже простого пробега по массиву. Я перепробовал несколько вариантов, мне хотелось всегда иметь представление о габаритах комнаты и точном положении её стен, поэтому я создал класс, в котором хранятся только углы комнаты, а стены автоматически создаются путём связывания двух соседних углов.

    Связывание стен это по сути поиск оболочки полигона из набора точек. Задача нетривиальная и с кучей подвохов, если интересно, то советую заглянуть сюда. К счастью, я решил ограничиться прямыми углами между соседними стенами и смастерил простенький алгоритм:
    • Находим минимальные и максимальные значения координат X и Y в наборе точек.
    • Из точки (minX, minY) отправляемся наверх по игреку и поочерёдно ищем точку с такими координатами, если её там нет, то ищем справа, снизу и слева. Когда находим, вытаскиваем её из старого списка, переносим в новый список.
    • От координат этой точки в старом списке ищем следующую точку выше по игреку, если нашли — переносим в новый список, удаляем из старого, запоминаем, что нашли стену, которая параллельна Y, значит следующая стена должна быть параллельна X.
    • Ищем точку по иксу справа и слева, переносим в новый список, запоминаем ориентацию только что найденной стены, ищем дальше по аналогии.
    • Последнюю точку в старом списке просто переносим в новый.

    Сортировка углов комнаты
        public GridVector SortCorners()
        {
            // Ищем границы комнаты
            var minX = corners[0].x;
            var maxX = corners[0].x;
            var minY = corners[0].y;
            var maxY = corners[0].y;
            foreach (var corner in corners)
            {
                if (corner.x < minX) minX = corner.x;
                if (corner.x > maxX) maxX = corner.x;
                if (corner.y < minY) minY = corner.y;
                if (corner.y > maxY) maxY = corner.y;
            }
    
            // Сортируем углы комнаты
            var oldC = new List<GridVector>(corners);
            var newC = new List<GridVector>();
            bool parallelX = false;
            while (oldC.Count > 1)
            {
                // Ищем первый угол
                if (newC.Count == 0)
                {
                    if (ScanUp(ref oldC, ref newC, minX, minY, maxY)) continue;
                    if (ScanRight(ref oldC, ref newC, minX, minY, maxX)) continue;
                    if (ScanDown(ref oldC, ref newC, minX, minY, minY)) continue;
                    if (!ScanLeft(ref oldC, ref newC, minX, minY, minX))
                    {
                        Debug.Log("Error on start");
                        return null;
                    }
                }
                // Ищем остальные углы
                else
                {
                    var last = newC[newC.Count - 1];
                    if (parallelX)
                    {
                        if (ScanRight(ref oldC, ref newC, last.x, last.y, maxX))
                        {
                            parallelX = false;
                            continue;
                        }
                        if (ScanLeft(ref oldC, ref newC, last.x, last.y, minX))
                        {
                            parallelX = false;
                            continue;
                        }
                    }
                    else
                    {
                        if (ScanUp(ref oldC, ref newC, last.x, last.y, maxY))
                        {
                            parallelX = true;
                            continue;
                        }
                        if (ScanDown(ref oldC, ref newC, last.x, last.y, minY))
                        {
                            parallelX = true;
                            continue;
                        }
                    }
                    Debug.Log("Error -------------------------------------------------");
                    Debug.Log("Corners: " + corners.Count);
                    Debug.Log("OldC: " + oldC.Count);
                    Debug.Log("NewC: " + newC.Count);
                    Debug.Log(last);
                    color = Color.red;
                    return last;
                }
            }
            // Добавляем последний оставшийся угол
            newC.Add(oldC[0]);
            corners = newC;
            return null;
        }
    
        bool ScanLeft(ref List<GridVector> oldC, ref List<GridVector> newC, int startX, int startY, int minX)
        {
            for (var x = startX; x >= minX; x--)
            {
                var index = oldC.FindIndex(gv => gv.x == x && gv.y == startY);
                if (index > -1)
                {
                    newC.Add(oldC[index]);
                    oldC.RemoveAt(index);
                    return true;
                }
            }
            return false;
        }
    
        bool ScanUp(ref List<GridVector> oldC, ref List<GridVector> newC, int startX, int startY, int maxY)
        {
            for (var y = startY; y <= maxY; y++)
            {
                var index = oldC.FindIndex(gv => gv.x == startX && gv.y == y);
                if (index > -1)
                {
                    newC.Add(oldC[index]);
                    oldC.RemoveAt(index);
                    return true;
                }
            }
            return false;
        }
    
        bool ScanRight(ref List<GridVector> oldC, ref List<GridVector> newC, int startX, int startY, int maxX)
        {
            for (var x = startX; x <= maxX; x++)
            {
                var index = oldC.FindIndex(gv => gv.x == x && gv.y == startY);
                if (index > -1)
                {
                    newC.Add(oldC[index]);
                    oldC.RemoveAt(index);
                    return true;
                }
            }
            return false;
        }
    
        bool ScanDown(ref List<GridVector> oldC, ref List<GridVector> newC, int startX, int startY, int minY)
        {
            for (var y = startY; y >= minY; y--)
            {
                var index = oldC.FindIndex(gv => gv.x == startX && gv.y == y);
                if (index > -1)
                {
                    newC.Add(oldC[index]);
                    oldC.RemoveAt(index);
                    return true;
                }
            }
            return false;
        }
    



    В конечном итоге, у нас получается список углов, отсортированных по часовой стрелке, из которого можно запросто вывести стены. Благодаря сортировке становится легко узнать ещё одну важную вещь — направление наружу от стены комнаты. Для того чтобы повернуть конец стены наружу, нужно поменять X и Y местами и инвертировать первую координату, чтобы получилось следующее: (-y, x).

    Комнаты хранятся в виде точек, точки сортируются, стены строятся автоматически, направление наружу известно — всего этого достаточно, чтобы проверять свободное пространство на плане этажа и выращивать комнаты. Иногда правда приходится добавлять новые стены, когда старые уже во что-то упёрлись и не могут расти.

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

    Поиск сегментов стены
    List<RoomWall> FindSegments(RoomWall wall, Color freeColor, Color roomColor)
        {
            var moved = wall + wall.outwards.minimized;
            BresenhamLine(moved, new Color(Random.value * 0.7f + 0.1f, Random.value * 0.7f + 0.1f, Random.value * 0.7f + 0.1f), segmentsTexture);
            var x0 = moved.start.x;
            var y0 = moved.start.y;
            var x1 = moved.end.x;
            var y1 = moved.end.y;
            var segments = new List<RoomWall>();
            GridVector start = null;
            GridVector end = null;
    
            bool steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0);
            if (steep)
            {
                Swap(ref x0, ref y0);
                Swap(ref x1, ref y1);
            }
            if (x0 > x1)
            {
                Swap(ref x0, ref x1);
                Swap(ref y0, ref y1);
            }
            for (int x = x0; x <= x1; x++)
            {
                for (int y = y0; y <= y1; y++)
                {
                    int coordX = steep ? y : x;
                    int coordY = steep ? x : y;
                    Color color = texture.GetPixel(coordX, coordY);
                    if (color != freeColor && color != roomColor)
                    {
                        if (end != null && start != null)
                        {
                            var segment = new RoomWall(start, end);
                            segment -= wall.outwards.minimized;
                            segments.Add(segment);
                            start = null;
                            end = null;
                        }
                        scanTexture.SetPixel(coordX, coordY, Color.red);
                    }
                    else
                    {
                        if (start == null)
                        {
                            start = new GridVector(coordX, coordY);
                        }
                        end = new GridVector(coordX, coordY);
                        scanTexture.SetPixel(coordX, coordY, Color.green);
                    }
                }
            }
            if (end != null && start != null)
            {
                var segment = new RoomWall(start, end);
                segment -= wall.outwards.minimized;
                segments.Add(segment);
            }
            return segments;
        }
    


    Для отображения всех манипуляций с комнатами я использую текстуру, в пиксели которой заношу положения стен. Если не стирать старые стенки, то получаются заполненные области, как на gif-ке в начале статьи. Стены рисую с помощью линий Брезенхема, про которые я писал здесь. В случае возникновения проблем со склейкой стен, всё сразу становится видно. Вместо текстуры можно использовать двумерный массив или сразу оперировать трёхмерной моделью.

    Внешние стены можно генерировать очень просто. Рисуем несколько чёрных прямоугольников произвольных размеров, а поверх них рисуем такие же только белые и на один пиксель меньше с каждой стороны. Получается много разных домиков. Ещё их можно сделать трёхмерными и покрыть крышей. Голосом Каневского: Впрочем, это уже совсем другая история.

    По ссылкам ниже можете посмотреть бинарники и исходники готового проекта.

    Unity Web Player | Windows | Linux | Mac | Исходники на GitHub

    Shift — Создаёт случайные внешние стены со случайными комнатами
    Ctrl — Загрузить тестовую текстуру со случайными комнатами
    Enter — Убрать все комнаты и загрузить тестовую текстуру
    Пробел — Остановить рост комнат
    Единица на алфавитной клавиатуре — Включить визуализацию поиска свободных клеток
    Левая кнопка мыши на свободной области — Добавить комнату
    Esc — Выход

    Для пользователей Linux: Сделайте файл ProceduralExperiments.x86 исполняемым с помощью «chmod +x ProceduralExperiments.x86» и запускайте.
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 29

      +11
    • UFO just landed and posted this here
        0
        Вариантов много. Если здание многоэтажное или создаётся от большего масштаба к меньшему, то окна скорее всего уже есть. Тогда можно насоздавать комнат, а потом просто сдвинуть стены, чтобы они не упирались в центр окон. Либо убирать перекрытые окна. Про окна здесь неплохо написано.

        С дверями поступают по-всякому. Либо дырявят каждую стену, потом закрывают лишние и проверяют связность с помощью A*. Либо изначально создают иерархию комнат и ставят двери только между нодами дерева. Например ветвь может выглядеть так: лифт — коридор — прихожая — ванная. Тогда все комнаты гарантированно будут доступны.
          0
          Некрасиво получается
          0
          Давайте прикинем. Для простоты пусть двери будут двусторонними. У вас есть полигоны с прямыми углами. Каждый отрезок на краю полигона может быть либо окном, либо дверью. Причём окно всегда идёт наружу, а между двумя комнатами может быть только дверь (пусть даже только одна). С учётом условия на отступ между окнами и дверьми (но не вместе) и неперекрытия окон дверьми, осталось только пройтись по каждому краю полигонов.

          Двери и окна — это всё цветочки. Вы лучше подумайте, как весело там мебель процедурно расставлять.
          +6
          Одна из гифок напомнила змейку

          • UFO just landed and posted this here
              +7
              «А сейчас мы вас покажем мультик.
              Соединение с сервером
              Связи нет. Спасибо, все свободны.»
              ааааааааааааааааа
              +4
              В первой гифке в чем логика закрашивания правого нижнего угла именно таким образом?
                +5
                Чёрт, заметили-таки) Включился рост угловых сегментов у двух комнат сразу, и они начали есть друг друга. Теоретически, чтобы такого не было, должна расти только одна комната за раз, а это ошибка, но я её ещё не отловил, сегодня буду допиливать генератор и разберусь.
                  +1
                  Такое часто случается. Получаются диагональные стены =)
                  />
                  Пример
                  image
                    0
                    Хммм, возможно я загрузил на гитхаб старую версию, таких суровых лесенок быть уже не должно.
                      +2
                      Имитация криворукости строителей.
                      +2
                      это не баг, это фича :)
                      0
                      Напоминает «В чем смысл прихода Бодхидхармы с запада»?
                      0
                      На анимации про поиск оболочки — рисуется невыпуклая, а ссылка ведёт на википедию о выпуклой оболочке.
                      Неувязочка?
                        0
                        Ссылка на вики это лишь отправная точка. Алгоритмы поиска выпуклых оболочек значительно проще, к тому же подобной статьи на википедии для впуклых оболочек нету. Про них можно попробовать поискать по запросу «alpha shape», это близкая тема.
                          0
                          Стоит об этом написать прямо в статье.
                          Немножко граммар-нацизма: не «впуклая», а «вогнутая» хотя бы. Ну или уже упомянутая «невыпуклая».

                          И всё равно, анимация не соответствует «простенькому алгоритму».
                          Из пятой по счёту точки, если перебирать направления вправо-вниз-влево, мы сразу же найдём восьмую по счёту точку (вправо). Но вместо этого, почему-то, полезли вниз.
                          Или ищется ближайшая точка? Какая метрика — манхеттенская, евклидова?
                          Что делать, если ближайшая точка находится не строго справа, например, а справа и чуть вверх? Где будет ступенька?

                          Или же алгоритм построения оболочки выдуман, а на самом деле, используется другой подход?
                          Вот лично я бы не парился с оболочками, а взял описывающий прямоугольник и пооткусывал из него с краёв и с углов.
                          Или наоборот: нашлёпал бы в пределах прямоугольной области достаточное количество прямоугольников, пока их объединение не стало бы односвязным.
                            0
                            Я пробовал искать оболочки классическими алгоритмами, но на выходе получались непредсказуемые результаты. Поэтому я придумал свой, он описан в статье. Только первая точка ищется во все стороны, просто на всякий случай, этот код на самом деле можно удалить.
                            запоминаем, что нашли стену, которая параллельна Y, значит следующая стена должна быть параллельна X.

                            В коде есть переменная, которая в цикле направляет «поисковую бригаду» либо вверх и вниз, либо вправо и влево, в зависимости от предыдущей точки. Пятая по счёту точка была найдена при движении по оси икс, следовательно шестую точку можно найти, если двигаться по оси игрек. Никакие косые стены алгоритмом не учитываются, все углы должны быть прямые как в подавляющем большинстве комнат в реальном мире.

                            Расскажите поподробнее про откусывание с краёв и с углов?
                              0
                              Углы-то пусть будут прямые, но что, если ближайшие точки — те, до которых мы интуитивно бы построили стену — находятся немного наискось?
                              Тут есть несколько вариантов:
                              — Проложить ломаную стену, — так, как это делают ортогональные соединительные линии в Visio, например; при этом надо уточнить, где именно мы будем стену ломать: с одного края, с другого, посередине, случайно…
                              — Просто не рассматривать эти точки. С риском не замкнуть контур или замкнуть преждевременно.
                              — Не рассматривать точки, но продолжить существующую стену по прямой, до тех пор, пока на перпендикулярном направлении не обнаружим точку. Естественно, тут дьявол в деталях, всякие эвристики, потому что так мы можем случайно замкнуть контур раньше времени. Например, будем обходить фигуру по часовой стрелке (как на анимации) — и рассматривать только точки по левую руку.
                              В отличие от алгоритмов выпуклой оболочки, которые хорошо формализованы, тут слишком много всяких выдумок и оговорок, — и это мне не нравится.

                              Про откусывание: ну это очень просто.
                              Есть два способа. Первый — это взять замкнутую ломаную (контур прямоугольника) и случайным образом наломать её, так, чтобы не возникло самопересечений. Второй — залить прямоугольник чёрным цветом и накидать на него с боков случайные белые прямоугольники меньшего размера, так, чтобы сохранилась односвязность чёрной фигуры.
                        +2
                        Для пользователей Linux: Сделайте файл ProceduralExperiments.x86 исполняемым с помощью «chmod +x ProceduralExperiments.x86» и запускайте.

                        Подскажите, а почему бы не запаковать linux-версию в какой-нибудь формат архива, поддерживающий сохранение прав — тот же tar.gz / tar.bz2?
                          0
                          Дак я же всё равно на винде компилирую и запаковываю, разве там есть чему сохраняться? Вообще мне не без разницы, щас перепакую.
                            0
                              0
                              Ну, так оно пакует все файлы с правами "-rwxrwxrwx", что тоже неидеально, но, по крайней мере, не требует дополнительных телодвижений со стороны пользователя для запуска. Я попробую спросить, как создавать на Windows tarball'ы с более правильными правами на файлах внутри — если ответят чего-нибудь хорошее — отпишу.
                          0
                          вот за статьи спасибо! будет что почитать ))
                            +1
                            Вот такая картинка приводит к остановке алгоритма и 100% загрузке проца юнити плеером

                            image
                              0
                              О, и вправду намертво виснет. Спасибо.
                                0
                                перезалил картинку на хабрасторадж

                              Only users with full accounts can post comments. Log in, please.