Пользователь
0,0
рейтинг
11 января 2011 в 01:22

Разработка → Алгоритм «diamond-square» для построения фрактальных ландшафтов

Карта игры Minecraft, созданная с помощью приложения CartographДумаю, многие знакомы с весьма необычной игрой Minecraft (справа — пример сгенерированной в ней карты), в которой игрок находится на (практически) бесконечной поверхности Земли и может исследовать окружающий мир с минимальными ограничениями.

Как же автору игры, Notch'у, удалось добиться подобного сходства его случайных «миров» с земными просторами? В этом топике я как раз и рассмотрю один из способов построить искусственный ландшафт такого рода (и вскользь упомяну пару других способов), а также расскажу о моем небольшом усовершенствовании этого алгоритма, позволяющем значительно увеличивать размеры ландшафта без заметных потерь в производительности.

Внутри вас ждет несколько схем и красивых картинок, довольно много букв и ссылка на пример реализации алгоритма.


Общий план действий


Что же в целом подразумевается под генерацией ландшафта? Если говорить о создании (почти в реальном времени) уровня для компьютерной игры — такой как, собственно, Minecraft, то этот процесс состоит из следующих пунктов:
  1. Создание карты высот. Изначально у нас есть плоская двумерная сетка и каждой её клетке мы присваиваем некоторую высоту. Каким образом? Об этом и пойдет речь далее. Кстати, сетка не обязательно должна быть прямоугольной — например, здесь описан аналогичный алгоритм для сетки, состоящей из треугольников. Тем не менее, в большинстве случаев удобнее сетка, состоящая из квадратных ячеек-пикселей. Вместе с картой высот задаются и области, покрытые водой — как минимум, моря и океаны (как правило, водой становятся просто те клетки, которые лежат ниже определенного уровня).
  2. Распределение биомов в зависимости от высоты и влажностиРаспределение биомов. Тут понадобятся некоторые знания в географии (впрочем, весь процесс создания ландшафта этого требует). Определить, где должна быть тундра, где пустыня, а где тропический лес — поможет уже созданная карта высот и, например, расстояние от водных пространств или до некоторых предопределенных точек (экватор/полюса). В свою очередь, биомы зададут многие другие параметры — например, травяной покров, количество каменистых участков, растения, количество рек и озер и т.д.
  3. Землю мы создали, океаны и моря тоже, географические зоны распределили. Что забыли? Пустить реки, конечно же! Кроме собственно вод, которые будут течь с гор и спускаться в моря или образовывать озера в ложбинах, следует проэмулировать их воздействие на поверхность земли — образовать русла рек и произвести перенос песка и мягкого грунта по течению с образованием пляжей на берегах озер и других водоемов. К сожалению, этот процесс, называемый водной эрозией, как и другие виды эрозий, я вынужден оставить за рамками данной статьи. Тем не менее, в списке использованной литературы есть пара ссылок на очень хорошие материалы по этой теме.
  4. Дополнительные действия. Фактически, ландшафт уже создан, но есть ещё много вещей, которые можно на нем улучшить — например, в Minecraft пространство под землей сплошь изрыто естественными пещерами, а на поверхности растет множество деревьев. Кроме того, разумеется, в зависимости от биомов можно разнообразить флору и фауну — если ставится целью максимально приблизиться к тому, что происходит в настоящей природе.

Наконец, сгенерированный ландшафт останется только отрисовать. Здесь хочется заметить только одну деталь — в то время как упомянутая выше треугольная сетка оказалась бы кстати при традиционной визуализации трехмерной карты, для квадратных ячеек очень кстати может оказаться использование вокселей. Впрочем, это уже совсем другая история.

Способы построения карты высот


Итак, займемся самым важным этапом построения ландшафта — определением того, на какой высоте находится каждая точка поверхности земли. Самая банальная идея — пробежаться по обоим координатам и сделать map[x][y] = random() — как ни странно, не даст приемлемых результатов, поэтому нужно использовать кое-что похитрее.

Создание холмов «вручную»


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

Ландшафт на базе диаграммы Вороного


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

Диаграмма ВороногоНачинается всё со случайного бросания точек на карту. Затем по этим точкам строится диаграмма Вороного (и, соответственно, триангуляция Делоне), а на ней выполняется несколько итераций релаксации Ллойда, чтобы избавиться от слишком мелких полигонов.

Если вам оказался непонятен предыдущий абзац — не страшно, его суть сводится к созданию примерно такой сетки, как на рисунке справа. Главное её свойство — это её нерегулярность. Это позволяет построенному на её основе ландшафту не выглядеть слишком «квадратным».

Полученный ландшафтДальнейшие действия тривиальны — мы случайным образом выбираем полигоны, подлежащие заполнению водой, а высоту точек, принадлежащих остальным полигонам, делаем равной кратчайшему расстоянию до моря-окияна. Осталось добавить всё тот же шум (причем как к собственно высоте, так и к границам полигонов) — и мы получим весьма симпатичный остров (или материк, в зависимости от масштабов).

