Procedural Planet Generator: Архітектура, Алгоритми та Математична Модель

Розподіл команди

1. Омелянчук Тимур - Славетний, Величний, Шляхентний, Геніальний сер Тимур I. Головний ентуізаст цього проекту. Організатор масових репресій в країнах Варшавського договору. Самотушки написав Perlin Noise в перший день проекту (а це тіпу нічого собі).
2. Оксентюк Олександр - Сумлінний, Справедливий, Далекоглядний лорд Олександр. Генератор ідей. Зробив сайт та все що його стосується.
3. Арламовська Олеся - Легендарна, Незламна, Мудра міні Олеся. Робила презентацію, поки інші були на парах. Творець системи генерації біомів.
4. коновал северин - сігма сігма бой. Неймовірна людина, яку до того ж змусили писати звіт. Організатор найбільшої суперечки в групі та робитель клітинних автоматів.
5. Данилків Павло - no comments.

---

Інструкція з використання

Проєкт може працювати у двох режимах: як веб-додаток (інтерактивно) та як консольна утиліта (CLI) для пакетної генерації.

0. Веб-додаток (Рекомендовано)

Просто перейти за посиланням -> https://genplan.pp.ua (після захисту працювати не буде, бо ми бідні студенти, пожалійте)

1. Веб-додаток (Не рекомендовано)

Запуск через Docker. Перейдіть у папку site та виконайте команду:

cd site
docker compose up --build

Після успішного запуску відкрийте у браузері http://localhost:5000. У бічній панелі ви зможете налаштувати параметри (Subdivisions, Noise, Seed) та побачити генерацію планети в реальному часі.

2. Консольна утиліта (CLI)

Для генерації та збереження результатів локально (у корінь проєкту). Потрібен Python 3.10+ та встановлені залежності з requirements.txt.

Експорт 2D-карти (PNG):

python src/main.py --seed 67 --radius 3 --subdivisions 7 --format png --output my_map

Експорт 3D-моделі (OBJ):

python src/main.py --seed 777 --radius 3 --subdivisions 7 --format obj --output my_planet

---

Принципи Дискретної Математики

В основі генерації поверхні лежать ключові концепції дискретної математики:

1. Теорія графів: Тривимірна сітка (ікосфера) моделюється як неорієнтований граф $G = (V, E)$, де $V$ — множина вершин, а $E$ — множина ребер. Для роботи алгоритмів (зокрема тектоніки) будується список суміжності, що дозволяє за $O(1)$ знаходити сусідів будь-якої вершини.
2. Топологія та Ейлерова характеристика: Ікосфера є триангульованим планарним графом (розгорнутим на сферу), який задовольняє формулу Ейлера: $V - E + F = 2$ (LOL).
3. Детерміновані Хеш-функції: Для забезпечення того, щоб один і той самий сід генерував однакову планету на будь-якому ПК, використовується кастомний безстанний генератор псевдовипадкових чисел (Stateless PRNG) з побітовими зсувами (Avalanche effect).

---

Генерація Макрорельєфу: Клітинні Автомати (Тектоніка)

Для формування великих континентів та океанів (макрорельєфу) використовуються Клітинні автомати (Cellular Automata), які симулюють рух тектонічних плит.

Як це працює

1. Ініціалізація: На графі випадково обираються "епіцентри" тектонічних плит. Їм призначається випадкова цільова висота (океанічна впадина або материковий щит).
2. Flood Fill (Поширення): Процес розширюється графом (широкий пошук BFS). На кожній ітерації активні клітинки "захоплюють" своїх вільних сусідів, передаючи їм свої властивості.
3. Зіткнення (Колізії): Коли дві плити зустрічаються, алгоритм розраховує змішування їх висот, створюючи "шви" — гірські хребти або розломи.

Порівняння: Клітинні Автомати vs. Діаграма Вороного

• Переваги: Автомати формують більш природні, "рвані" та органічні обриси континентів (подібні до реальної географії). Вони відмінно імітують фізичний процес тектоніки плит та взаємодію на кордонах.
• Недоліки: Значно важчі в обчисленні — складність $O(V \cdot iterations)$. Вимагають зберігання графа суміжності у пам'яті. Їх важко розпаралелити, оскільки стан кожної клітини залежить від її сусідів.

---

Генерація Мікрорельєфу: 3D Шум

На згенеровані континенти накладається Шум (Perlin Noise) для створення дрібних деталей: гір, пагорбів, нерівностей.

Як це працює

Замість класичної 2D розгортки (яка створює "стягування" полюсів), алгоритм оцінює шум безпосередньо у 3D Декартовому просторі за координатами вершини $(x, y, z)$.

Для реалізму використовується метод накладання кількох "шарів" шуму (октав):

• Octaves (Октави): Кількість шарів.
• Lacunarity (Лакунарність, зазвичай 2.0): З кожною октавою частота шуму подвоюється (деталі стають дрібнішими).
• Persistence (Персистенція, зазвичай 0.5): З кожною октавою вплив (амплітуда) шару зменшується вдвічі.

Кінцева формула: $H(p) = \sum_{i=0}^{octaves-1} amplitude \cdot Noise(p \cdot frequency)$

Порівняння: Noise vs. Клітинні автомати

• Переваги: Шум оцінюється за $O(1)$ для будь-якої точки в просторі, не вимагає графа суміжності. Шум генерує нескінченну кількість деталей без збільшення витрат пам'яті.
• Недоліки: Шум не має "глобальної структури". Якщо використовувати тільки його, планета виглядатиме як набір випадкових плям без логічних континентів чи ліній гірських хребтів.

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

---

Кліматична Модель та Біоми

Останній крок генерації — розрахунок клімату. Біом вершини визначається на основі перетину двох факторів:

1. Температура: Визначається близькістю до екватора (абсолютне значення $Y$) та висотою (Altitude/Lapse rate — гори завжди холодні).
2. Вологість: Найвища біля екватора та океанів, спадає у глибині континентів.

Перетин цих даних через 2D-таблицю (Lookup Table) формує реалістичне забарвлення: Низька висота - Океан. Екстремальний холод - Сніг або Тундра. Теплий клімат - розподіл між лісами та пустелями.

---

Архітектура та Оптимізація

Щоб планета генерувалась та відображалась у браузері без зависань:

1. Numba JIT: Усі складні цикли та математичні функції Python компілюються у машинний код, прискорюючи виконання до рівня C/C++.
2. Binary Packing: Flask-сервер не серіалізує масиви у важкий JSON. numpy масиви конвертуються в сирі байти (.tobytes()) і передаються через WebSockets.
3. Three.js BufferGeometry: Фронтенд напряму вантажить отримані байти у буфери відеокарти (WebGL), виконуючи анімацію перетворень (Morphing) між етапами тектоніки, шуму та фарбування.

Процес використання проєкту

архітектура - перлін нойз - аргпарс - перекус - генерація планет - біоми - сон - тектоніка

Враження від виконання

• [ Тимур ] - Враження неймовірні, враження, що ми все на колінкі робимо. Ну, тема — класна, Перлін нойз — класний, клітинний автомат — нафіг він тут взагалі існує я не знаю.

• [ Олеся ] - Мені дуже подобається шукати фотки людей.

• [ Олеся ] (дубль 2) - Дуже чудовий проект, мені дуже подобається наааш сайт, воно виглядає дуже потужно, дуже класні каляри, бо я їх вибирала, іі всьо. Ну, чудовий проект. Чудова дрім тім.

• [ Олександр ] - Я не знаю, вроді нормально, я люблю коли планета генерується, не люблю коли не генерується. Мені сподобалося коли мені згенерувало об'єкт 33 міліона рядків кода і в мене комп завіс. Лол.

• [ Павло] - no comments.

Северина нема, бо інтерв'ювера не інтерв'юють.

Фідбек

Лука чіл гай. чіл гай.

Завдання прикольне

Висновок

У ході виконання проекту було розроблено комплексну систему процедурної генерації ландшафту планет. Реалізовано два підходи — шум Перліна та клітинні автомати, що додає поверхні планети реалістичної деталізації. Розроблено кліматичну модель, що автоматично розраховує температуру та вологість для кожної вершини, враховуючи широту (від екватора до полюсів) та висоту над рівнем моря. Створено можливість для збереження результатів у форматі 2D-карт (PNG) та повноцінних 3D-моделей (OBJ). Результати проекту та візуалізація алгоритмів інтегровані у зручний веб-інтерфейс, що демонструє роботу системи та дозволяє взаємодіяти з параметрами генерації.