Одна из самых популярных статей на моём сайте посвящена генерации полигональных карт (перевод на Хабре). Создание таких карт требует много усилий. Но начинал я не с этого, а с гораздо более простой задачи, которую опишу здесь. Эта простая техника позволяет создавать подобные карты меньше чем в 50 строках кода:


Я не буду объяснять, как отрисовывать такие карты: это зависит от языка, графической библиотеки, платформы и т.д. Я просто объясню, как заполнить массив данными карты.

Шум

Стандартный способ генерации 2D-карт заключается в использовании в качестве строительного блока функции шума с ограниченной полосой частот, например шума Перлина или симплексного шума. Вот, как выглядит функция шума:


Мы присваиваем каждой точке карты число от 0.0 до 1.0. В этом изображении 0.0 — это чёрный цвет, а 1.0 — белый. Вот как задать цвет каждой точке сетки в синтаксисе похожего на C языка:

for (int y = 0; y < height; y++) {
  for (int x = 0; x < width; x++) {      
    double nx = x/width - 0.5, ny = y/height - 0.5;
    value[y][x] = noise(nx, ny);
  }
}

Цикл будет работать одинаково в Javascript, Python, Haxe, C++, C#, Java и большинстве других популярных языков, поэтому я покажу его в C-подобном синтаксисе, чтобы вы могли преобразовать его в нужный вам язык. В оставшейся части туториала я покажу, как изменяется тело цикла (строка value[y][x]=…) при добавлении новых функций. В демо будет показан полный пример.

В некоторых библиотеках необходимо будет сдвигать или умножать получаемые значения, чтобы возвратить их в интервал от 0.0 до 1.0.

Высота

Сам по себе шум — это просто набор чисел. Нам нужно наделить его смыслом. Первое, о чём можно подумать — привязать значение шума к высоте (это называется «картой высот»). Давайте возьмём показанный выше шум и отрисуем его как высоты:



Код остался почти таким же, за исключением внутреннего цикла. Теперь он выглядит так:

elevation[y][x] = noise(nx, ny);

Да, и это всё. Данные карты остались такими же, но теперь я буду называть их elevation (высотой), а не value.

У нас получилось много холмов, но ничего больше. Что не так?

Частота

Шум может генерироваться при любой частоте. Пока я выбирал только одну частоту. Давайте посмотрим, как она влияет.

Попробуйте изменять значение ползунком (в оригинале статьи) и посмотрите, что происходит при разных частотах:


Здесь просто меняется масштаб. Сначала это кажется не очень полезным, но это не так. У меня есть ещё один туториал (перевод на Хабре), в котором объясняется теория: такие понятия, как частота, амплитуда, октавы, розовый и синий шум, и так далее.

elevation[y][x] = noise(freq * nx, freq * ny);

Также иногда полезно вспомнить о длине волны, являющейся обратной частоте величиной. При удвоении частоты размер всего вдвое уменьшается. Удвоение длины волны всё вдвое увеличивается. Длина волны — это расстояние, измеряемое в пикселях/тайлах/метрах или любых других единицах, которые вы выбрали для карт. Она связана с частотой: wavelength = map_size / frequency.

Октавы

Чтобы сделать карту высот интереснее, мы добавим шум с разными частотами:

elevation[y][x] =    1 * noise(1 * nx, 1 * ny);
                +  0.5 * noise(2 * nx, 2 * ny);
                + 0.25 * noise(4 * nx, 2 * ny);

Давайте смешаем в одной карте большие низкочастотные холмы с мелкими высокочастотными холмами. Перемещайте ползунок (в оригинале статьи), чтобы добавлять в смешение мелкие холмы:


Теперь это гораздо больше походит на нужный нам фрактальный рельеф! Мы можем получить холмы и неровные горы, но у нас по-прежнему нет плоских равнин. Для этого нужно что-то ещё.

Перераспределение

Функция шума даёт нам значения в интервале от 0 и 1 (или от -1 до +1, в зависимости от библиотеки). Чтобы создать плоские равнины, мы можем возвести высоту в степень. Перемещайте ползунок (в оригинале статьи), чтобы получать разные степени.

e =    1 * noise(1 * nx, 1 * ny);
  +  0.5 * noise(2 * nx, 2 * ny);
  + 0.25 * noise(4 * nx, 4 * ny);
elevation[y][x] = Math.pow(e, exponent);

