Это вторая статья из цикла о процедурно генерируемых с помощью Unity и C# картах мира. Цикл будет состоять из четырех статей.

Содержание

Часть 1:

Введение
Генерирование шума
Начало работы
Генерирование карты высот

Часть 2 (эта статья):

Свертывание карты на одной оси
Свертывание карты на обеих осях
Поиск соседних элементов
Битовые маски
Заливка

Часть 3:

Генерирование тепловой карты
Генерирование карты влажности
Генерирование рек

Часть 4:

Генерирование биомов
Генерирование сферических карт

Свертывание карты по одной оси

(От переводчика: я не уверен, что wrapping в контексте математической терминологии переводится как «свертывание». Если кто-то знает более подходящий термин, напишите, исправлю.)

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

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

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



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

Чтобы сделать это, необходимо изменить функцию GetData в классе Generator.

private void GetData(ImplicitModuleBase module, ref MapData mapData)
{
    mapData = new MapData (Width, Height);
 
    // циклично проходим по каждой точке x,y - получаем значение высоты
    for (var x = 0; x < Width; x++) {
        for (var y = 0; y < Height; y++) {
 
            //Пределы шума
            float x1 = 0, x2 = 1;
            float y1 = 0, y2 = 1;               
            float dx = x2 - x1;
            float dy = y2 - y1;
 
            //Сэмплируем шум с небольшими интервалами
            float s = x / (float)Width;
            float t = y / (float)Height;
 
            // Вычисляем трехмерные координаты
            float nx = x1 + Mathf.Cos (s * 2 * Mathf.PI) * dx / (2 * Mathf.PI);
            float ny = x1 + Mathf.Sin (s * 2 * Mathf.PI) * dx / (2 * Mathf.PI);
            float nz = t;
 
            float heightValue = (float)HeightMap.Get (nx, ny, nz);
 
            // отслеживаем максимальные и минимальные найденные значения
            if (heightValue > mapData.Max)
                mapData.Max = heightValue;
            if (heightValue < mapData.Min)
                mapData.Min = heightValue;
 
            mapData.Data [x, y] = heightValue;
        }
    }
}

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



Свертывание карты на обеих осях

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

Вместо одного цилиндра у нас будут два цилиндра, соединенных в четырехмерном пространстве.

Следует учесть, что создание четырехмерных данных занимает гораздо больше времени, чем двухмерных.

Обновленная функция GetData() будет выглядеть следующим образом:

private void GetData(ImplicitModuleBase module, ref MapData mapData)
{
    mapData = new MapData (Width, Height);
 
    // циклично проходим по каждой точке x,y - получаем значение высоты
    for (var x = 0; x < Width; x++) {
        for (var y = 0; y < Height; y++) {
 
            // Пределы шума
            float x1 = 0, x2 = 2;
            float y1 = 0, y2 = 2;               
            float dx = x2 - x1;
            float dy = y2 - y1;
 
            // Сэмплируем шум с небольшими интервалами
            float s = x / (float)Width;
            float t = y / (float)Height;
         
            // Вычисляем четырехмерные координаты
            float nx = x1 + Mathf.Cos (s*2*Mathf.PI) * dx/(2*Mathf.PI);
            float ny = y1 + Mathf.Cos (t*2*Mathf.PI) * dy/(2*Mathf.PI);
            float nz = x1 + Mathf.Sin (s*2*Mathf.PI) * dx/(2*Mathf.PI);
            float nw = y1 + Mathf.Sin (t*2*Mathf.PI) * dy/(2*Mathf.PI);
         
            float heightValue = (float)HeightMap.Get (nx, ny, nz, nw);
             
            // отслеживаем максимальные и минимальные найденные значения
            if (heightValue > mapData.Max) mapData.Max = heightValue;
            if (heightValue < mapData.Min) mapData.Min = heightValue;
 
            mapData.Data[x,y] = heightValue;
        }
    }
}

Этот код создает бесшовную текстуру, процедурно сгенерированную из четырехмерного шума.



