wHDorld Jul 6 2018 at 16:51

Генератор случайных двумерных пещер

8 min

12K

Предисловие

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

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

По завершении чтения статьи у вас должно получиться что-то такое:

Итог

Теория

Гора

Если честно, то пещеру можно сгенерировать и на пустом месте, но ведь это будет как-то некрасиво? В роли «площадки» для размещения шахт я выбрал горный массив.
Эта гора генерируется достаточно просто: пускай у нас будет двумерный массив и переменная высоты, изначально равная половине длины массива по второму измерению; мы просто пройдемся по его столбикам и будем заполнять чем-то все строчки в столбике до значения переменной высоты, изменяя ее со случайным шансом в большую или меньшую сторону.

Пещера

Для генерации самих подземелий я выбрал — как мне показалось — отличный алгоритм. Простым языком его можно объяснить так: пускай у нас будут две (можно даже десять) переменные X и Y, и двумерный массив 50 на 50, мы задаем этим переменным случайные значения в пределах нашего массива, например, X = 26, а Y = 28. После чего мы некоторое количество раз делаем однообразные действия: получаем случайное число от нуля до

$display$

, в нашем случае до четырех; а потом в зависимости от выпавшего числа меняем
наши переменные:

switch (Random.Range(0, 4))
{
 case 0: X += 1; break;
 case 1: X -= 1; break;
 case 2: Y += 1; break;
 case 3: Y -= 1; break;
}

Потом мы, разумеется, проверяем не выпала-ли какая-нибудь переменная за границы нашего поля:

            X = X < 0 ? 0 :
                (X >= 50 ? 49 : X);
            Y = Y < 0 ? 0 :
                (Y >= 50 ? 49 : Y);

После всех этих проверок, мы в новых значениях X и Y для нашего массива что-нибудь выполняем (например: прибавляем к элементу единицу).

array[X, Y] += 1;

Подготовка

Давайте для простоты реализации и наглядности наших методов мы будем рисовать получившиеся объекты? Я так рад, что вы не против! Мы будем делать это с помощью Texture2D.

Для работы нам потребуется всего два скрипта:

ground_libray — это то, вокруг чего будет крутиться статья. Тут мы и генерируем, и чистим, и рисуем

ground_generator — это то, что будет пользоваться нашим ground_libray

Пускай первый будет статичным и ни от чего не будет наследоваться:

public static class ground_libray

А второй обычный, только метод Update нам не понадобится.

Так же давайте создадим на сцене игровой объект, с компонентом SpriteRenderer

Практическая часть

Из чего всё состоит?

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

Новый тип

Эту штуку мы пишем в ground_libray.

[System.Serializable]
public class block
    {
        public float[] color = new float[3];

        public block(Color col)
        {
            color = new float[3]
            {
                col.r,
                col.g,
                col.b
            };
        }
    }

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

Горный массив

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

В скрипте ground_generator я написал так:

    public int ground_size = 128;
    ground_libray.block[,] ground;
    Texture2D myT;

ground_size — размер нашего поля (то есть массив будет состоять из 16384-х элементов).
ground_libray.block[,] ground — это и есть наше поле для генерации.
Texture2D myT — это то, на чем мы будем рисовать.

Как это будет работать?

Принцип работы у нас будет такой — мы будем вызывать какие-нибудь методы ground_libray из ground_generator, отдавая первому наше поле ground.

Давайте создадим первый метод в скрипте ground_libray:

Создание горы

    public static float mount_noise = 0.02f;
    public static void generate_mount(ref block[,] b)
    {
        int h_now = b.GetLength(1) / 2;
        for (int x = 0; x < b.GetLength(0); x++)
            for (int y = 0; y < h_now; y++)
            {
                b[x, y] = new block(new Color(0.7f, 0.4f, 0));
                h_now +=
                    Random.value > (1.0f - mount_noise) ? 
                    (Random.value > 0.5 ? 1 : -1) : 0;
            }
    }

И сразу же попытаемся понять, что тут происходит: как я уже сказал, мы просто пробегаемся по столбикам нашего массива b, параллельно изменяя переменную высоты h_now, которая изначально была равна половине 128 (64). Но есть тут еще кое-что новое — mount_noise. Это переменная отвечает за шанс смены h_now, ибо если менять высоту очень часто, то гора будет смотреться как расческа.

Цвет

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

Теперь давайте перейдем в ground_generator и в методе Start напишем вот это:

        ground = new ground_libray.block
            [ground_size, ground_size];
        ground_libray.generate_mount(ref ground);

Мы инициализируем переменную ground ~~когда-то это нужно было сделать~~.
После без объяснений отправляем ее ground_libray-ю.
Так мы сгенерировали гору.

Почему я не вижу свою гору?

Давайте теперь нарисуем то, что у нас получилось!

Для рисования мы напишем в нашем ground_libray такой метод:

Рисование

    public static void paint(block[,] b, ref Texture2D t)
    {
        t = new Texture2D(b.GetLength(0), b.GetLength(1));
        t.filterMode = FilterMode.Point;
        for (int x = 0; x < b.GetLength(0); x++)
            for (int y = 0; y < b.GetLength(1); y++)
            {
                if (b[x, y] == null)
                {
                    t.SetPixel(x, y, new Color(0, 0, 0, 0));
                    continue;
                }
                t.SetPixel(x, y,
                    new Color(
                        b[x, y].color[0],
                        b[x, y].color[1],
                        b[x, y].color[2]
                        )
                    );
            }
        t.Apply();
    }

Тут мы уже не будем отдавать кому-то свое поле, дадим только его копию (правда, из-за слова class, мы дали чуточку больше, чем просто копию). А так же подарим этому методу нашу Texture2D.

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

После чего мы проходимся по всему нашему поле-массиву и там, где мы ничего не создали (class нужно инициализировать) — мы рисуем пустой квадратик, в ином случае, если там не пусто — мы рисуем то, что сохранили в элемент.

И, конечно, по завершении мы идем в ground_generator и дописываем это:

        ground = new ground_libray.block
            [ground_size, ground_size];
        ground_libray.generate_mount(ref ground);

        //вот тут дописываем
        ground_libray.paint(ground, ref myT);
        GetComponent<SpriteRenderer>().sprite =
            Sprite.Create(myT, 
            new Rect(0, 0, ground_size, ground_size),
            Vector3.zero
            );

Но сколько бы мы не рисовали на нашей текстуре, в игре мы это сможем увидеть, только наложив этот холст на что-нибудь:

SpriteRenderer нигде не принимает Texture2D, но нам ничего не мешает создать из этой текстуры спрайт — Sprite.Create(текстура, прямоугольник с координатами нижнего левого угла и верхнего правого, координата оси).

Эти строчки будут вызываться самыми последними, все остальное мы будем дописывать выше метода paint!

Шахты

Теперь нужно заполнить наше поля случайными пещерами. Для подобных действий мы тоже создадим отдельный метод в ground_libray. Я бы хотел сразу объяснить параметры метода:

ref block[,] b - это мы отдаем наше поле.
int thick - толщина краев пещеры
int size - в некотором роде это можно назвать размером пещеры
Color outLine - цвет краев

Пещера

    public static void make_cave(ref block[,] b, 
        int thick, int size, Color outLine)
    {
        int xNow = Random.Range(0, b.GetLength(0));
        int yNow = Random.Range(0, b.GetLength(1) / 2);
        for (int i = 0; i < size; i++)
        {
            b[xNow, yNow] = null;
            make_thick(ref b, thick, new int[2] { xNow, yNow }, outLine);
            switch (Random.Range(0, 4))
            {
                case 0: xNow += 1; break;
                case 1: xNow -= 1; break;
                case 2: yNow += 1; break;
                case 3: yNow -= 1; break;
            }
            xNow = xNow < 0 ? 0 :
                (xNow >= b.GetLength(0) ? b.GetLength(0) - 1 : xNow);
            yNow = yNow < 0 ? 0 :
                (yNow >= b.GetLength(1) ? b.GetLength(1) - 1 : yNow);
        }
    }

Для начала мы объявили наши переменные X и Y, вот только назвал я их xNow и yNow соответственно.

Первая, а именно xNow — получает случайное значение от нуля до размера поля по первому измерению.

А вторая — yNow — так же получает случайное значение: от нуля, до середины поля по второму измерению. Почему? Мы генерируем нашу гору с середины, шанс того, что она будет дорастать до «потолка» — не большой. Исходя из этого я не считаю релевантным генерировать пещеры в воздухе.

После сразу идет цикл, количество тиков которого зависит от параметра size. Каждый тик мы обновляем поле в позиции xNow и yNow, а уже потом обновляем их самих (обновления поля можно поставить в конец — разницы вы не ощутите)

Так же тут есть метод make_thick, в параметры которого мы передаем наше поле, ширину обводки пещеры, текущую позицию обновления пещеры и цвет обводки:

Обводка

    static void make_thick (ref block[,] b, int t, int[] start, Color o)
    {
        for (int x = (start[0] - t); x < (start[0] + t); x++)
        {
            if (x < 0 || x >= b.GetLength(0))
                continue;
            for (int y = (start[1] - t); y < (start[1] + t); y++)
            {
                if (y < 0 || y >= b.GetLength(1))
                    continue;
                if (b[x, y] == null)
                    continue;
                b[x, y] = new block(o);
            }
        }
    }

Метод берет переданную ему координату start, и вокруг нее на расстоянии t перекрашивает все блоки в цвет o — все очень просто!

Теперь давайте допишем в наш ground_generator эту строчку:

ground_libray.make_cave(ref ground, 2, 10000, 
 new Color(0.3f, 0.3f, 0.3f));

Вы можете установить скрипт ground_generator как компонент на наш объект и проверить как это работает!

Еще о пещерах...

Чтобы сделать больше пещер, вы можете вызвать метод make_cave несколько раз (использовать цикл)
Изменение параметра size не всегда увеличивает размер пещеры, но зачастую она становится больше
Изменяя параметр thick — вы значительно увеличиваете количество операций:
если параметр равен 3, то количество квадратиков в радиусе 3 будет 36, значит при параметре size = 40000 — количество операций будет 36* 40000 = 1440000