Высокие значения опускают средние высоты в равнины, а низкие значения поднимают средние высоты в сторону горных пиков. Нам нужно опустить их. Я использую степенные функции, потому что они проще, но вы можете использовать любую кривую; у меня есть более сложное демо.

Теперь, когда у нас есть реалистичная карта высот, давайте добавим биомы!

Биомы

Шум даёт числа, но нам нужна карта с лесами, пустынями и океанами. Первое, что можно сделать — превратить малые высоты в воду:

function biome(e) {
    if (e < waterlevel) return WATER;
    else return LAND;
}

Ого, это уже становится похоже на процедурно сгенерированный мир! У нас есть вода, трава и снег. Но что, если нам понадобится больше? Давайте сделаем последовательность из воды, песка, травы, леса, саванны, пустыни и снега:



Рельеф на основании высоты

function biome(e) {
  if (e < 0.1) return WATER;
  else if (e < 0.2) return BEACH;
  else if (e < 0.3) return FOREST;
  else if (e < 0.5) return JUNGLE;
  else if (e < 0.7) return SAVANNAH;
  else if (e < 0.9) return DESERT;
  else return SNOW;
}

Ух ты, выглядит здорово! Для своей игры можете поменять значения и биомы. В Crysis будет намного больше джунглей; в Skyrim намного больше льда и снега. Но как бы вы ни меняли числа, такой подход довольно ограничен. Типы рельефа соответствуют высотам, поэтому формируют полосы. Чтобы сделать их интереснее, нам нужно выбирать биомы на основе чего-то другого. Давайте создадим вторую карту шума для влажности.



Сверху — шум высот; снизу — шум влажности

Теперь давайте используем высоту и влажность вместе. На первом показанном ниже изображении ось y — это высота (взятая из изображения выше), а ось x — влажность (второе изображение выше). Это даёт нам убедительную карту:



Рельеф на основании двух значений шума

Малые высоты — это океаны и побережья. Большие высоты каменистые и заснеженные. В промежутке между ними мы получаем широкий диапазон биомов. Код выглядит так:

function biome(e, m) {      
  if (e < 0.1) return OCEAN;
  if (e < 0.12) return BEACH;
  
  if (e > 0.8) {
    if (m < 0.1) return SCORCHED;
    if (m < 0.2) return BARE;
    if (m < 0.5) return TUNDRA;
    return SNOW;
  }

  if (e > 0.6) {
    if (m < 0.33) return TEMPERATE_DESERT;
    if (m < 0.66) return SHRUBLAND;
    return TAIGA;
  }

  if (e > 0.3) {
    if (m < 0.16) return TEMPERATE_DESERT;
    if (m < 0.50) return GRASSLAND;
    if (m < 0.83) return TEMPERATE_DECIDUOUS_FOREST;
    return TEMPERATE_RAIN_FOREST;
  }

  if (m < 0.16) return SUBTROPICAL_DESERT;
  if (m < 0.33) return GRASSLAND;
  if (m < 0.66) return TROPICAL_SEASONAL_FOREST;
  return TROPICAL_RAIN_FOREST;
}

При необходимости можете изменять все эти значения в соответствии с требованиями своей игры.

Если же нам не нужны биомы, то плавные градиенты (см. эту статью) могут создавать цвета:



И для биомов, и для градиентов одно значение шума не обеспечивает достаточной вариативности, но двух вполне достаточно.

Климат

В предыдущем разделе я использовал высоту как замену температуры. Чем больше высота, тем ниже температуры. Однако на температуры также влияет географическая широта. Давайте используем для контроля температуры и высоту, и широту:


Рядом с полюсами (большие широты) климат холоднее, а на вершинах гор (большие высоты) климат тоже холоднее. Пока я проработал это не очень сильно: для правильного подхода к этим параметрам нужно множество тонких настроек.

Также существует сезонное изменение климата. Летом и зимой северное и южное полушарие становятся теплее и холоднее, но на экваторе ситуация особо не меняется. Здесь тоже можно сделать многое, например, можно смоделировать преобладающие ветра и океанские течения, влияние биомов на климат и усредняющее влияние океанов на температуры.

Острова

В некоторых проектах мне было нужно, чтобы границы карты были водой. Это превращает мир в один или несколько островов. Существует множество способов сделать это, но в своём генераторе полигональных карт я использовал довольно простое решение: я изменял высоту как e = e + a - b*d^c, где d — расстояние от центра (в масштабе 0-1). Ещё один вариант заключается в изменении e = (e + a) * (1 - b*d^c). Константа a поднимает всё вверх, b опускает края вниз, а c управляет скоростью снижения.