Если вы хотите узнать больше о том, как это работает, изучите эту и эту статьи.

Поиск соседних элементов

Теперь у нас есть бесшовная карта высот, и мы начинаем приближаться к нашей цели. Сейчас мы сконцентрируемся на классе Tile.

Было бы очень полезно, если бы каждый объект Tile имел указатель на каждый из соседних объектов (верхний, нижний, правый и левый). Это удобно для решения таких задач, как создание путей, битовых масок и заливки. Позже мы рассмотрим эти аспекты в статье.

Сначала нам нужно создать переменные в классе Tile:

public Tile Left;
public Tile Right;
public Tile Top;
public Tile Bottom;

Следующая часть довольно проста. Мы проходим по каждому тайлу, получая соседние к нему тайлы. Сначала мы создадим несколько функций внутри класса Generator, чтобы упростить получение соседей объекта Tile.

private Tile GetTop(Tile t)
{
    return Tiles [t.X, MathHelper.Mod (t.Y - 1, Height)];
}
private Tile GetBottom(Tile t)
{
    return Tiles [t.X, MathHelper.Mod (t.Y + 1, Height)];
}
private Tile GetLeft(Tile t)
{
    return Tiles [MathHelper.Mod(t.X - 1, Width), t.Y];
}
private Tile GetRight(Tile t)
{
    return Tiles [MathHelper.Mod (t.X + 1, Width), t.Y];
}

MathHelper.Mod() сворачивает значения x и y на основании ширины и высоты карты. Таким образом мы никогда не выйдем за пределы карты.

Затем нам нужно создать функцию, назначающую соседей.

private void UpdateNeighbors()
{
    for (var x = 0; x < Width; x++)
    {
        for (var y = 0; y < Height; y++)
        {
            Tile t = Tiles[x,y];
             
            t.Top = GetTop(t);
            t.Bottom = GetBottom (t);
            t.Left = GetLeft (t);
            t.Right = GetRight (t);
        }
    }
}

Визуально она пока делает не так уж много. Однако теперь каждый объект Tile «знает» своих соседей, что очень важно для дальнейших шагов.

Битовые маски

Я решил добавить эту часть в статью в основном из эстетических соображений. Создание битовой маски в данном контексте — это установка значения каждого тайла на основании значений его соседей. Взгляните на эту иллюстрацию:



На основании данных соседей тайла мы увеличивает битовую маску, как показано слева на иллюстрации. Все варианты показаны в правой части. Заметьте, что все значения уникальны. Это позволяет очень быстро определить конфигурацию блока.

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

Еще одно удобство битовой маски в том, что если значение битовой маски тайла не равно 15, мы знаем, что он не является крайним тайлом карты.

Добавим функцию в класс Tile для выполнения вычислений. Мы берем в расчет только тех соседей, которые имеют тот же тип высоты, что и анализируемый тайл.

public void UpdateBitmask()
{
    int count = 0;
     
    if (Top.HeightType == HeightType)
        count += 1;
    if (Right.HeightType == HeightType)
        count += 2;
    if (Bottom.HeightType == HeightType)
        count += 4;
    if (Left.HeightType == HeightType)
        count += 8;
     
    Bitmask = count;
}

Поскольку мы уже имеем указатели на соседние тайлы, а также назначили тип высоты (HeightType), этот расчет довольно тривиален. Сейчас мы добавим функцию в класс Generator для выполнения этого расчета для всех тайлов:

private void UpdateBitmasks()
{
    for (var x = 0; x < Width; x++) {
        for (var y = 0; y < Height; y++) {
            Tiles [x, y].UpdateBitmask ();
        }
    }
}

Теперь если мы изменим наш TextureGenerator следующим образом:

//затемняем цвет граничного тайла
if (tiles[x,y].Bitmask != 15)
    pixels[x + y * width] = Color.Lerp(pixels[x + y * width], Color.black, 0.4f);

Мы увидим четкую границу между типами высот:



Заливка

Было бы здорово определиться со следующими вопросами:

