Отделяем свет от тьмы. И другие способы сотворения мира
Давайте я пропущу все долгие предисловия по поводу того, как я докатился до такой жизни и прочая. Буквально пара слов предостережений и пойдем разбираться, как же делать миры.
Предостережения
В нашем мире любая вещь, особенно естественная, очень сложна. На каждый процесс влияют тысячи факторов, законов и возможностей. В полной мере все это отразить невозможно, даже положив на это всю жизнь. Я же занимался каждым аспектом программы ровно столько времени, чтобы достичь баланса “достаточно неплохо / лень дальше возиться”. Совершенно очевидно, что все можно сделать лучше, проще, реалистичнее или наоборот, делать вовсе не стоило. Так вот, забейте.
Подобных программ существует довольно много. И пишут их крайне интересные люди со своими взглядами на каждую деталь. У них можно почерпнуть уйму идей. Только вот копировать их не имеет смысла, так как главное не результат, а процесс.
Так что пойдемте посмотрим немного на процесс. Там будут в основном куски моих старых скриншотов, которыми я мучал всех, кто был готов смотреть.
Сначала была точка
Основная идея состоит в том, что карта — это множество “регионов” со своей высотой, типом местности и тому подобным. Для этого можно взять или квадратную сетку, что очень плохо, так как будет выглядеть кошмарно, или гексагональную, что куда лучше. Многие так и делают. Впрочем, спасибо русским ученым, у нас есть и другие варианты. Например, Диаграмма Вороного.
Сейчас будет некорректное, но, как мне кажется, понятное объяснение. Допустим, у нас есть лист бумаги. Бросим на него пару десятков маковых зернышек. Обведем каждое зернышко кружочком так, чтобы они не пересекались. А затем начнем “надувать” каждый, будто это воздушный шарик, до тех пор, пока на листе не останется пустого места.
Так у нас получаются случайные многоугольники, самой разной формы и площади, но в совершенно определенном количестве. Однако, многие понимают, что по-настоящему случайные вещи редко когда подходят для использования. Скорее всего, когда вы кидали мак на лист, он рассыпался крайне неравномерно, создав кучки и полностью пустые участки. Конечно, это не очень красиво смотрится. Благо и тут математики нас не подвели. Существует алгоритм Ллойда для, так называемой, “релаксации”. Заключается он в том, что точки сдвигаются в центроид многоугольника и диаграмма перестраивается. Это ведет к тому, что наше разбиение медленно, но верно стремится к гексагональному. В динамике это можно понаблюдать здесь.
Вот небольшой пример как смотрится карта без релаксации и с ней:
Стоит заметить, что это достаточно дорогая операция, так как по сути каждую итерацию диаграмма полностью перестраивается. Более того, библиотека которую я использую, частенько некорректно себя ведет в процессе. Кроме внезапных падений бывают ситуации, когда образуются многоугольники построенные так, что начальная точка лежит вне их контура. Приходится повторять итерации до тех пор, пока такой глюк не пропадет.
Из неприятного также хочется отметить тот факт, что прилегающие к краю регионы обычно отличаются по площади и форме от остальных.
Вглубь. Или ввысь.
Посмотрев на качество “настоящего рандома” приходит понимание, что для построения карты высот он не подойдет от слова совсем. Просто представьте, если у соседних регионов высота будет отличаться на 100 метров. Или на километр. И так у всех. Нет, это совершенно не годится.
Правда оно и в жизни совсем не случайно формируется. Тектонические плиты и вот это вот все. Некоторые учитывают и такие процессы. Может быть я тоже когда-нибудь осилю симуляцию формирования ландшафта. Но, если смириться с некоторыми ограничениями, можно воспользоваться другим инструментом, который уже многие годы держит первенство как генератор “достаточно хорошего” ландшафта. Я говорю о шуме Перлина. Наверное, это второй после сортировки алгоритм по частоте использования у игроделов.
Даже при самых простых настройках уже можно получить вот такую картинку:
Есть возможности комбинировать разные шумы, добавлять турбулентность и так далее, но главное то, что для каждой точки нашего региона мы будем знать высоту, которая не сильно отличается от соседних, но при этом уже напоминает реальный ландшафт.
Однако, раз мы решили (ну ладно, я решил), что у нас карта строится на регионах, внутри одного многоугольника нам не нужны все высоты. Нам нужна одна. Ну или N+1, где N — количество вершин многоугольника. Поэтому я поступаю так: считаю высоты у всех вершин и назначаю региону высоту равную среднеарифметическому. И вот у нас есть карта высот.
Избавлю вас от лицезрения промежуточных вариантов с вырвиглазными цветами, излишним шумом высот и малым количеством регионов и покажу уже что-то более приличное:
Правда вот тут придется откатиться немного назад. Последующая работа показала, что работать с массивом многоугольников, да еще и таких хитрых, очень сложно. Во-первых, если отсортировать их, допустим по координате Х, из-за их сложной формы можно получить совсем неожиданный порядок. Во-вторых, как нам понять, что десятый, 835-ый и 6.100-ый регион являются частью одной и той же горы. Или что две точки на рисунке выше, хоть и разделены морем, на самом деле на одном и том же острове.
Значит нам надо подняться на один уровень абстракции выше. В этом нам помогут кластеры. На самом деле, в коде есть три вида кластеров, хотя все они являются одним классом: кластеры, мега-кластеры и государственный кластер. Ух, как сложно переводить на русский названия классов.
Начнем с мега-кластеров, чтобы объяснить методику. Еще до получения картинки выше мы пробегаем по всем регионам и смотрим на их высоту. Если она выше “уровня моря”, то помечаем регион как “сушу”, иначе — как “море”. Наивно полагать, что мы добились своего, так как у нас вполне может быть несколько изолированных морей, не говоря уже про острова. Поэтому начинаем кластеризацию.
Наверняка, есть более быстрые и удачные алгоритмы, но я решил родить свой. Если в общих чертах, то мы снова бежим по регионам и смотрим их соседей, если они того же “вида”, то есть тоже суша, например, то спрашиваем, не знает ли он свой кластер. Если мы не нашли ни одного региона с кластером, то создаем новый. Если кто-то знает, то присоединяемся к его кластеру. Но есть проблема. Из-за указанных выше сложностей с сортировкой может случиться ситуация, когда у нескольких соседей разные кластеры, хотя они и одного вида. Тогда мы просто всех отличающихся переносим в один кластер, а старые удаляем. Долго ли, коротко ли, а у нас получились моря и острова.
И казалось бы, самое время сделать горы и леса. Когда-то так и было. Но потом я добавил влажность и температуру. Ими и займемся, так как они прямо влияют на то, луг у нас будет или пустыня.
Наяды
Итак, нам нужны реки. Берем кластеры суши размером более 50и регионов (ну вот почему-то я так решил) и находим локальные максимумы высоты. То есть регионы, высоты соседей у которых меньше его высоты. И выбираем те, которые выше ну какой-то эмпирически найденной высоты. Это наши возвышенности и точки зарождения рек.
Дальше все просто: мы просматриваем соседей и перемещаемся в низшую точку. Если доползли до моря, останавливаемся, если нет — делаем озеро. Будем считать, что мы просто не учитываем более мелкие реки, хотя если вдруг реки начавшиеся в разных местах попадают в один и тот же регион, далее они идут по одному пути.
Форма рек получается довольно извилистой. Вроде как это нормально, но на картах большого масштаба обычно такие вещи скрадываются, поэтому я немного их “упрощаю”. Для этого идем по уже выбранным точкам и смотрим на расстояние до “следующей” и до “через одну”. Если до “через одну” ближе, то выкидываем “следующую”. Так остается извилистость, но пропадают совсем уж узкие и длинные “вилюшки”.
Отрисовываю я их сплайном, то есть кривой, которая аппроксимируется до плавно извивающейся. Более того, я увеличиваю ее толщину по мере приближения к конечной точке. Выглядит не волшебно, но жить можно. Главное, что регионы по которым проходит река получают флаг “имеет реку” и увеличивает уровень плодородия, который потом будет использован для размещения аграрных городов.
Кстати, у аппроксимации сплайна есть недостаток: когда две реки сливаются в одну из-за того, что они подходят к одной точке с разных сторон, кривые несколько раз расходятся перед тем как объединиться. Реки так, конечно же, не умеют.
Влажность
Да, для формирования климата явно не хватает ветра и течений. Может быть руки дойдут, если я придумаю, как сделать это не слишком сложно.
Итак, скачем по регионам, назначая воде максимальную влажность, и прибавляя немного регионам с рекой.
Затем идем сначала, но уже только по суше, увеличивая влажность соседям рек и озер, а также в зависимости от перепада высоты корректируем влажность с соседями. Таким образом получается, что влажность меняется плавно, уменьшаясь по удалению от воды. И из-за учета перепада высоты, меняется с разной скоростью в горах и низинах.
Температура
Не скажу, что мне нравится моя реализация, но руки не доходят переделать. Сейчас это работает крайне просто: есть базовая температура, которая корректируется на влажность и высоту. Таким образом на побережье прохладнее, в горах холодно, а в глубине острова, вдали от рек может быть настоящая жара. В нашем мире все намного сложнее, но этому мирку пока хватает такого простого решения.
Подземные короли
С полезными ископаемыми я поступил еще проще. Вспоминая божественную Dwarf Fortress я понимаю, насколько много можно всего сделать по поводу ресурсов, но было лень концентрироваться именно на этом. Поэтому я тем же шумом Перлина сгенерировал карту, значения которой использовал не как высоту региона, а как уровень его богатства абстрактными полезными ископаемыми.
Я описал этот шаг сейчас, так как именно в таком порядке у меня они происходят в коде, однако следующий шаг не использует данные о ресурсах.
Биомы. Леса, степи и прочие горы
Наконец настала пора определить биомы для регионов. Биом — это тип растительности и ландшафта. Чтобы лучше это понять можно посмотреть карту биомов Земли. Самое простое решение — это выбирать биом исходя из высоты. Что, собственно, я и делаю для основных десяти биомов. На самом деле четыре из них обозначают глубину и используются только для отображения на карте.
Для средней высоты есть зависимость от влажности и температуры, что позволяет использовать дополнительные биомы, такие как “дождевые леса”, “прерии”, “пустыни” и прочие.
В этот же момент считается такой параметр как “комфортность” климата, который означает, насколько приятно в этом регионе жить. Это также будет влиять на то, насколько здесь благоприятная обстановка для земледелия.
Затем я делаю очередную кластеризацию, теперь уже по типу биома. Так у меня появляются списки лесов, гор и тому подобное.
Урбанизируем
Теперь, когда у нас есть климат и ресурсы, вычислить места для шахтерских или фермерских поселений не составляет труда.
Шахты ставим там, где много полезных ископаемых, а фермы — там где комфортно и плодородность биома достаточно высока. Плодородность я как-то умозрительно проставил и она увеличивается рядом с реками и озерами.
А вот с портовыми городами все несколько хитрее. Ясное дело, что нет смысла ставить их по всему побережью. Да и есть у них определенные требования. Например глубина и защищенность от волн, иначе ни один корабль не сможет причалить.
Найти тех, у кого глубокий сосед проще простого, а вот с защищенностью от волн все хитрее. Нам подойдут точки расположенные в бухтах и проливах. Их можно определить посчитав водные регионы на некотором расстоянии расстоянии. Понятное дело, что на побережье эта метрика будет равна примерно половине возможного значения (то есть полного круга), а вот в бухтах у нас вместо полукруга будет сектор, а в проливе круг будет обрезаться противоположным берегом.
Правда приходится делать еще одну итерацию основания портовых поселений: если на острове есть город, но нет порта, его нужно поставить, даже если место не очень удачное.
Города есть. А государства?
А вот тут все оказалось сложно. Ну то есть базовая идея проста: берем две случайные точки и строим диаграмму Вороного. Так мы делим карту на две части. При том так, что у нас случайные площади и направление. Нередки варианты, что на карте остается всего одно государство. Это все отлично. Но есть проблемы.
Деление прямой линией часто приводит к нежелательным ситуациям: небольшие или не имеющие городов анклавы на краю острова. Поэтому следует сделать еще одну кластеризацию, теперь уже по государству. И если кластер небольшой, то его надо присоединить к большому соседу. Осталось сделать так, чтобы оставшиеся на суше границы проходили не по прямой, а как-то более естественно, например, прилипая к границам биомных кластеров. Но это в будущем.
На этом заканчивается первоначальное генерирование карты. Если у меня хватит запала, напишу еще про отрисовку всего этого добра и режим симуляции, над которым я активно работаю. Там будут и дороги и экономика и прочие прелести. А пока, спасибо за внимание.
UPD: запала зватило еще на Вторую и Третью части.
Вот тут можно скачать Win версию генератора. Так как я пишу под linux, эта версия нестабильна и отстает от актуальной, но желающие могут потыкать. Для остальных выкладываю короткое видео карты после симуляции:
