Программисты — ленивые существа с тонкой душевной организацией, что помогает нам находить простые и красивые решения задач с минимальными затратами. В этой статье мы создадим реалистичный ландшафт с помощью алгоритма «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»