Положение дел с процедурной генерацией карт
На данный момент процедурная генерация карт это уже обширная тема получившая развитие, главным образом, в рамках гейм-индустрии. Существуют способы автоматической генерации различных типов карт от простых изображений в ролевых и экшен играх до tile-карт в стратегических играх. Первые дают представления о месте действия игры и отличаются маленьким охватом территории, вторые могут моделировать обширные области целых планет, но имеют малую детализацию.
Давно и хорошо известны методы создания карт и рельефов для небольших территорий:
метод срединного смещения, метод шумовых функций (Noise Functions). Сравнительно недавно появился интересный способ основанный на разбиении плоскости полигонами Polygonal Map Generation for Games. Существует сайт, где собраны ссылки на различные ресурсы по искусственной генерации рельефов.
Как правило, чаще всего, дело ограничивается созданием текстур для моделирования ландшафта, но какой бы красивый и зрелищный не получился ландшафт, это ещё не является полноценной картой.
Вообще, будем отличать в дальнейшем рельеф от карты: рельеф считаем разновидностью текстуры и имеем возможность его наблюдать, в отличие от рельефа, карту можем „пощупать“, это подразумевает, что объекты карты должны быть самостоятельными сущностями и существует определённый способ, которым можно их изменять. К тому же, наличие карты не отменяет существование и наблюдение рельефа.
GIS и OpenStreetMap как способ представления фантастических карт
Существует множество программных средств и стандартов для работы с картами Земли. Географические информационные системы предназначены для захвата, манипуляции, анализа и представления всех типов географических данных. OpenStreetMap (OSM) является одним из примеров GIS, который призван собирать географические данные и выдавать их в свободный доступ.
Широкий спектр разнообразных GIS, а так же множество программных средств и техник, появившихся в результате развития проекта OpenStreetMap, просто напрашивается использовать для работы с картами фантастических планет. Если бы такие уже существовали как существует Земля с ее поверхностью.
Процедурная генерация планеты
Далее описываю предлагаемый способ генерации планеты (на пальцах). Делая рельеф планетарного масштаба довольно быстро приходишь к пределам вычислительной системы. Количество производимых вычислений увеличивается квадратично по отношению к уменьшению шага между точками сетки на сфере. В этом главная причина, по которой карты планетарного масштаба не создавались. Вторая из причин — необходимость реализации глобальной речной сети и связывания ее с рельефом.
Двойной конус как приближение сферы
Приступая к этой задаче первое желание, которое возникает, это избежать вычисления тригонометрических функций, но на сфере это не представляется возможным. Существует способ, когда для создания текстуры на сфере она, сначала, рисуется на гранях правильного многогранника, например куба, и затем отображается на сферу. Понятно, что углы многогранника при таком отображении должны давать искажения. Применение такого способа к большой планете вызвало бы чересчур заметные искажения. Будем использовать другую разновидность этого подхода.
Без разрывов отображаем сферу планеты на соединённые в основании круглые конусы, линия экватора, при этом, должна совпадать с линией соединения конусов. В конце процесса построения рельефа на конусах делаем обратное отображение на сферу. Конечно, искажений не избежать, но, делая отображения по-разному, возможно различно распределить результирующие искажения на сфере. Хорошая новость — полностью избавляемся от вычисления тригонометрических функций.
В качестве рабочего отображения используем вариант, при котором сохраняются расстояния по меридианам. По вертикали мы избегаем искажений совсем, а по горизонтали искажения растут линейно, и около полюсов рост искажений уменьшается, достигая максимума 1.57.
Такое отображение хорошо подходит к планетам, у которых вблизи полюсов океаны или белые пятна. У экватора или в средних широтах визуально заметить привносимые искажения трудно (искажения, привносимые выбранной основной сеткой, могут быть заметны сильнее).
Два уровня генерации карты
Даже, с учётом упрощения с помощью конической проекции, вычисления для всей планеты остаются затратными по расходу памяти. Для решения этой проблемы прибегаем к двухуровневой генерации. Сначала генерируем основную или глобальную сетку высот. Основным параметром этой сетки служит величина gn, которая определяет количество делений сетки на четверти экватора равным 2gn. Процесс генерации высот на основной сетке выявляет основные участки сущи. Здесь же устанавливается уровень моря по соотношению количества точек попадающих в сушу и океан.
На примерах планет, которые были изготовлены, gn=7. Что является довольно скромной величиной и, в процессе оптимизации алгоритмов и наращивании „железа“, будет возможность постепенно увеличивать gn для новых планет.
Процесс построения основной сетки. Делим экватор 4*2gn точками на одинаковые отрезки длины l, далее отступаем по нулевому меридиану расстояние l на север и делим параллель, на которой находимся, на 4*(2gn-1) отрезков. Продолжаем процесс далее до полюса, уменьшая при каждой итерации количество точек на каждой следующей параллели на 4. То же самое делаем с южной полусферой. Каждая точка глобальной сетки определяет ромб на конусе (исключения: точки полюсов, которым нет сопоставимых ромбов) и весь двойной конус оказывается поделён на ромбы. Заметим, что это ромбы на поверхности круглого конуса, а не на плоскости. На следующем рисунке изображен фрагмент основной сетки ромбов, содержащий четверть верхнего конуса для gn=2 (без претензии на точность, но полезно для уяснения сути дела).
Переход к сетке на сдвоенных конусах приводит к неожиданному результату: точки основной сетки (без полюсов) компонуются в массив размерностью 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
При генерации рельефа на основной сетке стремимся к тому, чтобы образовалось несколько значительных участков суши. Достижение разделения суши на отдельные участки важно для распараллеливания вычислений, так как речная система строится для каждого участка суши независимо. Так выглядит модель планеты изображающей распределение высот основной сетки.
Для перехода на следующий уровень устанавливаем локальную сетку в каждом ромбе и строим рельеф отталкиваясь от уже известных значений высот в вершинах ромба (которые принадлежат основной сетке). Таким образом, итоговый рельеф будет представлять собой разновидность мульти-фрактала.
Основной параметр локальной сетки — величина ln, которая задаёт количество шагов сетки в двух направлениях: 2ln+1 и 2*2ln+1 соответственно. На рисунке пример ромба с локальной сеткой при ln=3.
Для генерации рельефа можно осуществить алгоритм, при котором в памяти обязан находится только массив высот одного ромба. Это позволяет осуществить генерацию планет с высоким разрешением объектов карты.
При реализации проектов со сложными и многоэтапными алгоритмами часто есть необходимость построения зрительных образов промежуточных данных. Вот, к примеру, образ средней величины острова в процессе создания планеты; видно деление на ромбы пунктирной линией.
Реки и озера
Существует работа посвященная созданию речной системы. Но двухуровневый характер генерации потребовал создать специфические алгоритмы составляющие реки из отдельных кусков. Схематическое изображение рек для небольшого острова смотрите на рисунке. Итоговое изображение рек будет зависеть от их полноводности в устье.
Озера возникают как места локальных минимумов в основной сетке высот. Задача состоит в том, чтобы определить полигон, внутри которого содержится этот локальный минимум.
Поэзия карт
Несколько красивых фрагментов карт несуществующих миров, которые возникают в результате реализации описанного алгоритма.
Комментарии (27)
leggiermente
24.10.2016 14:17+2О, статья как раз в точку для меня: потихоньку делаю игру с генерацией карты на всей планете. Спасибо!
Когда вижу алгоритмы процедурной генерации — всегда возникает мысль обучить нейронную сетку на реальных данных, а затем загнать в неё входные данные процедурной генерации, чтобы выбрать набор параметров, лучше соответствующих данным. Применяя такие сетки к генерации планетарных карт, можно, как минимум, получить более естественно выглядящие карты, а как максимум — узнать какие-нибудь доселе неизвестные географические или геологические закономерности Земли. В этом направлении совсем не копал, это просто мои размышления. Уверен, что много где так и делается.
T-362
24.10.2016 15:46+1Немного не в тему но нет ли софта или базы алгоритмов для генерации звездных систем? Что-бы наглядно — выбрали размер звезды, потыкали химический состав, получили развертку с зоной обитаемости, светимостью и т.д., накидали орбиты с планетами и их подкорректировало под физически реальные что-бы вся система не развалилась, и все в таком роде.
saggid
25.10.2016 04:06Star Citizen сегодня — это наверное самые продвинутые ребята, которые продвинулись дальше всех в этой теме. Они там много всего рассказывают и показывают в своих видео.
Сейчас ещё совершенно случайно увидел на ютубе видеоролик о неком проекте Outerra. С их сайта даже технодемку скачать можно. Но тут, как я понял — больше не процедурная генерация планет, а процедурная генерация разного контента на поверхности планет, типа деревьев, травы, и так далее. Сама планета в демке — это наша Земля.
igor720
25.10.2016 07:59Это старая путаница: принимают рельеф местности за карту. По ссылкам можно увидеть только виды рельефа. Реальную карту полномаштабной планеты можно найти только на моем сайте (на сколько я знаю, аналогов нет вообще). Реальную карту, в которой географические объекты являются сущностями и имеют вполне определенные цифровые характеристики, удобно использовать, например, в видеоиграх. Рельеф же, главным образом, годится только для фона.
T-362
25.10.2016 14:16> Реальную карту полномаштабной планеты можно найти только на моем сайте
Dwarf Fortress — тоже умеет создание карты планеты, только в более «классическом» исполнении в виде квадрата, в остальном — высоты, температура, осадки, биомы, легкий налет тектоники, и если не ошибусь даже эрозия. Проблема в том что автор пишет игру весьма эзотерически и понять-вытащить алгоритмы проблематично.
vikarti
25.10.2016 09:49Start Citizen? А Space Engine http://spaceengine.org/ не смотрели в плане именно процедурной генерации? Не только планет.
igor720
25.10.2016 13:59Я не знал о них вплоть до последнего времени, но знал о Mojoworld. В этих проектах все вертится вокруг текстур и способов их наблюдения. У меня с самого начала была другая цель — карта, которая охватывает полную большую планету и возможность манипулирования ею. Кстати, ландшафты можно генерировать и дать возможность наблюдать и в способе который используется мною для карт. Вот только пока что я не прилагал больших усилий в этом направлении, тем более текущее разрешение планет не может дать красивых картинок сравнимых с Mojoworld.
В качестве источника идей и способов я полагался на математическую литературу по фракталам.
Idot
А как имитировать дрейф континентальных плит? А эрозию рельефа?
igor720
Дрейф плит пока никак не рассматривался для реализации, но вообще это возможно, почему бы и нет: просто прибавляем к широте и долготе всех GSM данных материка и перерисовываем через равные интервалы времени.
А водная эрозия рельефа заложена в самом методе генерации.
Idot
Там, вроде бы, две зоны конвекции литосферы — та куда погружаются плиты, и та откуда они всплывают.
igor720
Да можно и без зон, если нужно только, чтобы было наблюдаемое движение материков.
Idot
Нужно чтобы генерировались длинные горные хребты = место столкновения материковых плит (и опционально «Марианские впадины» = там где океанические плиты расходятся). То есть то чего в данном алгоритме, как я понял, не хватает для большей реалистичности.
Иными словами, не хватает не столько самого движения материков в динамике, а сколько явно видимых результатов этого движения — в виде горных хребтов: как молодых и острых, так и старых и полуразрушенных.
Zenitchik
"Марианские впадины" — это зоны субдукции, а где плиты расходятся — это рифты.
igor720
В алгоритме действительно этого не предусмотрено. Но горные хребты могут быть реализованы без реализации дрейфа континентальных плит. Смотрите, например, программу Mojoworld (http://mojoworld.info/). Там есть реализация хребтов построенных с использованием теории турбулентности. Я сам еще не разбирался с этим, но обещаю, что когда разберусь, то сделаю хребты на картах.
Совсем необязательно привлекать сложную физическую теорию явления, если визуальный результат будет тем же самым, применяя простую модель. Так же, например, чтобы построить рельеф не требуется привлекать теорию процессов горообразования и выветривания. Ведь и фракталы дают хорошее изображение рельефа: есть много примеров горных долин, построенных с помощью фракталов, которые практически неотличимы от реальных.
trapwalker
Мне показалось, что автор вопроса про дрейф имел в виду особенности рельефа, вызванные дрейфом и наползанием литосферных плит. Это должно порождать характерные островные гряды, корные цепи, протяженные скалистые стены, вулканы…
Думаю тут пришлось бы городить куда более сложную геологическую модель. Например можно добавить нулевым этапом формирование литосферных плит и их небольшое сдвигание, чтобы сформировать базу, на которую будет напыляться уже основной рельеф.
Интересно было бы подумать о применении для этого нейронной сети. Уж очень здорово они такого рода задачки с изображениями сейчас проделывают.
Zenitchik
Я думаю, что сдвигать их не нужно. Достаточно обозначить направление их движения. А ещё нанести на карту рифты. Тогда по границам плит с учётом их относительного движения и характера (материковая/океаническая) можно заложить на первичной сетке высот характерные формы рельефа. Большего, мне кажется, не потребуется.
igor720
Zenitchik
А как вообще делаются горы?
Расположение хребтов и общее их направление я бы просто задал вдоль стыка плит и сообразно характеру их столкновения (там немного вариантов).
igor720
Любой рельеф местности по своей форме фрактал. А каждый тип местности отличает собственный тип фрактала. На планетах этого сайта я использовал везде один и тот же фрактал: и в низинах, и в горах. Это конечно не реалистично, и в будующем будет добавлено разнообразие. Горные хребты должны задаваться особой компонентой фрактала, которая сейчас мне не известна. На самом деле проблем еще очень много и более важных.
Idot
Нужно как-нибудь сгенерировать тектонические плиты.
Примерно вот так:
шаг 0 — генерим случайный лунный ландшафт
шаг 0.5 — метеоритная бомбардировка с целью получить метеоритные кратеры
шаг 1 — разбиваем на плиты
шаг 2 — сдвигаем => появятся горные хребты, рифты и субдукции
шаг 3 — заполняем водой
шаг 4 — производим эрозию с целью разрушения горных хребтов => получаем старые горы
шаг 5 — снова двигаем => получаем молодые горы
igor720
Все это хорошо, но Вы постоянно пропускаете шаг где требуется формировать рельеф гор.
Idot
Почему пропустил?
А ещё на шаге 0.5 можно ударить каким-нибудь супер-метеоритом.
PS субдукции — это в том числе и вулканы.
trapwalker
Вот не хватает «Profit!!!» в конце.
Я сперва вообще подумал, что это сарказм такой тонкий, мол, нужно всего лишь взорвать пару сверхновых, наделать кремния, кислорода, железа, углерода, потом за счет гравитации свалять из этого шарики, выбрать подходящий… Нужно где-то остановиться, у нас нет аких мощностей.
Хорошая идея уже звучала. Планету разбиваем на плиты, плитам даем импульс и вычисляем напряжения на узлах стыков. Получим ломанные линии с векторами напряжений в вершинах. Вот эти данные должны как-то влиять на превалирующую компоненту фрактальной функции. Хз как.
Idot
Попробую в выходные написать. Начну с лунного ландшафта, с шага 0.
(то есть континенты попробую создать на следующей неделе)
Idot
В прошлый выходной я оказался занят. Так что в эти выходные всё же попробую поднять мой старый проект 2005 года (попробовал запустить — падает, перекомпилил — все равно падает, буду разбираться).