Реализацией данного алгоритма я не занимался и для упрощения статьи опустил несколько деталей и промежуточных. С подробной статьей (из которой были позаимствованы картинки и большая часть информации), можно ознакомиться по ссылке (на английском), там же есть замечательное swf-демо, крайне наглядно иллюстрирующее все этапы процесса.

Алгоритм diamond-square


Самым же распространенным и дающим одни из самых реалистичных результатов является алгоритм diamond-square (или square-diamond), расширение одномерного алгоритма midpoint displacement на двумерную плоскость. Ландшафты, получающиеся с его помощью, как правило, называют фрактальными, хотя, следует признать, на самом деле они не так уж самоподобными — напротив, как мы увидим ниже, их не очень приятным свойством является то, что в крупном масштабе они становятся относительно гладкими, а в мелком превращаются в подобие наждачной бумаги.

Ночной горизонт, полученный с помощью алгоритма midpoint displacementРабота алгоритма midpoint displacementНачнем с более простого алгоритма midpoint displacement. Как уже сказано, он работает не на двумерной плоскости, а на одномерном отрезке (поэтому с его помощью можно, например, создать линию горизонта).

То, что роднит этот алгоритм с фракталами — это его рекурсивное поведение. Изначально мы любым образом задаем высоту на концах отрезка и разбиваем его точкой посередине на два под-отрезка. Эту точку мы смещаем на случайную величину и повторяем разбиение и смещение для каждого из полученных под-отрезков. И так далее — пока отрезки не станут длиной в один пиксель. Вот и весь алгоритм (см. рисунок справа). Ах, да — важное замечание: случайные смещения должны быть пропорциональны длинам отрезков, на которых произведятся разбиения. Например, мы разбиваем отрезок длиной l — тогда точка посередине него должна иметь высоту
h = (hL + hR) / 2 + random(- R * l, R * l)
(hL и hR — высоты на левом и правом конце отрезка, а константа R определяет «шероховатость» (roughness) получающейся ломаной и является главным параметром в данном алгоритме).

Midpoint displacement в двух измеренияхПопробуем обобщить этот алгоритм для двумерной карты высот. Начнем с присвоения случайных высот четырем углам всей карты целиком и разобъем её (для удобства я предполагаю, что мы работаем с квадратной картой, причем её сторона является степенью двойки) на четыре равных квадрата. В каждом из них известно значение в одном из углов. Где взять остальные?Результат работы двумерного midpoint displacement
Всё той же интерполяцией, как и в одномерном midpoint displacement — точка в центре получается усреднением высот всех 4 угловых точек, а каждая серединная точка на стороне большого квадрата — усреднением пары точек, лежащих на концах соответствующей стороны. Осталось привнести немного шума — сдвинуть случайным образом центральную точку вверх или вниз (в пределах, пропорциональных стороне квадрата) — и можно повторять рекурсивно наши действия для полученных под-квадратиков. Всё? Всё, да не всё.

Это ещё не diamond-square — данный алгоритм, как правило, тоже называют алгоритмом midpoint displacement и несмотря на то, что он дает уже относительно приемлимые результаты, в получившейся картинке без особого труда можно заметить её «прямолинейную» натуру.

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

Объяснения, думаю, могут показаться запутанными, поэтому советую внимательно изучить приложенные схемы — по ним должно стать яснее, высоты каких точек вычисляются на каждом этапе.

Кроме необходимости использовать, скажем так, обход в ширину вместо обхода в глубину, есть ещё одна тонкость — ситуация на краях ландшафта. Дело в том, что на этапе «diamond» алгоритм использует высоту точек, которых находятся за пределами текущего квадрата и, возможно, всей карты. Как быть? Варианта два (хотя вы можете придумать и свой собственный, конечно): либо считать эти высоты равными 0 (или 1, или любой другой константе; это, кстати, удобно для погружения краев нашего ландшафта под воду), либо представить что наша плоскость свернута в тор (тороидальная планета, хм...) и пытаясь узнать высоту точки, лежащей на 64 пикселя левее левой границы карты, мы узнаем высоту точки, отстоящей на 64 точки от правой границы. Реализуется очень просто (как, впрочем, и первый вариант) — нам поможет взятие координат по модулю, равному размеру карты.

Результат работы алгоритма diamond-squareИтак, таковы основные алгоритмы построения карт высот для искусственно генерируемых ландшафтов. На мой взгляд, наиболее реалистичные результат дает последний из них, diamond-square — хотя и он не лишен некоторых недостатков. Например, создав карту, которая хорошая выглядит при сильном приближении — при просмотре целиком вы увидите множество мелких островков (а то и вовсе сплошной шум, с которого мы начинали) вместо нескольких больших материков и океанов. Самоподобия не выходит. Исправить это можно различным комбинированием фрактальных ландшафтов разного масштаба. Их значения можно перемножать, складывать, использовать различные коэффициенты или, например, привнести данные, полученные с помощью диаграммы Вороного — в общем, простор для экспериментов достаточно велик. Кстати, даже используя только один diamond-square, полученные значения (предварительно нормализованные, то есть в диапазоне от 0.0 до 1.0) полезно возвести в квадрат — это сделает равнины более пологими, а склоны гор более крутыми (помните про эрозию?).

