Процедурный генератор хрущёвок

в 11:22, , рубрики: game development, unity3d, Алгоритмы, Программирование, процедурная генерация, метки: ,

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

На самом деле, у хрущёвок существует несколько десятков модификаций, но некая основа, сущность хрущёвки всё равно прослеживается.

В общем, недолго думая, я сел и написал генератор хрущёвок на C# под Unity3d. Под катом описание работы алгоритма и размышления на тему uv-карт, сабмешей и шейдеров.

▣ Первая попытка. Тотальное программирование всей геометрии.

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

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

Возьмём к примеру окно. Если оно абсолютно плоское и представляет собой просто квадратик в квадратике, то это уже выходит восемь вершин и десять треугольников. Если окно немного утопить в стену, то это ещё четыре вершины и ещё восемь треугольников. А если ещё добавить подоконник или ящик с цветами? Лично у меня от таких вычислений из ушей начинает валить пар.

Код для создания примитивного окошка

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

Mesh EntrancePanel(Vector3 vertex0, Vector3 vertex1, Vector3 vertex2, Vector3 vertex3)
{
    var normal = Vector3.Cross((vertex1 - vertex0), (vertex2 - vertex0)).normalized;
    var window0 = vertex0 + (vertex3 - vertex0) * 0.25f + (vertex1 - vertex0) * 0.25f;
    var window1 = vertex0 + (vertex3 - vertex0) * 0.25f + (vertex1 - vertex0) * 0.75f;
    var window2 = vertex0 + (vertex3 - vertex0) * 0.75f + (vertex1 - vertex0) * 0.75f;
    var window3 = vertex0 + (vertex3 - vertex0) * 0.75f + (vertex1 - vertex0) * 0.25f;

    var mesh = new Mesh
    {
        vertices = new[] {vertex0, vertex1, vertex2, vertex3,
                        window0, window1, window2, window3,
                        window0, window1, window2, window3},
        normals = new[] { normal, normal, normal, normal,
                        normal, normal, normal, normal,
                        normal, normal, normal, normal },
        uv = new[] {new Vector2(0, 0), new Vector2(0, 1), new Vector2(1, 1), new Vector2(1, 0),
                        new Vector2(0.25f, 0.25f), new Vector2(0.25f, 0.75f),
                        new Vector2(0.75f, 0.75f), new Vector2(0.75f, 0.25f),
                        new Vector2(0, 0), new Vector2(0, 1), new Vector2(1, 1), new Vector2(1, 0)},
        triangles = new[]
                {
                    0, 1, 4,
                    4, 1, 5,
                    1, 2, 5,
                    5, 2, 6,
                    2, 3, 6,
                    6, 3, 7,
                    3, 0, 7,
                    7, 0, 4,

                    8, 9, 10,
                    10, 11, 8},
        subMeshCount = 2
    };
    mesh.SetTriangles(new[] { 0, 1, 4,
                                4, 1, 5,
                                1, 2, 5,
                                5, 2, 6,
                                2, 3, 6,
                                6, 3, 7,
                                3, 0, 7,
                                7, 0, 4}, 0);
    mesh.SetTriangles(new[] { 8, 9, 10, 10, 11, 8 }, 1);
    return mesh;
}

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

▣ Вторая попытка. Всё через редактор, с сабмешами и множеством материалов

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

На каждый из сабмешей можно повесить свой материал, который будет делать стёкла блестящими, а стены шершавыми. Идея вполне сносная, вот только каждый материал это дополнительный вызов шейдера, а слежка за индексами сабмешей оказалась невероятно муторной задачей. Я немного поигрался с сабмешами и забросил эту затею.

▣ Третья попытка. Cамописный шейдер и текстурные карты

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

Я решил написать свой шейдер, благо в Unity это просто, и использовал для текстурирования моделей единый атлас. Шейдер принимает на вход этот атлас и дополнительную карту блестящих поверхностей, в которую я занёс все окна.

Код шейдера для хрущёвки

