Процедурна генерація на Unity. Частина 1: клітинні автомати

Enter the Gungeon, The Binding of Isaac, Risk of Rain 2... Усі ці ігри об’єднанні своїм жанром, який викликає асоціації з чимось смачненьким ‑ рогаликами. Кожен з нас хоч раз грав у них та насолоджувався нескінченними ігровими сеансами. І це не дивно — кожний запуск приносить повністю новий світ! Від ворогів, босів, зброї до карти. І про останнє ми сьогодні й поговоримо.

Очевидно, що створювати нескінченну кількість рівнів буде трошки складно та непродуктивно. Тож для цього використовують процедурну генерацію. Що ж це таке?

Procedural generation — автоматичне створення контенту за допомогою алгоритмів, як нам каже Вікіпедія.

Легше звичайно не стало, тож давайте розбиратися далі.

Існує величезна кількість таких алгоритмів. Деякі з них:

  1. Рандомайзер (нічого гарного з цього не вийде, проте він лежить в основі багатьох інших)
  2. Сellular automata
  3. Diamond square
  4. Fractal Noise
  5. ...

У цій статті я хочу розглянути другий алгоритм Сellular automata, базований на клітинних автоматах.

Клітинний автомат — це математична модель, що підпорядковується певним правилам. Одним з найвідоміших збірників правил є Game of Life.

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

Наш алгоритм процедурної генерації буде мати два етапи.

Перший, підготовчий, полягає в тому, щоб згенерувати випадковий набір даних.

Другий етап запускає клітинний автомат і створює кінцеву карту, оброблюючи попередній. Здається, що легко? Так і є!

Для створення рандомного масиву можна використовувати всі способи. Я використовував найпростіший алгоритм створення шуму: генерую число, перевіряю, чи більше воно густини, і якщо так, то ставимо там підлогу, якщо менше — стіну.

А тепер найцікавіша частина. Створення самого клітинного автомату.

Отже, нам потрібно проходити через всю карту та перевіряти кожну клітину за певним збірником правил. Я вирішив не заморочуватися та вибрав одне з найпростіших: якщо навколо клітини 4 і більше стін, то вона також стає стіною. В іншому випадку ми ставимо там підлогу. Перевірка проводиться по сусіднім 8 клітинам. Якщо ми поза картою, то вважаємо, що за нею також стіни. Що ж, тепер, коли ми розібралися з теорією, перейдемо до практики!

*Дизклеймер: моя реалізація далеко не найкраща та в більшості випадків можна було зробити краще, тож я розповім свій шлях написання. Дякую за розуміння)*

Отже, я вирішив, що для створення робочої генерації нам буде досить 3 класи: NoiseGenerator(клас, що буде створювати шум), CellularAutomata(саме клітинний автомат) та GameController(щоб зібрати та запустити всі функції разом).

NoiseGenerator: MakeNoiseMap

 public TileBase[,] MakeNoiseMap(int density, int height, int width)
    {
        TileBase[,] noiseGrid = new TileBase[width,height];
        int random = Random.Range(1, 100);
        for (int i = 0; i < width; i++)
        {
            for (int j = 0; j < height; j++)
            {
                if (random > density)
                    noiseGrid[i, j] = floorTile;
                else
                    noiseGrid[i, j] = wallTile;
                
                random = Random.Range(1, 100);
            }
        }
        return noiseGrid;
    }

Функція приймає три аргументи: густину стін і необхідні висоту та ширину карти. Далі ми створюємо двомірний масив з тайлів(TileBase) і створюємо змінну, що зберігатиме випадкове значення, яке ми будемо обновлювати кожну ітерацію по масиву. Тепер маємо вкладений цикл, в якому і відбувається магія створення шуму. Ось і все!

CellularAutomata: ApplyCellularAutomata