Модификация алгоритма diamond-square для больших карт


Ну и напоследок — несколько слов о моей реализации алгоритма diamond-square. Главный вопрос, которым задаешься при генерации ландшафта — как сделать так, чтобы можно было значительно увеличить его размеры? Стандартная реализация обсуждаемого алгоритма позволяет легко увеличивать детализацию (двигаться «вглубь»), но не размеры («вширь»).

Данная проблема была решена мною следующим образом. Не знаю — возможно, это решение окажется общеизвестным или вполне очевидным для кого-то — но до этого я с ним не сталкивался и придумать его получилось не сразу (более того — «на пустом месте» возникла одна неожиданная заминка, которую разрешить «правильно» так и не удалось — об этом ниже).

Итак, подход таков: пусть наш ландшафт изначально задуман гигантских размеров (например, 16777216x16777216 пикселей, хотя это далеко не предел). Важно то, что мы не собираемся узнавать высоту в каждой точке, а вместо этого у нас будет некое значительно меньшее «окно» (например, 128x128 пикселей), которое мы будем по необходимости перемещать над нашей картой высот. Оказывается, исходный алгоритм легко модифицируется так, что нам будет требоваться на просчет «окна» число операций, пропорциональное размеру окна, но мало зависящее от размера ландшафта. Именно поэтому мы можем изначально задать ландшафт почти сколь угодно большим.

Моя реализация алгоритма diamond-square


На помощь нам придет методика под названием ленивая динамика. Тем, кто знает, о чем речь, думаю, уже стало всё понятно, для несведущих в вопросе поясню. Мы «выворачиваем» весь процесс наизнанку — вместо того, чтобы начинать с больших квадратов и спускаться вниз к каждому пикселю, мы принимаем запрос вида «узнать высоту в точке (x, y)» и дальше поднимаемся вверх: наша точка, как мы знаем, была получена усреднением четырех других точек и случайным сдвигом. Самое сложное — понять, какими были эти 4 точки. После того, как мы это поймем, нам будет достаточно повторить запрос «узнать высоту», но уже для каждой из этих точек. Эти запросы, в свою очередь, поднимутся еще на уровень выше — и так далее, пока не дойдут до самого верха, до угловых точек карты (у меня они, как и точки за пределами карты, равны 0.0). В исходнике всё это выглядит примерно так:

function val(x, y, v) {
	if (typeof(v) != 'undefined')
		data[x + '_' + y] = Math.max(0.0, Math.min(1.0, v));
	else {
		if (x <= 0 || x >= size || y <= 0 || y >= size) return 0.0;
		if (data[x + '_' + y] == null) {
			// К этому блоку мы ещё вернемся ниже.
			base = 1;
			while (((x & base) == 0) && ((y & base) == 0))
				base <<= 1;
			if (((x & base) != 0) && ((y & base) != 0))
				squareStep(x, y, base);
			else
				diamondStep(x, y, base);
		}
		return data[x + '_' + y];
	}
}
function displace(v, blockSize, x, y) {
	return (v + (randFromPair(x, y, seed) - 0.5) * blockSize * 2 / size * roughness);
}
function squareStep(x, y, blockSize) {
	if (data[x + '_' + y] == null) {
		val(x, y,
			displace((val(x - blockSize, y - blockSize) +
				  val(x + blockSize, y - blockSize) +
				  val(x - blockSize, y + blockSize) +
				  val(x + blockSize, y + blockSize)) / 4, blockSize, x, y));
	}
}
function diamondStep(x, y, blockSize) {
	if (data[x + '_' + y] == null) {
		val(x, y,
			displace((val(x - blockSize, y) +
				  val(x + blockSize, y) +
				  val(x, y - blockSize) +
				  val(x, y + blockSize)) / 4, blockSize, x, y));
	}
}


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

Как уже было сказано, в алгоритме есть несколько магических строк — вот они:
base = 1;
while (((x & base) == 0) && ((y & base) == 0))
	base <<= 1;

if (((x & base) != 0) && ((y & base) != 0))
	squareStep(x, y, base);
else
	diamondStep(x, y, base);

Здесь определяется, является ли текущая точка центром квадрата или ромба и каков размер этой фигуры. Если честно — данный код был написан просто по наитию, его точное математическое обоснование я дать не могу. Мы просто находим наименее значащий бит, который отличен от нуля хотя бы у одной из координат — он и будет искомым размером. А чтобы определить, была ли фигура квадратом — проверяем, что у обоих координат был выставлен этот бит. Обе координаты здесь нуль-индексированные.