Коррекция пещер

Вы не замечали, что в этом виде пещера выглядит не лучшим образом? Слишком много лишних деталей (возможно, вы считаете иначе).

Чтобы избавиться от вкраплений какого-то #4d4d4d мы напишем в ground_libray вот этот метод:

Чистильщик

    public static void clear_caves(ref block[,] b)
    {
        for (int x = 0; x < b.GetLength(0); x++)
            for (int y = 0; y < b.GetLength(1); y++)
            {
                if (b[x, y] == null)
                    continue;
                if (solo(b, 2, 13, new int[2] { x, y }))
                    b[x, y] = null;
            }
    }

Но будет сложно понять, что тут происходит, если вы не будете знать, что делает функция solo:

    static bool solo (block[,] b, int rad, int min, int[] start)
    {
        int cnt = 0;
        for (int x = (start[0] - rad); x <= (start[0] + rad); x++)
        {
            if (x < 0 || x >= b.GetLength(0))
                continue;
            for (int y = (start[1] - rad); y <= (start[1] + rad); y++)
            {
                if (y < 0 || y >= b.GetLength(1))
                    continue;
                if (b[x, y] == null)
                    cnt += 1;
                else
                    continue;

                if (cnt >= min)
                    return true;
            }
        }
        return false;
    }

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

int cnt — то счетчик текущего «порога»
Далее идут два цикла, которые проверяют все точки вокруг той, координаты которой переданы в start. Если находится пустая точка, то мы прибавляем к cnt единицу, по достижении «порога уничтожения» мы возвращаем истину — точка является лишней. Иначе мы ее не трогаем.

Порог уничтожения я установил в 13 пустых точек, а радиус проверки 2 (то есть проверит он 24 точки, не включая центральную)

Пример

Вот эта останется невредимой, так как всего 9 пустых точек.

А вот этой не повезло — вокруг целых 14 пустых точек

Краткое описание алгоритма: мы проходимся по всему полю и проверяем все точки на то, нужны они ли нет.

Далее мы просто добавляем в наш ground_generator такую строчку:

ground_libray.clear_caves(ref ground);

Итог

Как мы видим — большая часть ненужных частичек просто ушло.

Добавим немного красок

Наша гора выглядит очень монотонно, я считаю это скучным.

Давайте добавим немного красок. Добавим метод level_paint в ground_libray:

Закрашивание горы

    public static void level_paint(ref block[,] b, Color[] all_c)
    {
        for (int x = 0; x < b.GetLength(0); x++)
        {
            int lvl_div = -1;
            int counter = 0;
            int lvl_now = 0;
            for (int y = b.GetLength(1) - 1; y > 0; y--)
            {
                if (b[x, y] != null && lvl_div == -1)
                    lvl_div = y / all_c.Length;
                else if (b[x, y] == null)
                    continue;

                b[x, y] = new block(all_c[lvl_now]);
                lvl_now += counter >= lvl_div ? 1 : 0;
                lvl_now = (lvl_now >= all_c.Length) ? 
                                (all_c.Length - 1) : lvl_now;
                counter = counter >= lvl_div ? 0 : (counter += 1);
            }
        }
    }
</
<cut />source>
В параметры к методу мы передаем нашу гору и массив красок. Цвета будут использовать так, чтобы нулевой элемент массива красок был сверху, а последний снизу.

Мы проходимся по всем столбикам нашего поля, а обход по строчкам начинаем сверху. Найдя первую строчку с существующим элементом мы делим значение <b>Y </b>на количество цветов, чтобы поровну разделить цвета на столбик.
</spoiler>
После мы дописываем в <b>ground_generator </b>вот это:

<source lang="cs">
        ground_libray.level_paint(ref ground,
            new Color[3]
            {
                new Color(0.2f, 0.8f, 0),
                new Color(0.6f, 0.2f, 0.05f),
                new Color(0.2f, 0.2f, 0.2f),
            });

Я выбрал всего 3 цвета: Зеленый, темно-красный и темно-серый.
Вы, разумеется, можете изменить как количество цветов, так и значения каждого. У меня получилось так:

Итог

Но все же это выглядит слишком строго, чтобы добавить немного хаотичности цветам, мы напишем в ground_libray вот такое свойство:

Случайные цвета

    public static float color_randomize = 0.1f;
    static float crnd
    {
        get
        {
            return Random.Range(1.0f - color_randomize,
                1.0f + color_randomize);
        }
    }

И теперь в методах level_paint и make_thick, в строчках, где мы присваиваем цвета, например в make_thick:

b[x, y] = new block(o);

Мы напишем так:

b[x, y] = new block(o * crnd);

А в level_paint

b[x, y] = new block(all_c[lvl_now] * crnd);

В итоге у вас должно все выглядеть примерно так:

Итог

Недостатки

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

1024 * 1024 + 24 * 64 * 80000 = 5 368 832 000 000 операций.

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

Tags:

Hubs: