Программисты — ленивые существа с тонкой душевной организацией, что помогает нам находить простые и красивые решения задач с минимальными затратами. В этой статье мы создадим реалистичный ландшафт с помощью алгоритма «diamond-square». Мы не будем долго прорисовывать вручную каменистый рельеф, который в итоге, скорее всего, окажется весьма убогим. Вместо этого, благодаря генерации фракталов, мы научим компьютер, что значит быть камнем.
Карта высот
Будем хранить ландшафт в виде карты высот — двумерного массива, в котором содержится информация о высоте каждой точки местности по координатам x и y. С помощью этой простой структуры данных можно визуализировать высоту как угодно — с Canvas, WebGL и т.д. Основное ограничение состоит в том, что мы не можем отображать вертикальные отверстия ландшафта, такие как пещеры или туннели.
1 2 3 4 5 | 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, которое повлияет на остальную визуализацию. Код ниже поднимет все углы на половину высоты куба:
1 2 3 4 | 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».
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | 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 — от четырех точек на ребрах.
1 2 3 4 5 6 7 8 9 | 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). Такой же цикл мы бы использовали для визуализации простого плоского квадрата.
1 2 3 4 5 6 7 8 9 10 11 12 | 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)'); } } |
Светотени
Наш непритязательный подход обеспечивает красивую визуальную текстуру. Мы сравниваем текущую высоту с высотой следующей точки, чтобы вычислить склон. И рисуем более яркие прямоугольники для более высоких склонов, чтобы заполнить одну сторону светом, а другую — тенью.
1 2 | var b = ~~(slope * 50) + 128; return ['rgba(', b, ',', b, ',', b, ',1)'].join(''); |
Изометрическая проекция
Визуально интереснее перевести наш ландшафт из фазы «square» в фазу «diamond» прежде чем делать его 3D-проекцию. Изометрическая проекция сводит верхний левый и нижний правый углы в центр изображения.
1 2 3 4 5 6 | function iso(x, y) { return { x: 0.5 * (self.size + x - y), y: 0.5 * (x + y) }; } |
Центральная (перспективная) проекция
Мы будем использовать столь же простую 3D-проекцию для конвертации значений x, y и z в плоскую картинку с перспективой на 2D-экране.
Основная идея любой проекции перспективы состоит в том, чтобы разделить горизонтальную и вертикальную позицию на глубину таким образом, чтобы более далекие объекты казались меньше.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | 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. Наконец, переносим ландшафт на сетку.
1 2 3 | var terrain = new Terrain(9); terrain.generate(0.7); terrain.draw(canvasContext, width, height); |
Можно посмотреть результат на сайте автора, а также изучить код на GitHub.
Если вам интересна разработка ландшафтов, советуем почитать наш перевод руководства «Создание ландшафта на Unity за 24 часа».
Перевод статьи «Realistic terrain in 130 lines»