Процедурная генерация используется для повышения вариабельности игр. Среди известных проектов можно упомянуть Minecraft, Enter the Gungeon и Descenders. В этом посте я объясню некоторые из алгоритмов, которые можно применять при работе с системой Tilemap, появившейся как 2D-функция в Unity 2017.2, и с RuleTile.

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

О чём этот пост?


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


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

Прежде чем читать дальше, неплохо будет знать следующее:

  1. Мы отличаем, что является тайлом, а что нет, при помощи двоичных значений. 1 — это тайл, 0 — его отсутствие.
  2. Мы будем хранить все карты в двухмерном целочисленном массиве, возвращаемом пользователю в конце каждой функции (за исключением той, где выполняется рендеринг).
  3. Я буду использовать функцию массива GetUpperBound() для получения высоты и ширины каждой карты, чтобы на функция получала меньше переменных, а код был более чистым.
  4. Я часто использую Mathf.FloorToInt(), потому что система координат Tilemap начинается с левого нижнего угла, а Mathf.FloorToInt() позволяет округлять числа до целого.
  5. Весь код в этом посте написан на C#.

Генерация массива


GenerateArray создаёт новый массив int заданного размера. Также мы можем указать, должен ли массив быть заполненным или пустым (1 или 0). Вот код:

public static int[,] GenerateArray(int width, int height, bool empty)
{
    int[,] map = new int[width, height];
    for (int x = 0; x < map.GetUpperBound(0); x++)
    {
        for (int y = 0; y < map.GetUpperBound(1); y++)
        {
            if (empty)
            {
                map[x, y] = 0;
            }
            else
            {
                map[x, y] = 1;
            }
        }
    }
    return map;
}

Рендеринг карты


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

public static void RenderMap(int[,] map, Tilemap tilemap, TileBase tile)
{
    //Clear the map (ensures we dont overlap)
    tilemap.ClearAllTiles(); 
    //Loop through the width of the map
    for (int x = 0; x < map.GetUpperBound(0) ; x++) 
    {
        //Loop through the height of the map
        for (int y = 0; y < map.GetUpperBound(1); y++) 
        {
            // 1 = tile, 0 = no tile
            if (map[x, y] == 1) 
            {
                tilemap.SetTile(new Vector3Int(x, y, 0), tile); 
            }
        }
    }
}

Обновление карты


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

public static void UpdateMap(int[,] map, Tilemap tilemap) //Takes in our map and tilemap, setting null tiles where needed
{
    for (int x = 0; x < map.GetUpperBound(0); x++)
    {
        for (int y = 0; y < map.GetUpperBound(1); y++)
        {
            //We are only going to update the map, rather than rendering again
            //This is because it uses less resources to update tiles to null
            //As opposed to re-drawing every single tile (and collision data)
            if (map[x, y] == 0)
            {
                tilemap.SetTile(new Vector3Int(x, y, 0), null);
            }
        }
    }
}

Шум Перлина


Шум Перлина можно использовать в различных целях. Во-первых, мы можем применить его для создания верхнего слоя нашей карты. Для этого достаточно просто получить новую точку при помощи текущей позиции x и seed.

Простое решение


Этот способ генерации использует в генерации уровней простейшую форму реализации шума Перлина. Мы можем взять функцию Unity для шума Перлина, чтобы не писать код самим. Также мы будем использовать для тайловой карты только целые числа, воспользовавшись функцией Mathf.FloorToInt().

public static int[,] PerlinNoise(int[,] map, float seed)
{
    int newPoint;
    //Used to reduced the position of the Perlin point
    float reduction = 0.5f;
    //Create the Perlin
    for (int x = 0; x < map.GetUpperBound(0); x++)
    {
        newPoint = Mathf.FloorToInt((Mathf.PerlinNoise(x, seed) - reduction) * map.GetUpperBound(1));

        //Make sure the noise starts near the halfway point of the height
        newPoint += (map.GetUpperBound(1) / 2); 
        for (int y = newPoint; y >= 0; y--)
        {
            map[x, y] = 1;
        }
    }
    return map;
}

Вот как это выглядит после рендеринга в тайловую карту:


Сглаживание


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

public static int[,] PerlinNoiseSmooth(int[,] map, float seed, int interval)
{
    //Smooth the noise and store it in the int array
    if (interval > 1)
    {
        int newPoint, points;
        //Used to reduced the position of the Perlin point
        float reduction = 0.5f;

        //Used in the smoothing process
        Vector2Int currentPos, lastPos; 
        //The corresponding points of the smoothing. One list for x and one for y
        List<int> noiseX = new List<int>();
        List<int> noiseY = new List<int>();

        //Generate the noise
        for (int x = 0; x < map.GetUpperBound(0); x += interval)
        {
            newPoint = Mathf.FloorToInt((Mathf.PerlinNoise(x, (seed * reduction))) * map.GetUpperBound(1));
            noiseY.Add(newPoint);
            noiseX.Add(x);
        }

        points = noiseY.Count;

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

//Start at 1 so we have a previous position already
            for (int i = 1; i < points; i++) 
            {
                //Get the current position
                currentPos = new Vector2Int(noiseX[i], noiseY[i]);
                //Also get the last position
                lastPos = new Vector2Int(noiseX[i - 1], noiseY[i - 1]);

                //Find the difference between the two
                Vector2 diff = currentPos - lastPos;

                //Set up what the height change value will be 
                float heightChange = diff.y / interval;
                //Determine the current height
                float currHeight = lastPos.y;

                //Work our way through from the last x to the current x
                for (int x = lastPos.x; x < currentPos.x; x++)
                {
                    for (int y = Mathf.FloorToInt(currHeight); y > 0; y--)
                    {
                        map[x, y] = 1;
                    }
                    currHeight += heightChange;
                }
            }
        }

Сглаживание выполняется следующим образом:

  1. Получаем текущую и последнюю позиции
  2. Получаем разность между двумя точками, самая важная информация, которая нам нужна — это разность по оси y
  3. Затем мы определяем, насколько нужно выполнить изменение, чтобы попасть в точку, это выполняется делением разности по y на переменную интервала.
  4. Далее мы начинаем задавать позиции, проходя весь путь до нуля
  5. Когда мы дошли до 0 по оси y, добавляем изменение высоты к текущей высоте и повторяем процесс для следующей позиции по x
  6. Завершив с каждой позицией между последней и текущей позициями, мы переходим к следующей точке

Если интервал меньше единицы, то мы просто используем предыдущую функцию, которая выполнит за нас всю работу.

 else
        {
            //Defaults to a normal Perlin gen
            map = PerlinNoise(map, seed);
        }

        return map;

Давайте взглянем, как выглядит рендер:


Random Walk


Random Walk Top


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

public static int[,] RandomWalkTop(int[,] map, float seed)
{
    //Seed our random
    System.Random rand = new System.Random(seed.GetHashCode()); 

    //Set our starting height
    int lastHeight = Random.Range(0, map.GetUpperBound(1));
        
    //Cycle through our width
    for (int x = 0; x < map.GetUpperBound(0); x++) 
    {
        //Flip a coin
        int nextMove = rand.Next(2);

        //If heads, and we aren't near the bottom, minus some height
        if (nextMove == 0 && lastHeight > 2) 
        {
            lastHeight--;
        }
        //If tails, and we aren't near the top, add some height
        else if (nextMove == 1 && lastHeight < map.GetUpperBound(1) - 2) 
        {
            lastHeight++;
        }

        //Circle through from the lastheight to the bottom
        for (int y = lastHeight; y >= 0; y--) 
        {
            map[x, y] = 1;
        }
    }
    //Return the map
    return map; 
}


Random Walk Top со сглаживанием

Такая генерация даёт нам более плавные высоты по сравнению с генерацией шумом Перлина.

Эта разновидность Random Walk обеспечивает гораздо более плавный результат по сравнению с предыдущей версией. Мы можем реализовать её, добавив в функцию ещё две переменные:

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

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

public static int[,] RandomWalkTopSmoothed(int[,] map, float seed, int minSectionWidth)
{
    //Seed our random
    System.Random rand = new System.Random(seed.GetHashCode());

    //Determine the start position
    int lastHeight = Random.Range(0, map.GetUpperBound(1));

    //Used to determine which direction to go
    int nextMove = 0;
    //Used to keep track of the current sections width
    int sectionWidth = 0;

    //Work through the array width
    for (int x = 0; x <= map.GetUpperBound(0); x++)
    {
        //Determine the next move
        nextMove = rand.Next(2);

        //Only change the height if we have used the current height more than the minimum required section width
        if (nextMove == 0 && lastHeight > 0 && sectionWidth > minSectionWidth)
        {
            lastHeight--;
            sectionWidth = 0;
        }
        else if (nextMove == 1 && lastHeight < map.GetUpperBound(1) && sectionWidth > minSectionWidth)
        {
            lastHeight++;
            sectionWidth = 0;
        }
        //Increment the section width
        sectionWidth++;

        //Work our way from the height down to 0
        for (int y = lastHeight; y >= 0; y--)
        {
            map[x, y] = 1;
        }
    }

    //Return the modified map
    return map;
}

Как видно в показанном ниже gif, сглаживание алгоритма random walk позволяет получать на уровне красивые плоские сегменты.


Заключение


Надеюсь, эта статья вдохновит вас на использование процедурной генерации в своих проектах. Если вы хотите больше узнать о процедурно генерируемых картах, то изучите отличные ресурсы Procedural Generation Wiki или Roguebasin.com.

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

Часть 2


Всё, что мы будем обсуждать в этой части, можно найти в этом проекте. Можете скачать ассеты и попробовать свои собственные процедурные алгоритмы.


Шум Перлина


В предыдущей части мы рассматривали способы применения шума Перлина для создания верхних слоёв. К счастью, шум Перлина также можно использовать для создания пещеры. Это реализуется благодаря вычислению нового значения шума Перлина, которое получает параметры текущей позиции, умноженные на модификатор. Модификатор — это значение от 0 до 1. Чем больше значение модификатора, тем хаотичнее генерация Перлина. Затем мы округляем это значение до целого (0 или 1), которое сохраняем в массив карты. Посмотрите, как это реализуется:

public static int[,] PerlinNoiseCave(int[,] map, float modifier, bool edgesAreWalls)
{
	int newPoint;
	for (int x = 0; x < map.GetUpperBound(0); x++)
	{
		for (int y = 0; y < map.GetUpperBound(1); y++)
		{

			if (edgesAreWalls && (x == 0 || y == 0 || x == map.GetUpperBound(0) - 1 || y == map.GetUpperBound(1) - 1))
			{
				map[x, y] = 1; //Keep the edges as walls
			}
			else
			{
				//Generate a new point using Perlin noise, then round it to a value of either 0 or 1
				newPoint = Mathf.RoundToInt(Mathf.PerlinNoise(x * modifier, y * modifier));
				map[x, y] = newPoint;
			}
		}
	}
	return map;
}

Мы используем вместо seed модификатор потому, что результаты генерации Перлина выглядят лучше при умножении на число от 0 до 0.5. Чем ниже значение, тем более блочным будет результат. Взгляните на примеры результатов. Gif начинается со значения модификатора 0.01 и инкрементно доходит до значения 0.25.


Из этого gif видно, что генерация Перлина с каждым инкрементом просто увеличивает паттерн.

Random Walk


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

public static int[,] RandomWalkCave(int[,] map, float seed,  int requiredFloorPercent)
{
    //Seed our random
    System.Random rand = new System.Random(seed.GetHashCode());

    //Define our start x position
    int floorX = rand.Next(1, map.GetUpperBound(0) - 1);
    //Define our start y position
    int floorY = rand.Next(1, map.GetUpperBound(1) - 1);
    //Determine our required floorAmount
    int reqFloorAmount = ((map.GetUpperBound(1) * map.GetUpperBound(0)) * requiredFloorPercent) / 100; 
    //Used for our while loop, when this reaches our reqFloorAmount we will stop tunneling
    int floorCount = 0;

    //Set our start position to not be a tile (0 = no tile, 1 = tile)
    map[floorX, floorY] = 0;
    //Increase our floor count
    floorCount++;

Функция начинается со следующего:

  1. Находим начальную позицию
  2. Вычисляем количество тайлов пола, которые нужно удалить
  3. Удаляем тайл в начальной позиции
  4. Добавляем единицу к количеству тайлов

Затем мы переходим к циклу while. Он создаст пещеру:

while (floorCount < reqFloorAmount)
    { 
        //Determine our next direction
        int randDir = rand.Next(4); 

        switch (randDir)
        {
            //Up
            case 0: 
                //Ensure that the edges are still tiles
                if ((floorY + 1) < map.GetUpperBound(1) - 1) 
                {
                    //Move the y up one
                    floorY++;

                    //Check if that piece is currently still a tile
                    if (map[floorX, floorY] == 1) 
                    {
                        //Change it to not a tile
                        map[floorX, floorY] = 0;
                        //Increase floor count
                        floorCount++; 
                    }
                }
                break;
            //Down
            case 1: 
                //Ensure that the edges are still tiles
                if ((floorY - 1) > 1)
                { 
                    //Move the y down one
                    floorY--;
                    //Check if that piece is currently still a tile
                    if (map[floorX, floorY] == 1) 
                    {
                        //Change it to not a tile
                        map[floorX, floorY] = 0;
                        //Increase the floor count
                        floorCount++; 
                    }
                }
                break;
            //Right
            case 2: 
                //Ensure that the edges are still tiles
                if ((floorX + 1) < map.GetUpperBound(0) - 1)
                {
                    //Move the x to the right
                    floorX++;
                    //Check if that piece is currently still a tile
                    if (map[floorX, floorY] == 1) 
                    {
                        //Change it to not a tile
                        map[floorX, floorY] = 0;
                        //Increase the floor count
                        floorCount++; 
                    }
                }
                break;
            //Left
            case 3: 
                //Ensure that the edges are still tiles
                if ((floorX - 1) > 1)
                {
                    //Move the x to the left
                    floorX--;
                    //Check if that piece is currently still a tile
                    if (map[floorX, floorY] == 1) 
                    {
                        //Change it to not a tile
                        map[floorX, floorY] = 0;
                        //Increase the floor count
                        floorCount++; 
                    }
                }
                break;
        }
    }
    //Return the updated map
    return map; 
}

Что же мы здесь делаем?


Ну, во-первых, при помощи случайного числа мы выбираем, в каком направлении двигаться. Затем мы проверяем новое направление при помощи оператора switch case. В этом операторе мы проверяем, является ли позиция стеной. Если нет, то удаляем из массива элемент с тайлом. Продолжаем это делать, пока не достигнем нужной площади пола. Результат показан ниже:


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

Направленный туннель


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

public static int[,] DirectionalTunnel(int[,] map, int minPathWidth, int maxPathWidth, int maxPathChange, int roughness, int curvyness)
{
    //This value goes from its minus counterpart to its positive value, in this case with a width value of 1, the width of the tunnel is 3
    int tunnelWidth = 1; 
    //Set the start X position to the center of the tunnel
    int x = map.GetUpperBound(0) / 2; 

    //Set up our random with the seed
    System.Random rand = new System.Random(Time.time.GetHashCode()); 

    //Create the first part of the tunnel
    for (int i = -tunnelWidth; i <= tunnelWidth; i++) 
    {
        map[x + i, 0] = 0;
    }

Что происходит?


Сначала мы задаём значение ширины. Значение ширины будет идти от значения с минусом до положительного. Благодаря этому мы получим нужный нам размер. В данном случаем мы используем значение 1, что, в свою очедедь даст нам общую ширину 3, потому что мы используем значения -1, 0, 1.

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


Теперь давайте займёмся созданием остальной части карты.

    //Cycle through the array
    for (int y = 1; y < map.GetUpperBound(1); y++) 
    {
        //Check if we can change the roughness
        if (rand.Next(0, 100) > roughness) 
        {
            //Get the amount we will change for the width
            int widthChange = Random.Range(-maxPathWidth, maxPathWidth); 
            //Add it to our tunnel width value
            tunnelWidth += widthChange;
            //Check to see we arent making the path too small
            if (tunnelWidth < minPathWidth) 
            {
                tunnelWidth = minPathWidth;
            }
            //Check that the path width isnt over our maximum
            if (tunnelWidth > maxPathWidth) 
            {
                tunnelWidth = maxPathWidth;
            }
        }

        //Check if we can change the curve
        if (rand.Next(0, 100) > curvyness) 
        {
            //Get the amount we will change for the x position
            int xChange = Random.Range(-maxPathChange, maxPathChange); 
            //Add it to our x value
            x += xChange;
            //Check we arent too close to the left side of the map
            if (x < maxPathWidth) 
            {
                x = maxPathWidth;
            }
            //Check we arent too close to the right side of the map
            if (x > (map.GetUpperBound(0) - maxPathWidth)) 
            {
                x = map.GetUpperBound(0) - maxPathWidth;
            }
        }

        //Work through the width of the tunnel
        for (int i = -tunnelWidth; i <= tunnelWidth; i++) 
        {
            map[x + i, y] = 0;
        }
    }
    return map;
}

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

  1. Генерируем новое случайное число, сравниваемое с значением кривизны. Как и в предыдущей проверке, если оно больше значения, то мы меняем центральную точку пути. Также мы выполняем проверку, чтобы не выйти за пределы карты.
  2. Наконец, мы прокладываем туннель в только что созданной части.

Результаты этой реализации выглядят так:


Клеточные автоматы


Клеточные автоматы используют соседние ячейки, чтобы определить, включена (1) или выключена (0) текущая ячейка. Основа для определения соседних ячеек создаётся на основе случайно сгенерированной сетки ячеек. Мы будем генерировать эту исходную сетку при помощи функции Random.Next языка C#.

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

public static int[,] GenerateCellularAutomata(int width, int height, float seed, int fillPercent, bool edgesAreWalls)
{
    //Seed our random number generator
    System.Random rand = new System.Random(seed.GetHashCode());

    //Initialise the map
    int[,] map = new int[width, height];

    for (int x = 0; x < map.GetUpperBound(0); x++)
    {
        for (int y = 0; y < map.GetUpperBound(1); y++)
        {
            //If we have the edges set to be walls, ensure the cell is set to on (1)
            if (edgesAreWalls && (x == 0 || x == map.GetUpperBound(0) - 1 || y == 0 || y == map.GetUpperBound(1) - 1))
            {
                map[x, y] = 1;
            }
            else
            {
                //Randomly generate the grid
                map[x, y] = (rand.Next(0, 100) < fillPercent) ? 1 : 0; 
            }
        }
    }
    return map;
}

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


Окрестность Мура


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


К окрестности применяются следующие правила:

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

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

static int GetMooreSurroundingTiles(int[,] map, int x, int y, bool edgesAreWalls)
{
    /* Moore Neighbourhood looks like this ('T' is our tile, 'N' is our neighbours)
     * 
     * N N N
     * N T N
     * N N N
     * 
     */

    int tileCount = 0;       
    
    for(int neighbourX = x - 1; neighbourX <= x + 1; neighbourX++)
    {
        for(int neighbourY = y - 1; neighbourY <= y + 1; neighbourY++)
        {
            if (neighbourX >= 0 && neighbourX < map.GetUpperBound(0) && neighbourY >= 0 && neighbourY < map.GetUpperBound(1))
            {
                //We don't want to count the tile we are checking the surroundings of
                if(neighbourX != x || neighbourY != y) 
                {
                    tileCount += map[neighbourX, neighbourY];
                }
            }
        }
    }
    return tileCount;
}

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

public static int[,] SmoothMooreCellularAutomata(int[,] map, bool edgesAreWalls, int smoothCount)
{
	for (int i = 0; i < smoothCount; i++)
	{
		for (int x = 0; x < map.GetUpperBound(0); x++)
		{
			for (int y = 0; y < map.GetUpperBound(1); y++)
			{
				int surroundingTiles = GetMooreSurroundingTiles(map, x, y, edgesAreWalls);

				if (edgesAreWalls && (x == 0 || x == (map.GetUpperBound(0) - 1) || y == 0 || y == (map.GetUpperBound(1) - 1)))
				{
                    //Set the edge to be a wall if we have edgesAreWalls to be true
					map[x, y] = 1; 
				}
                //The default moore rule requires more than 4 neighbours
				else if (surroundingTiles > 4)
				{
					map[x, y] = 1;
				}
				else if (surroundingTiles < 4)
				{
					map[x, y] = 0;
				}
			}
		}
	}
    //Return the modified map
    return map;
}

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


Мы всегда можем модифицировать этот алгоритм, соединяя комнаты, если, например, между ними всего два блока.

Окрестность фон Неймана


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


К окрестности применяются следующие правила:

  • Проверяем непосредственных соседей тайла, не учитывая диагональные.
  • Если ячейка активна, прибавляем к количеству единицу.
  • Если ячейка неактивна, то ничего не делаем.
  • Если у ячейки больше 2 соседей, то делаем текущую ячейку активной.
  • Если у ячейки меньше 2 соседей, то делаем текущую ячейку неактивной.
  • Если соседей ровно 2, то не изменяем текущую ячейку.

Второй результат использует те же принципы, что и первый, но расширяет площадь окрестности.

Мы проверяем соседей при помощи следующей функции:

static int GetVNSurroundingTiles(int[,] map, int x, int y, bool edgesAreWalls)
{
	/* von Neumann Neighbourhood looks like this ('T' is our Tile, 'N' is our Neighbour)
	* 
	*   N 
	* N T N
	*   N
	*   
    */
     
	int tileCount = 0;

    //Keep the edges as walls
    if(edgesAreWalls && (x - 1 == 0 || x + 1 == map.GetUpperBound(0) || y - 1 == 0 || y + 1 == map.GetUpperBound(1)))
    {
        tileCount++;
    }

    //Ensure we aren't touching the left side of the map
	if(x - 1 > 0)
	{
		tileCount += map[x - 1, y];
	}

    //Ensure we aren't touching the bottom of the map
	if(y - 1 > 0)
	{
		tileCount += map[x, y - 1];
	}

    //Ensure we aren't touching the right side of the map
	if(x + 1 < map.GetUpperBound(0)) 
	{
		tileCount += map[x + 1, y];
	}

    //Ensure we aren't touching the top of the map
	if(y + 1 < map.GetUpperBound(1)) 
	{
		tileCount += map[x, y + 1];
	}

	return tileCount;
}

Получив количество соседей, можно перейти к сглаживанию массива. Как и раньше, нам нужен цикл for для выполнения переданного на вход количества итераций сглаживания.

public static int[,] SmoothVNCellularAutomata(int[,] map, bool edgesAreWalls, int smoothCount)
{
	for (int i = 0; i < smoothCount; i++)
	{
		for (int x = 0; x < map.GetUpperBound(0); x++)
		{
			for (int y = 0; y < map.GetUpperBound(1); y++)
			{
				//Get the surrounding tiles
				int surroundingTiles = GetVNSurroundingTiles(map, x, y, edgesAreWalls);

				if (edgesAreWalls && (x == 0 || x == map.GetUpperBound(0) - 1 || y == 0 || y == map.GetUpperBound(1)))
				{
                    //Keep our edges as walls
					map[x, y] = 1; 
				}
                //von Neuemann Neighbourhood requires only 3 or more surrounding tiles to be changed to a tile
				else if (surroundingTiles > 2) 
				{
					map[x, y] = 1;
				}
				else if (surroundingTiles < 2)
				{
					map[x, y] = 0;
				}
			}
		}
	}
    //Return the modified map
    return map;
}

Как видно ниже, конечный результат получается намного более блочным, чем у окрестности Мура:


Здесь, как и в окрестности Мура, можно запустить дополнительный скрипт для оптимизации соединений между частями карты.

Заключение


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

Комментарии (1)


  1. evil_me
    16.10.2019 14:44

    Спасибо, очень полезная статья!
    Делал игру на Unity c похожими алгоритмами генерации поверхности. Но всё могло быть чуть плавнее :)