Код ниже это обычный Specular шейдер, идущий в комплекте с Unity, в котором в отдельную карту вынесены окна и добавлен параметр для смены их цвета.
Shader "Custom/Khrushchyovka" {
	Properties {
		_Color ("Main Color", Color) = (1,1,1,1)
		_MainTex ("Base (RGBA)", 2D) = "white" {}
		_GlassColor ("Glass Color", Color) = (0.5, 0.5, 0.5, 1)
		_Shininess ("Shininess", Range (0.01, 1)) = 0.078125
		_SpecColor ("Specular Color", Color) = (0.5, 0.5, 0.5, 1)
		_SpecTex ("Specular (RGB)", 2D) = "gray" {}
	}
	SubShader {
		Tags { "RenderType"="Opaque" }
		LOD 200
		
		CGPROGRAM
		#pragma surface surf BlinnPhong

		sampler2D _MainTex, _SpecTex;
		fixed4 _Color, _GlassColor;
		half _Shininess;

		struct Input {
			float2 uv_MainTex;
		};

		void surf (Input IN, inout SurfaceOutput o) {
			half4 main = tex2D (_MainTex, IN.uv_MainTex);
			half4 spec = tex2D(_SpecTex, IN.uv_MainTex);
			o.Albedo = main.rgb * _Color.rgb + spec.rgb * _GlassColor.rgb;
			o.Gloss = spec.rgb;
			o.Specular = _Shininess;
		}
		ENDCG
	} 
	FallBack "Diffuse"
}

▣ Возводим стенку

Теперь самое интересное — сборка здания. Проще всего начать с одной стены. Чтобы сделать из нескольких панелей стену, их нужно расставить рядом. В предыдущей статье я упоминал CombineMeshes, используемый для объединения моделей. Вместе с моделями ему можно скармливать матрицы трансформирования, с помощью которых можно двигать, вращать и менять размер моделей. Логика простая: в цикле набираем нужное количество моделей, каждую сдвигаем на определённое расстояние, получаем непрерывную стену. Если нужна стена определённой размера, то просто делим его на длину одной панели и узнаём необходимое количество панелей.

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

С двумя разными плитами заполнить интервал заданной длины гораздо сложнее. У этой задачи есть своё название — Subset sum problem. Вариантов решения этой проблемы много, я выбрал простой рекурсивный алгоритм.

Изначально есть массив с доступными длинами панелей и отрезок, который необходимо заполнить. В результате работы алгоритма получается другой массив, числа в котором означают количество необходимых панелей с длиной по совпадающему индексу из первого массива. То есть первый массив выглядит так: {3, 2.5f}. А второй для отрезка 11 метров выглядит так: {2, 2}. Отмечу ещё, что массив с панелями отсортирован в убывающем порядке.

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

Код алгоритма

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

int[] ExteriorWallSizesDraft(float remainder, int[] draft = null, int startIndex = 0)
{
    if (draft == null)
    {
        draft = new int[panels.Length];
        for (int i = 0; i < draft.Length; i++)
        {
            draft[i] = 0;
        }
    }
    if (remainder < panels[panels.Length - 1])
    {
        draft[draft.Length - 1] = 1;
        return draft;
    }
    for (var i = startIndex; i < panels.Length; i++)
    {
        draft[i] += (int)(remainder / panels[i]);
        remainder %= panels[i];
    }
    if (remainder > 0)
    {
        for (var i = 0; i < draft.Length; i++)
        {
            if (draft[i] != 0)
            {
                if (i == draft.Length - 1)
                {
                    return draft;
                }
                draft[i]--;
                remainder += panels[i];
                startIndex = i+1;
                break;
            }
        }
        draft = ExteriorWallSizesDraft(remainder, draft, startIndex);
    }
    return draft;
}

Сколько я ни силился, не смог понять принципа распределения панелей разной длины, поэтому после преобразования массива с количеством в массив с длинами, он перемешивается по алгоритму Фишера–Йетса. Получается вполне сносный результат.

Процедурный генератор хрущёвок

▣ Проектируем фасад

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

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

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

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

Код генератора фасадов

Для указания типа панели я использую перечисление, выглядит оно следующим образом:

public enum PanelType
{
    Wall,
    Window,
    Balcony,
    Entrance,
    EntranceWall,
    EntranceWallLast,
    Socle,
    Attic,
};

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