И, наконец, неожиданный подводный камень: генератор псевдослучайных чисел. В моем коде к нему предъявлялись необычные требования: для каждой точки (x, y) всегда хочется получать одно и то же случайное число, и делать это быстро. Многие языки программирования в генераторе случайных чисел имеют возможность указать т.н. «зерно» (seed), от которого будет зависеть вся следующая последовательность генерируемых чисел (в JavaScript этого нет, но для него есть реализация распространенного вихря Мерсенна). Проблема в том, что последовательность нас не устраивает — при сдвиге окна (и очистке кэша) мы подойдем к одной точке совсем с другой стороны и случайный сдвиг станет иным. Мы же хотим статичный ландшафт, при каких бы условиях мы его ни рассматривали. Попытка инициализировать вихрь Мерсенна каждый раз «зерном», зависящим от обоих координат, провалилась: его инициализация длится слишком долго.

После некоторых размышлений я пришел к выводу, что быстрого способа преобразовать две координаты в число, которое было бы мало скоррелировано с ними, в принципе невозможно. В итоге я остановился на такой функции, которая дает приемлимые результаты из-за многократного взятия чисел по простым модулям:
function randFromPair(x, y) {
	for (var i = 0; i < 80; i++) {
		var xm7 = x % 7;
		var xm13 = x % 13;
		var xm1301081 = x % 1301081;
		var ym8461 = y % 8461;
		var ym105467 = y % 105467;
		var ym105943 = y % 105943;
		y = x + seed;
		x += (xm7 + xm13 + xm1301081 + ym8461 + ym105467 + ym105943);
	}
	return (xm7 + xm13 + xm1301081 + ym8461 + ym105467 + ym105943) / 1520972.0;
}

Кроме того, в эту функцию удалось без труда привнести «глобальное зерно», определяющее весь ландшафт целиком, а из-за взятия остатков её возращаемые значения оказались достаточно равномерно распределены по диапазону [0, 1). Впрочем, я уверен, что можно придумать более быстрое элегантное решение — можете считать это «домашним заданием» в данной статье :)

Как уже все, наверное, догадались, реализацию я написал на JavaScript, что позволяет одинаково легко поэкспериментировать как со значениями, так и с исходным кодом. Собственно страница доступна по адресу http://denull.ru/terrain.htm, а весь код расположился в файле http://denull.ru/terrain.js. Для просмотра потребуется браузер, поддерживающий html5 (скажу честно — тестировал только в Google Chrome), поскольку отрисовка идет в canvas (и, надо заметить, на собственно отрисовку тоже тратится некоторое время).

Материалы по теме


  • Realtime Procedural Terrain Generation (PDF, 1,52 Мб). Очень подробный и интересный материал по созданию ландшафтов — как с помощью диаграммы Вороного, так и алгоритмом diamond-square, с описанием способов эрозии и множеством иллюстраций и формул.
  • Polygonal Map Generation, замечательная статья о построении ландшафта на основе диаграммы Вороного. Хорошо проиллюстрировано, имеется демонстрационный swf-файлик, множество ссылок на другие материалы.
  • Fast Hydraulic Erosion Simulation and Visualization on GPU. Статья про оптимизацию симуляции водной эрозии, в наличии не только PDF и изображения, но и несколько видеороликов, помогающих понять, о чем речь. Безотносительно идеи оптимизировать процесс, переложив нагрузку на GPU, — в документе достаточно информации об механизмах эрозии.
  • Несколько коротких статей о фрактальных алгоритмах: Generating Random Fractal Terrain, Fractal landscape, Fractal Terrains, Diamond-square algorithm.