• где озера?
• где океаны?
• где массивы суши?
• какого размера каждый из них?

Мы можем ответить на этот вопрос с помощью простого алгоритма заливки.

Сначала мы создадим объект, в котором будет храниться информация о наших тайлах:

using UnityEngine;
using System.Collections.Generic;
 
public enum TileGroupType
{
    Water, 
    Land
}
 
public class TileGroup  {
     
    public TileGroupType Type;
    public List<Tile> Tiles;
 
    public TileGroup()
    {
        Tiles = new List<Tile> ();
    }
}

Класс TileGroup будет хранить указатель на список тайлов. Также он будет сообщать нам, является ли конкретная группа водой или сушей.

Принцип состоит в разбиении соединенных частей суши и воды на коллекции TileGroup.

Также мы немного изменим класс Tile, добавив две новые переменные:

public bool Collidable;
public bool FloodFilled;

Collidable устанавливается в методе LoadTiles(). Все, что не является водным тайлом, будет присваивать значение «истина» переменной Collidable. Переменная FloodFilled служит для отслеживания тайлов, уже обработанных алгоритмом заливки.

Для добавления алгоритма заливки в класс Generator сначала нужна пара переменных TileGroup:

List<TileGroup> Waters = new List<TileGroup> ();
List<TileGroup> Lands = new List<TileGroup> ();

Теперь мы готовы обозначить массивы суши и воды на нашей карте.

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

private void FloodFill()
{
    // Используем стек вместо рекурсии
    Stack<Tile> stack = new Stack<Tile>();
     
    for (int x = 0; x < Width; x++) {
        for (int y = 0; y < Height; y++) {
             
            Tile t = Tiles[x,y];
 
            //Тайл уже залит, пропускаем его
            if (t.FloodFilled) continue;
 
            // Суша
            if (t.Collidable)   
            {
                TileGroup group = new TileGroup();
                group.Type = TileGroupType.Land;
                stack.Push(t);
                 
                while(stack.Count > 0) {
                    FloodFill(stack.Pop(), ref group, ref stack);
                }
                 
                if (group.Tiles.Count > 0)
                    Lands.Add (group);
            }
            // Вода
            else {              
                TileGroup group = new TileGroup();
                group.Type = TileGroupType.Water;
                stack.Push(t);
                 
                while(stack.Count > 0)   {
                    FloodFill(stack.Pop(), ref group, ref stack);
                }
                 
                if (group.Tiles.Count > 0)
                    Waters.Add (group);
            }
        }
    }
}
 
 
private void FloodFill(Tile tile, ref TileGroup tiles, ref Stack<Tile> stack)
{
    // Валидация
    if (tile.FloodFilled) 
        return;
    if (tiles.Type == TileGroupType.Land && !tile.Collidable)
        return;
    if (tiles.Type == TileGroupType.Water && tile.Collidable)
        return;
 
    // Добавление в TileGroup
    tiles.Tiles.Add (tile);
    tile.FloodFilled = true;
 
    // заливка соседей
    Tile t = GetTop (tile);
    if (!t.FloodFilled && tile.Collidable == t.Collidable)
        stack.Push (t);
    t = GetBottom (tile);
    if (!t.FloodFilled && tile.Collidable == t.Collidable)
        stack.Push (t);
    t = GetLeft (tile);
    if (!t.FloodFilled && tile.Collidable == t.Collidable)
        stack.Push (t);
    t = GetRight (tile);
    if (!t.FloodFilled && tile.Collidable == t.Collidable)
        stack.Push (t);
}

С помощью вышеприведенного кода мы разделяем массивы суши и воды, и помещаем их в TileGroups

Я сгенерировал пару текстур, чтобы показать, как полезны могут быть эти данные.



На левом изображении все тайлы суши залиты черным. Тайлы океана синие, а тайлы озер голубые.

На правом изображении все тайлы воды синие. Большие массивы суши имеют темно-зеленый цвет, а острова — светло-зеленый.

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

Исходники кода второй части вы можете скачать с github: World Generator Part 2.

Третья часть.