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