public void ApplyCellularAutomata(Tilemap levelMap, int count, int height, int width, TileBase floor, TileBase wall)
    {
        for (int i = 0; i < count; i++)
        {
            var tempMap = Instantiate(levelMap);
            tempMap.gameObject.SetActive(false);
            for (int j = 0; j < width; j++)
            {
                for (int k = 0; k < height; k++)
                {
                    int neighborWallCount = 0;
                    for (int x = j - 1; x <= j + 1; x++)
                    {
                        for (int y = k - 1; y <= k + 1; y++)
                        {
                            if (isWithinMapBounds(x, y, levelMap))
                            {
                                if (x != j || y != k)
                                    if (tempMap.GetTile(new Vector3Int(y,x,0)) == wall)
                                        neighborWallCount++;
                            }
                            else
                            { 
                                neighborWallCount++;
                            }
                        }
                    }
                    int minimumWallCount = 4;
                    if (neighborWallCount > minimumWallCount)
                        levelMap.SetTile(new Vector3Int(j, k, 0), wall);
                    else
                        levelMap.SetTile(new Vector3Int(j, k, 0), floor);
                }
            }
        }
    }

Тепер складніший етап написання клітинного автомату.

По-перше, функція приймає 6 аргументів: карту(Tilemap), на яку будуть накладені зміни, кількість ітерацій, знову розміри карти, та тайли підлоги і стін. Це явно занадто багато аргументів, їх кількість можна зменшити.

Тепер пройдемося по алгоритму. Спочатку нам потрібен цикл, що проходитиме по карті count разів, щоб алгоритм повністю опрацював шум.

Далі ми копіюємо карту. Це дуже важливо, бо тоді алгоритм буде проходитись по зміненим даним і замість згладжування буде просто розширювати клітини шуму і створювати симетричні картини.

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

private bool isWithinMapBounds(int x, int y, Tilemap map)
    {
        if (map.GetTile(new Vector3Int(x, y, 0)) == null)
            return false;
        return true;
    }

Тепер, коли ми впевнені, що знаходимося у межах та не натрапимо на null, можемо перевіряти, тип тайлу та збільшувати лічильник стін. Профіт!

А далі замінюємо тип клітини і повторюємо цей процес. Готово, ми створили клітинний автомат!

Тепер ми просто повинні накласти шум на тайлмап у GameController та зробити трошки UI магії, щоб можна було визивати функції при кліку на кнопки. Готово! Наша процедурна генерація повністю працює і її можна використовувати у проєктах)

Ось як все вишло:


Ось посилання на проєкт на гітхабі, щоб ви мали можливість погратися)

P.S: Всім дякую за те, що прочитали, коментуйте, пропонуйте, та давайте подискутуємо. А поки, до наступної статті 🤗

Підписуйтеся на Telegram-канал @gamedev_dou, щоб не пропустити найважливіші статті і новини про геймдев.

👍ПодобаєтьсяСподобалось4
До обраногоВ обраному3
LinkedIn
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

І вам дякую за прочитання)

Метод математично ОК, але с точки зору дизайну, навіть для рогаликів трішки слабенький — неможливо/важко контролювати розміри і співвідношеня "коридори"/"кімнати"

Метод кімнат і коридорів в більшості випадків дає кращі генеровані карти, бо більше контролю що буде на виході.

Якщо потрібно щось типу «біонічного» — то краще діаграми Вороного, але з ними важко працювати «в голові»

Уоу! А зможете трошки детальніше про діаграми Вороного розказати? Наприклад, якщо я до вас у лінкедіні додамся.

Вороной:
www.gamedeveloper.com/...​rld-maps-for-unexplored-2

І мабуть найбільш детальний огляд автомати+тунелі+метрики(або оцінка «якості карти»):
www.reddit.com/...​on_in_cogmind_5_articles

Величезне Вам дякую!

Добре, дякую, що виправили)
Можете порадити, де знайти гарне роз’яснення цих алгоритмів?

Підписатись на коментарі