Я не совсем доволен этим и ещё многое предстоит исследовать. Должно ли это быть манхэттанское или эвклидово расстояние? Должно ли оно зависеть от расстояния до центра или от расстояния до края? Должно ли расстояние возводиться в квадрат, или быть линейным, или иметь какую-то другую степень? Должно ли это быть сложение/вычитание, или умножение/деление, или что-то ещё? В оригинале статьи попробуйте Add, a = 0.1, b = 0.3, c = 2.0 или попробуйте Multiply, a = 0.05, b = 1.00, c = 1.5. Подходящие вам параметры зависят от вашего проекта.

Зачем вообще придерживаться стандартных математических функций? Как я рассказал в своей статье об уроне в RPG (перевод на Хабре), все (в том числе и я) пользуются математическими функциями, такими как многочлены, показательные распределения и т.п., но на компьютере мы можем ими не ограничиваться. Мы можем взять любую функцию формирования и использовать её здесь, воспользовавшись таблицей поиска e = e + height_adjust[d]. Пока этот вопрос я не изучал.

Остроконечный шум

Вместо возведения высоты в степень, мы можем использовать абсолютное значение, чтобы создать острые пики:

function ridgenoise(nx, ny) {
  return 2 * (0.5 - abs(0.5 - noise(nx, ny)));
}

Чтобы добавить октавы, мы можем варьировать амплитуды больших частот, чтобы добавленный шум получали только горы:

e0 =    1 * ridgenoise(1 * nx, 1 * ny);
e1 =  0.5 * ridgenoise(2 * nx, 2 * ny) * e0;
e2 = 0.25 * ridgenoise(4 * nx, 4 * ny) * (e0+e1);
e = e0 + e1 + e2;
elevation[y][x] = Math.pow(e, exponent);

У меня не такой большой опыт работы с этой техникой, поэтому мне нужно поэкспериментировать, чтобы научиться хорошо ею пользоваться. Возможно, будет интересно также смешать остроконечный низкочастотный шум с неостроконечным высокочастотным.

Террасы

Если мы округлим высоту до ближайших n уровней, мы получим террасы:


Это результат применения функции перераспределения высот в виде e = f(e). Выше мы использовали e = Math.pow(e, exponent), чтобы сделать резче горные пики; здесь мы используем e = Math.round(e * n) / n для создания террас. Если использовать не ступенчатую функцию, то террасы могут быть округлей или возникать только на некоторых высотах.

Размещение деревьев

Обычно мы использовали фрактальный шум для высоты и влажности, но его можно применять и для размещения неравномерно расставленных объектов, таких как деревья и камни. Для высоты мы используем высокие амплитуры с низкими частотами («красный шум»). Для размещения объектов нужно использовать высокие амплитуды с высокими частотами («синий шум»). Слева показан паттерн синего шума; справа показаны места, где шум больше соседних значений:

for (int yc = 0; yc < height; yc++) {
  for (int xc = 0; xc < width; xc++) {
    double max = 0;
    // существуют более эффективные алгоритмы
    for (int yn = yc - R; yn <= yc + R; yn++) {
      for (int xn = xc - R; xn <= xc + R; xn++) {
        double e = value[yn][xn];
        if (e > max) { max = e; }
      }
    }
    if (value[yc][xc] == max) {
      // размещаем дерево в xc,yc
    }
  }
}

Выбирая для каждого биома разные R, мы можем получить переменную плотность деревьев:



Здорово, что такой шум можно использовать для размещения деревьев, но часто более эффективны и создают более равномерное распределение другие алгоритмы: пятна Пуассона, плитки Вана или графический дизеринг.

В бесконечность и дальше

Вычисления биома в позиции (x,y) не зависят от вычислений всех других позиций. Это локальное вычисление обладает двумя удобными свойствами: его можно вычислять параллельно, и его можно использовать для бесконечного рельефа. Поместите курсор мыши на миникарту (в оригинале статьи) слева, чтобы сгенерировать карту справа. Можно генерировать любую часть карты без генерации (и даже без хранения) всей карты.

Реализация

Использование шума для генерации рельефа — популярное решение, и в Интернете можно найти туториалы для множества разных языков и платформ. Код генерации карты на разных языках примерно одинаков. Вот простейший цикл на трёх разных языках:

• Javascript:
  
  

  let gen = new SimplexNoise();
  function noise(nx, ny) {
    // Rescale from -1.0:+1.0 to 0.0:1.0
    return gen.noise2D(nx, ny) / 2 + 0.5;
  }
  
  let value = [];   
  for (let y = 0; y < height; y++) {
    value[y] = [];
    for (let x = 0; x < width; x++) {      
      let nx = x/width - 0.5, ny = y/height - 0.5;
      value[y][x] = noise(nx, ny);
    }
  }

• C++:
  
  

  module::Perlin gen;
  double noise(double nx, double ny) {
    // Rescale from -1.0:+1.0 to 0.0:1.0
    return gen.GetValue(nx, ny, 0) / 2.0 + 0.5;
  }
  
  double value[height][width];
  for (int y = 0; y < height; y++) {
    for (int x = 0; x < width; x++) {
      double nx = x/width - 0.5, 
               ny = y/height - 0.5;
      value[y][x] = noise(nx, ny);
    }
  }

• Python:
  
  

  from opensimplex import OpenSimplex
  gen = OpenSimplex()
  def noise(nx, ny):
      # Rescale from -1.0:+1.0 to 0.0:1.0
      return gen.noise2d(nx, ny) / 2.0 + 0.5
  
  value = []
  for y in range(height):
      value.append([0] * width)
      for x in range(width):
          nx = x/width - 0.5
          ny = y/height - 0.5
          value[y][x] = noise(nx, ny)

Все библиотеки шума довольно похожи друг на друга. Попробуйте opensimplex для Python, или libnoise для C++, или simplex-noise для Javascript. Для большинства популярных языков существует множество библиотек шума. Или же вы можете изучить, как работает шум Перлина или реализовать шум самостоятельно. Я этого не делал.

В разных библиотеках шума для вашего языка подробности применения могут слегка различаться (некоторые возвращают числа в интервале от 0.0 до 1.0, другие — в интервале от -1.0 до +1.0), но основная идея одинакова. Для реального проекта вам может потребоваться обернуть функцию noise и объект gen в класс, но эти подробности не относятся к делу, поэтому я сделал их глобальными.

Для такого простого проекта не важно, какой шум вы используете: шум Перлина, симплексный шум, шум OpenSimplex, value noise, смещение средних точек, алгоритм diamond или обратное преобразование Фурье. У каждого из них есть свои плюсы и минусы, но для подобного генератора карт все они создают более-менее одинаковые выходные значения.

Отрисовка карты зависит от платформы и игры, поэтому её я не реализовал; этот код нужен только для генерации высот и биомов, отрисовка которых зависит от использованного в игре стиля. Можете копировать, портировать и использовать его в своих проектах.

Эксперименты

Я рассмотрел смешивание октав, возведение высоты в степень и комбинирование высоты с влажностью для получения биома. Здесь можно изучить интерактивный график, позволяющий поэкспериментировать со всеми этими параметрами, который показывает, из чего состоит код:


Вот пример кода:

var rng1 = PM_PRNG.create(seed1);
var rng2 = PM_PRNG.create(seed2);
var gen1 = new SimplexNoise(rng1.nextDouble.bind(rng1));
var gen2 = new SimplexNoise(rng2.nextDouble.bind(rng2));
function noise1(nx, ny) { return gen1.noise2D(nx, ny)/2 + 0.5; }
function noise2(nx, ny) { return gen2.noise2D(nx, ny)/2 + 0.5; }
   
for (var y = 0; y < height; y++) {
  for (var x = 0; x < width; x++) {      
    var nx = x/width - 0.5, ny = y/height - 0.5;
    var e = (1.00 * noise1( 1 * nx,  1 * ny)
           + 0.50 * noise1( 2 * nx,  2 * ny)
           + 0.25 * noise1( 4 * nx,  4 * ny)
           + 0.13 * noise1( 8 * nx,  8 * ny)
           + 0.06 * noise1(16 * nx, 16 * ny)
           + 0.03 * noise1(32 * nx, 32 * ny));
    e /= (1.00+0.50+0.25+0.13+0.06+0.03);
    e = Math.pow(e, 5.00);
    var m = (1.00 * noise2( 1 * nx,  1 * ny)
           + 0.75 * noise2( 2 * nx,  2 * ny)
           + 0.33 * noise2( 4 * nx,  4 * ny)
           + 0.33 * noise2( 8 * nx,  8 * ny)
           + 0.33 * noise2(16 * nx, 16 * ny)
           + 0.50 * noise2(32 * nx, 32 * ny));
    m /= (1.00+0.75+0.33+0.33+0.33+0.50);
    /* draw biome(e, m) at x,y */
  }
}

