Процедурна генерація планетарних карт

Мова піде про картографії, що має справу з фантастичними світами.

Стан справ з процедурної генерацією карт
На даний момент процедурна генерація карт це вже велика тема отримала розвиток, головним чином, в рамках гейм-індустрії. Існують способи автоматичної генерації різних типів карт від простих зображень в рольових і екшен іграх до tile-карт в стратегічних іграх. Перші дають уявлення про місце дії гри і відрізняються маленьким охопленням території, другі можуть моделювати великі області цілих планет, але мають малу деталізацію.

Давно і добре відомі методи створення карт і рельєфів для невеликих територій:
метод серединного зміщення, метод шумових функцій (Noise Functions). Порівняно недавно з'явився цікавий спосіб заснований на розбитті площині полігонами Polygonal Map Generation for Games. Існує сайт, де зібрані посилання на різні ресурси штучної генерації рельєфів.

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

Взагалі, будемо відрізняти надалі рельєф від карти: рельєф вважаємо різновидом текстури і маємо можливість спостерігати, на відміну від рельєфу, карту можемо „помацати“, це означає, що об'єкти карти повинні бути самостійними сутностями і існує певний спосіб, яким можна їх змінювати. До того ж, наявність карти не скасовує існування і спостереження рельєфу.

GIS і OpenStreetMap як спосіб подання фантастичних карт
Існує безліч програмних засобів і стандартів для роботи з картами Землі. Географічні інформаційні системи призначені для захоплення, маніпуляції, аналізу та подання всіх типів географічних даних. OpenStreetMap (OSM) є одним з прикладів GIS, який покликаний збирати географічні дані і видавати їх у вільний доступ.

Широкий спектр різноманітних GIS, а так само безліч програмних засобів і технік, що з'явилися в результаті розвитку проекту OpenStreetMap, просто напрошується використовувати для роботи з картами фантастичних планет. Якщо б такі вже існували як існує Земля з її поверхнею.

Процедурна генерація планети
Далі описую пропонований спосіб генерації планети (на пальцях). Роблячи рельєф планетарного масштабу досить швидко приходиш до меж обчислювальної системи. Кількість вироблених обчислень зростає квадратично по відношенню до зменшення кроку між точками сітки на сфері. У цьому головна причина, по якій карти планетарного масштабу не створювалися. Друга з причин — необхідність реалізації глобальної річкової мережі і зв'язування її з рельєфом.

Подвійний конус як наближення сфери

Приступаючи до цієї задачі перше бажання, яке виникає, це уникнути обчислення тригонометричних функцій, але сфері це не представляється можливим. Існує спосіб, коли для створення текстури на сфері вона спочатку малюється на гранях правильного багатогранника, наприклад куба, і потім відображається на сферу. Зрозуміло, що кути багатогранника при такому відображенні повинні давати спотворення. Застосування такого способу до великої планеті викликало б надто помітні спотворення. Будемо використовувати іншу різновид цього підходу.

Без розривів відображаємо сферу планети на сполучені в підставі круглі конуси, лінія екватора, при цьому, повинна співпадати з лінією з'єднання конусів. В кінці процесу побудови рельєфу на конусах робимо зворотне відображення на сферу. Звичайно, спотворень не уникнути, але, роблячи відображення по-різному, можливо по-різному розподілити результуючі спотворення на сфері. Хороша новина — повністю позбавляємося від обчислення тригонометричних функцій.

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

distortion
Таке відображення добре підходить до планет, у яких поблизу полюсів океани або білі плями. Біля екватора або в середніх широтах візуально помітити вносяться спотворення важко (спотворення, які вносяться обраної основною сіткою, можуть бути помітні сильніше).

Два рівня генерації карти

Навіть, з урахуванням спрощення за допомогою конічної проекції, обчислення для всієї планети залишаються витратними по витраті пам'яті. Для вирішення цієї проблеми вдаємося до дворівневої генерації. Спочатку генеруємо основну або глобальну сітку висот. Основним параметром цієї сітки служить величина gn, яка визначає кількість поділок сітки на чверті екватора рівним 2gn. Процес генерації висот на основній сітці виявляє основні ділянки сущи. Тут же встановлюється рівень моря за співвідношенням кількості точок потрапляють в сушу і океан.

прикладах планет, які були виготовлені, gn=7. Що є досить скромною величиною і, в процесі оптимізації алгоритмів і нарощуванні „заліза“, буде можливість поступово збільшувати gn для нових планет.

Процес побудови основної сітки. Ділимо екватор 4*2gn точками на однакові відрізки довжини l, далі відступаємо по нульовому меридіану відстань l на північ і ділимо паралель, на якій знаходимося, на 4*(2gn-1) відрізків. Продовжуємо процес далі до полюса, зменшуючи при кожній ітерації кількість точок на кожній наступній паралелі на 4. Те ж саме робимо з південною півкулею. Кожна точка глобальної сітки визначає ромб на конусі (виключення: точки полюсів, яким немає порівнянних ромбів) і весь подвійний конус виявляється поділений на ромби. Зауважимо, що це ромби на поверхні круглого конуса, а не на площині. На наступному рисунку зображено фрагмент основної сітки ромбів, містить чверть верхнього конуса gn=2 (без претензії на точність, але корисно для з'ясування суті справи).

mesh
Перехід до сітки на здвоєних конусах призводить до несподіваного результату: точки основної сітки (без полюсів) компонуються в масив розмірністю 2gn 4*2gn. Для цього спочатку заносимо в масив точки південного конуса і екватора, а потім праворуч на вільні місця поміщаємо точки північного конуса, при цьому розгорнувши їх зліва направо. Як наслідок, багато алгоритми реалізації на конусах виглядають простіше ніж їх можливі аналоги на сфері.

Ось, наприклад, як може виглядати код функції збільшує висоту околиці південного полюса радіусом r на одиницю (реальна функція в коді проекту виглядає інакше, враховуючи більш загальний випадок).

import Data.Array.Base
import Data.Array.ST

type Height = Int
type GHeights = UArray (Int,Int) Height
type GHeightsMutable s = (STUArray s (Int,Int) Height)

-- | Make Heights array mutable
thawGHeightsArr :: GHeights -> ST s (GHeightsMutable s)
thawGHeightsArr = unsafeThaw

-- | Increase values around south pole
shiftSouth :: GHeights -> Int -> GHeights
shiftSouth hs r = runSTUArray $ do
a <- thawGHeightsArr hs
mapM_ (\y ->
(mapM_ (\x -> do 
v <- readArray a (x,y)
writeArray a (x,y) (v + 1)
) [1..4*y])
) [1..r]
return a

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

gmesh
Для переходу на наступний рівень встановлюємо локальну сітку в кожному ромбі і будуємо рельєф відштовхуючись від вже відомих значень висот у вершинах ромба (які належать основній сітці). Таким чином, підсумковий рельєф буде представляти собою різновид мульти-фрактала.

Основний параметр локальної сітки — величина ln, яка задає кількість кроків сітки в двох напрямках: 2ln+1 і 2*2ln+1 відповідно. На малюнку приклад ромба з локальної сіткою при ln=3.

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

При реалізації проектів зі складними і многоэтапными алгоритмами часто є необхідність побудови зорових образів проміжних даних. Ось, наприклад, образ середньої величини острова в процесі створення планети; видно поділ на ромби пунктирною лінією.

island model

Річки і озера

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

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

Поезія карт
Кілька красивих фрагментів карт неіснуючих світів, які виникають в результаті реалізації описаного алгоритму.

image image

image image

image image
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.