Денис Ольшин @deNULL
карма
118,0
рейтинг 0,0
Пользователь
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (54)

  • +3
    извините, я читаю это в 5 утра, и, возможно, напишу чушь, но правильно ли я понял, что мы можем нагенерить небольшой кусок ландшафта, и затем, по мере необходимости, динамически достраивать его при сдвигании окна? тогда, это ведь шикарно, мы можем заселить юзеров на карту и позволить им исследовать огромный мир, динамически создаваемый находу, пока у нас хватает памяти.
    • +3
      Собственно — Minecraft именно это и предлагает… Огромный мир, который генерируется по ходу движения игроков…
      Только там ещё и нагружено пещерами разнообразными…
      • 0
        думаю, девелоперам мморпг стоит уже присмотреться к этому подходу, понятно, что генерить квесты и ключевых мобов таким методом как-то странно, но можно сделать те же самые пещеры под землей со всякими вкусностями или еще что-то
        • +4
          Нечто подобное, насколько знаю, применялось в серии TES. В TES3:Morrowind многочисленные дома и подземелья были сгенерированы автоматически.
          И далеко не всем это пришлось по вкусу. Почему? Да потому что игрок рубится с монстрами, зачищает немаленькое подземелье, а что в конце? Сундук с зельями. На пятом подземелье становится откровенно скучно. Игрокам нужна награда. Слишком частые и весомые награды могут сделать дальнейшую игру слишком легкой.

          Критика была учтена и в следующей части серии автоматически генерировались только леса и прочие мелкие детали ландшафта. Впрочем, это тоже не всем понравилось и возник замечательный проект Unique Landscapes, который заменяет скучный однообразные ландшафты, сделанные генератором на созданные вручную и добавляет всяческие водопады, пустыни, особенные леса.

          Так что автогенерация есть, но пока что она далека от совершенства. И чтобы довести ее до этого самого совершенства нужен титанический труд разработчиков.
          PS. Карта в приведенных выше играх была сгенерирована еще на этапе разработки, а не во время начала новой игры. Просто привел пример того, что большие пространства, сделанные генераторами, это здорово, но этого явно недостаточно.
          • +3
            Не путайте Morrowind и Daggerfall, пожалуйста. В моровинде как раз все локации были зашиты в ресурсы, а местами даже сделаны вручную.
            • +2
              Тьфу, не дочитал. В общем, в Daggerfall генерилка работала по новой каждый раз, что вносило в игру «разнообразие».
          • +3
            Игр с генерируемыми подземельями довольно много — с ходу могу вспомнить «Сферу», Диабло и ещё два десятка с псевдографикой…

            Собственно ситуация "… а в конце — сундук с зельями" — недоработка разработчиков: как минимум в результате должен быть достаточно ценный предмет, на ценность которого влияют параметры «Размеры подземелья», «Число и уровень мобов» и т.п.
            Т.е. — если весь дандж «три поворота и один тупик», а монстров в охране — маленькая мышка — награда тоже не велика, но для нуба, на которого рассчитан квест — вполне существенна.
            А если группа игроков с трудом прорывается сквозь крутых боссов и кучу монстров — то и награда будет вполне приличная для их уровня. Но с другой стороны — спустя несколько уровней они смогут зачистить тот-же уровень и в одиночку, но и награда им уже не будет казаться такой «вкусной».
          • 0
            Первая (да и вторая) Диабла тоже генерировала свои подземелья случайным образом. Пусть не идеально, но все же со случайными подземельями игра вышла интересней, чем со статикой. Так что критиковать стоит не столько концепцию случайно генерированных карт сколько конкретную реализацию алгоритма в морровинде, ПМСМ.
          • 0
            Это действительно вопрос, понравится пользователям автогенерация ландшафта или нет.
            М какой она должна, быть чтобы игрокам понравилось и было интересно?
      • 0
        В Celestia такую штуку надо встроить, чтобы планеты более реальными казались.
    • +3
      Совершенно верно.

      У меня была идея реализовать клон Minecraft, но я решил, что не осилю, и ограничился этим топиком :)
  • 0
    Молодца! Хорошая подборка!
  • +6
    Это великолепно, мои геймдевовские корешки шевелятся и лезут на поверхность :)
  • +3
    Браво. Отличная статья, спасибо, прочитал без отрыва.
    Редко сейчас встретишь в «Алгоритмах» настолько качественный материал.
  • 0
    Фракталы отлично справляются подобными задачами, особенно хорошо тем, что можно спокойно масштабировать, так же очень не плохо и различные другие объекты генерируются, будь то растительность, камни и т.д. Взять к примеру стариннейшую игру Elite, весь мир описан 6ю байтами, изменив которые в исполняемом файле получали совершенно иной мир. А статья хороша.
  • 0
    хм, а генетический алгоритм сюда можно применить? делать много раз heights[i][j] += random(), где random() возвращает какую-нибудь маленькую величину (как положительную, так и отрицательную)
    • 0
      генетические алгоритмы используются для поиска экстремума функции, зачем вам здесь искать экстремум о_О
      • 0
        только ли для экстремумов? хотя здесь мне видится экстремум (локальный) — пик горы или впадина в океане
  • +1
    Спасибо за отличную статью?

    Итак, подход таков: пусть наш ландшафт изначально задуман гигантских размеров (например, 16777216x16777216 пикселей, хотя это далеко не предел).

    Почему бы не отказаться от размера и прегенерации карты? Давайте генерировать только то, что нам нужно. Берем тайл, небольшого размера, скажем, в два раза больший, чем (дальность зрения игрок*2). Если игрок видит на 16 клеток, то пусть это будет 16*2*2 = 64 пикселя, генерируем блок 64*64 и ставим пользователя в середину. Когда пользователь подойдёт к краю — догенерируем следующий блок на базе предыдущего. К примеру, на картинке ниже у нового блока есть три точки, случайно выбираем четвертую и погнали простым алгоритмом.
    • +2
      простите, не тот знак. правильно так:
      Спасибо за отличную статью!!!
    • +1
      Дело в том, что у нас получится тогда не часть цельного ландшафта, а новый маленький подландшафтик (к тому же при его создании нам понядобятся высоты в еще не построенных блоках ниже и правее нового — и откуда их брать, не совсем ясно).
      • 0
        почему бы не сгенерить (только) ключевые точки при прегенерации, а потом догенерировать детали?
        • 0
          А что такое «ключевые точки»? Там каждая вторая точка будет получаться «ключевой», от неё будут другие точки зависеть.
          • 0
            каждая 64-ая точка, например?
            • 0
              Да в общем-то ничего не мешает как угодно поступать — хоть всю карту прегенерировать, хоть каждую N-ую точку, хоть вообще ничего.

              Просто следует понимать, что имея, например, точки (64, 64), (127, 64), (64, 127) и (127, 127) — корректно заполнить только по ним все внутренние точки в квадрате (64, 64) — (127, 127) не выйдет: на этапах «diamond» нам часто будут нужны точки «снаружи», из соседних квадратов.
              • 0
                а можно как-то так? то есть генерить клетки+ дополнительные данные. просто время генерации карты сейчас не очень радует. плюс делается дофига ненужной работы. плюс карта ограниченная.
                • 0
                  Мне кажется, вы не до конца разобрались в том приеме, который я предложил.

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

                  А что до времени отрисовки — я думаю, здесь меня подвел попиксельный доступ к canvas. Если не выводить значение каждой точки на экран, будет гораздо быстрее.
                  • 0
                    возможно, не до конца. надо будет написать реализацию вручную, тогда осилю.)
      • НЛО прилетело и опубликовало эту надпись здесь
        • 0
          а представьте, если бы огромная карта генерировалась заранее. включил, ушёл на полчаса.
          сейчас, при относительно небольшом размере в 2к*2к у меня фокс висит, а что если необходим размер больше?
          • НЛО прилетело и опубликовало эту надпись здесь
            • 0
              Не, майнкрафт я еще не купил, а говорю про то, что автор описал в топике =) Меня интересует способ ускорить это.
              • НЛО прилетело и опубликовало эту надпись здесь
                • НЛО прилетело и опубликовало эту надпись здесь
          • 0
            Ну, в статье я как раз и описываю подход, в котором нет надобности генерировать сразу всю карту.

            Высота в каждой точке может определяться в любой момент, и даже в худшем случае число операций, которые на это уйдут, будет порядка двоичного логарифма от размера карты.
          • +1
            dwarf fortress :3
    • 0
      У него общий случай. Нотч тоже, хоть и уверяет, что карта бесконечная, на практике называет цифру, на которой она кончается таки. ;)
      В Майнкрафте приняты блоки-«чанки» размером 16 на 16 на 128, при этом видимость — этак на 64 клетки, примерно…
  • +2
    Спасибо, очень интересная и качественная статья.
    Скажите, а не пробовали ли, хотя бы грубо, моделировать взаимодействие тектонических плит с последующей эрозией и почвообразованием, чтобы получать ландшафт? Ведь, все-таки представленные методы генерирования являются чисто математическими, без учета реального строения, то есть попыткой подобрать математическую модель, визуально похожую на то, что мы можем наблюдать.
    • +1
      Нет, я, в общем-то, даже эрозию толком не изучал.

      А такую вещь, как взаимодействие тектонических плит, думается, будет весьма проблематично промоделировать — этому, по крайней мере, нужно посвящать целое отдельное исследование. В любом случае понадобятся серьезные упрощения модели (мы же не станем рассматривать взаимодействие каждой пары песчинок), и они вполне могут отдалить результат от реальности значительно более, чем то, что получается искусственным фрактальным путем.
      • 0
        Нет, я не спорю, имелось ввиду грубое упрощение. Просто это может помочь избежать повторяемости ландшафта. Впрочем поскольку сам не делал, утверждать естественно не берусь, но эксперимент был бы занятный.
  • 0
    Любому из этих способов генерации нехватает водной эрозии чтобы выглядеть правдоподобно. Горы без ущелий в реальном мире никогда не встречаются.
    • +1
      Разумеется.

      В разделе «Общий план действий» я упомянул о том, какие действия стоит проделать дополнительно после начальной генерации карты высот. Собственно моделирование эрозии я здесь не рассматривал, но в паре статей, ссылки на которые находятся в конце топика, есть информация и об этом.
  • +3
    Превосходный материал, огромное спасибо!

    Давно слежу за ходом разработки игры от ребят, которые выкатили Дарвинию и Дефкон ( www.introversion.co.uk/blog/archive.php, советую начинать с архива блога ), там исходная идея была в генерации огромного города, видео-материалы впечатляли даже пару лет назад. Правда за время разработки идея менялась, ну не суть важно :)

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

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

    Кто-нибудь сталкивался с чем-то подобным?
  • 0
    Функция randFromPair(x, y) — очень заинтересовала.

    Да, идёт генерация псевдослучайного числа на основе «состояния» {x,y}. Всё в лучших добрых традициях ГПСЧ — простые числа, остатки от деления и последующие математические операции.

    Но позвольте спросить, — откуда взяты именно такие простые числа?
    А именно, 7; 13; 1301081 для X, и 8461; 105467; 105943 для Y?
    Чем обусловлен выбор именно этих чисел и именно по три штуки?

    Вопрос про 80-1 проездов напильником по результату также остаётся открытым.
    • 0
      Честно говоря, все бралось практически с потолка в попытках избежать видимых глазу закономерностей в генерируемых ландшафтах. Как оказалось, при небольшом числе итераций в данной функции, практически всегда оказывается заметна зависимость от входных координат. Подобное «перемешивание» остатков дало наиболее приемлемый результат.

      К сожалению, не удалось нигде найти способов решения задачи быстрого получения достаточно «хорошего» псевдослучайного числа на основе заданного зерна. Все известные мне алгоритмы предполагают задание зерна единожды чтобы получить быстро генерируемую последовательность ПСЧ. Их время задержки перед выдачей первого элемента последовательности оказалось слишком большим для моих нужд, пришлось выкручиваться.

      Буду очень рад, если укажете на более эффективный подход к этой задаче.
      • 0
        Поэкспериментировал, и предлагаю такой вариант функции:

        function randFromPair(x, y) {
        var s = seed * 1972854929;
        s ^= (x * 2971902361) ^ (y * 3572953751);
        s = 0x6C078965 * s;// & 0xFFFFFFFF;
        /*
        s ^= s >> 11;
        s ^= (s << 7) & 0x9D2C5680;
        s ^= (s << 15) & 0xEFC60000;
        s ^= s >> 18;
        */
        return (s & 0x7FFFFFFF) * 4.656612875245796924105750827168e-10; //(1./2147483647.);;
        }


        Скорость работы (в моём хроме) поднялась почти в два раза.
        Каких-либо артефактов или закономерностей я не заметил, результат выглядит столь же неплохо.

        К сожалению, метод такой же — простые числа 1972854929, 2971902361, 3572953751 взяты "с потолка", математическое доказательство или исследование «подходящести» данного способа генерации ПСЧ на основе зерна {x,y,seed} — также открытая задача.
        Возможно другие простые числа могут вести себя лучше.

        s = 0x6C078965 * s;// & 0xFFFFFFFF; и далее
        — взято из всеми любимого Вихря Мерсенна.
        Закомментированный блок битового перемешивания — отключен поскольку он не производил видимых улучшений результирующей картины. (так и незачем его считать, для наших целей)
        Сама строка «s = 0x6C...» оставлена по той же причине — без неё не происходит минимально необходимого перемешивания данных исходной тройки {x,y,seed}

        Попробовать сейчас твой фрактальный ландшафт с моим вариантом функции можно здесь.

        Я тоже буду рад помощи в доведении данного вопроса {x1,x2,...,xn} => PRN до итогового результата.
        Причём даже больший интерес представляет расширенная задача, где исходные данные x1,...,xn — вещественные числа, и накладывается требование непрерывности построенного по ним поля PRN.
        • 0
          В результате более охватывающего тестирования к сожалению было выявлено, что предложенный мной способ вычисления PRN(x1,...,xn) для существенно больших размеров карты ведёт себя неприемлимо — начинают проявляться артефакты: диагональная симметрия и периодичность «островков» карты.

          Это происходит при ширине квадрата карты примерно от 128М и более (смотрел до 4Г, т.е. до карт шириной и высотой по 4*1024^3 клеток).

          Между тем, deNull, твой метод выдаёт результат ничем не хуже, чем для карт малых размеров.

          В результате приходится продолжить поиск более совершенного алгоритма, который с одной стороны работал бы быстро и выглядел красиво (что характерно для элегантных и эффективных решений), и с другой не давал бы никаких заметных артефактов вплоть до размеров используемой при вычислениях разрядности (в нашем случае 2^32).

          Пока что экспериментирование с различными операциями и вариациями на тему дополнительных перемешиваний почти не принесло видимых результатов.

          Что же касается предложенного выше алгоритма randFromPair — его вполне успешно можно использовать для не очень больших карт (до 100млн х 100млн), получая при этом заметный выигрыш производительности. Для экстремально больших карт же пока остаётся актуальным только метод автора статьи.

          / Большой респект за хорошую статью! /

          Продолжаю поиски грааля.
          • 0
            Реализовал оба варианта на С++, поэкспериментировал.

            На мой взгляд, 80 прогонов у тебя избыточны, хватает 32 раз. Соответственно время генерации существенно уменьшается. (грубо говоря в 2 раза)

            Также примечательное свойство данного генератора ландшафтов (в целом генератора) — отображаемая карта (512х512) просчитывается практически за константное время, вне зависимости от размеров «полной карты». *
            При размерах от 512 и до 1.073.741.824 время генерации отстаётся неизменным в пределах погрешностей.

            Имеется ввиду как раз первичный просчёт, когда в «кэше» нет ни одного элемента и необходимо считать все.

            _____________
            * Данное поведение проявилось в реализации на С++, с использованием stl::map, в качестве ключа взята структура {dword x; dword y;}, вместо предлагаемого в оригинале строкового ключа «x+'_'+y». Однако же в браузерном исполнении JS-варианта прослеживается заметное увеличение времени генерации при росте «размера карты».
  • 0
    Взял нормальное распределение гаусса функцию вместо randFromPair, сигмачку и мю поднастроил. Ускорил алгоритм на порядки. Правда написал на питоне. Но я думаю можно и ручками функцию запрогать.
  • 0
    А не подскажете, как это можно адаптировать под сферические поверхности?
  • 0
    У вас получаются очень хорошие материки. А вот у меня почему-то выходят сплошные архипелаги:

    (черная самая глубокая точка, красная самая высокая)

    В чем моя ошибка?
    Вот код:

    QImage MainWindow::diamondSquare(int _width, int _height)
    {
        width = _width;
        height = _height;
    
        QImage stage(width, height, QImage::Format_ARGB32);;
    
        int featuresize = 16;
    
        values = new double[width * height];
    
        for( int y = 0; y < height; y += featuresize)
            for (int x = 0; x < width; x += featuresize)
            {
                setSample(x, y, frand());
            }
    
        int samplesize = featuresize;
    
        double scale = 1.0;
    
        while (samplesize > 1)
        {
    
            DiamondSquare(samplesize, scale);
    
            samplesize /= 2;
            scale /= 2.0;
        }
    
        double smpl;
        int red, green, blue;
    
        for( int y = 0; y < height; y ++)
            for (int x = 0; x < width; x ++)
            {
                smpl = sample(x, y);
    
                if(smpl <= 0)
                {
                    smpl += 1;
                    blue = (int)255*smpl;
                    if(blue > 255) blue = 255;
                    if(blue < 0) blue = 0;
    
                    stage.setPixel(x, y, QColor(0, 0, blue).rgb());
                }
                else
                {
                    red = (int)255*smpl;
                    if(red > 255) red = 255;
                    if(red < 0) red = 0;
                    green = (int)255*(1 - smpl);
                    if(green > 255) green = 255;
                    if(green < 0) green = 0;
    
                    stage.setPixel(x, y, QColor(red, green, 0).rgb());
                }
            }
    
        delete[] values;
    
        return stage;
    }
    
    double MainWindow::sample(int x, int y)
    {
        return values[(x & (width - 1)) + (y & (height - 1)) * width];
    }
    
    void MainWindow::setSample(int x, int y, double value)
    {
        values[(x & (width - 1)) + (y & (height - 1)) * width] = value;
    }
    
    void MainWindow::sampleSquare(int x, int y, int size, double value)
    {
        int hs = size / 2;
    
        double a = sample(x - hs, y - hs);
        double b = sample(x + hs, y - hs);
        double c = sample(x - hs, y + hs);
        double d = sample(x + hs, y + hs);
    
        setSample(x, y, ((a + b + c + d) / 4.0) + value);
    }
    
    void MainWindow::sampleDiamond(int x, int y, int size, double value)
    {
        int hs = size / 2;
        double a = sample(x - hs, y);
        double b = sample(x + hs, y);
        double c = sample(x, y - hs);
        double d = sample(x, y + hs);
    
        setSample(x, y, ((a + b + c + d) / 4.0) + value);
    }
    
    void MainWindow::DiamondSquare(int stepsize, double scale)
    {
        int halfstep = stepsize / 2;
    
        for (int y = halfstep; y < height + halfstep; y += stepsize)
        {
            for (int x = halfstep; x < width + halfstep; x += stepsize)
            {
                sampleSquare(x, y, stepsize, frand() * scale);
            }
        }
    
        for (int y = 0; y < height; y += stepsize)
        {
            for (int x = 0; x < width; x += stepsize)
            {
                sampleDiamond(x + halfstep, y, stepsize, frand() * scale);
                sampleDiamond(x, y + halfstep, stepsize, frand() * scale);
            }
        }
    }
    


    frand() возвращает случайное число от -1 до 1
  • 0
    О спасибо, а то я от лени просто рандомом высоту наращивал — не просто каждой точке, а какой-то случайной точке на карте с указанным разбросом по X и Y, и таких точек 50 штук на карте. Каждый раз когда на точку выпадает кон — её высота увеличивается на 5, начальная высота -100. Рандом не простой а Гауссовый из библиотеки d3js — он больше ближе к середине выдаёт (с простым квадраты получались). Чёрные — это гоные пики типа. Примерно так выходило (10 сек для карты 150х150, AthX2 1.9G, Linux, Chrome).
    image
  • 0
    Большое спасибо за статью, очень помогла!

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.