WikiSort.ru - Не сортированное

Алгоритм Diamond-Square — метод генерации карт высот для компьютерной графики.

Идея впервые была введена Фурнье^[en], Фусселем^[en] и Карпентером^[en] на конференции siggraph 1982^[1]. Он был позже проанализирован Гэвином Миллером на конференции siggraph-1986^[2], Миллер описал в алгоритме ряд недостатков, таких как «складки», возникающие на краях карты.

Алгоритм начинает работу с 2D сетки, затем, из четырёх начальных значений, случайным образом генерирует карту высот, упорядоченную в виде сетки из точек так, чтобы вся плоскость была покрыта квадратами.

Алгоритм

Алгоритм diamond-square начинает работу с двумерного массива размера 2ⁿ + 1. В четырёх угловых точках массива устанавливаются начальные значения высот. Шаги diamond и square выполняются поочередно до тех пор, пока все значения массива не будут установлены.

Шаг square (квадрат). Для каждого квадрата в массиве, находится срединная точка, в которую устанавливается среднее значение четырёх угловых точек плюс случайное значение.

Шаг diamond (ромб). Для каждого ромба в массиве, устанавливается срединная точка, которой присваивается среднее арифметическое из четырёх угловых точек плюс случайное значение.

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

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

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

На рисунке ниже показаны шаги, проходимые алгоритмом diamond-square на примере массива 5х5.

Шаг 1. Инициализация угловых точек. Присваивание им значений высот (например, выбором случайных чисел).

Шаг 2. Шаг square. Нахождение срединной точки, присваивание ей значения, на основе среднего от угловых, плюс случайное число.

Шаг 3. Шаг diamond. Нахождение срединных точек для ромбов отмеченных черными точками (на этом шаге, по одной точке каждого ромба выходят за пределы массива)

Шаг 4. square. Для каждого квадрата (на этом шаге их 4), повторяем шаг № 2.

Шаг 5. diamond. Повторяем шаг № 3 для каждого ромба. У ромбов, имеющих точки на краю массива, одна из точек выходит за пределы массива.

Приложения

Этот алгоритм может быть использован для генерации реалистичных ландшафтов. Различные реализации используются в компьютерных графических программах, например terragen.

Примечания

Ссылки

• Простой проект генерации карт высок с открытым кодом (lua), использующий алгоритм diamond-square
• Плазма-фракталы от Патрика Хана
• Метод случайного смещения срединной точки (англ.)
• Алгоритм Diamond-And-Square репозиторий на github (PHP)