Здесь есть сложность: для шума высот и влажности необходимо использовать разный seed, в противном случае они окажутся одинаковыми, и карты будут выглядеть не так интересно. В Javascript я использую библиотеку prng-parkmiller; в C++ можно использовать два отдельных объекта linear_congruential_engine; в Python можно создать два отдельных экземпляра random.Random class.

Мысли

Этот подход к генерации карт мне нравится своей простотой. Он быстр и требует очень мало кода для создания приличных результатов.

Не нравится мне в этом подходе его ограниченность. Локальные вычисления означают, что каждая точка независима от всех других. Разные области карты не связаны друг с другом. Каждое место на карте «кажется» одинаковым. Здесь не существует глобальных ограничений, например «на карте должно быть от 3 до 5 озёр» или глобальных характерных особенностей, например реки, текущей с вершины высочайшего пика в океан. Также мне не нравится то, что для получения хорошей картинки нужно долго настраивать параметры.

Почему же я его рекомендую? Я считаю, что это хорошая отправная точка, особенно для инди-игр и гейм-джемов. Двое моих друзей написали первоначальную версию Realm of the Mad God всего за 30 дне для игрового конкурса. Они попросили меня помочь в создании карт. Я использовал эту технику (плюс ещё несколько функций, оказавшихся не особо полезными) и сделал им карту. Через несколько месяцев, получив отзывы игроков и внимательнее изучив дизайн игры, мы создали более продвинутый генератор карт на основе многоугольников Вороного, описанный здесь (перевод на Хабре). В этом генераторе карт не используются описанные в данной статье техники. В нём шум для создания карт применяется совсем по-другому.

Дополнительная информация

Существует множество крутых вещей, которые можно сделать с помощью функций шума. Если поискать в Интернете, то можно найти такие варианты, как turbulence, billow, ridged multifractal, amplitude damping, terraced, voronoi noise, analytical derivatives, domain warping и другие. Можно использовать эту страницу как источник вдохновения. Здесь я их не рассматриваю, моя статья сосредоточена на простоте.

На этот проект повлияли мои предыдущие проекты генерации карт:

• Я использовал общий шум Перлина для моего первого генератора карт игры Realm of the Mad God. Мы использовали его для первых шести месяцев альфа-тестирования, а затем заменили его на генератор карт на многоугольниках Вороного, специально созданный под требования геймплея, определённые нами в процессе альфа-тестирования. Биомы и их цвета для статьи взяты из этих проектов.
• При изучении обработки звуковых сигналов я написал туториал по шуму, в котором объясняются такие концепции, как частота, амплитуда, октавы и «цвет» шума. Те же концепции, работающие для звука, также применимы для генерации карт на основе шума. В то время я создал несколько сырых демо генерации рельефа, но так их и не доделал.
• Иногда я экспериментирую, чтобы найти границы. Я хотел узнать, сколько кода минимально необходимо для создания убедительных карт. В этом минипроекте я дошёл до нуля строк кода — всё делается фильтрами изображений (турбулентность, пороги, цветовые градиенты). Это меня и порадовало, и огорчило. В какой степени генерация карт может выполняться фильтрами изображений? В достаточно большой. Всё, рассказанное выше о «схеме плавных цветовых градиентов» взято из этого эксперимента. Слой шума — это фильтр изображения «турбулентность»; октавы — это изображения, наложенные друг на друга; инструмент степени называется в Photoshop «коррекция кривых».

Меня немного напрягает то, что бОльшая часть кода, которую пишут разработчики игр для генерации рельефа на основе шума (в том числе и смещение средней точки (midpoint displacement)), оказывается той же, что и в фильтрах звука и изображений. С другой стороны, он создаёт вполне достойные результаты всего в нескольких строках кода, поэтому я и написал данную статью. Это быстрая и простая опорная точка. Обычно я не использую такие карты долго, а заменяю их на более сложный генератор карт, как только узнаю, какие типы карт лучше подойдут к дизайну игры. Для меня это является стандартным паттерном: начинать с чего-то чрезвычайно простого, а потом заменять это только после того, как я лучше пойму систему, с которой работаю.

Есть ещё множество штук, которые можно проделать с шумом, в статье я упомянул лишь несколько. Попробуйте Noise Studio, чтобы интерактивно протестировать различные возможности.