Создаем реалистичный ландшафт за 130 строк кода на JavaScript

Программисты — ленивые существа с тонкой душевной организацией, что помогает нам находить простые и красивые решения задач с минимальными затратами. В этой статье мы создадим реалистичный ландшафт с помощью алгоритма «diamond-square». Мы не будем долго прорисовывать вручную каменистый рельеф, который в итоге, скорее всего, окажется весьма убогим. Вместо этого, благодаря генерации фракталов, мы научим компьютер, что значит быть камнем.

Карта высот

Будем хранить ландшафт в виде карты высот — двумерного массива, в котором содержится информация о высоте каждой точки местности по координатам x и y. С помощью этой простой структуры данных можно визуализировать высоту как угодно — с Canvas, WebGL и т.д. Основное ограничение состоит в том, что мы не можем отображать вертикальные отверстия ландшафта, такие как пещеры или туннели.

function Terrain(detail) {
  this.size = Math.pow(2, detail) + 1;
  this.max = this.size - 1;
  this.map = new Float32Array(this.size * this.size);
}

Этот алгоритм можно применять к сетке любого размера, но удобнее всего использовать квадрат размера степени двойки + 1. Мы будем использовать одно и то же значение size для осей x, y и z, оформляя наш ландшафт в куб. Конвертируем detail в степень двойки + 1, чтобы при более подробной детализации генерировались кубы большего размера.

Алгоритм

Возьмём квадрат. Разделим его ещё на четыре квадрата и сдвинем их центры вверх или вниз случайным образом. Разделим каждый из них ещё на квадраты и повторим, раз за разом уменьшая диапазон случайного сдвига для получения более мелких деталей.

Это алгоритм «diamond-square». В нашем случае он немного усовершенствован для получения более реалистичного результата: пространство попеременно делится на квадраты (squares) и ромбы (diamonds).

Устанавливаем углы

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

this.set(0, 0, self.max / 2);
this.set(this.max, 0, self.max / 2);
this.set(this.max, this.max, self.max / 2);
this.set(0, this.max, self.max / 2);

Делим карту

Теперь будем рекурсивно наблюдать за все более малыми делениями карты высот. При каждом делении мы будем разбивать карту на квадраты и обновлять положение центральной точки каждого из них во время фазы «square». Потом мы разделим карту на ромбы и обновим их центральные точки на этапе «diamond».

divide(this.max);

function divide(size) {
  var x, y, half = size / 2;
  var scale = roughness * size;
  if (half < 1) return;

  for (y = half; y < self.max; y += size) {
    for (x = half; x < self.max; x += size) {
      square(x, y, half, Math.random() * scale * 2 - scale);
    }
  }
  for (y = 0; y <= self.max; y += half) {
    for (x = (y + half) % size; x <= self.max; x += size) {
      diamond(x, y, half, Math.random() * scale * 2 - scale);
    }
  }
  divide(size / 2);
}

Использование переменной scale гарантирует, что величина сдвигов уменьшается вместе с величиной делений. Для каждого деления мы умножаем текущий размер на коэффициент неровности roughness, который определяет, будет ландшафт гладким (значения около 0) или гористым (значения около 1).

Формы

Обе формы (square и diamond) работают по одному принципу, но получают данные из разных точек. На фазе square перед случайным сдвигом мы находим среднее от четырех угловых точек, а на фазе diamond — от четырех точек на ребрах.

function diamond(x, y, size, offset) {
  var ave = average([
    self.get(x, y - size),      // top
    self.get(x + size, y),      // right
    self.get(x, y + size),      // bottom
    self.get(x - size, y)       // left
  ]);
  self.set(x, y, ave + offset);
}

Визуализация

Этот алгоритм лишь даёт нам данные, которые мы уже можем визуализировать разными способами. Здесь мы совместим несколько техник для создания растровой изометрической 3D-проекции ландшафтной карты на сетке.

Задом наперёд

Сначала мы создаём вложенные циклы, которые вытаскивают прямоугольники с «задней части» нашей карты (y = 0) «вперёд» (y = this.size). Такой же цикл мы бы использовали для визуализации простого плоского квадрата.

for (var y = 0; y < this.size; y++) {
  for (var x = 0; x < this.size; x++) {
    var val = this.get(x, y);
    var top = project(x, y, val);
    var bottom = project(x + 1, y, 0);
    var water = project(x, y, waterVal);
    var style = brightness(x, y, this.get(x + 1, y) - val);

    rect(top, bottom, style);
    rect(water, bottom, 'rgba(50, 150, 200, 0.15)');
  }
}

Светотени

Наш непритязательный подход обеспечивает красивую визуальную текстуру. Мы сравниваем текущую высоту с высотой следующей точки, чтобы вычислить склон. И рисуем более яркие прямоугольники для более высоких склонов, чтобы заполнить одну сторону светом, а другую — тенью.

var b = ~~(slope * 50) + 128;
return ['rgba(', b, ',', b, ',', b, ',1)'].join('');

Изометрическая проекция

Визуально интереснее перевести наш ландшафт из фазы «square» в фазу «diamond» прежде чем делать его 3D-проекцию. Изометрическая проекция сводит верхний левый и нижний правый углы в центр изображения.

function iso(x, y) {
  return {
    x: 0.5 * (self.size + x - y),
    y: 0.5 * (x + y)
  };
}

Центральная (перспективная) проекция

Мы будем использовать столь же простую 3D-проекцию для конвертации значений x, y и z в плоскую картинку с перспективой на 2D-экране.

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

  function project(flatX, flatY, flatZ) {
    var point = iso(flatX, flatY);
    var x0 = width * 0.5;
    var y0 = height * 0.2;
    var z = self.size * 0.5 - flatZ + point.y * 0.75;
    var x = (point.x - self.size * 0.5) * 6;
    var y = (self.size - point.y) * 0.005 + 1;

    return {
      x: x0 + x / y,
      y: y0 + z / y
    };
  }
};

Собираем воедино

Создаем новый экземпляр Terrain с необходимым уровнем детализации. Затем генерируем его карту высот со значением неровности (roughness) между 0 и 1. Наконец, переносим ландшафт на сетку.

var terrain = new Terrain(9);
terrain.generate(0.7);
terrain.draw(canvasContext, width, height);

Можно посмотреть результат на сайте автора, а также изучить код на GitHub.

Если вам интересна разработка ландшафтов, советуем почитать наш перевод руководства «Создание ландшафта на Unity за 24 часа».

Перевод статьи «Realistic terrain in 130 lines»

Как Яндекс использует ваши данные и машинное обучение для персонализации сервисов — читать и смотреть YaC 2019.