List<List<PanelType>> FacadePattern(int panelCount, int floorCount, bool haveAttic=false, bool longFacade=false, int entrancesCount=0)
{
    var panelPattern = new List<List<PanelType>>();
    var entranceIndex = panelCount / (entrances + 1);
    var entranceCount = 1;

    for (var i = 0; i < floorCount+1; i++)
    {
        panelPattern.Add(new List<PanelType>());
        for (var j = 0; j < panelCount; j++)
        {
            if (i == 0)
            {
                if (entrancesCount > 0 && j == entranceIndex && entranceCount <= entrances)
                {
                    panelPattern[0].Add(PanelType.Entrance);
                    entranceCount++;
                    entranceIndex = panelCount*entranceCount/(entrances + 1);
                }
                else
                {
                    panelPattern[0].Add(PanelType.Socle);
                }
            }
            else if (i == 1)
            {
                if (panelPattern[0][j] == PanelType.Entrance)
                {
                    panelPattern[1].Add(PanelType.EntranceWall);
                }
                else if (longFacade)
                {
                    panelPattern[1].Add(PanelType.Window);
                }
                else
                {
                    panelPattern[1].Add(PanelType.Wall);
                }
            }
            else
            {
                panelPattern[i].Add(panelPattern[i - 1][j]);
            }
            if (i == floorCount)
            {
                if (panelPattern[i - 1][j] == PanelType.Entrance || panelPattern[i - 1][j] == PanelType.EntranceWall)
                {
                    panelPattern[i][j] = PanelType.EntranceWallLast;
                }
            }
        }
        if (i == 1 && !longFacade)
        {
            for (int j = 0; j <= panelPattern[1].Count / 2; j++)
            {
                if (j != 0 && j != panelCount - 1 && Random.value > 0.5f)
                {
                    panelPattern[1][j] = PanelType.Window;
                    panelPattern[1][panelPattern[1].Count - 1 - j] = PanelType.Window;
                }
            }
        }
        if (i == 2)
        {
            for (int j = 0; j <= panelPattern[2].Count/2; j++)
            {
                if (panelPattern[2][j] == PanelType.Window && panelPattern[2][panelPattern[2].Count - 1 - j] == PanelType.Window && Random.value > 0.5f)
                {
                    panelPattern[2][j] = PanelType.Balcony;
                    panelPattern[2][panelPattern[2].Count - 1 - j] = PanelType.Balcony;
                }
            }
        }
    }
    if (haveAttic)
    {
        panelPattern.Add(new List<PanelType>());
        for (var j = 0; j < panelCount; j++)
        {
            panelPattern[panelPattern.Count-1].Add(PanelType.Attic);
        }
    }
    return panelPattern;
}

Процедурный генератор хрущёвок

▣ Крышуем хрущёвку

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

Для крыши я сделал модели с шириной и длиной один метр, а потом просто растягивал их как нужно.

Выбор крыши

switch (roofType)
{
    case RoofType.Flat:
        combine.Add(RandomItem(roofFlat));
        matrices.Add(Matrix4x4.TRS(roofHeight, Quaternion.identity, new Vector3(length, 1, width)));
        break;
    case RoofType.FlatOverhang:
        combine.Add(RandomItem(roofFlat));
        matrices.Add(Matrix4x4.TRS(roofHeight, Quaternion.identity, new Vector3(length + 1, 1, width + 1)));
        break;
    case RoofType.Gabled:
        combine.Add(RandomItem(roofGabled));
        matrices.Add(Matrix4x4.TRS(roofHeight, Quaternion.identity, new Vector3(length, 1, width + 1)));
        break;
    case RoofType.Hipped:
        combine.Add(RandomItem(roofHipped));
        matrices.Add(Matrix4x4.TRS(roofHeight, Quaternion.identity, new Vector3(length + 1, 1, width + 1)));
        break;
}

Вот и всё. Хрущёвка готова.

Процедурный генератор хрущёвок

▣ Заключение

У описанного подхода есть одно узкое место. CombineMeshes мало того, что работает медленно, так у него ещё есть ограничение на количество вершин и треугольников для объединения. Если вы вдруг как я решили сделать хрущёвку-небоскрёб, то число вершин быстро превысит 65 тысяч, и получатся руины как на картинке ниже. Чтобы этого не случалось, нужно писать собственную функцию склейки моделей.

Процедурный генератор хрущёвок

Исходники проекта и бинарники для разных платформ можете скачать по ссылкам ниже.

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

Левая кнопка мыши — новое здание, Esc — Выход.

P. S. Буду рад, если кто-нибудь поможет с доработкой моделек, из меня моделлер плохой.

Автор: BasmanovDaniil

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js